《数据结构习题集答案(C语言严版).doc》由会员分享，可在线阅读，更多相关《数据结构习题集答案(C语言严版).doc（91页珍藏版）》请在三一文库上搜索。
1、1.1解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。1.2 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直
2、接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。1.3 解：1.4 解：ADT Complex数据对象：D=r,i|r,i为实数数据关系：R=基本操作：InitComplex(&C,re,im)操作结果：构造一个复数C，其实部和虚部分别为re和imDestroyCmoplex(&C)操作结果：销毁复数CGet(C,k,&e)操作结果：用e
3、返回复数C的第k元的值Put(&C,k,e)操作结果：改变复数C的第k元的值为eIsAscending(C)操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0IsDescending(C)操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0Max(C,&e)操作结果：用e返回复数C的两个元素中值较大的一个Min(C,&e)操作结果：用e返回复数C的两个元素中值较小的一个ADT ComplexADT RationalNumber数据对象：D=s,m|s,m为自然数，且m不为0数据关系：R=基本操作：InitRationalNumber(&R,s,m)操作结果：构造一个有理数
4、R，其分子和分母分别为s和mDestroyRationalNumber(&R)操作结果：销毁有理数RGet(R,k,&e)操作结果：用e返回有理数R的第k元的值Put(&R,k,e)操作结果：改变有理数R的第k元的值为eIsAscending(R)操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0IsDescending(R)操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0Max(R,&e)操作结果：用e返回有理数R的两个元素中值较大的一个Min(R,&e)操作结果：用e返回有理数R的两个元素中值较小的一个ADT RationalNumber1.6 解：(1)exit
5、常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。 (2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。 (3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。1.7 解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制， 较为烦琐，如果出现错误，则会引起整个系统的崩溃。 (2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。 (3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量 使程序的维护较为困难。1.8 解：(1) n-1 (2) n
6、-1 (3) n-1 (4) n+(n-1)+(n-2)+.+1= (5) 1+(1+2)+(1+2+3)+.+(1+2+3+.+n)= = = (6) n (7) 向下取整 (8) 11001.9 解： count=1.11 解：n=40 n=16 则对于同样的循环次数n，在这个规模下，第二种算法所花费的代价要大得多。故在这个规模 下，第一种算法更适宜。1.12 解：(1)对 (2)错 (3)错 (4)对 (5)错1.13 解：的增长趋势快。但在n较小的时候，的值较大。当n438时，1.14 解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快1.16 试写一算法，自
7、大至小依次输出顺序读入的三个整数X，Y和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;1.17 解：k0为阶数，n为数列的第n项int Fibonacci(int k,int n)if(k1) exit(OVERFLOW);int *p,x;p=new intk+1;if(!p) exit(OVERFLOW);int i,j;for(i=0;ik+1;i+)if(ik-1) pi=0;else pi=1;for(i=k+1;in+1;i+
8、)x=p0;for(j=0;jk;j+) pj=pj+1;pk=2*pk-1-x;return pk;1.18 解：typedef enumA,B,C,D,E SchoolName;typedef enumFemale,Male SexType;typedef structchar event3; /项目SexType sex;SchoolName school;int score; Component;typedef structint MaleSum;/男团总分int FemaleSum;/女团总分int TotalSum;/团体总分 Sum;Sum SumScore(SchoolName
9、 sn,Component a,int n)Sum temp;temp.MaleSum=0;temp.FemaleSum=0;temp.TotalSum=0;int i;for(i=0;in;i+)if(ai.school=sn)if(ai.sex=Male) temp.MaleSum+=ai.score;if(ai.sex=Female) temp.FemaleSum+=ai.score;temp.TotalSum=temp.MaleSum+temp.FemaleSum;return temp;1.19 解：#include#include#define MAXINT 65535#defin
10、e ArrSize 100int fun(int i);int main()int i,k;int aArrSize;coutk;if(kArrSize-1) exit(0);for(i=0;iMAXINT) exit(0);else ai=2*i*ai-1;for(i=0;iMAXINT) exit(0);else coutai ;return 0;1.20 解：#include#include#define N 10double polynomail(int a,int i,double x,int n);int main() double x;int n,i;int aN;coutx;c
11、outn;if(nN-1) exit(0);cout输入多项式的系数a0-an:;for(i=0;iai;coutThe polynomail value is polynomail(a,n,x,n)0) return an-i+polynomail(a,i-1,x,n)*x;else return an;本算法的时间复杂度为o(n)。第2章 线性表2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用
12、主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。2.2 填空题。解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。2.3 在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取
13、。2.4 解： 2.5 解：2.6 解：a. (4) (1)b. (7) (11) (8) (4) (1)c. (5) (12)d. (9) (1) (6)2.7 解：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)2.8 解：a. (7) (3) (6) (12)b. (8) (4) (5) (13)c. (15) (1) (11) (18)d. (16) (2) (10) (18)e. (14) (9) (17)2.9 解：(
14、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|ka.length-i) return INFEASIBLE;for(j=0;j0,xB.length?A.length:B.length;for(i=0;iB.elemi) j=1;if(A.elemik) j=1;if(B.lengthk) j=-1;if(A.length=B.length
15、) j=0;return j;2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,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;2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。解：/返回单链表的长度int ListLength_L(LinkList &L)int i=0;LinkList p=L;if(p) p=p-next;while(
16、p)p=p-next;i+;return i;2.15解：void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc)LinkList pa,pb;pa=ha;pb=hb;while(pa-next&pb-next)pa=pa-next;pb=pb-next;if(!pa-next)hc=hb;while(pb-next) pb=pb-next;pb-next=ha-next;elsehc=ha;while(pa-next) pa=pa-next;pa-next=hb-next;2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结
17、点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len)if(i0|j0|len0) return INFEASIBLE;p=la;k=1;while(knext;k+;q=p;while(knext;k+;s=lb; k=1;while(knext;k+;s-next=p; q-next=s-next;return OK;解：Status DeleteAndInsert
18、Sub(LinkList &la,LinkList &lb,int i,int j,int len)LinkList p,q,s,prev=NULL;int k=1;if(i0|j0|len0) return INFEASIBLE;/ 在la表中查找第i个结点p=la;while(p&knext;k+;if(!p)return INFEASIBLE;/ 在la表中查找第i+len-1个结点q=p;k=1;while(q&knext;k+;if(!q)return INFEASIBLE;/ 完成删除，注意，i=1的情况需要特殊处理if(!prev) la=q-next;else prev-nex
19、t=q-next;/ 将从la中删除的结点插入到lb中if(j=1)q-next=lb;lb=p;elses=lb;k=1;while(s&knext;k+;if(!s)return INFEASIBLE;q-next=s-next;s-next=p; /完成插入return OK;2.19 解：Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk)LinkList p,q,prev=NULL;if(minkmaxk)return ERROR;p=L;prev=p;p=p-next;while(p&p-datadatanext;
20、elseprev-next=p-next;q=p;p=p-next;free(q);return OK;2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。解：void ListDelete_LSameNode(LinkList &L)LinkList p,q,prev;p=L;prev=p;p=p-next;while(p)prev=p;p=p-next;if(p&p-data=prev-data)prev-next=p-next;q=p;p=p-next;free(q);2
21、.21 解：/ 顺序表的逆置Status ListOppose_Sq(SqList &L)int i;ElemType x;for(i=0;inext;L-next=NULL;while(p)q=p;p=p-next;q-next=L-next;L-next=q;return OK;2.23 解：/ 将合并后的结果放在C表中，并删除B表Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C)LinkList pa,pb,qa,qb;pa=A-next;pb=B-next;C=A;while(pa&pb)qa=pa;qb=pb;pa=pa-n
22、ext;pb=pb-next;qb-next=qa-next;qa-next=qb;if(!pa)qb-next=pb;pb=B;free(pb);return OK;2.24 解：/ 将合并逆置后的结果放在C表中，并删除B表Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;/ 保存pa的前驱指针qb=pb;/ 保存pb的前驱指针pa=pa-next;pb=pb-next;A-next=NULL;C=A;while(pa&pb)if(pa-datad
23、ata)qa=pa;pa=pa-next;qa-next=A-next;/将当前最小结点插入A表表头A-next=qa;elseqb=pb;pb=pb-next;qb-next=A-next;/将当前最小结点插入A表表头A-next=qb;while(pa)qa=pa;pa=pa-next;qa-next=A-next;A-next=qa;while(pb)qb=pb;pb=pb-next;qb-next=A-next;A-next=qb;pb=B;free(pb);return OK;2.25解：/ 将A、B求交后的结果放在C表中Status ListCross_Sq(SqList &A,S
24、qList &B,SqList &C)int i=0,j=0,k=0;while(iA.length & jB.length)if(A.elemiB.elemj)j+;elseListInsert_Sq(C,k,A.elemi);i+;k+;return OK;2.26 要求同2.25题。试对单链表编写求C的算法。解：/ 将A、B求交后的结果放在C表中，并删除B表Status ListCross_L(LinkList &A,LinkList &B,LinkList &C)LinkList pa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;/ 保存pa的前驱指针qb=pb;/ 保存p
25、b的前驱指针pa=pa-next;pb=pb-next;C=A;while(pa&pb)if(pa-datadata)pt=pa;pa=pa-next;qa-next=pa;free(pt);elseif(pa-datapb-data)pt=pb;pb=pb-next;qb-next=pb;free(pt);elseqa=pa;pa=pa-next;while(pa)pt=pa;pa=pa-next;qa-next=pa;free(pt);while(pb)pt=pb;pb=pb-next;qb-next=pb;free(pt);pb=B;free(pb);return OK;2.27 解：(
26、1)/ A、B求交，然后删除相同元素，将结果放在C表中Status ListCrossDelSame_Sq(SqList &A,SqList &B,SqList &C)int i=0,j=0,k=0;while(iA.length & jB.length)if(A.elemiB.elemj)j+;elseif(C.length=0)ListInsert_Sq(C,k,A.elemi);k+;elseif(C.elemC.length-1!=A.elemi)ListInsert_Sq(C,k,A.elemi);k+;i+;return OK;(2)/ A、B求交，然后删除相同元素，将结果放在A表
27、中Status ListCrossDelSame_Sq(SqList &A,SqList &B)int i=0,j=0,k=0;while(iA.length & jB.length)if(A.elemiB.elemj)j+;elseif(k=0)A.elemk=A.elemi;k+;elseif(A.elemk!=A.elemi)A.elemk=A.elemi;k+;i+;A.length=k;return OK;2.28 解：(1)/ A、B求交，结果放在C表中，并删除相同元素Status ListCrossDelSame_L(LinkList &A,LinkList &B,LinkLis
28、t &C)LinkList pa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;/ 保存pa的前驱指针qb=pb;/ 保存pb的前驱指针pa=pa-next;pb=pb-next;C=A;while(pa&pb)if(pa-datadata)pt=pa;pa=pa-next;qa-next=pa;free(pt);elseif(pa-datapb-data)pt=pb;pb=pb-next;qb-next=pb;free(pt);elseif(pa-data=qa-data)pt=pa;pa=pa-next;qa-next=pa;free(pt);elseqa=pa;pa=pa-ne
29、xt;while(pa)pt=pa;pa=pa-next;qa-next=pa;free(pt);while(pb)pt=pb;pb=pb-next;qb-next=pb;free(pt);pb=B;free(pb);return OK;(2)/ A、B求交，结果放在A表中，并删除相同元素Status ListCrossDelSame_L(LinkList &A,LinkList &B)LinkList pa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;/ 保存pa的前驱指针qb=pb;/ 保存pb的前驱指针pa=pa-next;pb=pb-next;while(pa&pb)if(
30、pa-datadata)pt=pa;pa=pa-next;qa-next=pa;free(pt);elseif(pa-datapb-data)pt=pb;pb=pb-next;qb-next=pb;free(pt);elseif(pa-data=qa-data)pt=pa;pa=pa-next;qa-next=pa;free(pt);elseqa=pa;pa=pa-next;while(pa)pt=pa;pa=pa-next;qa-next=pa;free(pt);while(pb)pt=pb;pb=pb-next;qb-next=pb;free(pt);pb=B;free(pb);retur
31、n OK;2.29 解：/ 在A中删除既在B中出现又在C中出现的元素，结果放在D中Status ListUnion_Sq(SqList &D,SqList &A,SqList &B,SqList &C)SqList Temp;InitList_Sq(Temp);ListCross_L(B,C,Temp);ListMinus_L(A,Temp,D);2.30 要求同2.29题。试对单链表编写算法，请释放A表中的无用结点空间。解：/ 在A中删除既在B中出现又在C中出现的元素，并释放B、CStatus ListUnion_L(LinkList &A,LinkList &B,LinkList &C)L
32、istCross_L(B,C);ListMinus_L(A,B);/ 求集合A-B，结果放在A表中，并删除B表Status ListMinus_L(LinkList &A,LinkList &B)LinkList pa,pb,qa,qb,pt;pa=A;pb=B;qa=pa;/ 保存pa的前驱指针qb=pb;/ 保存pb的前驱指针pa=pa-next;pb=pb-next;while(pa&pb)if(pb-datadata)pt=pb;pb=pb-next;qb-next=pb;free(pt);elseif(pb-datapa-data)qa=pa;pa=pa-next;elsept=pa;pa=pa-next;qa-next=pa;free(pt);while(pb)pt=pb;pb=pb-next;qb-next=pb;free(pt);