严蔚敏数据结构题集(c语言版)史上最全答案（一题可有多解）.docx

《严蔚敏数据结构题集(c语言版)史上最全答案（一题可有多解）.docx》由会员分享，可在线阅读，更多相关《严蔚敏数据结构题集(c语言版)史上最全答案（一题可有多解）.docx（198页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章绪论1.1解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为个整体进行考虑和处理。数据对象是性质相同的数据元素的集合,是数据的个子集。数据结构是相互之间存在种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指个数学模型以及定义在该模型上的组操作。是对一般数据类型的扩展。1. 2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解:抽象数据类型包含一般数据类型的概念，但含义比一般数

2、据类型更广、更抽象。一般数据类型由具体语言系 统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包 括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义 到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现，这样抽象层次更高,更能为其他用户提供 良好的使用接口。1.3 解:(dT)(d4)1. 4 解：ADT Complex 数据对象：D=r,i|r,i为实数数据关系：R=基本操作：InitRationalNumber(&R, s, m)操作结果：构造一个有理数R,其分子和分母分别为

3、s和mDestroyRationalNumber(&R)操作结果:销毁有理数RGet (R, k, &e)操作结果：用e返回有理数R的第k元的值Put (&R, k, e)操作结果:改变有理数R的第k元的值为eIsAscending(R)操作结果:若有理数R的两个元素按升序排列，则返回1,否则返回 IsDescending(R)操作结果:若有理数R的两个元素按降序排列,则返回1,否则返回 Max (R, &e)操作结果:用e返回有理数R的两个元素中值较大的个Min(R, &e)操作结果:用e返回有理数R的两个元素中值较小的一个ADT RationalNumber1.5 试画出与下列程序段等价的

4、框图。(1) product=l; i=l;while(i=n)product *= i;i+；)(2) i=0;do i+； while(i!=n) & (ai!=x);(3) switch case x438 时，n 50/7 log2 n1.14 解:(l)g(n)快(2)g(n)快(3)f(n)快(4) f(n)快1.1 15试用数学归纳法证明：(1) /2 = .( + *2 +1)/6 n 0) z=i(2) = (xrt+, -l)/(x-l) (x l,n 0)i=0(3)右2=2-1(/71)1=1(4)豆-1) = 2(nl)1.16 试写算法,自大至小依次输出顺序读入的三

5、个整数X, 丫和Z的值 解:int max3(int x, int y,int z)if(xy)if(xz) return x;else return z;elseif(yz) return y;else return z;解2：void print_descending(int x,int y,int z)按从大到小顺序输出三个数scanf(H%d,%d,%dn,&x,&y,&z);if(xy) xy; 0为表示交换的双目运算符,以下同if(yz) yz;if(xvy) xv-y; 冒泡排序printf(M%d %d %dM,x,y,z);/print_descending解3:(上机已实现

6、)要求实现下列函数:void Descend(int &x, int &y, int &z);/按从大到小顺序返回x, y和z的值/void Descend(int &x, int &y, int &z)/按从大到小顺序返回x, y和z的值/(int temp;if(xy)temp=x;x=y;y=temp;if (y=temp) y=temp; elsey=x;x=temp;1.17 解:k0为阶数,n为数列的第n项 int Fibonacci(int k, int n)(if(kl) exit(OVERFLOW);int *p, x;p=new intk+1;if(!p) exit(OVE

7、RFLOW);int i, j;for(i=0;ik+1;i+) if(ik-l) pi=0;else pi=l;for(i=k+l;in+l;i+) x二p;for(j=0;jk;j+) pj=pj+l;pk=2*pk-l-x; return pk;解2：Status fib(int k,int m,int &f)求k阶斐波那契序列的第m项的值f int tempd;if(k2llm0) return ERROR;if(mk-l) f=0;else if (m=k-1) f=l;else(for(i=0;i=k-2;i+) tempi=0;tempk-l=l;初始化for(i=k;i=m;i

8、+)/求Hl序列第k至第m个元素的值(sum=0;for(j=i-k;ji;j+) sum+=tempj;tempi=sum;)f=tempm;)return OK;/fib分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m9).如果采用递归编程(大多数人都会首先想到递归方 法),则时间复杂度将高达O(kAm).解3:(上机已实现)要求实现下列函数:Status Fibonacci(int k, int m, int &f);/如果能求得k阶斐波那契序列的第m项的值f(则返回0K； */否则(比如,参数k和m不合理)返回ERROR*/Status Fibonacci(int k,

9、int m, int &f) /求k阶斐波那契序列的第m项的值f */(int temp200, i, j, sum;if(k2|m0) return ERROR;if(mk-l) f=0;else if(m=kT) f=l;else(for(i=0;i=k-2;i+) tempi=0;tempk-l=l;/初始化for(i=k; i=m; i+)/求出序列第k至第m个元素的值(sum=0;for(j=i-k;j=i-l;j+) sum+=tempj;tempi=sum;f=tempm;)return OK;1. 18 解:typedef enumA, B, C, D, E SchoolNam

10、e;typedef enumFemale, Male SexType;typedef struct (char event 3; 项目SexType sex;SchoolName school; int score; Component;typedef structint Mal eSum;男团总分int FemaleSum;女团总分int TotalSum;团体总分 Sum;Sum SumScore(SchoolName sn, Component a, int n) Sum temp;temp. MaleSum;temp. FernaleSum=0;temp. TotalSum=0; in

11、t i;for (i=0;in;i+) if(ai. school=sn) if(ai. sex=Male) temp. MaleSum+=ai. score;if(ai. sex=Female) temp. Fema1eSum+=ai. score; )temp. TotalSum=temp. MaleSum+temp. FemaleSum; return temp;)解二:typedef struct char *sport;enum male,female gender;char schoolname; 校名为或Echar *result; int score; resulttype;t

12、ypedef struct int malescore;int femalescore;int total score; scoretype;void summary(resulttype result)求各校的男女总分和团体总分,假设结果已经储存在result口数组中scoretype score;i=0;while(resulti.sport!=NULL)(switch(resulti.schoolname)(case A:score 0 .totalscore+=resu 11 i. score;if(resulti.gender=0) score 0 .malescore+=resul

13、ti.score;else score 0 .femalescore+=resulti.score;break;case ,B:score.totalscore+=resulti.score;if(resulti.gender=O) score.malescore+=resulti.score;else score.femalescore+=resulti.score;break;i+:1for(i=0;i5;i+)(printf(HSchool %d:nn,i);printf(Total score of male:%dnn,scorei.malescore);printf(MTotal s

14、core of female:%dn,scorei.femalescore);printf(Total score of all:%dnnu,scorei.totalscore);)/summary解3:(上机已实现)要求实现下列函数:void Scores(ResultType *result, ScoreType *score);/求各校的男、女总分和团体总分,并依次存入数组score */*假设比赛结果已经储存在result数组中,*/ 并以特殊记录 ,male,0 (域 scorce=0) */*表示结束*/相关数据类型定义如下:typedef enum female,male Sex

15、;typedef struct char *sport; 项目名称Sex gender; / 性别(女:female:男:male)char schoolname; / 校名为或Echar *result; /Z 成绩int score; / 得分(7,5,4,3,2 或 1) ResultType;typedef struct int malescore; /Z 男子总分int femalescore; /Z 女子总分inttotalscore; /Z男女团体总分 ScoreType;void Scores(ResuItType *result, ScoreType *score)/求各校的

16、男、女点分和团体总分,穽依次存入数组score */假设比赛结果已经储存在result数组中,*/ 并以特殊记录male,二,(域 scorce=0) */表示结束/(int i=0;while(resulti.sport !=NULL)(switch(resulti.schoolname)(case *A:score0.totalscore+=resulti.score;if(resulti.gender=O) scorefO.femalescore+=resulti.score;else score0.malescore+=resulti.score;break;case B:score

17、1 .totalscore+=resultli.score;if(resulti.gender=O) score 1 .femalescore+=resulti.score;else score 1 .malescore+=resulti.score;break;case C:score2.totalscore+=resulti.score;if(resulti.gender=O) score2.femalescore+=resulti.score;else score2.malescore+=resulti.score;break;case D:score 3 . totalscore+=r

18、e sultfi. score;if(resulti.gender=O) score3.femalescore+=resulti.score;else score3.malescore+=resulti.score; break;case E:score4.totalscore+=resulti.score;if(resulti.gender=O) score4.femalescore+=resulti.score;else score4J.malescore+=resulti.score; break; i+;)for(i=0;i5;i+)(printf(MSchool %d:nn,i);p

19、rintf(Total score of male:%dn,scoreij.malescore);printf(nTotal score of female:%dn,scorei.femalescore);printf(Total score of all:%dnn,scorei.totalscore);) 1.19 解:#include#include#define MAXINT 65535#define ArrSize 100 int fun(int i);int mainO (int i, k;int aArrSize;coutEnter k:;cink;if(kArrSizel) ex

20、it(0);for(i=0;iMAXINT) exit(0); else ai=2*i*ai-l;)for(i=0;iMAXINT) exit(0); else coutai* return 0;)解二:Status algoll9(int aARRSIZE)求 i!*2序列的值且不超过 maxint (last= 1;for(i= l;i=ARRSIZE;i+)(ai-l=last*2*i;if(ai-l/last)!=(2*i)reum OVERFLOW;last=ai-l;return OK;1Z/algoll9分析:当某项的结果超过了 maxint时,它除以前面一项的商会发生异常. 1

21、.20 void polyvalue()float ad;float *p=a;printf(Input number of terms:);scanf(%d,&n);printf(lnput the %d coefficients from aO to a%d:n,n,n);for(i=0;i=n;i+) scanf(%f,p+);printf(Input value of x:);scanf(H%r,&x);p=a;xp= 1 ;sum=0; /xp用于存放x的i次方for(i=0;i=n;i+)(sum+=xp*(*p+);xp*=x;)printf(Value is:%fsum);/p

22、olyvalue解3:(上机已实现)要求实现下列函数:Status Series(int ARRSIZE, int a);/求i!*2T序列的值并依次存入长度为ARRSIZE的数组a；*/若所有值均不超过MAXINT,则返回0K,否则返回OVERFLOW */Status Series(int ARRSIZE, int a)/求i!*2序列的值并依次存入长度为ARRSIZE的数组a；*/若所有值均不超过MAXINT,则返回0K,否则返回OVERFLOW */(int s=l, i, t;for(i=l;it) return OVERFLOW;s=ai-l;return OK;1.20 解:#i

23、nclude#include#define N 10double polynomai1(int a, int i,double x, int n);int main()(double x;int n, i;int aN;cout输入变量的值X;cinx;cout”输入多项式的阶次n:;cinn;if(nN-l) exit (0);cout”输入多项式的系数a0an:;for (i=0; i0) return an-i+polynomail(a, i-l, x, n)*x;else return an;本算法的时间复杂度为o(n)。解3:(上机已实现)要求实现下列函数:float Polynom

24、ial(int n, int a,float xO);/求一元多项式的值P(xO)。*/数组a的元素ai为i次项的系数,i=0,l,.,n /float Polynomial(int n, int a, float x)/求一元多项式的值P(x) */数组a的元素ai为i次项的系数,i=0,., n */(int i;float t=l, s, p=0;/t 存放 x 的 i 次方for(i=0;i=n;i+)(if(i!=0) t*二x;s=ai*t;P+=s;return p;第2章线性表1.1 描述以下三个概念的区别:头指针,头结点,首元结点(第一个元素结点).解:头指针是指向链表中第一

25、个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元 结点之前附设的个结点,该结点不存储数据元素,其指针域指向首元结点,其作用主要是为了方便对链表的操作。 它可以对空表、非空表以及首元结点的操作进行统处理。1.2 填空题。解:(1)在顺序表中插入或删除一个元素，需要平均移动表中表元素,具体移动的元素个数与元素在差声除生 量有关。(2)顺序表中逻辑上相邻的元素的物理位置还紧邻。单链表中逻辑上相邻的元素的物理位置至二定紧邻。(3)在单链表中,除了首元结点外,任一结点的存储位置由除燧绮点的整城物期斤示。(4)在冷犧表中、设置”点的N辻插入和删除首元结点时不用进行特殊处理,1.3

26、在什么情况下用顺序表比链表好?解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。1.4 解:6-1RRT Q?! p_1 p6TISp2.6 解:2.? 解:2.8 解:2.9 解:a. (4) (1)b. (7) (11) (8) (4) (1)c. (5) (12)d. (9) (1) (6)a. (11) (3) (14)b. (10) (12) (8) (3) (14)c. (10) (12) (7) (3) (14)d. (12) (11) (3) (14)e. (9)(11)(3)(14)a. (7) (3) (6) (12)b. (

27、8) (4) (5) (13)c. (15)(1)(11)(18)d. (16)(2)(10)(18)e. (14)(9)(17)(1)如果L的长度不小于2,将L的首元结点变成尾元结点。(2)将单循环链表拆成两个单循环链表。2.10 解:Status DeleteK(SqList &a, int i,int k)(从顺序存储结构的线性表a中删除第i个元素起的k个元素注意i的编号从0开始int j;if(ia. length-1 I|ka. length-i) return INFEASIBLE;for(j=0;j=k;j+)a. elemj+i=a. elemj+i+k;a. Iength=a

28、. length-k;return OK;解二:Status DeleteK(SqList &a, int i, int k)删除线性表a中第i个元素起的k个元素if(il|ka. length) return INFEASIBLE;for (count=l; i+count-K=a. length-k;count+) 注意循环结束的条件1.1 e1emi +count-1=a. elemi+count+k-l;a.length一二k;return OK;/DeleteK2.11 设顺序表va中的数据元素递增有序。试写算法,将x插入到顺序表的适当位置上,以保持该表的有序性。 解:Status

29、InsertOrderList(SqList &va, ElemType x)(在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;if(va. length=va. listsize)return(OVERFLOW);for(i=va. length;i0, xva. listsize) return ERROR;va. length+;for(i=va. length-1;va. elemix&i=0;i)va. elemi+l=va. elemi;va. elemi+l=x;return OK;/Insert_SqList解3:(上机已实现)要求实现下列函数:void

30、InsertOrderList(SqList &L, ElemType x)/在有序的顺序表L中保序插入数据元素x */顺序表类型定义如下:typedef struct ElemType *elem;intlength;intlistsize; SqList;void InsertOrderList(SqList &L, ElemType x)/在有序的顺序表L中保序插入数据元素x (int i,j;i=L. length-1;while(i=0&x=i+l;j)L. elemj+l=L. elemj;L. elemi+l=x;L.length+;)2.12 解:Status CompareO

31、rderList(SqList &A, SqList &B)(int i, k, j;k=A. lengthB. length?A. length:B. length;for(i=0;iB. elemi) j=l;if (A. elemik) j=l;if(B. lengthk) j=-l;if(A. length=B. length) j=0;return j;解二:int ListComp (SqList A, SqList B) 比较字符表A和B,并用返回值表示结果,值为正,表示AB;值为负,表示A B; 值为零,表示A二B (for (i=l ;A. elemi | |B. elemi

32、; i+)if(A. elemi!=B. elemi) return A. elemi-B. elemi;return 0;/ListComp解3:(上机已实现)要求实现下列函数:char Compare(SqList A, SqList B);/比较顺序表A和B,*/返回,若A B;*/*=,若 A=B;*/*若 AB*/顺序表类型定义如下:typedef struct ElemType *elem;intlength;intlistsize; SqList;char Compare(SqList A, SqList B)/Z比较顺序表A和B,/返回,若A B;/=,若 A=B;/ ,若 A

33、Bint i;for(i=0;A. elemi i B. elemi;i+)if(A. elemi!=B. elemi)if(A. elemi-B. elemi0) return ;else return ；return 二；)2.13试写算法在带头结点的单链表结构上实现线性表操作Located, x);解： int LocateElem_L(LinkList &L, ElemType x) (int i=0;LinkList p二L;while(p&p-data!=x) p=p-next;i+；if(!p) return 0;else return i;)解二:LNode* Locate(L

34、inkList L, int x)链表上的元素查找,返回指针(for (p=l-next;p&pdata!=x;p=p-next);return p;/Locate解3:(上机已实现)实现下列函数:LinkList Locate(LinkList L, ElemType x);/ It x in the linked list whose head node is pointed by l , then return pointer pointing node x, / otherwise return NULL单链表类型定义如下:typedef struct LNode ElemType d

35、ata;struct LNode *next; LNode, *LinkList;LinkList Locate(LinkList &L, ElemType x)/ If x in the linked list whose head node is pointed/ by L, then return pointer ha pointing node x, / otherwise return NULL (LinkList p;for(p二L-)next;p&p-)data!二x;p=pnext); return p;)2.14试写一算法在带头结点的单链表结构上实现线性表操作Length(L

36、)。解: 返回单链表的长度int ListLength_L(LinkList &L) int i=0;LinkList p=L;if(p) p=p-next; while(p)p=p-next; i+；) return i;解二:int Length(LinkList L)求链表的长度(for (k二,p=L;p-next;p=p-next, k+);return k;/Length解3:(上机已实现)实现下列函数:int Length(LinkList L);/ Return the length of the linked list/ whose head node is pointed

37、by L单链表类型定义如下：typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;int Length(LinkList L)/ Return the length of the linked list/ whose head node is pointed by LLinkList p;int k;for (k=0,p=L;p-next;p=p-next, k+);return k;)2.15 解:void MergeList_L(LinkList &ha, LinkList &hb, LinkList &hc)(LinkList pa, pb;pa=ha;pb=hb;while (pa-