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

《数据结构(第4版)习题与实验参考答案数据结构复习资料完整版(c语言版)》由会员分享，可在线阅读，更多相关《数据结构(第4版)习题与实验参考答案数据结构复习资料完整版(c语言版)（50页珍藏版）》请在装配图网上搜索。

1、WORD格式 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据 的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。 它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构 成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使 用与实现分

2、离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换 为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（C） A、动态结构和表态结构B、紧凑结构和非紧凑结构 C、线性结构和非线性结构D、内部结构和外部结构 6、算法的时间复杂度取决于（A） A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时， 插入一个元素所需移动元素的平均次数为（E

3、），删除一个元素需要移动的元素的个数 为（A）。 A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（B） A、正确的B、错误的C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D） A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可 以 5、带头结点的单链表为空的判定条件是（B） A、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL 6、不带头结点

4、的单链表head为空的判定条件是（A） A、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL 7、非空的循环单链表head的尾结点P满足（C） A、p->next==NULLB、p==NULLC、p->next==headD、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 （B） A、O(1)B、O(n)C、O(n2)D、O(nlog2n) 1 专业资料整理 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 9、在一个单链表中，若删除p所指结点的后继结

5、点，则执行（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->ne

6、xt=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.base<>0B、ST.top=ST.ba

7、se==0 C、ST.top=ST.base<>nD、ST.top=ST.base==n 3、向一个栈顶指针为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

8、->next; 5、用单链表表示的链示队列的队头在链表的（A）位置。 A、链头B、链尾C、链中 6、判定一个链队列Ｑ（最多元素个数为n）为空的条件是（A） Ａ、Ｑ.front==Q.rearB、Q.front!=Q.rear C、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n 7、在链队列Ｑ中，插入要所指结点需顺序执行的指令是（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.fron

9、t=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、线性表、栈和队列都是线性结

10、构，可以在线性表的任何位置插入和删除元素；对于栈只 能在栈顶插入和删除元素；对于队列只能在队尾插入元素和在队首删除元素。 串和数组 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、BCDEFEF 2、串是一种特殊的线性表，其特殊性体现在（D）

11、 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、6 3、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0 的结点数为n0，则树

12、的最大高度为（E），其叶结点数为（G）；树的最小高 度为（B），其叶结点数为（G）；若采用链表存储结构，则有（I） 个空链域。 A、n/2B、[log2n]+1C、log2nD、nE、n0+n1+n2F、n1+n2 G、n2+1H、1I、n+1J、n1K、n2L、n1+1 4、在一棵二叉树上第5层的结点数最多为（B）。（假设根结点的层数为0） A、8B、16C、15D、32 5、深度为5的二叉树至多有（C）个结点。 A、16B、32C、31D、10 6、在一非空二叉树的中序遍历序列中，根结点的右边（A） A、只有右子树上的所有结点B、只有右子树上的部分结点 C、只有左子树

13、上的部分结点D、只有左子树上的所有结点 7、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前趋 为（D），后序遍历中结点B的直接后继是（E）。 3 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 A、BB、DC、AD、IE、FF、C 8、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 （D） A、acbedB、decabC、deabcD、cedba 9、在树形结构中，树根结点没有___前趋________结点，其余每个结点有且只有 _______1______个前趋结点；叶子结点没有___

14、___后继___________结点，其余每个结点的 后继结点可以__任意多个____。 10、有一棵树如图所示，回答下面的问题： K1 K2K4 K3 K5K6 K7 这棵树的根结点是____K1_______，这棵树的叶子结点是__K2，K5，K7，K4______；结点 k3的度是____2________;这棵树的度为___3_______；这棵树的深度是_____4_________；结 点k3的子女是______K5，K6_____；结点k3的父结点是_____K1_________. 11、已知一棵二叉树的中序遍历序列为CDBAEGF，前序遍历序列为ABCDE

15、FG，试问能不 能惟一确定一棵二叉树，若能请画出该二叉树。若给定前序遍历序列和后序遍历序列，能否 惟一确定一棵二叉树，说明理由。 答： ?由中序遍历序列和前序遍历序列或中序遍历序列和后序遍历序列可以惟一确定一棵二叉 树。基本思想是前序（后序）定根，中序分左右。 对于给定的前序和中序序列。可确定根结点为A，以A为根的左子树结点为B，C，D，右 子树结点为E，F，G。进一步可确定所有子树的根结点，因而也就确定了整个二叉树。对 应的二叉树如图所示： A BE CF DG ?由前序遍历和后序遍历序列不能惟一确定一棵二叉树。如图所示为4棵不同的二叉树，它 们的前序遍历序列都是

16、ABC，而后序遍历序列都是CBA。 4 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 AAAA BBBB CCCC 12、设二叉树bt的存储结构如下： 12345678910 left00237580101 datajhfdbacegi right0009400000 其中bt为树根结点指针，left，right分别为结点的左右孩子指针域，data为结点的数据域， 请完成下列各题： ?画出二叉树bt的逻辑结构 ?写出按前序、中序和后序遍历二叉树bt所得到的结点序列。 答： ?二叉树bt的逻辑结构如图所示： a b cd e fg h

17、 i j ?前序遍历：abcedfhgij 中序遍历：ecbhfdjiga 后序遍历：echfjigdba 13、给定一棵以二叉链表存储结构表示的二叉树，其根结点指针为T，试写出求二叉树的叶 子数目的算法。 intCountLeaf(BiTreeT){ //返回指针T所指二叉树中所有叶子结点个数 if(!T)return0; if(!T->lchild&&!T->rchild)return1; 5 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 else{ m=CountLeaf(T->lchild); n=CountLeaf(T->rchild)

18、; return(m+n); }//else }//CountLeaf 14、给定一棵以二叉链表存储结构表示的二叉树，其根结点指针为T，试写出求二叉树的深 度的算法。 intDepth(BiTreeT){//返回二叉树的深度 if(!T)depthval=0; else{ depthLeft=Depth(T->lchild); depthRight=Depth(T->rchild); depthval=1+(depthLeft>depthRight? depthLeft:depthRight); } returndepthval; } 图 1、一个有n个顶点的

19、无向图最多有（C）条边。 A、nB、n(n-1)C、n(n-1)/2D、2n 2、具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。 A、5B、6C、7D、8 3、存储稀疏图的数据结构常用的是（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

20、出发按深度优先搜索法进行遍历，则可能得到的一种 顶点序列为（D），按广度优先搜索法进行遍历，则可能得到的一种顶点序列为 （B）。 ?A、abecdfB、acfebdC、acebfdD、acfdeb ?A、abcedfB、abcefdC、abedfcD、acfdeb 6 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 a b c e df 7、采用邻接表存储的图的广度优先搜索遍历算法类似于二叉树的（D） A、中序遍历B、先序遍历C、后序遍历D、按层遍历 8、已知一个图如图所示，则由该图得到的一种拓扑序列为（A） 123 4 5 6 A、V1，V4

21、，V6，V2，V5，V3B、V1，V2，V3，V4，V5，V6 C、V1，V4，V2，V3，V6，V5D、V1，V2，V4，V6，V3，V5 9、在图形结构中，每个结点的前趋结点数和后续结点数可以___任意多个_______。 10、在AOE网中，从源点到汇点各活动时间总和最长的路径称为关键路径。 11、给出图G，如图所示： 1 234 5678 91011 7 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 （1）给出图G的邻接表（画图即可） （2）在你给出的邻接表的情况下，以顶点V4为根，画出图G的深度优先生成树和广度优 先生成树。 （3）将你画

22、出的广度优先生成树转换为对应的二叉树。 答： （1）图的邻接表如下图所示：略 （2）以顶点V4为根的深度优先生成树和广度优先生成树如图所示 1 234 5678 91011 1 234 5678 91011 （3）广度优先生成树转换成二叉树如下图所示 8 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 1 2 5 4 3 6 8 711 9 10 9 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 附录习题及实验参考答案 习题1参考答案 1.1.选择题 (1).A.(2).A.(3).A.(4).B.,C.

23、(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名词解释如下： 数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。 数据项：数据项指不可分割的、具有独立

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

25、参考程序： 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);} else 10 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 {printf(“%d,%d,%d”,X,Z,Y);} else {printf(“%d,%d,%d”,Z,X,Y);} else if(Z>=X) if(Y>=Z) {printf(“%d,%d,%d”,Y,Z,X);} else {printf(“%d,%d,%

26、d”,Z,Y,X);} else {printf(“%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”,&a[i]); p=a[0]; for(i=1;i<=n;i++) {p=p+a[i]*x; x=x*x;} printf(“%f”,p)’ } 习题2参考答案 2.1选择题 (1).C.(2).B.(3)

27、.B.(4).B.5.D.6.B.7.B.8.A.9.A.10.D. 2.2.填空题 (1).有限序列 (2).顺序存储和链式存储 (3).Ｏ(n)O(n) (4).n-i+1n-i (5).链式 (6).数据指针 (7).前驱后继 (8).Ο(1)Ο(n) (9).s->next=p->next;p->next=s; 11 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 (10).s->next 2.3.解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0， 1,2,,,（n-1）/2的元素依次与下标为n,n-1,,,（n-

28、1）/2的元素交换，输出数组a的 元素。 参考程序如下： main() { inti,n; floatt,a[]; printf(“nn=”);scanf(“%f”,&n); for(i=0;i<=n-1;i++) scanf(“%f”,&a[i]); for(i=0;i<=(n-1)/2;i++) {t=a[i];a[i]=a[n-1-i];a[n-1-i]=t;} for(i=0;i<=n-1;i++) printf(“%f”,a[i]); } 2.4算法与程序： main() { inti,n; floatt,a[]; printf(“nn=”);

29、scanf(“%f”,&n); for(i=0;ia[0] {t=a[i];a[i]=a[0];a[0]=t;} printf(“%f”,a[0]); for(i=2;ia[1] {t=a[i];a[i]=a[1];a[1]=t;} printf(“%f”,a[0]); } 2.5算法与程序： main() { inti,j,k,n; 12 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 floatx,t,a

30、[]; printf(“\nx=”);scanf(“%f”,&x); printf(“nn=”);scanf(“%f”,&n); for(i=0;ij){t=a[i];a[i]=a[k];a[k]=t;} } for(i=0;ix)break; for(k=n-1;k>=i;i--

31、)//移动线性表中元素，然后插入元素x a[k+1]=a[k]; a[i]=x; for(i=0;i<=n;i++)//依次输出线性表中的元素 printf(“%f”,a[i]); } 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&

32、&j<=B.last) if(A.data[i]<=B.data[j]) C->data[k++]=A.data[i++]； else C->data[k++]=B.data[j++]； while(i<=A.last) C->data[k++]=A.data[i++]； while(j<=B.last) C->data[k++]=B.data[j++]； C->last=k-1； } 13 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 2.7算法思路：依次将A中的元素和B的元素比较，将值相等的元素赋给C，如此直到线性 表扫描完毕，线性表C就是所求

33、递增有序线性表。 算法： voidmerge(SeqListA,SeqListB,SeqList*C) {inti，j，k； i=0；j=0；k=0； while(i<=A.last) while（j<=B.last) if(A.data[i]=B.data[j]) C->data[k++]=A.data[i++]； 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

34、(18).C(19).C(20).C 3.2.填空题 （1）FILO,FIFO （2）-1,34X*+2Y*3/- （3）stack.top++,stack.s[stack.top]=x （4）p>llink->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-1 3.3答：一般线性表使用数组来表示的 线性表一般有插入、删除、读取等对于任意元素的操作 而栈只是一种特殊的线性表 栈只

35、能在线性表的一端插入（称为入栈,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，按如

36、下方式进行push(1),pop(),push(2),push(3), 14 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 pop(),push(4),push(5),pop(),pop(),pop(),push(6),pop()。 3.7答：stack 3.8非递归: intvonvert(intno,inta[])//将十进制数转换为2进制存放在a[]，并返回位数 { intr; SeStacks,*p; P=&s; Init_stack(p); while(no) { push(p,no%2); no/=10; } r=0; whil

37、e(!empty_stack(p)) { pop(p,a+r); r++; } returnr; } 递归算法: voidconvert(intno) { if(no/2>0) { Convert(no/2); Printf(“%d”,no%2); } else printf(“%d”,no); } 3.9参考程序： voidview(SeStacks) { SeStack*p;//假设栈元素为字符型 charc; p=&s; while(!empty_stack(p)) { c=pop(p); printf(“%c”,c); } 15

38、 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 printf(”n”); } 3.10答：char 3.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).D 4.2填空题： （1）串长相等且对应位置字符相等 （2）不含任何元素的串，0 （3）所含字符均是空格，所含空格数

39、 （4）10 （5）“helloboy” （6）18 （7）1066 （8）由零个或多个任意字符组成的字符序列 （9）串中所含不同字符的个数 （10）36 4.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空串：不含任何字符；空格串：所含字符

40、都是空格 串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过 程中是可以改变和重新赋值的 主串与子串：子串是主串的一个子集 串变量的名字与串变量的值:串变量的名字表示串值的标识符 4.6 intEQUAl(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+4

41、7*6=1282 (3)1000+(8+4)*6=1072 (4)1000+(6*7+4)*6=1276 4.8 ijv 1121 215-1 3214 4347 5426 6518 7539 矩阵的三元组表 习题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）C 5.2填空 （1）1 （2）1036；1040 （3）2i （4）1；n;n-1;2 （5）2k-1；2k-1 （6）ACDBGJKIHFE 17 数据结构(第4版）习题及实验

42、参考答案 数据结构复习资料完整版 （7）p!=NULL （8）Huffman树 （9）其第一个孩子;下一个兄弟 （10）先序遍历；中序遍历 5.3 叶子结点:C、F、G、L、I、M、K； 非终端结点：A、B、D、E、J； 各结点的度： 结点：ABCDEFGLIJKM 度：430120000100 树深：4 5.4 无序树形态如下： 二叉树形态如下： 5.5 二叉链表如下: 18 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 A BC ∧D∧E∧F∧G∧ ∧H∧∧I∧∧J∧ 三叉链表如下: A∧ BC ∧D∧E∧F∧G∧

43、∧H∧∧I∧∧J 5.6 先序遍历序列:ABDEHICFJG 中序遍历序列:DBHEIAFJCG 后序遍历序列:DHIEBJFGCA 5.7 (1)先序序列和中序序列相同：空树或缺左子树的单支树； (2)后序序列和中序序列相同：空树或缺右子树的单支树； (3)先序序列和后序序列相同：空树或只有根结点的二叉树。 5.8 这棵二叉树为: 19 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 5.9 先根遍历序列:ABFGLCDIEJMK 后根遍历序列:FGLBCIDMJKEA 层次遍历序列:ABCDEFGLIJKM 5.10 证明：设树中结点总数

44、为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+1 5.11 由5.10结论得，n0=(k-1)nk+1 又由n=n0+nk，得nk=n-n0，代入上式，得 n0=(k-1)（n-n0）+1 叶子结点数为：n0=n(k-1)/k 5.12 int

45、NodeCount(BiTreeT) {//计算结点总数 if(T) if(T->lchild==NULL)&&(T-->rchild==NULL) return1; else returnNodeCount(T->lchild)+Node(T-->rchild)+1; else return0; 20 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 } 5.13 voidExchangeLR(Bitreebt){ /*将bt所指二叉树中所有结点的左、右子树相互交换*/ if(bt&&(bt->lchild||bt->rchild)){ bt->

46、lchild<->bt->rchild; Exchange-lr(bt->lchild); Exchange-lr(bt->rchild); } }/*ExchangeLR*/ 5.14 intIsFullBitree(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。若以后出队列

47、 的指针存在非空，则可断定不是完全二叉树*/ elseif(flag)return0;/*断定不是完全二叉树*/ else { In_Queue(Q，p->lchild); In_Queue(Q，p->rchild);/*不管孩子是否为空，都入队列。*/ } }/*while*/ return1;/*只有从某个孩子指针开始，之后所有孩子指针都为空，才可断定为完全二 叉树*/ }/*IsFullBitree*/ 5.15 转换的二叉树为： 21 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 5.16 对应的森林分别为： C 5.17 ty

48、pedefcharelemtype; typedefstruct {elemtypedata; intparent; }NodeType; 22 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 (1)求树中结点双亲的算法: intParent(NodeTypet[],elemtypex){ /*x不存在时返回-2,否则返回x双亲的下标(根的双亲为-1*/ for(i=0;i

49、dChildren(NodeTypet[],elemtypex){ for(i=0;i=MAXNODE)printf(“x不存在\n”); else{ flag=0; for(j=0;j

50、typedefcharelemtype; typedefstructChildNode {intchildcode; structChildNode*nextchild; } typedefstruct {elemtypedata; structChildNode*firstchild; }NodeType; (1)求树中结点双亲的算法: intParentCL(NodeTypet[],elemtypex){ /*x不存在时返回-2,否则返回x双亲的下标*/ for(i=0;i

51、标*/ 23 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 break; } if(i>=MAXNODE)return-2;/*x不存在*/ /*搜索x的双亲*/ for(i=0;inextchild) if(loc==p->childcode) returni;/*返回x结点的双亲下标*/ }/*ParentL*/ (2)求树中结点孩子的算法: voidChildrenCL(NodeTypet[],elemtypex){ for(i=0;i

52、ODE;i++) if(x==t[i].data)/*依次打印x的孩子*/ { flag=0;/*x存在*/ for(p=t[i].firstchild;p;p=p->nextchild) {printf(“x的孩子:%c\n”,t[p->childcode].data); flag=1; } if(flag==0)printf(“x无孩子\n”); return; }/*if*/ printf(“x不存在\n”); return; }/*ChildrenL*/ 5.19 typedefcharelemtype; typedefstructTreeNode {

53、elemtypedata; 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

54、 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 else {printf(“x的第%i个孩子:%c\n”,++count,p->data);/*输出第一个孩子*/ p=p->nextsibling;/*沿右分支*/ while(p){ printf(“x的第%i个孩子:%c\n”,++count,p->data); p=p->nextsibling; } } return; } if(p->firstchild)In_Queue(Q,p->firstchild); if(p->nextsibling)In_Queue(Q,p->nextsibling

55、); } }/*ChildrenCSL*/ 5.20 (1)哈夫曼树为: 69 4128 22 19 16 12 10 9 75 34 (2)在上述哈夫曼树的每个左分支上标以1，右分支上标以0，并设这7个字母分别为A、B、 C、D、E、F和H，如下图所示： 则它们的哈夫曼树为分别为: 25 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 A：1100 B：1101 C：10 D：011 E：00 F：010 H：111 习题6参考答案 6.1选择题 （1）C（2）A（3）B（4）C（5）B______条边。（6）B（7）A（

56、8）A（9）B（10）A （11）A（12）A（13）B（14）A（15）B（16）A（17）C 6.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）每个顶点的度： 顶点度 V13 V23 V32

57、 V43 V53 6.4 （1）邻接链表： （2）逆邻接链表： （3）顶点入度出度 V130 V222 V312 V413 27 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 V521 V623 6.5 （1）深度优先查找遍历序列：V1V2V3V4V5;V1V3V5V4V2;V1V4V3V5V2 （1）广度优先查找遍历序列：V1V2V3V4V5;V1V3V2V4V5;V1V4V3V2V5 6.6 有两个连通分量： 6.7 （1）（2）（3）（4）（5）顶 LowCloseLowCloseLowCloseLowCloseLowClos

58、e点 CostVexCostVexCostVexCostVexCostVex V10101010101 V21101010101 1 V31111010101 V43122220202 V5∞152332404 U {v1}{v1,v2}{v1,v2,v3}{v1,v2,v3, v4} {v1,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)} 最小生成树的示意图

59、如下： 6.8 28 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 拓扑排序结果：V3V1V4V5V2V6 6.9 （1）建立无向图邻接矩阵算法： 提示：参见算法6.1 因为无向图的邻接矩阵是对称的，所以有 for(k=0;ke;k++)/*输入e条边，建立无向图邻接矩阵*/ {scanf("\n%d,%d",&i,&j); G->edges[i][j]=G->edges[j][i]=1; } (2)建立无向网邻接矩阵算法: 提示：参见算法6.1。 初始化邻接矩阵： #defineINFINITY32768/*表示极大值*/ for(

60、i=0;in;i++) for(j=0;jn;j++)G->edges[i][j]=INFINITY; 输入边的信息： 不仅要输入边邻接的两个顶点序号，还要输入边上的权值 for(k=0;ke;k++)/*输入e条边，建立无向网邻接矩阵*/ {scanf("\n%d,%d,%d",&i,&j,&cost);/*设权值为int型*/ G->edges[i][j]=G->edges[j][i]=cost;/*对称矩阵*/ } (3)建立有向图邻接矩阵算法: 提示：参见算法6.1。 6.10 (1)建立无向图邻接链表算法： typedefVertexT

61、ypechar; intCreate_NgAdjList(ALGraph*G) {/*输入无向图的顶点数、边数、顶点信息和边的信息建立邻接表*/ scanf("%d",&n);if(n<0)return-1;/*顶点数不能为负*/ G->n=n; scanf("%d",&e);if(e<0)return=1;/*边数不能为负*/ G->e=e; for(m=0;mn;m++) G->adjlist[m].firstedge=NULL;/*置每个单链表为空表*/ for(m=0;mn;m++) G->adjlist[m].vertex=getchar();/*

62、输入各顶点的符号*/ for(m=1;m<=G->e;m++) { scanf(“\n%d,%d”,&i,&j);/*输入一对邻接顶点序号*/ 29 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 if((i<0||j<0)return-1; p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第i+1个链表中插入一个边表结点*/ p->adjvex=j;p->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=p; p=(EdgeNode*)malloc(sizeof(E

63、dgeNode));/*在第j+1个链表中插入一个边表结点*/ p->adjvex=i;p->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=p; }/*for*/ return0;/*成功*/ }//Create_NgAdjList (2)建立有向图逆邻接链表算法： typedefVertexTypechar; intCreate_AdjList(ALGraph*G) {/*输入有向图的顶点数、边数、顶点信息和边的信息建立逆邻接链表*/ scanf("%d",&n);if(n<0)return-1;/*顶点数不能

64、为负*/ G->n=n; scanf("%d",&e);if(e<0)return=1;/*弧数不能为负*/ G->e=e; for(m=0;mn;m++) G->adjlist[m].firstedge=NULL;/*置每个单链表为空表*/ for(m=0;mn;m++) G->adjlist[m].vertex=getchar();/*输入各顶点的符号*/ for(m=1;m<=G->e;m++) { scanf(“\n%d,%d”,&t,&h);/*输入弧尾和弧头序号*/ if((t<0||h<0)return-1; p=(EdgeNode*)ma

65、lloc(sizeof(EdgeNode));/*在第h+1个链表中插入一个边表结点*/ p->adjvex=t;p->next=G->adjlist[h].firstedge; G->adjlist[h].firstedge=p; }/*for*/ return0;/*成功*/ }//Create_AdjList 6.11 voidCreate_AdjM(ALGraph*G1，MGraph*G2) {/*通过无向图的邻接链表G1生成无向图的邻接矩阵G2*/ G2->n=G1->n;G2->e=G1->e; for(i=0;in;i++)/*置G2每个元素为0*/

66、 for(j=0;jn;j++)G2->edges[i][j]=0; for(m=0;mn;m++) G2->vexs[m]=G1->adjlist[m].vertex;/*复制顶点信息*/ num=（G1->n/2==0?G1->n/2:G1->n/2+1）;/*只要搜索前n/2个单链表即可*/ 30 数据结构(第4版）习题及实验参考答案 数据结构复习资料完整版 for(m=0;madjlist[m].firstedge; while(p) {/*无向图的存储具有对称性*/ G2->edges[m][p->adjvex]=G2->edges[p->adjvex][m]=1; p==p->next; } }/*for*/ }/*Create_AdjM*/ 6.12 voidCreate_AdjL(ALGraph*G1，MGraph*G2) {/*通过无向图的邻接矩阵G1，生成无向图的邻接链表G2*/ G2->n=G1->n;G2->e=G1->e; for(i=0;in;i++)/