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

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

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

3、量封装成一个构造体，因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，假设有，那么根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，也可以从上下标端开始一边比较，一边移位然后插入x ，最后修改表示表长的变量。int insert (datatype A,int *elenum,datatype x)/* 设 elenum 为表的最大下标*/if (*elenum=arrsize-1)return 0;/* 表已满，无法插入*/else i=*elenum;while (i=0 & Aix)/* 边找位置边移动*/Ai+1=Ai;i-;专业资料

4、整理WORD格式Ai+1=x;(*elenum)+;return 1;时间复杂度为O(n) 。/* 找到的位置是插入位的下一位*/* 插入成功 */专业资料整理WORD格式2一顺序表 A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值一样的元素。【提示】 对顺序表 A ，从第一个元素开场，查找其后与之值一样的所有元素，将它们删除；再对第二个元素做同样处理，依此类推。专业资料整理WORD格式void delete(Seqlist *A)i=0;while(ilast)/* 将第 i 个元素以后与其值一样的元素删除专业资料整理WORD格式*/专业资料整理WORD格式k=i+1;while

5、(klast&A-datai=A-datak)k+;n=k-i-1;for(j=k;jlast;j+)A-dataj-n=A-dataj;A-last= A-last -n;i+;/* 使 k 指向第一个与Ai 不同的元素 */ /*n 表示要删除元素的个数 */* 删除多余元素 */专业资料整理WORD格式3写一个算法，从一个给定的顺序表A 中删除值在xy(xdatai 是否介于x 和 y 之间，假设是，并不立即删除，而是用n 记录删除时应前移元素的位移量；假设不是，那么将A-datai 向前移动 n 位。 n 用来记录当前已删除元素的个数。void delete(Seqlist *A,in

6、t x,int y)i=0;n=0;while (ilast)if (A-datai=x & A-dataidatai介于 x 和 y 之间， n 自增 */elseA-datai-n=A-datai;/* 否那么向前移动A-datai*/i+;A-last-=n;4线性表中有n 个元素，每个元素是一个字符，现存于向量Rn 中，试写一算法，使R 中的字符按字母字符、 数字字符和其它字符的顺序排列。 要求利用原来的存储空间， 元素移动次数最小。【提示】 对线性表进展两次扫描， 第一次将所有的字母放在前面， 第二次将所有的数字放在字母之后，其它字符之前。专业资料整理WORD格式int fch(ch

7、ar c)if(c=a&c=A&c=0&c=9)return (1);/* 判断 c 是否数字 */专业资料整理WORD格式elsereturn (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(lowhi

8、gh&!fnum(Rhigh) high-; if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;/* 将字母放在前面*/* 将数字放在字母后面，其它字符前面*/专业资料整理WORD格式5线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m 个元素和后 n 个元素进展整体互换。即将线性表： a, , a改变为：, , b1, a2m, b1, b2n b1, b2, , nb , a1 , a2, , ma。【提示】 比较 m 和 n 的大小，假设 mn，那么将表中元素依次前移m 次；否那么 ,将表中元素依次后移 n 次。void process(Seq

9、list *L,int m,int n)if(m=n)for(i=1;idata0;for(k=1;klast;k+)L-datak-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;专业资料整理WORD格式L-data0=x;6带头结点的单链表L 中的结点是按整数值递增排列的，试写一算法， 将值为 x 的结点插入到表L 中，使得 L 仍然递增有序，并且分析算法的时间复杂度。专业资料整理WORD格式LinkList insert(LinkList L, int

10、x)p=L;while(p-next & xp-next-data)p=p-next;s=(LNode *)malloc(sizeof(LNode);s-data=x;s-next=p-next;p-next=s;return(L);/* 寻找插入位置*/* 申请结点空间*/* 填装结点 */* 将结点插入到链表中*/专业资料整理WORD格式7假设有两个已排序递增的单链表A 和 B，编写算法将它们合并成一个链表C 而不改变其排序性。LinkList Combine(LinkList A, LinkList B)C=A;rc=C;pa=A-next;/*pa 指向表 A 的第一个结点 */pb=

11、B-next;/*pb 指向表 B 的第一个结点*/free(B);/* 释放 B 的头结点 */while (pa & pb)/* 将 pa、pb 所指向结点中，值较小的一个插入到链表C 的表尾 */if(pa-datadata)rc-next=pa;rc=pa;pa=pa-next;elserc-next=pb;rc=pb;pb=pb-next;if(pa)rc-next=pa;elserc-next=pb;/* 将链表 A 或 B 中剩余的局部到链表C 的表尾 */return(C);8假设长度大于1 的循环单链表中，既无头结点也无头指针，p 为指向该链表中某一结点的指针，编写算法删除该

12、结点的前驱结点。【提示】 利用循环单链表的特点，通过s 指针可循环找到其前驱结点p 及 p 的前驱结点q，然后可删除结点* p。viod delepre(LNode *s)LNode* p, *q;专业资料整理WORD格式p=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 中

13、的当前结点，指针q 用来指向 B 中的当前结点，将其值进展比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，继续后面的比较。LinkList Intersect(LinkList A, LinkList B)LNode * 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;elseif (p-data=q-data)s=(LNode *)malloc(sizeof(LNode);s

14、-data=p-data;r-next=s;r=s;p=p-next;q=q-next;elseq=q-next;r-next=NULL;C=C-next;return C;10设有一个双向链表，每个结点中除有prior 、 data 和 next 域外，还有一个访问频度freq 域，在链表被起用之前， 该域的值初始化为零。 每当在链表进展一次 Locata(L,x) 运算后，令值为 x 的结点中的 freq 域增 1，并调整表中结点的次序， 使其按访问频度的非递增序列排列，以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的Locata(L,x) 算法。【提示】 在定位操作的同时，需要调

15、整链表中结点的次序：每次进展定位操作后，要查看所查找结点的freq 域，将其同前面结点的freq 域进展比较，同时进展结点次序的调整。typedef struct dnode专业资料整理WORD格式datatype data;int freq;struct 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-fr

16、eqfreq)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);/* 查找值为 x 的结点，使p 指向它 */* 假设查找失败，返回空指针*/* 修改 p 的 freq 域 */* 调整结点的次序*/* 返回找到的结点的地址*/专业资料整理WORD格式3.3 课后习题解答#3.3.1 选择题1向一个栈顶指针为Top 的链栈中插入一个 p 所指结点时，其操作步骤为C。A Top-next=p;B p-next=Top-next;To

17、p-next=p;C p-next=Top;Top=p;D p-next=Top;Top=Top-next;2对于栈操作数据的原那么是B。A 先进先出B后进先出C后进后出D不分顺序3假设一个栈的入栈序列是1,2,3, ，,n其输出序列为 p1,p2,p3， pN,假设 pN是 n，那么 pi是 D 。A iB n-iC n-i+1D 不确定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 的底在 S

18、m ，那么栈满的条件是 B。A top2-top1|=0B top1+1=top2Ctop1+top2=mD top1=top26一个栈的入栈序列是a,b,c,d,e，那么栈的不可能的输出序列是C。A edcbaB decbaC dceabD abcde专业资料整理WORD格式7在一个链队列中，假设 A f-next=r;f=s; Cs-next=r;r=s;f,r 分别为队首、队尾指针，那么插入s 所指结点的操作为B。B r-next=s;r=s;D s-next=f;f=s;专业资料整理WORD格式8用不带头结点的单链表存储队列时，在进展删除运算时D。专业资料整理WORD格式A 仅修改头指

19、针B 仅修改尾指针C头、尾指针都要修改D 头、尾指针可能都要修改9递归过程或函数调用时，处理参数及返回地址，要用一种称为C的数据构造。A 队列B 静态链表C栈D顺序表10栈和队都是 C。A 顺序存储的线性构造B 链式存储的非线性构造C限制存取点的线性构造D 限制存取点的非线性构造3.3.2 判断题1栈和队列的存储，既可以采用顺序存储构造，又可以采用链式存储构造。2任何一个递归过程都可以转换成非递归过程。3假设输入序列为1,2,3,4,5,6，那么通过一个栈可以输出序列3,2,5,6,4,1。4通常使用队列来处理函数的调用。5循环队列通常用指针来实现队列的头尾相接。3.3.3 简答题1循环队列的

20、优点是什么？如何判别它的空和满？循环队列的优点是能够抑制“假溢满现象。设有循环队列sq，队满的判别条件为：（ sq-rear+1 %maxsize=sq-front; 或 sq-num=maxsize 。队空的判别条件为：sq-rear=sq-front 。2栈和队列数据构造各有什么特点，什么情况下用到栈，什么情况下用到队列？栈和队列都是操作受限的线性表， 栈的运算规那么是 “后进先出 ，队列的运算规那么是 “先进先出。栈的应用如数制转换、递归算法的实现等，队列的应用如树的层次遍历等。3什么是递归？递归程序有什么优缺点？一个函数在完毕本函数之前，直接或间接调用函数自身，称为递归。例如，函数f

21、在执行中，又调用函数f 自身，这称为直接递归；假设函数f 在执行中，调用函数g，而 g 在执行中，又调用函数f，这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。递归程序的优点是程序构造简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。4设有编号为1,2,3,4 的四辆车，顺序进入一个栈式构造的站台，试写出这四辆车开出车站的所有可能的顺序每辆车可能入站，可能不入站，时间也可能不等。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,43214.3 课后习题解答 #4.3.1 选择题1下面关于

22、串的表达错误的选项是C。A 串是字符的有限序列B串既可以采用顺序存储，也可以采用链式存储C空串是由空格构成的串D模式匹配是串的一种重要运算2串的长度是指B 。A 串中所含不同字母的个数B串中所含字符的个数专业资料整理WORD格式C串中所含不同字符的个数D串中所含非空格字符的个数3串S=aaab ,其 Next 数组值为 A。A 0123B 1123C 1231D 12114二维数组M 的成员是6 个字符每个字符占一个存储单元组成的串，行下标X围从 0 到 8，列下标 j 的X围从1 到 10，那么存放 M 至少需要 D个字节； M 的第第 5 行共占 A 个字节；假设M 按行优先方式存储，元素

23、M85 的起始地址与当M先方式存储时的C元素的起始地址一致。 1A 90B 180C240D 5402A 108B114C54D60 3A M85B M310CM58D M09i 的8 列和按列优专业资料整理WORD格式5数组 A 中，每个元素的存储占从首地址SA 开场连续存放在存储器内，按行存放，元素A85 的起始地址是B 。1A 80B100 2A SA+141B SA+144 3A SA+141B SA+1803 个单元，行下标i 从 1 到 8，列下标j 从 1 到 10，存放该数组至少需要的单元个数是C，假设该数组D，假设该数组按列存放，元素A85 的起始地址是C 240D 270C

24、 SA+222D SA+225C SA+117D SA+225专业资料整理WORD格式6稀疏矩阵采用压缩存储，一般有C两种方法。A 二维数组和三维数组B三元组和散列C三元组表和十字链表D散列和十字链表4.3.2 判断题专业资料整理WORD格式1串相等是指两个串的长度相等。2 KMP 算法的特点是在模式匹配时指示主串的指针不会变小。专业资料整理WORD格式3稀疏矩阵压缩存储后，必会失去随机存取功能。4数组是线性构造的一种推广，因此与线性表一样，可以对它进展插入，删除等操作。5假设采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。 6假设一个广义表的表头为空表，那

25、么此广义表亦为空表。7所谓取广义表的表尾就是返回广义表中最后一个元素。4.3.3 简答题1 KMP 算法较朴素的模式匹配算法有哪些改进KMP 算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生局部匹配时， KMP 算法的优点更为突出。2设字符串S= aabaabaabaac， P= aabaac。专业资料整理WORD格式 1给出 S 和 P 的 next 值和 nextval 值； 2假设 S 作主串， P 作模式串，试给出利用KMP 算法的匹配过程。【解答】专业资料整理WORD格式（ 1S 的 next 与 nextval 值分别为 012123456789 和 002002

26、002021，p 的 next 与 nextval专业资料整理WORD格式值分别为012123 和 002003 。专业资料整理WORD格式 2利用 BF 算法的匹配过程：第一趟匹配：aabaabaabaac利用 KMP第一趟匹配：算法的匹配过程：aabaabaabaac专业资料整理WORD格式aabaac(i=6,j=6)aabaac(i=6,j=6)专业资料整理WORD格式第二趟匹配：aabaabaabaac第二趟匹配：aabaabaabaacaa(i=3,j=2)(aa)baac第三趟匹配：aabaabaabaac第三趟匹配： aabaabaabaaca(i=3,j=1)(成功 ) (a

27、a)baac第四趟匹配： aabaabaabaacaabaac(i=9,j=6)第五趟匹配： aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配： aabaabaabaac( 成功 )aabaac(i=13,j=7)3假设按行优先存储整数数组A9358时，第一个元素的字节地址是100，每个整数占个字节。问以下元素的存储地址是什么？(1) a0000(2)a1111(3)a3125(4)a8247【解答】 (1) LOC( a 0000)= 100(2) LOC( a 1111)=100+(3*5*8*1+5*8*1+8*1+1)*4

28、=776(3) 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假设一个准对角矩阵：a11a12a21a22a33a34a43a44.aija2m-1,2m-1a2m-1,2ma2m,2m-1a2m,2m专业资料整理WORD格式按以下方式存储于一维数组B4m 中 m 为一个整数：0123456ka 11a 12a21a22a33a34a43aij4m-14ma2m-1,2ma2m,2m-1a2m,2m专业资料整理WORD格式写出下标转换函数k=f(

29、i,j) 。【解答】由题目可知，每一行有两个非0 元素。当 i 为奇数时，第 i 行的元素为： ai,i、 ai,(i+1)，此时 k=2*(i-1)+j-i=i+j-2当 i 为偶数时，第 i 行的元素为： ai,(i-1)、 ai,i，此时 k=2*(i-1)+j-I+1=i+j-1 综上所述， k=i+j-i%2-1 。5设有 nn 的带宽为 3 的带状矩阵 A ，将其 3 条对角线上的元素存于数组 B3n 中，使得元素 Buv=a ij，试推导出从 i,j 到 (u,v) 的下标变换公式。【解答】u=j-i+1v=j-1专业资料整理WORD格式6现有如下的稀疏矩阵A 如下列图，要求画出

30、以下各种表示方法。（ 1三元组表表示法（ 2十字链表法。000220-150133000000-60000000091000000028000【解答】1三元组表表示法:ijv1 14222 1 6-15322134233534-665191763282十字链表法：0123450142216 -1512213233234-63519146328专业资料整理WORD格式5专业资料整理WORD格式7画出以下广义表的头尾表示存储构造示意图。（ 1A=(a,b,c),d,(a,b,c)（ 2B=(a,(b,(c,d),e),f)（ 11111111 d0 a1 b1c（ 21110a1110f0 b11

31、0 c0 c0d5.3 课后习题解答5.3.1 选择题专业资料整理WORD格式1以下说法正确的选项是C。A 二叉树中任何一个结点的度都为2B二叉树的度为2C一棵二叉树的度可小于2D任何一棵二叉树中至少有一个结点的度为2专业资料整理WORD格式2以二叉链表作为二叉树的存储构造，在具有的个数为 C。n 个结点的二叉链表中n0 ，空链域专业资料整理WORD格式A 2n-1B n-1Cn+1D 2n+1专业资料整理WORD格式3线索化二叉树中，某结点 A p-lchild=NULL Cp-ltag=0*p 没有孩子的充要条件是B。B p-ltag=1 且 p-rtag=1D p-lchild=NULL

32、且 p-ltag=1专业资料整理WORD格式4如果结点A 有 3 个兄弟 ,而且 B 是 A 的双亲 ,那么 B 的度是 B 。A3B4C5D15某二叉树 T 有 n 个结点 ,设按某种顺序对T 中的每个结点进展编号，编号值为1,2,.n。且有如下性质 :T 中任意结点v,其编号等于左子树上的最小编号减,而 v 的右子树的结点中,其最小编号等于v 左子树上结点的最大编号加，这是按B 编号的。A 中序遍历序列B 先序遍历序列C后序遍历序列D层次顺序6设 F 是一个森林，B 是由 F 转换得到的二叉树，F 中有 n 个非终端结点,B 中右指针域为空的结点有C个。专业资料整理WORD格式A n-1B

33、nCn+1D n+2专业资料整理WORD格式7一棵完全二叉树上有1001 个结点，其中叶子结点的个数是C。A 500B 501C 490D 4958设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为N1 ，N2 和 N3。与森林 F 对应的二叉树根结点的右子树上的结点个数是D。AN1B N1+N2CN2DN2+N39任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序A 。A 不发生改变B发生改变C不能确定D以上都不对10假设一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，那么先序遍历序列为D。A cbedB decabC deabcD cedba11假设一棵

34、二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，那么后序遍历的结果为 D 。A gcefhaBgdbecfhaC bdgaechfD gdbehfca12一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，那么该二叉树一定满足B 。A 所有的结点均无左孩子B 所有的结点均无右孩子C只有一个叶子结点D 是一棵满二叉树13引入线索二叉树的目的是A。A 加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进展插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一14设高度为h 的二叉树上只有度为和度为的结点，那么此类二叉树中所包含的结点数至少为 B 。A 2*hB 2*

35、h-1C 2*h+1D h+115一个具有567 个结点的二叉树的高h 为 D。A9B10C9 至 566 之间D10 至 567 之间16给一个整数集合3 ， 5， 6， 7， 9 ，与该整数集合对应的哈夫曼树是B。ABCD专业资料整理WORD格式399专业资料整理WORD格式59767专业资料整理WORD格式63563567专业资料整理WORD格式7935专业资料整理WORD格式5.3.2 判断题1二叉树是树的特殊形式。2由树转换成二叉树，其根结点的右子树总是空的。3先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不同。4先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。5完全二叉

36、树中，假设一个结点没有左孩子，那么它必是叶子。6对于有N 个结点的二叉树，其高度为log 2N 1。7假设一个结点是某二叉树子树的中序遍历序列中的最后一个结点，那么它必是该子树的专业资料整理WORD格式先序遍历序列中的最后一个结点。8假设一个结点是某二叉树子树的中序遍历序列中的第一个结点，那么它必是该子树的后序遍历序列中的第一个结点。 9不使用递归也可实现二叉树的先序、中序和后序遍历。10先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。11先序和中序遍历用线索树方式存储的二叉树，不必使用栈。12在后序线索二叉树中，在任何情况下都能够很方便地找到任意结点的后继。13哈夫曼树

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

38、树， 树是无序树， 且每个结点可以有多棵子树。A2对于图 1 所示二叉树，试给出： 1它的顺序存储构造示意图；BC 2它的二叉链表存储构造示意图； 3它的三叉链表存储构造示意图。DEF【解答】1顺序存储构造示意图：专业资料整理WORD格式ABCDEFGHGH(图1)专业资料整理WORD格式2二叉链表存储构造示意图：3三叉链表存储构造示意图：AABC C B D EF D E F G H G H 专业资料整理WORD格式3对于图2 所示的树，试给出：（ 1双亲数组表示法示意图；（ 2孩子链表表示法示意图；（ 3孩子兄弟链表表示法示意图。【解答】（ 1双亲数组表示法示意图：2孩子链表表示法示意图：

39、ABCGFEDIHJKMN (图 2)专业资料整理WORD格式0A-10A11B01B52C02C33D23D114E24E95F15F76G16G7H57H8I28I129J49J10K410K11M311M12N812N 3孩子兄弟链表表示法示意图：ABCGFED2 64810I专业资料整理WORD格式HJKMN4画出图 3 所示的森林经转换后所对应的二叉树，并指出森林中满足什么条件的结点在二叉树中是叶子。AFJBCDGEHI(图 3)【解答】ABFECGJDH专业资料整理WORD格式I专业资料整理WORD格式在二叉树中某结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有孩子也没有右兄弟结点。5将题 5 图所示的二叉树转换成相应的森林。ABCDEFG H(题5图)【解答】 森林：专业资料整理WORD格式AC专业资料整理WORD格式BEHF专业资料整理WORD格式DG6证明：在结点数多于1 的哈夫曼树中不存在度为1 的结点。证明：由哈夫曼树的构造过程可知，哈夫曼树的每一分支结点都是由两棵子