数据结构与算法课后习题答案

1、课后习题解答判断题1 线性表的逻辑顺序与存储顺序总是一致的。（X）2 顺序存储的线性表可以按序号随机存取。（V）3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一 半的元素需要移动。 （X）4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性， 因此属于同一数据对象。 （V）5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（X）6 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（V）7 线性表的链式存储结构优于顺序存储结构。（X）&在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（

2、V）9 线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（V）10.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机 存取的存储结构。 （X）11 静态链表既有顺序存储的优点， 又有动态链表的优点。 所以它存取表中第 i 个元素 的时间与i无关。（X）12 线性表的特点是每个元素都有一个前驱和一个后继。（X）算法设计题1.设线性表存放在向量 Aarrsize的前elenum个分量中，且递增有序。试写一算法， 将 x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。 【提示】 直接用题目中所给定的数据结构 （顺序存储的思想是用

3、物理上的相邻表示逻辑上的 相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的， 所以首先确定是否还有存储空间， 若有， 则根据原线性表中元素 的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开 始一边比较，一边移位）然后插入 x ，最后修改表示表长的变量。/* 设 elenum 为表的/* 表已满，无法插入 */* 边找位置边移动 */* 找到的位置是插入位的下一/* 插入成功 */int insert （datatype A,int *elenum,datatype x）最大下标 */if (*elenum=a

4、rrsize-1) return 0; else i=*elenum;while (i=0 & Aix)Ai+1=Ai;i-;Ai+1=x;位*/(*elenum)+; return 1;时间复杂度为 O(n) 。2 已知一顺序表 A,其元素值非递减有序排列，编写一个算法删除顺序表中多余的值 相同的元素。【提示】对顺序表 A从第一个元素开始，查找其后与之值相同的所有元素，将它们删除； 再对第二个元素做同样处理，依此类推。void delete(Seqlist *A) i=0; while(ilast)*/k=i+1;while(klast&A-datai=A-datak)k+;/* 将第 i

5、个元素以后与其值相同的元素删除/* 使 k 指向第一个与 Ai 不同的元n=k-i-1;for(j=k;jlast;j+)A-dataj-n=A-dataj;A-last= A-last -n;/*n表示要删除元素的个数 */* 删除多余元素 */i+;3 写一个算法，从一个给定的顺序表A中删除值在以较高的效率来实现。xy(xdatai是否介于x和y之间，并不立即删除，而是用 n 记录删除时应前移元素的位移量；若不是，则将 A-datai 向前 移动n位。n用来记录当前已删除元素的个数。void delete(Seqlist *A,int x,int y)i=0;n=0;while (ilas

6、t)if (A-datai=x & A-dataidatai-n=A-datai;牡曰 若是，/* 若 A-datai 介于 x 和 y 之/* 否则向前移动 A-datai*/素*/i+;A-last-=n;4 线性表中有n个元素，每个元素是一个字符，现存于向量Rn中，试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素 移动次数最小。【提示】 对线性表进行两次扫描， 第一次将所有的字母放在前面， 第二次将所有的数字放在 字母之后，其它字符之前。int fch(char c)/* 判断 c 是否字母 */if(c=a&c=A&c=0&c=9) ret

7、urn (1);else return (0);void process(char Rn)low=0;high=n-1;while(lowhigh) /* 将字母放在前面 */ while(lowhigh&fch(Rlow) low+;while(lowhigh&!fch(Rhigh) high-;if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;low=low+1;high=n-1;while(lowhigh) /* 将数字放在字母后面， 其它字符前面 */ while(lowhigh&fnum(Rlow) low+;while(lowhigh&!fnum(Rhigh

8、) high-;if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;5线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后 n 个元素进行整体互换。即将线性表：(a1, a 2,，am， b 1， b 2，b n）改变为：(b1, b 2,，bn ， a 1， a 2， ， a m）。【提示】比较m和n的大小，若mn则将表中兀素依次前移 m次；否则，将表中兀素依次后移 n 次。void process(Seqlist *L,int m,int n) if(m=n) for(i=1;idata0;for(k=1;klast;k+)L-datak-

9、1=L-datak; L-dataL-last=x;else for(i=1;idataL-last;for(k=L-last-1;k=0;k- -)L-datak+1=L-datak;L-data0=x;6已知带头结点的单链表 L中的结点是按整数值递增排列的， 试写一算法，将值为x的 结点插入到表L中，使得L仍然递增有序，并且分析算法的时间复杂度。LinkList insert(LinkList L, int x) p=L;while(p-next & xp-next-data) p=p-next;置*/s=(LNode *)malloc(sizeof(LNode); s-data=x; s

10、-next=p-next; p-next=s;return(L);7假设有两个已排序(递增)的单链表 不改变其排序性。/* 寻找插入位/* 申请结点空间 */* 填装结点 */* 将结点插入到链表中 */A和B,编写算法将它们合并成一个链表C而LinkList Combine(LinkList A, LinkList B) C=A;rc=C;pa=A-next; pb=B-next;free(B);while (pa & pb)/*pa指向表A的第一个结点*/*pb指向表B的第一个结点*/*释放B的头结点*/* 将 pa、pb 所指向结点中， 值较小的一个插入到链表C 的表尾 */if(pa-

11、datadata)rc-next=pa;rc=pa; pa=pa-next;elserc-next=pb; rc=pb; pb=pb-next;if(pa) rc-next=pa;else rc-next=pb;/*将链表A或B中剩余的部分链接到链表C的表尾*/return(C);8假设长度大于 1 的循环单链表中，既无头结点也无头指针， p 为指向该链表中某一 结点的指针，编写算法删除该结点的前驱结点。【提示】利用循环单链表的特点，通过 s 指针可循环找到其前驱结点 p 及 p 的前驱结点 q， 然后可删除结点 *p。viod delepre(LNode *s)LNode *p, *q;p=

12、s;while (p-next!=s)q=p;p=p-next;q-next=s;free(p);9. 已知两个单链表 A和B分别表示两个集合，其元素递增排列，编写算法求出A和B的交集C,要求C同样以元素递增的单链表形式存储。【提示】交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表C带有一个头结点，最后将其删除掉。算法中指针p用来指向A中的当前结点，指针q用来指 向B中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不等时， 将其较小者跳过，继续后面的比较。LinkList Intersect(LinkList A, LinkList B)LNode *

13、q, * p, * r, *s;LinkList C;C= (LNode *)malloc(sizeof(LNode);C-next=NULL;r=C;p=A;q=B;while (p & q )if (p-datadata) p=p-next;else if (p-data=q-data)s=(LNode *)malloc(sizeof(LNode);s-data=p-data;r-next=s;r=s;p=p-next;q=q-next;else q=q-next;r-next=NULL;C=C-next;return C;10设有一个双向链表，每个结点中除有prior 、 data 和

14、next 域外，还有一个访问频 度 freq 域，在链表被起用之前，该域的值初始化为零。每当在链表进行一次 Locata(L,x) 运算后，令值为 x 的结点中的 freq 域增 1，并调整表中结点的次序，使其按访问频度的非 递增序列排列， 以便使频繁访问的结点总是靠近表头。 试写一个满足上述要求的 Locata(L,x) 算法。【提示】在定位操作的同时，需要调整链表中结点的次序：每次进行定位操作后， 要查看所 查找结点的 freq 域，将其同前面结点的 freq 域进行比较，同时进行结点次序的调整。typedef struct dnodedatatype data;int freq;stru

15、ct DLnode *prior,*next;DLnode,*DLinkList;DlinkList Locate(DLinkList L, datatype x)p=L-next; while(p&p-data!=x) p=p-next;它*/if(!p) return(NULL);*/p-freq+;*/ while(p-prior!=L&p-prior-freqfreq) k=p-prior-data;p-prior-data=p-data;p-data=k;k=p-prior-freq;p-prior-freq=p-freq;p-freq=k;p=p-prior;return(p);*

16、/* 查找值为 x 的结点，使 p 指向/* 若查找失败，返回空指针/* 修改 p 的 freq 域/* 调整结点的次序 */* 返回找到的结点的地址课后习题解答 #1向一个栈顶指针为 Top 的链栈中插入一个 A Top-next=p;C p-next=Top;Top=p; 2对于栈操作数据的原则是( ABDp 所指结点时，其操作步骤为( p-next=Top-next;Top-next=p; p-next=Top;Top=Top-next;C)。3 则 pi 是A先进先出 B 后进先出 若已知一个栈的入栈序列是D)。i n-i CB)。C 后进后出D 不分顺序1,2,3,n，其输出序列为p

17、i,p2,p3,，PN,若PN是n,n-i+1 D不确定选择题4表达式 a*（b c） d 的后缀表达式是（ B）。A abcd*-+ B abc-*d+ C abc*-d+ D +-*abcd5采用顺序存储的两个栈共享空间S1.m ，topi 代表第 i 个栈 （ i=1,2） 的栈顶，栈 1 的底在 S1 ，栈 2 的底在 Sm ，则栈满的条件是（ B）。A top2-top1|=0B top1+1=top2C top1+top2=mD top1=top26一个栈的入栈序列是 a,b,c,d,e ，则栈的不可能的输出序列是（ C）。A edcbaB decbaC dceabD abcde7

18、在一个链队列中，若 f,r 分别为队首、队尾指针，则插入 s 所指结点的操作为（ B）。 A f-next=r;f=s;B r-next=s;r=s;C s-next=r;r=s;D s-next=f;f=s;8用不带头结点的单链表存储队列时，在进行删除运算时（D）。A. 仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改9递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。A.队列B .静态链表C.栈 D .顺序表10. 栈和队都是（ C）。A. 顺序存储的线性结构C.限制存取点的线性结构B. 链式存储的非线性结构D.限制存取点的非线性结构判断题

19、1栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。（V）2任何一个递归过程都可以转换成非递归过程。（V）3若输入序列为1,2,3,4,5,6 ，则通过一个栈可以输出序列3,2,5,6,4,1。 （V）4通常使用队列来处理函数的调用。（X）5循环队列通常用指针来实现队列的头尾相接。（X）简答题1. 循环队列的优点是什么？如何判别它的空和满？ 循环队列的优点是能够克服“假溢满”现象。设有循环队列sq,队满的判别条件为：（ sq-rear+1 ） %maxsize=sq-front; 或 sq-num=maxsize 。队空的判别条件为：sq-rear=sq-front 。2. 栈和

20、队列数据结构各有什么特点,什么情况下用到栈,什么情况下用到队列？ 栈和队列都是操作受限的线性表, 栈的运算规则是 “后进先出” ,队列的运算规则是 “先进先出”。栈的应用如数制转换、递归算法的实现等,队列的应用如树的层次遍历等。3. 什么是递归？递归程序有什么优缺点？一个函数在结束本函数之前,直接或间接调用函数自身,称为递归。例如,函数 f 在执行中，又调用函数f自身，这称为直接递归；若函数 f在执行中，调用函数 g，而g在执行 中,又调用函数 f ,这称为间接递归。在实际应用中,多为直接递归,也常简称为递归。递归程序的优点是程序结构简单、 清晰, 易证明其正确性。 缺点是执行中占内存空间较

21、多,运行效率低。4. 设有编号为 1,2,3,4 的四辆车,顺序进入一个栈式结构的站台,试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站,可能不入站,时间也可能不等）。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,4321课后习题解答 #选择题1下面关于串的叙述错误的是（ C）。A. 串是字符的有限序列B. 串既可以采用顺序存储，也可以采用链式存储C. 空串是由空格构成的串D. 模式匹配是串的一种重要运算2串的长度是指（ B）。A.串中所含不同字母的个数B 串中所含字符的个数C. 串中所含不同字符的个数D

22、串中所含非空格字符的个数3.已知串S= aaab,其Next数组值为（A）。A. 0123 B . 1123 C . 1231 D . 12114二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标 i的 范围从0到8,列下标j的范围从1到10,则存放M至少需要（D）个字节；M的第8列和第5行共占（A）个字节；若 M按行优先方式存储，兀素M8 5的起始地址与当M按列优先方式存储时的（C）兀素的起始地址一致。（ 1 ） A. 90 B . 180 C .240 D. 540（ 2） A. 108 B . 114 C .54 D. 60（3） A. M85 B. M310C.M58

23、D. M095.数组A中，每个兀素的存储占3 个单元,行下标i 从 1 到 8,列下标 j 从 1 到 10,从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（C）,若该数组按行存放，元素 A85的起始地址是（D）,若该数组按列存放，元素A85的起始地址是（ B）。（ 1 ） A. 80B.100C. 240D. 270（ 2） A. SA+141 B .SA+144 C. SA+222D .SA+225（ 3） A. SA+141 B .SA+180 C. SA+117D .SA+2256.稀疏矩阵采用压缩存储,一般有（C）两种方法。A.二维数组和三维数组B .三元组和散列

24、C.三元组表和十字链表D .散列和十字链表判断题1. 串相等是指两个串的长度相等。（X）2. KMP算法的特点是在模式匹配时指示主串的指针不会变小。（V）3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（V）4. 数组是线性结构的一种推广,因此与线性表一样,可以对它进行插入,删除等操作。（X）5. 若采用三元组存储稀疏矩阵,把每个元素的行下标和列下标互换,就完成了对该矩 阵的转置运算。 （X）6. 若一个广义表的表头为空表,则此广义表亦为空表。（X）7. 所谓取广义表的表尾就是返回广义表中最后一个元素。（X）0123456k 4m -1 4m简答题1. KMP算法较朴素的模式匹配算法有哪些改进

25、？KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。2. 设字符串 S= aabaabaabaac ， P= aabaac。(1) 给出S和P的next值和nextval值；(2) 若S作主串，P作模式串，试给出利用KMP算法的匹配过程。【解答】(1) S的next与nextval值分别为 0和0009, p的next与nextval值分别为 012123 和 002003。(2) 利用BF算法的匹配过程：利用KMP算法的匹配过程：第一趟匹配： aabaabaabaac第一趟匹配：aabaabaabaacaabaac(i=6,j=6)

26、aabaac(i=6,j=6)第二趟匹配： aabaabaabaac第二趟匹配： aabaabaabaac1第三趟匹配：aabaabaabaac成功)(aa)baac时，第一个元素的字节地址是100,每个aa(i=3,j=2)(aa)baac第三趟匹配： aabaabaabaaca(i=3,j=1)(第四趟匹配： aabaabaabaacaabaac(i=9,j=6)第五趟匹配： aabaabaabaacaa(i=6,j=2)第六趟匹配： aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac(成功)aabaac(i=13,j=7)3.假设按行优先存储整数数组A93

27、5 8整数占4个字节。问下列元素的存储地址是什么？(1) a 0000 (2)a1111 (3)a3125(4)a 8247【解答】(1) LOC( a 0000)= 100(2) LOC( a 1111)=100+(3*5*8*1+5*8*1+8*1+1)*4=776 LOC( a 3125)=100+(3*5*8*3+5*8*1+8*2+5) *4=1784 (4) LOC( a 8247)= 100+(3*5*8*8+5*8*2+8*4+7) *4=48164假设一个准对角矩阵：an a 12a21 a 22a33 a 34a43 a 44a2m-1,2m-1 a 2m-1,2ma2m,

28、2m-1a 2m,2m按以下方式存储于一维数组 B4m中(m为一个整数)a 11a 12a21a22a33a34a43aija2m-1,2ma2m,2m-1a2m,2m写出下标转换函数k=f(i,j)。【解答】由题目可知，每一行有两个非0元素。当i为奇数时，第i行的元素为：a,i、aw+D，此时k=2*(i-1)+j-i=i+j-2当i为偶数时，第i行的元素为：a,(i-i)、ai,i，此时k=2*(i-1)+j-I+1=i+j-1 综上所述，k=i+j-i%2-1。5. 设有nXn的带宽为3的带状矩阵A,将其3条对角线上的元素存于数组B3n中,使得元素Buv=a j，试推导出从(i,j )到

29、(u,v)的下标变换公式。【解答】u=j-i+1v=j-16现有如下的稀疏矩阵A (如图所示)，要求画出以下各种表示方法。(1) 三元组表表示法(2) 十字链表法。000220-150133000000-60000000091000000028000【解答】(1 )三元组表表示法i j v114 2221 6 -1532 2 1342 3 353 4 -665 1 9176 3 28(2)十字链表法:31142251f1r221323316-15A| A7.画出下列广义表的头尾表示存储结构示意图。(1) A=(a,b,c),d,(a,b,c)(2) B=(a,(b,(c,d),e),f)11-

30、11110a111A0f0c0d课后习题解答选择题1. 下列说法正确的是(C。A. 二叉树中任何一个结点的度都为2B. 二叉树的度为2C. 一棵二叉树的度可小于 2D. 任何一棵二叉树中至少有一个结点的度为22. 以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中(n0),空链域的个数为（C）。A.3 .A.C.4 .2n-1 B . n-1 C线索化二叉树中，某结点BDp-lchild=NULLp_ltag=0如果结点3 B .某二叉树.n+1 D . 2n+1*p没有孩子的充要条件是（B）。.p-ltag=1 且 p-rtag=1.p-lchild=NULL 且 p-ltag=1A

31、有3个兄弟，而且B是A的双亲，则B的度是（B）。4 C . 5 D . 1T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为,而v的右子 * v左子树上结点的最大编号加1,这是按（ B）编号的。B.先序遍历序列 C .后序遍历序列D .层次顺序B是由F转换得到的二叉树，F中有n个非终端结点,B中右指针A.5 .1,2,.n 树的结点中，其最小编号等于A.中序遍历序列I6. 设F是一个森林， 域为空的结点有（0个。A. n-1 B . n7. 一棵完全二叉树上有A. 500 B . 501 C&设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为 森林F对应的二叉树根结点的右子树上

32、的结点个数是（A. N1 B . N1+N2 C . N29.任何一棵二叉树的叶结点在先序、A.不发生改变B .发生改变10 .若一棵二叉树的后序遍历序列为 为（D）。A. cbed B . decab C11.若一棵二叉树的先序遍历序列为 遍历的结果为（D）。A. gcefha B . gdbecfha C12 . 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。且有如下性质:T中任意结点v,其编号等于左子树上的最小编号减1n+11001个结点，其中叶子结点的个数是（.490 D.495D）。0。N1, N2 和 N3。与D . N2+N3中序、后序遍历序列中的相对次

33、序（C .不能确定D .以上都不对dabec,中序遍历序列为 debac，则先序遍历序列A）。.deabc D abdgcefh ,bdgaechf.cedba中序遍历的序列为dgbaechf，则后序D . gdbehfca（B）。A.所有的结点均无左孩子BC.只有一个叶子结点D13 .引入线索二叉树的目的是（.所有的结点均无右孩子.是一棵满二叉树A）。A.B.C.D.加快查找结点的前驱或后继的速度 为了能在二叉树中方便的进行插入与删除 为了能方便的找到双亲 使二叉树的遍历结果唯一14 .设高度为 数至少为（B）。A. 2*h B15 . 一个具有A. 9 Bh的二叉树上只有度为0和度为2的结

34、点,2*h+1 D567个结点的二叉树的高 h为（D）。.9至566之间 D2*h-1 C.10 C则此类二叉树中所包含的结点.h+1.10至567之间6,DOO7, 9，与该整数集合对应的哈夫曼树是（CO16 .给一个整数集合3 , 5,A.B .B）。9ABCDEFAAAGAAH（图1）判断题1二叉树是树的特殊形式。（V）2. 由树转换成二叉树，其根结点的右子树总是空的。（V）3. 先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不同。（X）4. 先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。（X）5. 完全二叉树中，若一个结点没有左孩子，则它必是叶子。（V）6. 对于有N个结

35、点的二叉树，其高度为log 2N + 1。（X）7. 若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。（V）&若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后 序遍历序列中的第一个结点。（V）9. 不使用递归也可实现二叉树的先序、中序和后序遍历。（V）10. 先序遍历二叉树的序列中， 任何结点的子树的所有结点不一定跟在该结点之后。（X）11. 先序和中序遍历用线索树方式存储的二叉树，不必使用栈。（X）12. 在后序线索二叉树中，在任何情况下都能够很方便地找到任意结点的后继。（X）13. 哈夫曼树是带权路径长度最短的树

36、，路径上权值较大的结点离根较近。（V）14. 在哈夫曼编码中，出现频率相同的字符编码长度也一定相同。（X）15. 用一维数组存放二叉树时，总是以先序遍历存储结点。（X）16. 由先序序列和后序序列能唯一确定一棵二叉树。（X）17. 由先序序列和中序序列能唯一确定一棵二叉树。（V）18. 对一棵二叉树进行层次遍历时，应借助于一个栈。（X）19. 完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。（X）20. 满二叉树一定是完全二叉树，反之未必。（V）简答题1. 一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别?【解答】二叉树是有序树，度为2的树是无序树，二叉树的度不一定是2。二

37、叉树是有序树， 每个结点最多有两棵子树， 树是无序树，且每个结点可以有多棵子 树。2. 对于图1所示二叉树，试给出：（1）它的顺序存储结构示意图；（2）它的二叉链表存储结构示意图;（3）它的三叉链表存储结构示意图。 【解答】（1 ）顺序存储结构示意图：(2)二叉链表存储结构示意图:(3)三叉链表存储结构示意图:、g/人 HT3.对于图2所示的树，试给出：(1) 双亲数组表示法示意图；(2) 孩子链表表示法示意图；(3) 孩子兄弟链表表示法示意图。【解答】(1)双亲数组表示法示意图：(2)孩子链表表示法示意图:FJ（图2）0A-11B02C03D24E25F16G17H58I29J410K411

38、M312N8(3) 孩子兄弟链表表示法示意图:4画出图3所示的森林经转换后所对应的二叉树，并指出森林中满足什么条件的结点 在二叉树中是叶子。J【解答】ABFCGEJDHIF森林CAFBGD（图3）GE H在二叉树中某结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有孩 子也没有右兄弟结点。5.将题5图所示的二叉树转换成相应的森林。1的哈夫曼树中不存在度为 1的结点。哈夫曼树的每一分支结点都是由两棵子树合并产生1的结点。2n 1个结点。6证明：在结点数多于证明：由哈夫曼树的构造过程可知，的新结点，其度必为 2,所以哈夫曼树中不存在度为7.证明：若哈夫曼树中有 n个叶结点，则树中共有证明

39、：n个叶结点，需经n-1次合并形成哈夫曼树，而每次合并产生一个分支结点，所 以树中共有2n-1个结点。&证明：由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。证明：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因 为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设I个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根一左子树一右子树”的顺序，则由从第二元素开始的I个结点序列和中序序列根左边的I个结点序列构造左子树，由前序序列最后r个兀素序列与中序序列根右边的 r个元素序列构造

40、右子树。9. 已知一棵度为 m的树中有ni个度为1的结点，n2个度为2的结点，nm个度为 m的结点，问该树中共有多少个叶子结点？有多少个非终端结点？解：设树中共有n个结点，no个叶结点，那么n=no+n i+nm树中除根结点外，每个结点对应着一个分支，而度为k的结点发出k个分支，所以：n=n计 2* n2+m* nm+1(2)由(1)、(2)可知 no= n 2+2*ns+3*n4+(m-1)*n m+110. 在具有n (n1)个结点的树中，深度最小的那棵树其深度是多少？它共有多少叶 子和非叶子结点？深度最大的那棵树其深度是多少？它共有多少叶子和非叶子结点？2; n-1; 1; n; 1,

41、n-111. 设高度为h的二叉树上只有度为 0和度为2的结点，问该二叉树的结点数可能达到 的最大值和最小值。最大值：2h-1 ; 最小值：2h-112. 求表达式：a + b*(c d) e/f的波兰式(前缀式)和逆波兰式(后缀式) 。波兰式：-+ a * b - c d / e f逆波兰式：a b c d - * + e f / -13. 画出和下列已知序列对应的树T：树的先根次序访问序列为：GFKDAIEBCHJ树的后根访问次序为：DIAEKFCJHBG【解答】对应的二叉树和树分别如下左、右图所示：14. 画出和下列已知序列对应的森林F：森林的先根次序访问序列为：ABCDEFGHIJKL森

42、林的后根访问次序为：CBEFDGAJIKLH15. 画出和下列已知序列对应的树T：二叉树的层次访问序列为：ABCDEFGHIJ二叉树的中序访问次序为：DBGEHJACIF【解答】按层次遍历，第一个结点(若树不空)为根，该结点在中序序列中把序列分成左右两部分一左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子树为空， 则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。16.假设用于通信的电文由字符集a,b,c,d,e,f,g中的字母构成。它们在电文中出现的频度分别为,(1) 为这7个字母设计哈夫曼编码。(

43、2) 对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？(1)哈夫曼树:a： 10b： 110c： 010d: 1110e： 011f: 00g： 1111(2)对这7个字母进行等长编码，至少需要3位二进制数。等长编码的平均长度：*3+*3+*3+*3+*3+*3+*3=3哈夫曼编码：*2+*3+*3+*4+*3+*2+*4=哈夫曼编码比等长编码使电文总长压缩了：1 - 3=%算法设计题1. 给定一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树结点的数目的算法。【提示】采用递归算法实现。二叉树结点的数目=.1I左子树结点数目+右子树结点数目+

44、1当二叉树为空当二叉树非空int coun t(BiTree root) if (root=NULL)return (0);elseretur n (co un t(root-lchild)+co un t(root-rchild)+1);2. 请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按Ichild-rchild方式存储，链接时用叶结点的rchild域存放链指针。【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各个叶子结点，因为不论前序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是相同的，即都是从左至右。而题目要求是将二叉树中的叶子结点按

45、从左至右顺序建立一个单链表, 遍历中的任意一种方法遍历。这里使用中序递归遍历。设置前驱结点指针第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的因此，可以采用三种pre ,初始为空。rchild 指针指向它,最后叶子结点的rchild 为空。LinkList head,pre=NULL;/* 全局变量 */Lin kList In Order(BiTree T)/*中序遍历二叉树T,将叶子结点从左到右链成一个单链表，表头指针为head*/ if(T) In Order(T-lchild);*/if (T-lchild=NULL & T-rchild=NULL) if (pre=N

46、ULL) head=T; pre=T; else pre-rchild=T;pre=T; In Order(T-rchild);pre-rchild=NULL ; return(head);3 给定一棵用二叉链表表示的二叉树，其根指针为 法。【提示】采取递归算法。int Height(BiTree root) int hl,hr;if (root=NULL) return(O); else hl=Height(root-lchild);hr=Height(root-rchild);if (hlhr) return (hl+1); else return(hr+1);4.给定一棵用二叉链表表示的

47、二叉树，其根指针为 【提示】采用先序递归遍历算法实现。/*中序遍历左子树/*当前是叶子结点*/*处理第一个叶子结点*/*将叶子结点链入链表*/*中序遍历右子树*/*设置链表尾结点*/root，试写出求二叉树的深度的算root，试求二叉树各结点的层数。二叉树结点的层次数=其双亲结点的层次数+1当结点为根结点当结点非根结点void fun (BiTree root, int n) if (t=NULL) return;else printf( “ d ,n);fun( root-lchild, n+1);fun( root-rchild ,n+1);5给定一棵用二叉链表表示的二叉树，其根指针为ro

48、ot ，试写出将二叉树中所有结点的左、右子树相互交换的算法。【提示】设 root 为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算可基于 后序遍历实现： 交换左子树上各结点的左右子树； 交换左子树上各结点的左右子树； 再交换 根结点的左右子树。void Exchange(BiTree root) BiTNode *p;if (root) Exchange(root-lchild);Exchange(root-rchild);p=root-lchild;root-lchild=root-rchild;root-rchild=p;6一棵具有 n 个结点的完全二叉树采用顺序结构存储，试设计非递归算法对其进行先 序遍历。【提示】 二叉树的顺序存储是按完全二叉树的顺序存