数据结构(C语言版)第三版--清华大学出版社-习题参考答案.docx

《数据结构(C语言版)第三版--清华大学出版社-习题参考答案.docx》由会员分享，可在线阅读，更多相关《数据结构(C语言版)第三版--清华大学出版社-习题参考答案.docx（29页珍藏版）》请在课桌文档上搜索。

1、附录习题参考答案习题1参考答案1.1.选择题(1).A.(2).A.(3).A.(4).B.,C.(5).A.(6).A.(7).C.(8).A.(9).B.(10.)A.1.2.填空题(1) .数据关系(2) .逻辑结构物理结构(3) .线性数据结构树型结构图结构(4) .顺序存储链式存储索引存储散列表(Hash)存储(5) .变量的取值范围操作的类别(6) .数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7) .关系网状结构树结构(8) .空间复杂度和时间复杂度(9) .空间时间(10) .O(n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包

2、括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的根本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由假设千个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述，是指令的有限序列。1.4 语句的时间复杂度为：7 1 )/ - 7 2 2 2 3 n n n n z(x z( z( z(x Zfx Ooooo J 7 J

3、 )/ / I 2 3 4 5 f zrf1.5 参考程序：main()(intX,Y,Z;scanf(w%d,%d,%d”，&X,&Y,Z)；if(X=Y)if(X=Z)if(Y=Z)printf(rt%d,%d,%dw,X,Y,Z)Jelseprintf(tt%df%d,%dw,X,Z,Y);)elseprintf(u%d,%d,%dw,Z,X,Y)Jelseif(Z=X)if(Y=Z)printf(w%d,%d,%dw,Y,Z,X)Jelseprintf(ii%dt%d,%d”，Z,Y,X);elseprintf(%(1,%d,%dw,Y,X,Z);)1.6 参考程序：main()int

4、i,n;floatx,a,p;printf(unn=w);scanf(%f,&n);printf(unx=w)jscanf(%fw,&x);for(i=0;i=n;i+)scanf(ii%fn,&ai);P=a0;for(i=l;inext=p-next;p-next=s;(10) .s-next2. 3.解题思路:将顺序表A中的元素输入数组a,假设数组a中元素个数为n,将下标为0,1,2,，(nT)/2的元素依次与下标为n,nT,，InT)/2的元素交换，输出数组a的元素。参考程序如下：main()inti,n;floatt,a;Printf(nn=);SCanf(%f,&n);for(i=

5、0;i=n-l;i+)scanf(w%fn,&ai);for(i=0;i=(n-l)/2;i+)t=ai;ai=a11-l-i;an-l-i=t;for(i=0;i=n-l;i+)printf(%f,ai);2.4 算法与程序：main()inti,n;floatt,a;printf(unn=w);scanf(%fw,&n);for(i=0;in;i+)scanf(ii%fn,&ai);for(i=l;ia0)t=ai;ai=a0;a0=t;)printf(%fw,a0);for(i=2;ial)t=ai;ai=al;al=t;printf(u%fn,a0);2.5 算法与程序：main()i

6、nti,j,k,n;floatx,t,a;Printf(nx=);SCanf(%f,&x);printf(wnn=,);scanf(ii%fff,&n);for(i=0;in;i+)scanf(%f,&ai);/输入线性表中的元素for(i=0;in;i+)/对线性表中的元素递增排序k=i;for(j=i+l;jn;j+)if(ajak)k=j;if(kj)t=ai;ai=ak;ak=t;for(i=0;ix)break;for(k=n-l;k=i;i-)/移动线性表中元素，然后插入元素Xak+l=ak;ai=x;for(i=0;i=n;i+)/依次输出线性表中的元素Printf(%f,ai)

7、;2.6 算法思路：依次扫描A和B的元素，比拟A、B当前的元素的值，将较小值的元素赋给C,如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下局部赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。有序表的合并算法：voidmerge(SeqListA,SeqListB,SeqList*C)inti,j,k；i=0:j=0；k=0；while(i=A.last&j=B.last)if(A.dataidatak+=A.datai+；elseC-datak+=B.dataj+；while(idatak+三A.datai+；while(jdatak+=B.dataj+；C-last=k-l

8、;2.7 算法思路：依次将A中的元素和B的元素比拟，将值相等的元素赋给3如此直到线性表扫描完毕,线性表C就是所求递增有序线性表。算法：voidmerge(SeqListA,SeqListB,SeqList*C)inti,j,k；i=0:j=0；k=0；while(i=A.last)while(jdatak+=A.datai+；C-last=k-l;习题3参考答案3. 1.选择题(I) .D(2).C(3).D(4).C(5).B(6).C(7).C(8).C(9).B(10).AB(II) .D(12).B(13).D(14).C(15).C(16).D(17).D(18).C(19).C(2

9、0).C3. 2.填空题(1) FILO,FIFO(2) -1,34X*+2Y*3-(3) stack,top,stack,sstack,top=x(4) pllink-rlink=p-rlink,p-rlink-l1ink=p-r1ink(5) (R-F+M)%M(6) topl+l=top2(7) F=R(8) front=rear(9) front=(rear+l)%n(10) N-I(11) ：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表栈只能在线性表的一端插入(称为入栈,push)或者读取栈顶元素或者称为“弹出、出栈(pop)。(

10、12) ：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。不同点：栈只在一端(栈顶)进行插入，删除操作；队列在一端(top)删除，一端(rear)插入。(13) 答：可能序列有14种:ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA0(14) ：不能得到4,3,5,6,1,2,最先出栈的是4,那么按321的方式出，不可能得到1在2前的序列,可以得到L3,5,4,2,6,按如下方式进行PUSh(I),pop(),push(2),push(3),pop(),push(4),push(5),po

11、p(),pop(),popO,push(6),pop()o(15) 答：stack(16) 递归：intvonvert(intno,inta)/将十进制数转换为2进制存放在a,并返回位数intr;SeStacks,*p;P=&s;Init_stack(p);while(no)push(p,no%2);no=10;r=0;while(!empty_stack(p)pop(p,a+r);r+;returnr;递归算法：voidconvert(intno)if(no20)Convert(no2);Printf(u%dn,no%2);)elsePrintf(%d”，no);(17) 考程序：voidv

12、iew(SeStacks)SeStack*p;假设栈元素为字符型charc;P=&s;while(!empty_stack(p)c=pop(p);Printf(%c,c);)Printf(n);3. 10答：char3.11参考程序：voidout(linkqueueq)inte;while(q.rear!=q.front)dequeue(q,e);print(e);打印习题4参考答案4. 1选择题：(1) .A(2).D(3).C(4).C(5).B(6).B(7).D(8).A(9).B(10).D4.2填空题：(I)串长相等且对应位置字符相等(2) 不含任何元素的串，O(3) 所含字符均

13、是空格，所含空格数(4) 10(5) “helloboy”(6) 13(7) 1066(8) 模式匹配(9)串中所含不同字符的个数(10) 36(11) StrLength(s)=14,StrLength(t)=4,SubStr(s,8,7)=STUDENTw,SubStr(t,2,1)二0”，StrIndeX(S,A”)=3,StrIndex(s,t)=0,StrRep(s,“STUDENT,q)=IAMAWORKER,4.4StrReP(s,“Y”，+);StrReP(s,+*，*Y);(12) 串：不含任何字符；空格串：所含字符都是空格串变量和串常量：串常量在程序的执行过程中只能引用不能

14、改变；串变量的值在程序执行过程中是可以改变和重新赋值的主串与子串：子串是主串的一个子集串变量的名字与串变量的值:串变量的名字表示串值的标识符(13)intEQUAl(S,T)char*p,*q;P=&S;q=&T;while(*p&*q)if(*p!=*q)return*p-*q;p+；q+；return*p-*q;(14)(1)6*8*6=288(2)1000+47*6=1282(3)1000+(8+4)*8=1096(4)1000+(6*7+4)*8=1368ijv4.81I21215-132144347542665187539矩阵的三元组表习题5参考答案5. 1选择(1) C(2)B(3

15、)C(4)B(5)C(6)D(7)C(8)C(9)B(10)C(11) B(12)C(13)C(14)C(15)C(16)B(12) 空(1)11036；1040(3) 2i；n;11T;2(5)对；2j1(6) ACDBGJKlHFE(7) p!:NULL(8) HUffman树(9)其第一个孩子;下一个兄弟(10)先序遍历;中序遍历5.3叶子结点:C、F、G、L、I、M、K；非终端结点：A、B、D、E、J；各结点的度：结点：Abcdefglijkm度：430120000100树深：45.4无序树形态如下:9o二叉树形态如下:5.5二叉链表如下:ADA/IEIFIGA5.6先序遍历序列:Ab

16、dehicfjg中序遍历序列:Dbheiafjcg后序遍历序列：Dhiebjfgca5.7(1)先序序列和中序序列相同：空树或缺左子树的单支树；(2)后序序列和中序序列相同：空树或缺右子树的单支树；(3)先序序列和后序序列相同：空树或只有根结点的二叉树。5.8这棵二叉树为:5.9先根遍历序列:Abfglcdiejmk后根遍历序列:FGLBCIDMJKEA层次遍历序列:Abcdefglijkm5.10证明：设树中结点总数为n,叶子结点数为n。，那么n=no+11+nl(1)再设树中分支数目为B,那么B=n+2112+3m+mn1(2)因为除根结点外，每个结点均对应一个进入它的分支，所以有n=B+

17、1(3)将(1)和(2)代入(3),得no+ni+nll=11+2m+3ru+mnn+1从而可得叶子结点数为：no=n2+2n3+(m-l)n1+15.11由5.10结论得，no=(k-l)nk+1又由n=no+m,得Iik=n-11o,代入上式，得no=(k-l)(n-11o)+1叶子结点数为：11o=n(k-l)/k5.12intNodeCount(BiTreeT)计算结点总数ifC)if(T-Ichild=NULL)&(TrchiId=NULL)return1;elsereturnNocIeCount(T-Ichild)+Node(T-rchild)+1;elsereturnO;5.13

18、voidExchangeLR(Bitreebt)*将bt所指二叉树中所有结点的左、右子树相互交换*/if(bt&(bt-lchild|bt-rchild)bt-lchildbt-rchild;Exchange-Ir(bt-lchiId);Exchange-Ir(bt-rchiId);*ExchangeLR*/5. 14intIsFullBitree(BitreeT)/*是那么返回1,否那么返回0。*/Init_Queue(Q);/*初始化队列*/fIag=O;In_Queue(Q,T);/*根指针入队列，按层次遍历*/while(!Empty_Queue(Q)(OutQueue(Q,p);if

19、(!p)flag=l;/*假设本次出队列的是空指针时，那么修改flag值为1。假设以后出队列的指针存在非空，那么可断定不是完全二叉树*/elseif(flag)returnO;*断定不是完全二叉树*/elseIn_Queue(Q,p-lchild);In,Queue(Q,p-rchild);/*不管孩子是否为空,都入队列。*/)*while*/return1;/*只有从某个孩子指针开始，之后所有孩子指针都为空，才可断定为完全二叉树*/*IsFullBitree*/5. 155.16对应的森林分别为:O O OB(d)5. 17(e)typedefcharelemtype;typedefstru

20、ctelemtypedata;intparent;NodeType;(1)求树中结点双亲的算法：intParent(NodeTypet,elemtypex)*x不存在时返回-2,否那么返回X双亲的下标(根的双亲为T*/for(i=0;iMAXN0DE;i+)if(x=ti.data)returnti.parent;return-2;*Parent*/(2)求树中结点孩子的算法：voidChiIdren(NodeTypet,elemtypex)for(i=0;i=MAXNODE)printf(mx不存在n”);elseflag=O;for(j=0;jMAXNODE;j+)if(i=tj.pare

21、nt)printf(mx的孩子:%cn”,tj.data);fIag=I;if(fIag=O)Printf(x无孩子n”)；*Children*/5.18typedefcharelemtype;typedefstructChildNodeintchildcode;structChildNode*nextchild;typedefstructelemtypedata;structChildNode*firstchild;NodeType;(1)求树中结点双亲的算法：intParentCL(NodeTypet,elemtypex)*x不存在时返回-2,否那么返回X双亲的下标*/for(i=0;i=

22、MAXNODE)return-2;*X不存在*/*搜索x的双亲*/for(i=0;inextchild)if(loc=p-chiIdcode)returni;*返回X结点的双亲下标*/*ParentL*/(2)求树中结点孩子的算法：voidChildrenCL(NodeTypet,elemtypex)for(i=0;inextchiId)Printf(x的孩子:%cn”，tp-chiIdcode.data);flag=l;)if(fIag=O)Printf(x无孩子n”)；return;*if*/printf( 19typedef char elemtype; typedef struct T

23、reeNode elemtype data;struct TreeNode *firstchild;struct TreeNode *nextsibling; NodeType;void ChildrenCSL(NodeType *t, elemtype x) * 层次遍历方法 */ Init_Queue(Q); * 初始化队列 */In Queue(Q, t);count=0;while(!EmptyQueue (Q) Out Queue(Q, p);if (p-data=x) *输出x的孩子*/ p=p-firstchild;x不存在n);return;*ChildrenL*/if(!p)

24、Printf(无孩子n);elseprintf(ii的第%i个孩子:%cn”,+count,p-data);/*输出第一个孩子*/p=p-nextsibling;/*沿右分支*/while(p)Printf(x的第%i个孩子:%cn,+count,p-data);p=p-nextsibling;)return;)if(p-firstchild)InQueue(Q,p-firstchild);if(p-nextsibling)InQueue(Q,p-nextsibling);*ChildrenCSL*/5.20(1)哈夫曼树为:(2)在上述哈夫曼树的每个左分支上标以1,右分支上标以0,并设这7个

25、字母分别为A、B、C、D、E、F和H,如以下图所示：那么它们的哈夫曼树为分别为:A：1100B：IlOlC：10D：OilE：OOF：OlOH：111习题6参考答案6.1 选择题(I) C(2)A(3)B(4)C(5)B条边。(6)B(7)A(8)A(9)B(10)A(II) A(12)A(13)B(14)A(15)B(16)A(17)C6.2 填空(1) 4(2) 1对多；多对多(3) n-l;n(4) 0(5) 有向图(6) _J(7) 一半(8) 一半(9) 第i个链表中边表结点数(10) 第i个链表中边表结点数(11)深度优先遍历;广度优先遍历(12) 0方)(13) 无回路6.3(1

26、)邻接矩阵:0111010011M=1000111001OlllO邻接链表:0vlIiI-H21-H3a1v2TI01-H31-H4IAl2WfOlX4|3|3v4fQI-HIl-H4八I4v5TiI2I+|31八I(3)每个顶点的度:顶点度Vl3V23V32V43V53VlV2V3V4VSV63A1/(3)顶点入度出度Vl3V22V31O22313V41V52V626.5(1)深度优先查找遍历序列：VlV2V3V4V5;VlV3V5V4V2;VlV4V3V5V2(1)广度优先查找遍历序列：VlV2V3V4V5;VlV3V2V4V5;VlV4V3V2V56.6有两个连通分量:(ss)顶点(1)

27、(2)(4)(5)LowLowLowLowLowVlOOOOOOOOOOV21OOOOOOOOOV31O1OOOOOOOV43O2121O1O1V5OO()513223O3Uvlvl,v2vl,v2,v3)(vl,v3,v2,v4)vl,v3,v2,v4,T)(vl,v2)(vl,v2),(vl,v3)(vl,v2),(vl,v3),(v2,v4)(vl,v2),(vl,v3),(v2,v4),(v4,v5)最小生成树的示意图如下:6.8拓扑排序结果：V3VlV4V5V2V66.9(1)建立无向图邻接矩阵算法：提示：参见算法6.1因为无向图的邻接矩阵是对称的，所以有for(k=0;ke;k+)

28、/*输入。条边，建立无向图邻接矩阵*/SCanf(“n%d,%d,&i,&j);G-edgesij=G-edgesji=l;(2)建立无向网邻接矩阵算法：提示：参见算法6.1。初始化邻接矩阵：#defineINFINITY32768/*表示极大值*/for(i=0;in;i+)for(j=0;jn;j+)G-edgesij=INFINITY;输入边的信息：不仅要输入边邻接的两个顶点序号，还要输入边上的权值for(k=0;ke;k+)/*输入e条边，建立无向网邻接矩阵*/scanf(*n%d,%dt%d*,&i,&j,&cost);/*设权值为int型*/G-edgesij=G-edgesji=

29、cost;/*对称矩阵*/)(3)建立有向图邻接矩阵算法：提示：参见算法6.1。6.10(1)建立无向图邻接链表算法：typedefVertexTypechar;intCreate_NgAdjList(ALGraph*G)/*输入无向图的顶点数、边数、顶点信息和边的信息建立邻接表*/SCanf(%d,&n);if(nn=n;SCanf(%d,&e);if(ee=e;for(m=0;mn;m+)G-adjlistm.firstedge=NULL;*置每个单链表为空表*/for(m=0;mn;m+)G-adjlistm.vertex=getchar();*输入各顶点的符号*/for(m=l;me;

30、m+)scanf(n%d,%d”，&i,&j);/*输入一对邻接顶点序号*/if(i0IIjadjvex=j;p-next=G-adjlisti.firstedge;G-adjlisti.firstedge=p;p=(EdgeNode*)malIoc(sizeof(EdgeNode);/*在第j+1个链表中插入一个边表结点*/p-adjvex=i;p-next=G-adjlistj.firstedge;G-adjlistj.firstedge=p;*for*/returnO;*成功*/Create_NgAdjList(2)建立有向图逆邻接链表算法：typedefVertexTypechar;i

31、ntCreate_AdjList(ALGraph*G)/*输入有向图的顶点数、边数、顶点信息和边的信息建立逆邻接链表*/SCanf(,&n);if(nn=n;scanf(,z%dz,&e);if(ee=e;for(m=0;mn;m+)G-adjlistm.firstedge=NULL;*置每个单链表为空表*/for(m=0;mn;m+)G-adjlistm.vertex=getchar();/*输入各顶点的符号*/for(m=l;me;m+)scanf(iiM,%dw,&t,&h);/*输入弧尾和弧头序号*/if(t0IIhadjvex=t;p-next=G-adjlisth.firstedg

32、e;G-adjlisth.firstedge=p;*for*/returnO;*成功*/CreateAdjList6.11voidCreateAdjM(ALGraph*G1,MGraph*G2)*通过无向图的邻接链表Gl生成无向图的邻接矩阵G2*/G2-n=Gl-n;G2-e=Gl-e;for(i=0;in;i+)/*置G2每个元素为O*/for(j=0;jn;j+)G2-edgesij=O;for(m=O;mnjm+)G2-vexsm=Gl-adjlistm.vertex;*复制顶点信息*/num=(Gl-n/2=0?Gl-n/2:Gl-n/2+l);*只要搜索前n/2个单链表即可*/for

33、(m=0;madjlistm.firstedge;while(p)*无向图的存储具有对称性*/G2-edgesmp-adjvex=G2-edgesp-adjvexm=1;p=p-next;*for*/*CreateAdjM*/6.12voidCreateAdjL(ALGraph*G1,MGraph*G2)*通过无向图的邻接矩阵GL生成无向图的邻接链表G2*/G2-n=Gl-n;G2-e=Gl-e;for(i=0;in;i+)*建立每个单链表*/G2-vexsi=Gl-adjlisti.vertex;G2-adjlisti.firstedge=NULL;for(j=i;jn;j+)/*对称矩阵，

34、只要搜索主对角以上的元素即可*/if(Gl-edgesij=1)P=(EeIgeNOde*)malIoc(sizeof(EdgeNode);/*在第i+1个链表中插入一个边表结点*/p-adjvex=j;p-next=G-adjlisti.firstedge;G-adjlisti.firstedge=p;P=(EdgeNode*)malIoc(sizeof(EdgeNode);/*在第j+1个链表中插入一个边表结点*/p-adjvex=i;p-next=G-adjlistj.firstedge;G-adjlistj.firstedge=p;*if*/*for*/*for*/*Create_Ad

35、jL*/6.13(1)邻接矩阵中1的个数的一半；(2)假设位于i-1,jT或口-1,51位置的元素值等于1,那么有边相连，否那么没有。(3)顶点i的度等于第Ll行中或第i-1列中1的个数。6.14(1)邻接链表中边表结点的个数的一半；(2)假设第i-1(或j-1)个单链表中存在adjvex域值等于jT(或i-1)的边表结点，那么有边相连,否那么没有。(3)顶点i的度等于第i-1个单链表中边表结点的个数。6. 15提示：参见算法6.2和6.3。习题7参考答案7. 1选择题(1) C(2)C(3)C(4)B(5)A(6)A(7)D(8)B(9)D(10)B（三）B(12)A(13)C(14)C(1

36、5)A(16)D(17)C(18)B,C(19)B(20)A7. 2填空题(1) 0(n),O(log2n)(2) 1,2,4,8,5,log2(n+l)-l(3) 小于，大于(4) 增序序列(5) 2,m-1(6) 70;34,20,55(7) n/m(8) 开放地址法，链地址法(9) 产生冲突的可能性就越大，产生冲突的可能性就越小(IO)关键码直接(11)，(12) 16,16,8,21(13)直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法(14)开放地址法，再哈希法，链地址法，建立一个公共溢出区(15)装满程度(16)索引，快(17)哈希函数，装填因子(18)一个结点(

37、19)中序(20)等于7.3 棵二叉排序树(又称二叉查找树)或者是一棵空树，或者是一棵同时满足以下条件的二叉树：(1)假设它的左子树不空，那么左子树上所有结点的键值均小于它根结点键值。(2)假设它的右子树不空，那么右子树上所有结点的键值均大于它根结点键值。(3)它的左、右子树也分别为二叉排序树。7.4 对地址单元d=H(K),如发生冲突，以d为中心在左右两边交替进行探测。按照二次探测法，键值K的散列地址序列为：do=H(K),dl=(do+l2)modm,d2=(do-12)modm,d3=(do+22)modm,d4=(do-l2)modm,7.5 衡量算法的标准有很多，时间复杂度只是其中之

38、一。尽管有些算法时间性能很好，但是其他方面可能就存在着缺乏。比方散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而排序也是费时的，所以常应用于频繁查找的场合。对于顺序查找，尽管效率不高，但却比拟简单，常用于查找范围较小或偶而进行查找的情况。7.6 6此法要求设立多个散列函数H“i=l,，ko当给定值K与闭散列表中的某个键值是相对于某个散列函数Hl的同义词因而发生冲突时，继续计算该给定值K在下一个散列函数He下的散列地址，直到不再产生冲突为止。7.7散列表由两个一维数组组成。一个称为根本表，另一个称为溢出表。插