数据结构(第4版)习题与实验参考答案数据结构复习资料完整版(c语言版)

WORD格式数据结构(第4版）习题及实验参考答案数据结构复习资料完整版数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。5、在数据结构中，从逻辑上可以把数据结构分成（C）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素的个数为（A）。A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（B）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（B）A、head=NULLB、head-next=NULLC、head-next=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（A）A、head=NULLB、head-next=NULLC、head-next=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（C）A、p-next=NULLB、p=NULLC、p-next=headD、p=head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)1专业资料整理数据结构(第4版）习题及实验参考答案数据结构复习资料完整版9、在一个单链表中，若删除p所指结点的后继结点，则执行（A）A、p-next=p-next-next;B、p=p-next;p-next=p-next-next;C、p-next=p-next;D、p=p-next-next;10、在一个单链表中，若在p所指结点之后插入s所指结点，则执行（B）A、s-next=p;p-next=s;B、s-next=p-next;p-next=s;C、s-next=p-next;p=s;D、p-next=s;s-next=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点s，则执行（C）A、s-next=p-next;p-next=s;B、p-next=s-next;s-next=p;C、q-next=s;s-next=p;D、p-next=s;s-next=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有1个前趋结点。栈和队列1、在栈操作中，输入序列为（A，B，C，D），不可能得到的输出数列是（D）A、（A，B，C，D）B、（D，C，B，A）C、（A，C，D，B）D、（C，A，D，B）2、设栈ST用顺序存储结构表示，则栈ST为空的条件（B）A、ST.top=ST.base0B、ST.top=ST.base=0C、ST.top=ST.basenD、ST.top=ST.base=n3、向一个栈顶指针为HS的链栈中插入一个s结点时，执行（C）A、HS-next=s;B、s-next=HS-next;HS-next=s;C、s-next=HS;HS=S;D、s-next=HS;HS=HS-next;4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删结点的值，则执行（C）A、x=HS;HS=HS-next;B、HS=HS-next;x=HS-data;C、x=HS-data;HS=HS-next;D、s-next=HS;HS=HS-next;5、用单链表表示的链示队列的队头在链表的（A）位置。A、链头B、链尾C、链中6、判定一个链队列（最多元素个数为n）为空的条件是（A）、.front=Q.rearB、Q.front!=Q.rearC、Q.front=(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n7、在链队列中，插入要所指结点需顺序执行的指令是（B）A、Q.front-next=s;f=s;B、Q.rear-next=s;Q.rear=s;C、s-next=Q.rear;Q.rear=s;D、s-next=Q.front;Q.front=s;8、在一个链队列Q中，删除一个结点需要执行的指令是（C）A、Q.rear=Q.front-next;B、Q.rear-next=Q.rear-next-next;2数据结构(第4版）习题及实验参考答案数据结构复习资料完整版C、Q.front-next=Q.front-next-next;D、Q.front=Q.rear-next;9、栈和队列的共同点（C）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10、栈的特点是_先进后出，队列的特点是先进先出11、线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和在队首删除元素。串和数组1、设串s1=ABCDEFG，s2=PQRST，函数Concat(x,y)返回x和y串的连接串，Substr(s,I,j)返回串s从序号i开始的j个字符组成的子串，length(s)返回串s的长度，则Concat(Substr(s1,2,length(s2),Substr(s1,length(s2),2)的结果串是（D）A、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF2、串是一种特殊的线性表，其特殊性体现在（D）A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符3、设有两个串p和q，求q在p中首次出现的位置的运算称作（B）A、连接B、模式匹配C、求子串联D、求串长4、串的两种最基本的存储方式是顺序存储方式和链接存储方式。树和二叉树1、树最合适用来表示（B）A、有序数据元素B、元素之间具有分支层次关系的数据C、无序数据元素D、元素之间无联系的数据2、按照二叉树的定义，具有3个结点的二叉树有（C）种。A、3B、4C、5D、63、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高度为（E），其叶结点数为（G）；树的最小高度为（B），其叶结点数为（G）；若采用链表存储结构，则有（I）个空链域。A、n/2B、log2n+1C、log2nD、nE、n0+n1+n2F、n1+n2G、n2+1H、1I、n+1J、n1K、n2L、n1+14、在一棵二叉树上第5层的结点数最多为（B）。（假设根结点的层数为0）A、8B、16C、15D、325、深度为5的二叉树至多有（C）个结点。A、16B、32C、31D、106、在一非空二叉树的中序遍历序列中，根结点的右边（A）A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D、只有左子树上的所有结点7、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前趋为（D），后序遍历中结点B的直接后继是（E）。3数据结构(第4版）习题及实验参考答案数据结构复习资料完整版A、BB、DC、AD、IE、FF、C8、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（D）A、acbedB、decabC、deabcD、cedba9、在树形结构中，树根结点没有_前趋_结点，其余每个结点有且只有_1_个前趋结点；叶子结点没有_后继_结点，其余每个结点的后继结点可以_任意多个_。10、有一棵树如图所示，回答下面的问题：K1K2K4K3K5K6K7这棵树的根结点是_K1_，这棵树的叶子结点是_K2，K5，K7，K4_；结点k3的度是_2_;这棵树的度为_3_；这棵树的深度是_4_；结点k3的子女是_K5，K6_；结点k3的父结点是_K1_.11、已知一棵二叉树的中序遍历序列为CDBAEGF，前序遍历序列为ABCDEFG，试问能不能惟一确定一棵二叉树，若能请画出该二叉树。若给定前序遍历序列和后序遍历序列，能否惟一确定一棵二叉树，说明理由。答：?由中序遍历序列和前序遍历序列或中序遍历序列和后序遍历序列可以惟一确定一棵二叉树。基本思想是前序（后序）定根，中序分左右。对于给定的前序和中序序列。可确定根结点为A，以A为根的左子树结点为B，C，D，右子树结点为E，F，G。进一步可确定所有子树的根结点，因而也就确定了整个二叉树。对应的二叉树如图所示：ABECFDG?由前序遍历和后序遍历序列不能惟一确定一棵二叉树。如图所示为4棵不同的二叉树，它们的前序遍历序列都是ABC，而后序遍历序列都是CBA。4数据结构(第4版）习题及实验参考答案数据结构复习资料完整版AAAABBBBCCCC12、设二叉树bt的存储结构如下：12345678910left00237580101datajhfdbacegiright0009400000其中bt为树根结点指针，left，right分别为结点的左右孩子指针域，data为结点的数据域，请完成下列各题：?画出二叉树bt的逻辑结构?写出按前序、中序和后序遍历二叉树bt所得到的结点序列。答：?二叉树bt的逻辑结构如图所示：abcdefghij?前序遍历：abcedfhgij中序遍历：ecbhfdjiga后序遍历：echfjigdba13、给定一棵以二叉链表存储结构表示的二叉树，其根结点指针为T，试写出求二叉树的叶子数目的算法。intCountLeaf(BiTreeT)/返回指针T所指二叉树中所有叶子结点个数if(!T)return0;if(!T-lchild&!T-rchild)return1;5数据结构(第4版）习题及实验参考答案数据结构复习资料完整版elsem=CountLeaf(T-lchild);n=CountLeaf(T-rchild);return(m+n);/else/CountLeaf14、给定一棵以二叉链表存储结构表示的二叉树，其根结点指针为T，试写出求二叉树的深度的算法。intDepth(BiTreeT)/返回二叉树的深度if(!T)depthval=0;elsedepthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);returndepthval;图1、一个有n个顶点的无向图最多有（C）条边。A、nB、n(n-1)C、n(n-1)/2D、2n2、具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。A、5B、6C、7D、83、存储稀疏图的数据结构常用的是（C）A、邻接矩阵B、三元组C、邻接表D、十字链表4、在有向图的邻接表存储结构中，顶点V在表结点中出现的次数是（C）A、顶点V的度B、顶点V的出度C、顶点V的入度D、依附于顶点V的边数5、用DFS遍历一个无环有向图，并在DFS算法退栈返回时，打印出相应的顶点，则输出的顶点序列是（A）A、逆拓扑有序的B、拓扑有序的C、无序的6、已知一个图如图所示，若从顶点a出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（D），按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（B）。?A、abecdfB、acfebdC、acebfdD、acfdeb?A、abcedfB、abcefdC、abedfcD、acfdeb6数据结构(第4版）习题及实验参考答案数据结构复习资料完整版abcedf7、采用邻接表存储的图的广度优先搜索遍历算法类似于二叉树的（D）A、中序遍历B、先序遍历C、后序遍历D、按层遍历8、已知一个图如图所示，则由该图得到的一种拓扑序列为（A）123456A、V1，V4，V6，V2，V5，V3B、V1，V2，V3，V4，V5，V6C、V1，V4，V2，V3，V6，V5D、V1，V2，V4，V6，V3，V59、在图形结构中，每个结点的前趋结点数和后续结点数可以_任意多个_。10、在AOE网中，从源点到汇点各活动时间总和最长的路径称为关键路径。11、给出图G，如图所示：12345678910117数据结构(第4版）习题及实验参考答案数据结构复习资料完整版（1）给出图G的邻接表（画图即可）（2）在你给出的邻接表的情况下，以顶点V4为根，画出图G的深度优先生成树和广度优先生成树。（3）将你画出的广度优先生成树转换为对应的二叉树。答：（1）图的邻接表如下图所示：略（2）以顶点V4为根的深度优先生成树和广度优先生成树如图所示12345678910111234567891011（3）广度优先生成树转换成二叉树如下图所示8数据结构(第4版）习题及实验参考答案数据结构复习资料完整版12543687119109数据结构(第4版）习题及实验参考答案数据结构复习资料完整版附录习题及实验参考答案习题1参考答案1.1.选择题(1).A.(2).A.(3).A.(4).B.,C.(5).A.(6).A.(7).C.(8).C.(9).B.(10.)A.1.2.填空题(1).数据关系(2).逻辑结构物理结构(3).线性数据结构树型结构图结构(4).顺序存储链式存储索引存储散列表（Hash）存储(5).变量的取值范围操作的类别(6).数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7).关系网状结构树结构(8).空间复杂度和时间复杂度(9).空间时间(10).(n)1.3名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述，是指令的有限序列。1.4语句的时间复杂度为：(1)(n2)(2)(n2)(3)(n2)(4)(n-1)(5)(n3)1.5参考程序：main()intX,Y,Z；scanf(“%d,%d,%d”,&X,&Y,Z)；if(X=Y)if(X=Z)if(Y=Z)printf(“%d,%d,%d”,X,Y,Z);else10数据结构(第4版）习题及实验参考答案数据结构复习资料完整版printf(“%d,%d,%d”,X,Z,Y);elseprintf(“%d,%d,%d”,Z,X,Y);elseif(Z=X)if(Y=Z)printf(“%d,%d,%d”,Y,Z,X);elseprintf(“%d,%d,%d”,Z,Y,X);elseprintf(“%d,%d,%d”,Y,X,Z);1.6参考程序：main()inti,n;floatx,a,p;printf(“nn=”);scanf(“%f”,&n);printf(“nx=”);scanf(“%f”,&x);for(i=0;i=n;i+)scanf(“%f”,&ai);p=a0;for(i=1;inext=p-next;p-next=s;11数据结构(第4版）习题及实验参考答案数据结构复习资料完整版(10).s-next2.3.解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,（n-1）/2的元素依次与下标为n,n-1,（n-1）/2的元素交换，输出数组a的元素。参考程序如下：main()inti,n;floatt,a;printf(“nn=”);scanf(“%f”,&n);for(i=0;i=n-1;i+)scanf(“%f”,&ai);for(i=0;i=(n-1)/2;i+)t=ai;ai=an-1-i;an-1-i=t;for(i=0;i=n-1;i+)printf(“%f”,ai);2.4算法与程序：main()inti,n;floatt,a;printf(“nn=”);scanf(“%f”,&n);for(i=0;in;i+)scanf(“%f”,&ai);for(i=1;ia0t=ai;ai=a0;a0=t;printf(“%f”,a0);for(i=2;ia1t=ai;ai=a1;a1=t;printf(“%f”,a0);2.5算法与程序：main()inti,j,k,n;12数据结构(第4版）习题及实验参考答案数据结构复习资料完整版floatx,t,a;printf(“nx=”);scanf(“%f”,&x);printf(“nn=”);scanf(“%f”,&n);for(i=0;in;i+)scanf(“%f”,&ai);/输入线性表中的元素for(i=0;in;i+)/对线性表中的元素递增排序k=i;for(j=i+1;jn;j+)if(ajak)k=j;if(kj)t=ai;ai=ak;ak=t;for(i=0;ix)break;for(k=n-1;k=i;i-)/移动线性表中元素，然后插入元素xak+1=ak;ai=x;for(i=0;i=n;i+)/依次输出线性表中的元素printf(“%f”,ai);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-1；13数据结构(第4版）习题及实验参考答案数据结构复习资料完整版2.7算法思路：依次将A中的元素和B的元素比较，将值相等的元素赋给C，如此直到线性表扫描完毕，线性表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-1；习题3参考答案3.1.选择题(1).D(2).C(3).D(4).C(5).B(6).C(7).C(8).C(9).B(10).AB(11).D(12).B(13).D(14).C(15).C(16).D(17).B(18).C(19).C(20).C3.2.填空题（1）FILO,FIFO（2）-1,34X*+2Y*3/-（3）stack.top+,stack.sstack.top=x（4）pllink-rlink=p-rlink,p-rlink-llink=p-rlink（5）(R-F+M)%M（6）top1+1=top2（7）F=R（8）front=rear（9）front=(rear+1)%n（10）N-13.3答：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性表栈只能在线性表的一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出栈”(pop)。3.4答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（top）删除，一端(rear)插入。3.5答：可能序列有14种：ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA。3.6答：不能得到4，3，5，6，1，2，最先出栈的是4,则按321的方式出，不可能得到1在2前的序列，可以得到1，3，5，4，2，6，按如下方式进行push(1),pop(),push(2),push(3),14数据结构(第4版）习题及实验参考答案数据结构复习资料完整版pop(),push(4),push(5),pop(),pop(),pop(),push(6),pop()。3.7答：stack3.8非递归: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(no/20)Convert(no/2);Printf(“%d”,no%2);elseprintf(“%d”,no);3.9参考程序：voidview(SeStacks)SeStack*p;/假设栈元素为字符型charc;p=&s;while(!empty_stack(p)c=pop(p);printf(“%c”,c);15数据结构(第4版）习题及实验参考答案数据结构复习资料完整版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填空题：（1）串长相等且对应位置字符相等（2）不含任何元素的串，0（3）所含字符均是空格，所含空格数（4）10（5）“helloboy”（6）18（7）1066（8）由零个或多个任意字符组成的字符序列（9）串中所含不同字符的个数（10）364.3StrLength(s)=14,StrLength(t)=4,SubStr(s，8，7)=”STUDEN”T,SubStr(t，2，1)=”O”,StrIndex(s,“A”)=3,StrIndex(s，t)=0,StrRep(s，“STUDEN”T，q)=”IAMAWORKE”R,4.4StrRep(s,”Y”,”+”);StrRep(s,”+*”,”*Y”);4.5空串：不含任何字符；空格串：所含字符都是空格串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的主串与子串：子串是主串的一个子集串变量的名字与串变量的值:串变量的名字表示串值的标识符4.6intEQUAl(S,T)char*p,*q;p=&S;16数据结构(第4版）习题及实验参考答案数据结构复习资料完整版q=&T;while(*p&*q)if(*p!=*q)return*p-*q;p+;q+;return*p-*q;4.7(1)6*8*6=288(2)1000+47*6=1282(3)1000+(8+4)*6=1072(4)1000+(6*7+4)*6=12764.8ijv1121215-132144347542665187539矩阵的三元组表习题5参考答案5.1选择（1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C（11）B（12）C（13）C（14）C（15）C5.2填空（1）1（2）1036；1040（3）2i（4）1；n;n-1;2（5）2k-1；2k-1（6）ACDBGJKIHFE17数据结构(第4版）习题及实验参考答案数据结构复习资料完整版（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无序树形态如下：二叉树形态如下：5.5二叉链表如下:18数据结构(第4版）习题及实验参考答案数据结构复习资料完整版ABCDEFGHIJ三叉链表如下:ABCDEFGHIJ5.6先序遍历序列:ABDEHICFJG中序遍历序列:DBHEIAFJCG后序遍历序列:DHIEBJFGCA5.7(1)先序序列和中序序列相同：空树或缺左子树的单支树；(2)后序序列和中序序列相同：空树或缺右子树的单支树；(3)先序序列和后序序列相同：空树或只有根结点的二叉树。5.8这棵二叉树为:19数据结构(第4版）习题及实验参考答案数据结构复习资料完整版5.9先根遍历序列:ABFGLCDIEJMK后根遍历序列:FGLBCIDMJKEA层次遍历序列:ABCDEFGLIJKM5.10证明：设树中结点总数为n，叶子结点数为n0，则n=n0+n1+,+nm（1）再设树中分支数目为B，则B=n1+2n2+3n3+,+mnm（2）因为除根结点外，每个结点均对应一个进入它的分支，所以有n=B+1（3）将（1）和（2）代入（3），得n0+n1+,+nm=n1+2n2+3n3+,+mnm+1从而可得叶子结点数为：n0=n2+2n3+,+(m-1)nm+15.11由5.10结论得，n0=(k-1)nk+1又由n=n0+nk，得nk=n-n0，代入上式，得n0=(k-1)（n-n0）+1叶子结点数为：n0=n(k-1)/k5.12intNodeCount(BiTreeT)/计算结点总数if(T)if(T-lchild=NULL)&(T-rchild=NULL)return1;elsereturnNodeCount(T-lchild)+Node(T-rchild)+1;elsereturn0;20数据结构(第4版）习题及实验参考答案数据结构复习资料完整版5.13voidExchangeLR(Bitreebt)/*将bt所指二叉树中所有结点的左、右子树相互交换*/if(bt&(bt-lchild|bt-rchild)bt-lchildbt-rchild;Exchange-lr(bt-lchild);Exchange-lr(bt-rchild);/*ExchangeLR*/5.14intIsFullBitree(BitreeT)/*是则返回1，否则返回0。*/Init_Queue(Q);/*初始化队列*/flag=0;In_Queue(Q，T);/*根指针入队列，按层次遍历*/while(!Empty_Queue(Q)Out_Queue(Q,p);if(!p)flag=1;/*若本次出队列的是空指针时，则修改flag值为1。若以后出队列的指针存在非空，则可断定不是完全二叉树*/elseif(flag)return0;/*断定不是完全二叉树*/elseIn_Queue(Q，p-lchild);In_Queue(Q，p-rchild);/*不管孩子是否为空，都入队列。*/*while*/return1;/*只有从某个孩子指针开始，之后所有孩子指针都为空，才可断定为完全二叉树*/*IsFullBitree*/5.15转换的二叉树为：21数据结构(第4版）习题及实验参考答案数据结构复习资料完整版5.16对应的森林分别为：C5.17typedefcharelemtype;typedefstructelemtypedata;intparent;NodeType;22数据结构(第4版）习题及实验参考答案数据结构复习资料完整版(1)求树中结点双亲的算法:intParent(NodeTypet,elemtypex)/*x不存在时返回-2,否则返回x双亲的下标(根的双亲为-1*/for(i=0;iMAXNODE;i+)if(x=ti.data)returnti.parent;return-2;/*Parent*/(2)求树中结点孩子的算法:voidChildren(NodeTypet,elemtypex)for(i=0;i=MAXNODE)printf(“x不存在n”);elseflag=0;for(j=0;jMAXNODE;j+)if(i=tj.parent)printf(“x的孩子:%cn”,tj.data);flag=1;if(flag=0)printf(“x无孩子n”);/*Children*/5.18typedefcharelemtype;typedefstructChildNodeintchildcode;structChildNode*nextchild;typedefstructelemtypedata;structChildNode*firstchild;NodeType;(1)求树中结点双亲的算法:intParentCL(NodeTypet,elemtypex)/*x不存在时返回-2,否则返回x双亲的下标*/for(i=0;i=MAXNODE)return-2;/*x不存在*/*搜索x的双亲*/for(i=0;inextchild)if(loc=p-childcode)returni;/*返回x结点的双亲下标*/*ParentL*/(2)求树中结点孩子的算法:voidChildrenCL(NodeTypet,elemtypex)for(i=0;inextchild)printf(“x的孩子:%cn”,tp-childcode.data);flag=1;if(flag=0)printf(“x无孩子n”);return;/*if*/printf(“x不存在n”);return;/*ChildrenL*/5.19typedefcharelemtype;typedefstructTreeNodeelemtypedata;structTreeNode*firstchild;structTreeNode*nextsibling;NodeType;voidChildrenCSL(NodeType*t,elemtypex)/*层次遍历方法*/Init_Queue(Q);/*初始化队列*/In_Queue(Q,t);count=0;while(!Empty_Queue(Q)Out_Queue(Q,p);if(p-data=x)/*输出x的孩子*/p=p-firstchild;if(!p)printf(“无孩子n”);24数据结构(第4版）习题及实验参考答案数据结构复习资料完整版elseprintf(“x的第%i个孩子:%cn”,+count,p-data);/*输出第一个孩子*/p=p-nextsibling;/*沿右分支*/while(p)printf(“x的第%i个孩子:%cn”,+count,p-data);p=p-nextsibling;return;if(p-firstchild)In_Queue(Q,p-firstchild);if(p-nextsibling)In_Queue(Q,p-nextsibling);/*ChildrenCSL*/5.20(1)哈夫曼树为:694128221916121097534(2)在上述哈夫曼树的每个左分支上标以1，右分支上标以0，并设这7个字母分别为A、B、C、D、E、F和H，如下图所示：则它们的哈夫曼树为分别为:25数据结构(第4版）习题及实验参考答案数据结构复习资料完整版A：1100B：1101C：10D：011E：00F：010H：111习题6参考答案6.1选择题（1）C（2）A（3）B（4）C（5）B_条边。（6）B（7）A（8）A（9）B（10）A（11）A（12）A（13）B（14）A（15）B（16）A（17）C6.2填空（1）4（2）1对多;多对多（3）n-1;n（4）0_（5）有向图（6）1（7）一半（8）一半（9）_第i个链表中边表结点数_（10）_第i个链表中边表结点数_（11）深度优先遍历；广度优先遍历（12）O（n2）（13）_无回路6.3（1）邻接矩阵:（2）邻接链表：26数据结构(第4版）习题及实验参考答案数据结构复习资料完整版（3）每个顶点的度：顶点度V13V23V32V43V536.4（1）邻接链表：（2）逆邻接链表：（3）顶点入度出度V130V222V312V41327数据结构(第4版）习题及实验参考答案数据结构复习资料完整版V521V6236.5（1）深度优先查找遍历序列：V1V2V3V4V5;V1V3V5V4V2;V1V4V3V5V2（1）广度优先查找遍历序列：V1V2V3V4V5;V1V3V2V4V5;V1V4V3V2V56.6有两个连通分量：6.7（1）（2）（3）（4）（5）顶LowCloseLowCloseLowCloseLowCloseLowClose点CostVexCostVexCostVexCostVexCostVexV10101010101V211010101011V31111010101V43122220202V5152332404Uv1v1,v2v1,v2,v3v1,v2,v3,v4v1,v2,v3,v4,v5(v1,v2)(v1,v2),(v1,v2),(v1,v2),T(v1,v3)(v1,v3),(v2,v4)(v1,v3),(v2,v4),(v4,v5)最小生成树的示意图如下：6.828数据结构(第4版）习题及实验参考答案数据结构复习资料完整版拓扑排序结果：V3V1V4V5V2V66.9（1）建立无向图邻接矩阵算法：提示：参见算法6.1因为无向图的邻接矩阵是对称的，所以有for(k=0;ke;k+)/*输入e条边，建立无向图邻接矩阵*/scanf(n%d,%d,&i,&j);G-edgesij=G-edgesji=1;(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,%d,%d,&i,&j,&cost);/*设权值为int型*/G-edgesij=G-edgesji=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=1;me;m+)scanf(“n%d,%d”,&i,&j);/*输入一对邻接顶点序号*/29数据结构(第4版）习题及实验参考答案数据结构复习资料完整版if(i0|jadjvex=j;p-next=G-adjlisti.firstedge;G-adjlisti.firstedge=p;p=(EdgeNode*)malloc(sizeof(EdgeNode);/*在第j+1个链表中插入一个边表结点*/p-adjvex=i;p-next=G-adjlistj.firstedge;G-adjlistj.firstedge=p;/*for*/return0;/*成功*/Create_NgAdjList(2)建立有向图逆邻接链表算法：typedefVertexTypechar;intCreate_AdjList(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=1;me;m+)scanf(“n%d,%d”,&t,&h);/*输入弧尾和弧头序号*/if(t0|hadjvex=t;p-next=G-adjlisth.firstedge;G-adjlisth.firstedge=p;/*for*/return0;/*成功*/Create_AdjList6.11voidCreate_AdjM(ALGraph*G1，MGraph*G2)/*通过无向图的邻接链表G1生成无向图的邻接矩阵G2*/G2-n=G1-n;G2-e=G1-e;for(i=0;in;i+)/*置G2每个元素为0*/for(j=0;jn;j+)G2-edgesij=0;for(m=0;mn;m+)G2-vexsm=G1-adjlistm.vertex;/*复制顶点信息*/num=（G1-n/2=0?G1-n/2:G1-n/2+1）;/*只要搜索前n/2个单链表即可*/30数据结构(第4版）习题及实验参考答案数据结构复习资料完整版for(m=0;madjlistm.firstedge;while(p)/*无向图的存储具有对称性*/G2-edgesmp-adjvex=G2-edgesp-adjvexm=1;p=p-next;/*for*/*Create_AdjM*/6.12voidCreate_AdjL(ALGraph*G1，MGraph*G2)/*通过无向图的邻接矩阵G1，生成无向图的邻接链表G2*/G2-n=G1-n;G2-e=G1-e;for(i=0;in;i+)/