数据结构课后习题答案及解析

1、.WORD完美格式.专业知识编辑整理第六章树和二叉树(下载后用阅读版式视图或web版式可以看清)、选择题14.5.有一“遗传”关系：设A.向量B.树.树最合适用来表示(A.有序数据元素C无序数据元素.树B的层号表示为la , 2b,A. la (2b (3d,3e),2c)C. a(b(d,e),c)高度为h的完全二叉树至少有A. 2h_lB.h在一棵完全二叉树中，若编号为A. 2iB. 2i-lx是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为(C图D.二叉树B元素之间具有分支层次关系的数据D. 一3d,兀素之间无联系的数据3e, 2c,对应于下面选择的(B. a(b

2、(D,e),c)D. a(b,d(e),c)个结点，至多有()个结点。2h-1 D. 2hf的结点存在右孩子，则右子结点的编号为 (C. 2i+lD. 2i+26.7.8.9.一棵二叉树的广义表表示为a(b(c) , d(e( , g(h) , f)，则该二叉树的高度为 (A.3B.4C.5D.6深度为5的二叉树至多有()个结点。A. 31B. 32C. 16假定在一棵二叉树中，双分支结点数为A. 15B. 16C. 17题图6-1中，()是完全二叉树，(D. 1015,单分支结点数为 30个，则叶子结点数为()个。D. 47)是满二叉树。A.AS 6-110.在题图6-2所示的二叉树中:(1

3、)A结点是A.叶结点B根结点但不是分支结点C根结点也是分支结点D.分支结点但不是根结点(2)J结点是A.叶结点B.根结点但不是分支结点C根结点也是分支结点D.分支结点但不是根结点F结点的兄弟结点是A.EB.DC .空D.I(4)F结点的双亲结点是A.AB.BC.CD.D树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.411. 在一棵具有35个结点的完全二叉树中，该树的深度为（）。A.5B.6C.7D.812. 一棵有124个叶结点的完全二叉树，最多有 （）个结点。A. 247B. 248C. 249D. 25013. 用

4、顺序存储的方法将完全二叉树中所有结点逐层存放在数组R1n中，结点Ri若有左子树，则左子树是结点（）。A. R2i+IB. R2iC.Ri/2D. R2i-114. 在一非空二叉树的中序遍历序列中，根结点的右边（）。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点15 .一棵度为m的树中，有m个度为1的结点，有n2个度为2的结点，有nm个度为m的结点，则该树的叶结点数为（）。A. n 1+n2+.+n mB. （m-l） nm+.+n 2+1C.n计n2+1D. n l-n216. 已知某二叉树的中序遍历序列是debac，后序遍历序列是 d

5、abec,它的前序遍历序列是（）。A.acbedB. decabC. deabcD. cedba17. 在一棵二叉树的二叉链表中，空指针域等于所有非空指针域数加（）。A.2B.1C.0D.-118. 线索二叉树是一种（）结构。A.逻辑B .逻辑和存储 C .物理D.线性19. 由权值分别是8, 7, 2, 5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A. 23B. 37C. 46D. 4320. 设T是哈夫曼树，具有 5个叶结点，树T的高度最高可以是（）。A.2B.3C.4D.5、填空题1. 对于一棵具有n个结点的树，该树中所有结点的度数之和为 。2. 在树型结构中，树根结点没有 结

6、点，其余每个结点有且只有 个前驱结点：叶子结点没有 结点，其余每个结点可以有 后继结点。3. 有一棵树如题图6-3所示，回答下面的问题。这棵树的根点是 ;叶子结点是 ;结点k3的度是;结点k3的子女是;结点k3的父结点是 ;这棵树的度为 ;这棵树的深度是4假定一棵树的广义表表示为A(B(E) , C(F(H , I , J , G), D)，则该树的度为 ，树的深度为 ，终端结点的个数为 ，单分支结点的个数为，双分支结点的个数为 ，3分支结点的个数为 ，C结点的双亲结点为 ，其孩子结点为 。5. 一棵深度为h的满k叉树有如下性质：第 h层上的结点都是叶子结点，其余各层上的每个结点都有k棵非空子

7、树。如果按层次顺序(同层自左至右)从 1开始对全部结点编号，则：(1) 第i层结点数目是。(2) 编号为n的结点的双亲结点(若存在)的编号是_。(3) 编号为n的结点的第i个孩子结点(若存在)的编号是 _。(4) 编号为n的结点有右兄弟的条件是 :其右兄弟的编号是 。6. 前序遍历一棵树相当于 树中对应的二叉树，后序遍历一棵树则相当于树中对应的二叉树。7 .二叉树的遍历分为 ，树与森林的遍历包括 。&一棵二叉树的第i(i=1)层最多有个结点；一棵有n(n0)个结点的满二叉树共有 个叶子和 个非终端结点。9. 在一棵二叉树中，假定双分支结点数为5个，单分支结点数为 6个，则叶子结点为 个。10

8、在一棵二叉树中，第五层上的结点数最多为 。11. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为个，其中 个用于链接孩子结点， 个空闲着。12. 前序遍历的顺序是 ABDGEHICF,则二叉树的根是。13. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是14. 结点最少的树为，结点最少的二叉树为。15. 一棵完全二叉树按层次遍历的序列为ABCDEFGHI则在前序遍历中结点 E的直接前驱为 ，后序遍历中结点 B的直接后继是 。16. 某二叉树的中序遍历序列为ABCDEFG后序序列为BDCAFGE则该二叉树结点的前序序列为 ，该二叉树对应的森

9、林包括 棵树。17. 用一维数组存放的一棵完全二叉树如题图6-4所示。1 2456780 | 21 HCDEFG讣K L剧图6-4则后序遍历该二叉树时结点访问的顺序为 。18. 由n个权值构成的哈夫曼树共有 个结点。19. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为 。20. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则 B中右指针域为空的结点有 个。21. 二叉树的存储结构分为，树的存储结构分为。三、判断题1 树中任意结点的子树不必是有序的。（）2. 树可以看成特殊的无向图。（）3. 可以使用双链表表示树型结构。（）4 顺序存储方式只能用

10、于存储线性结构。（）5. 完全二叉树的某结点若无左孩子，则必是叶结点。（）6. 在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。（）7. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树。（）&二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。（）9. 二叉树的前序和后序遍历序列能惟一确定这棵二叉树。（）10. 中序线索二叉树中，右线索若不为空，则一定指向其父结点。（）四、算法和操作题1. 假定一棵二叉树广义表表示为a（b（c） , d（e, D），分别写出对它进行前序、中序、后序遍历的结果。前序：中序：后序：2. 已知一棵二叉树的中序和后序序列，求该二叉树

11、的高度和双支、单支及叶子结点数。中根序列：c, b, d, e, a, g, i,h,j , f 后根序列：c, e, d, b, i , j , h, g, fa 高度：双支：单支：叶子：3. 已知一棵树边的集合为 l, I , E I , B, B D, A B, G J , G K , C G, C F , H L , C H, A C）,请画出这棵树,并回答下列问题：(1) 哪个是根结点？哪些是叶子结点?(3)哪个是结点G的双亲? 哪些是结点G的祖先?(5) 哪些是结点G的孩子?(6) 哪些是结点E的子孙? 哪些是结点E的兄弟？哪些是结点 F的兄弟?(8) 结点B和N的层次号分别是什么

12、？(9) 树的深度是多少?(10) 以结点C为根的子树的深度是多少？4 将算术表达式(a+b)+c*(d+e)+f*(g+h)转化为二叉树。BT中，如题表6-1所示。画出该二叉树的链接表示形式。数组BT的存放形式是相对于满二叉5. 一棵二叉树的结点数据采用顺序存储结构，存储于数组树中编号为数组下标值的结点值。若该结点不存在，则取0值。123456； 781011121314151617 1819 afdcJIhlb6 假设前序遍历某棵树的结点次序为SACEFBDGHIJK后序遍历该树的结点次序为CFEABHGIKJDS请画出这棵树。7. 已知一棵树如题图 6-5所示，将其转换为其孩子兄弟表示的

13、二叉树。并画出该二叉树的后序线索二叉树。&试找出分别满足下列条件的所有二叉树:(1) 前序遍历序列和中序遍历序列相同。(2) 中序遍历序列和后序遍历序列相同。(3) 前序遍历序列和后序遍历序列相同。9 .已知信息为“ ABCD BCD CB DB AC”，请按此信息构造哈夫曼树，求出每一字符的最优编码。10.己知中序线索二叉树采用二叉链表存储结构，链结点的构造为：1吨lihiM |ahi Idrug其中若Itag为0,则Ichild指向结点的前驱，否则Ichild指向左孩子结点；若 rtag为0，则rchild 指向结点的后继，否则 rchild指向右孩子结点。下面的算法返回x所指结点的直接后

14、继结点的位置。若该算法有错，则请改正错误；若无错，请写“正确”二字。BiTree INSUCC (BiTree x) s=X-rchild;if ( s-rtag ) while ( s-ltag ) s=s-rchild;return s ； )五、算法设计题1 编写对二叉树进行中序遍历的非递归算法，并对算法执行题图6-6所示的二叉树的情况进行跟踪(即给出各阶段栈的变化及输出的结点序列)。栈已经定义：InitStack(S)(初始化)、Empty(S)(判栈空)、Push(S , p)(入栈)、Pop(S, p)(出栈)等操作。2假设在表示一棵二叉树的二叉链表上增加两个域：双亲域用于指示其双

15、亲结点，标志域flag (可取0.2 )的值，用以区分在遍历过程中到达该结点时继续向右或向左或访问该结点。试以此存储结构编写不用栈进行后序遍历的递归形式的算法。3棵具有n个结点的完全二叉树，以一维数组作为存储结构，试设计一个对该完全二叉树进行前序遍历的算法。4 设中序线索树的结点由5个域组成。Info :给出结点的数据域。LT:标志域，为0或1。LL :当LT为1时，给出该结点的左孩子的地址。当LT为0时，给出按中序遍历的前驱结点地址。RT:标志域，为0或1。RL :当RT为1时，给出该结点的右孩子的地址。 当RT 为O时，给出按中序遍历的后继结点地址。请编写 程序，在具有上述结点结构的中序线

16、索二叉树上，求某一结点p按后序遍历次序的后继结点的地址 q,设该中序线索二叉树的根结点地址为r。另外，请注意必须满足：(1) 额外空间的使用只能为 0(1)。(2) 程序为非递归形式。5 假设二叉树采用链接方法存储，编写一个函数按凹入表表示法打印出该二叉树。6. 给出中序线索树的结点结构，设计算法在不使用栈和递归的情况下前序遍历一棵中序线索树，并分析它的时间复杂度。7. 以二叉链表为存储结构，写出交换各结点左右子树的算法。&假设二叉树采用链接方法存储，编写一个函数按凹入表表示法打印出该二叉树。第六章树和二叉树 第6章树和二叉树 、选择题(参考答案)1 .B2.B3.C4.A,C5 . C6 .

17、C7.A8.B9.A,B10. (1)C(2)Ac(4)Ac(6)Ac11.B12.A13.B14 .A15 . B16.D17 .A18 .C19.D20 . D二、填空题(参考答案)1 .树的总结点数-1。2 .前驱：1,后继，任意多个。3. k i , k 2, k 4, k 5, k 7,2,k 5, k 6, k i ,3,4 。4.3 , 4, 6, 1, 1 , 2, A, F, G5.(1) k i-1 ,6 前序遍历，中序遍历。8. 2i-1,2/n ,2/n, n-l x k+n+1,(4)i 工 nk+l(n=0,l,2，),n+1.7 前序，中序，后序，前序，后序。9.

18、6 个。10. 16011.2n , n-l , n+l 。12 A13. 树可采用二叉树的存储结构并可利用二叉树的已有算法解决树的有关问题。14. 只有1个结点的树，空树。15.1 ，F。16. 前序遍历序列为：EACBDGF森林包括1棵树。17. HIDJKEBLFGCAO18. 2n-l 。19. 56020 n+l。21.顺序存储和链式存储，双亲链表表示法，孩子链表表示法，孩子兄弟链表表示法三、判断题1. V 2. V 3. V 4. X 5. V 6. X 7. x 8. V 9. x 10. x四、算法和操作题1 假设一棵二叉树广义表表示为a(b(c) , d(e , D),分别写

19、出对它进行前序、中序、后序遍历的结果。【解答】前序：a, b, c, d, e, D中序：c, b, a, e, d, D后序：c, b, e, D, d, a2 已知一棵二叉树的中序和后序序列，求该二叉树的高度和双支、单支及叶子结点数。【解答】中序序列：c, b, d, e, a, g, i , h, j , f后序序列：c, e, d, b, i , j , h , g , f, a由中序和后序(前序)遍历序列可惟一确定一棵二叉树，基本思想是后序(前序)定根，中序分左右。由后序序列可知该树的根结点为 该树的左子树为c , b , d , e,右子树为g , i , h , j , f);再

20、由后序序列可知该树的左子树的根结点为b,右子树的根结点为 f树为c,右子树为d, e);再由后序遍历序列可知右子树 d , e的根结点为d,再由中序遍历序列可知 d的左子树为空，右子树为 的分析。最后得到由中序和后序序列决定的二叉树为：a(b(c , d( , e) , f(g( , h(i , j),由此可知该树：高度：5双分支：3单分支：3叶结点：4。3 .已知一棵树边的集合为, , , , , ,H,并回答问题？a,由中序遍历序列可知 再由中序遍历序列可知 b结点的左子 e。对以f为根结点的子树可做类似, ，请画出这棵树,【解答】根据边集画出的树如下所示:(1)根结点是：A。(2)叶子结

21、点是:D, M N, F, J,K, L。(3) 结点G的双亲是(4) 结点G的祖先是(5) 结点G的孩子是(6) 结点E的子孙是(7) 结点E的兄弟是CoA, CoJ, KoI , M, NoD;结点F的兄弟是：G, Ho(8) 结点B和N的层次号分别是：2 , 5o(9) 树的深度是：5 o(10)以结点C为根的子树的深度是：3o4 将算术表达式(a+b)+c*(d+e)+f*(g+h)转化为二叉树。【解答】转化成如下二叉树:BT的存放形式是相对于满二叉树中编号为数组下标值的结点值。若该结点不存在，则取0值。5 -棵二叉树的结点数据采用顺序存储结构，存储于数组BT中，如题表6-1所示。画出

22、该二叉树的链接表示形式。数组题表6-141II11ItpI#Jlj1 Cf4hh【解答】二叉树的链式表示为:6 .若前序遍历某树的结点次序:CFEABHGIKJD,画出这棵树。【解答】画出树如下：SACEFBDGHIJK后序遍历的结点次序为:7 .将原教材题图6-5转换为孩子兄弟所表示的二叉树及该二叉树的后序线索二叉树如下:8 .空树满足所有条件。非空树如下：(1) 前序和中序遍历序列相同的二叉树是没有左子树的二叉树(右单支树)。(2) 中序和后序遍历序列相同的二叉树是没有右子树的二叉树(左单支树)。(3) 前序和后序遍历序列相同的二叉树是只有根的二叉树。9 在信息“ ABCD BCD CB

23、DB ACB中A, B, C, D四个字符出现的频率依次 是：2, 5, 4, 3。在哈夫曼树中每个字符的最优编码:1 1(1可得编码为:.WORD完美格式.A-110 B-O C-10 D-II1信息编码为：110010111 0101111001110 11010010.错误。修改如下：BiTree INSUCC (BiTree x) S=X-rchild;if(s_rtag)while (s-ltag )s=s-lchild;return S;五、算法设计题1 编写对二叉树进行中序遍历的非递归算法，并对算法执行原教材题图6-6所示的二叉树的情况进行跟踪(即给出各阶段栈的变化及输出的结点序

24、列)。【解答】中序遍历的非递归算法如下：void In orderTraverse (BTree T) In itStack (S);P=T;while (p& 1Empty (S) if (P) Push(S,p);p=p-lchild;)else pop (S,p);prin tf( ooC, p-data);p=p-rchild);对于给定的二叉树，算法执行情况如下：A入栈，B入栈，D入栈，D出栈，访问D, B出栈，访问B, A出栈，访问A, C入栈，E入栈，E出栈，访问E, G入栈，G出栈，访问.专业知识编辑整理.WORD完美格式.G, C出栈，访问C, F入栈，F出栈，访问F,栈和指

25、针p均空，结束。最后的遍历序列是：DBAGECF2 假设在表示一棵二叉树的二叉链表上增加两个域：双亲域用于指示其双亲结点，标志域flag (可取0,，2)的值，用以区分在遍历过程中到达该结点时继续向右或向左或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。【解答】要解决这一问题必须区分结点在访问过程中的状态，这可通过结点的标志域来处理。对一个结点来说当前的结点可能由：(1)其双亲结点转换；(2)其左子树遍历结束转换；(3)其右予树遍历结束转换。所以，算法主要执行按这三种状态进行处理或处理当前结点或 转换结点的状态，从而算法可描述为：void postorder (BTree

26、T)/ 后序遍历二叉树/Btree 类型的结点含 4个域：flag , pare nt , lchild , rchild; flag 初值为0,指针指向根结点 BiTree p=T;while (p)switch (p-flag) case O:p-flag=l; if (p-lchild) p=p-lchild;break;case l:p-flag=2; if (p-rchild) p=p-rchild;break; case 2:p-flag=0; printf (p-data);p=p-pare nt ; 3. 一棵具有n个结点的完全二叉树，以一维数组作为存储结构，试设计一个对该完全

27、二 叉树进行前序遍历的算法。【解答】设完全二叉树的结点以层次为序，按从上至下，由左至右的顺序编号，存放在 一维数组R1，n中。对于编号为t的结点，若存在子结点，其左孩子结点一定是 2*t，右孩子结点是2*t+l ,由此可得对完全二叉树进行前序遍历的递归算法。void preorder (int R, int n , int t)/ 前序遍历二叉树 R printf (” %Cn, Rt ) ;/ 输出当前结点值if(t*2=n)preorder(R, n, t*2);/递归前序遍历左子结点if(t*2+1Ltag! =Thread)p-p-lchild;if (p-lchild)retur n

28、 p-lchild;/求T的最左子孙的左线索else return NULL;BiTHrNode *RightMost (BiTHrTree T) BiThrNode *p=T;/求T的最右子孙的右线索while (p-Rtag!=Thread)p-p-rchild;if (p-rchild)return p-rchild;else return NULL;int Isrightchild (BiThrTree T,BiThrTree/判断T是否是pare nt=LeftMost(T);if (parent & parent-rchild=p) else (pare nt=NUIL; retu

29、rn&pare nt)pare nt的右孩子，若是返回 1否则返回return l;O;) voidposttraverse In ThrTree (BiTheTree T)/后序遍历中序线索树，当访问标志tag为RIGHT时才访问当前结点Tagtype tag;/待访问标志，表示当前结点是从左孩子还是右孩子返回的while (p) while (p-ltag!=Thread)p=p-lchild;if (p-rtag=li nk) tag=LEFT;/左孩子为线索，右孩子为链，相当于从左返回else tag=RIGHT;当前结点为叶结点，相当于从右返回while( tag=RiGHT) vi

30、sit (p);/ 仅当 tag=RIGHT 时返回if (Isrightchild (p, pare nt)/从右孩子返回，需访问pare nt，修改p指向双亲 p=pare nt;tag=RIGHT;)else/p是左孩子，用最右的线索找双亲结点 p=RightMost (p);if (p & p-Rtag=Thread) tag=RIGHT;else tag=LEFT; if (tag=LEFT & p) p=p-rchild;5 凹入表示法打印二叉树：3个字符宽度，具体实现算法如下:采用前序遍历的递归函数依次输出各结点的值，子结点比父结点右缩进Void disp (BiTree T ,

31、 int space)/space为空格数 int i;if (t) for (i=l;idata);disp (T-lchild,space+3);disp (T-rchild,space+3);6 .前序遍历一棵中序线索树：在不使用栈和递归的情况下对线索二叉树进行前序遍历，需要知道任意结点前序的直接后继。typedef enumf Link ， Thread)PointerTag;/Link:O 指针，Thread:1 线索typedef struct BiThrNodet/中序线索树结点结构ElemType data;Struct BiThrNode lchild, rchild;Poin terTagLtag, Rt