文档介绍：该【中国铁道出版社数据结构(第二版)单元7练习参考答案 】是由【1781111****】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【中国铁道出版社数据结构(第二版)单元7练习参考答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..中国铁道出版社数据结构(第二版)(下列各题,正确的请在前面的括号内打√;错误的打w)(√)(1)树结构中每个结点最多只有一个直接前驱。(ㄨ)(2)完全二叉树一定是满二查树。(ㄨ)(3)在中序线索二叉树中,右线索若不为空,则一定指向其双亲。(√)(4)一棵二叉树中序遍历序列的最后一个结点,必定是该二叉树前序遍历的最后一个结点。(√)(5)二叉树的前序遍历中,任意一个结点均处于其子女结点的前面。(√)(6)由二叉树的前序遍历序列和中序遍历序列,可以推导出后序遍历的序列。(√)(7)在完全二叉树中,若一个结点没有左孩子,则它必然是叶子结点。(ㄨ)(8)在哈夫曼编码中,当两个字符出现的频率相同,其编码也相同,对于这种情况应该做特殊处理。(ㄨ)(9)含多于两棵树的森林转换的二叉树,其根结点一定无右孩子。(√)(10)具有n个叶子结点的哈夫曼树共有2n-1个结点。(1)在树中,一个结点所拥有的子树数称为该结点的度。(2)度为零的结点称为叶(或叶子,或终端)结点。(3)树中结点的最大层次称为树的深度(或高度)。(4)对于二叉树来说,第i层上至多有2i-1个结点。(5)深度为h的二叉树至多有2h-1个结点。(6)由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。(7)有20个结点的完全二叉树,编号为10的结点的父结点的编号是5。(8)哈夫曼树是带权路径长度最小的二叉树。(9)由二叉树的后序和中序遍历序列,可以唯一确定一棵二叉树。(10)某二叉树的中序遍历序列为:DEBAC,后序遍历序列为:EBCAD。则前序遍历序列为:DABEC。(11)设一棵二叉树结点的先序遍历序历为:ABDECFGH,中序遍历序历为:DEBAFCHG,则二:..叉树中叶结点是:E、F、H。(12)已知完全二叉树的第8层有8个结点,则其叶结点数是68。(13)由树转换成二叉树时,其根结点无右子树。(14)采用二叉链表存储的n个结点的二叉树,一共有2n个指针域。(15)采用二叉链表存储的n个结点的二叉树,共有空指针n+1个。(16)前序为A,B,C且后序为C,B,A的二叉树共有4种。BBBBAAAA(17)三个结点可以组成2种不同形态的树。(18)将一棵完全二叉树按层次编号,对于任意一个编号为i的结点,其左孩子结点的编号为:2*i。(19)给定如下图所示的二叉树,其前序遍历序列为:ABEFHCG。HEFGBH(20)给定如下图所示的二叉树,其层次遍历序列为:ABCEFGH。(1)树最适合用来表示(D)。(2)前序为A,B,C的二叉树共有(D)种。:..(3)根据二叉树的定义,具有3个结点的二叉树有(C)种树型。(4)在一棵具有五层的满二叉树中,结点的总数为(B)(5)具有64个结点的完全二叉树的深度为(C)(6)任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序(A)。(7)A,B为一棵二叉树上的两个结点,在中序遍历时,A在B前的条件是(C)。(8)下列4棵树中,(B)不是完全二叉树。(9)如右图所示的二叉树,后序遍历的序列是(D)、B、C、D、E、F、G、H、、B、D、H、I、E、C、F、、D、I、B、E、A、F、C、、I、D、E、B、F、G、C、A:..HIDBEFACGABCBACBACBAC(10)对于下边的二叉树,其中序序列为(A)+-(11)某二叉树的后序遍历序列为:DABEC,中序遍历序列为:DEBAC,则前序遍历序列为(D)。(12)具有n(n>1)个结点的完全二叉树中,结点i(2i>n)的左孩子结点是(D)。(若2i<=n,则答案为A)(13)把一棵树转换为二叉树后,这棵二叉树的形态是(A)。,,但根结点都没有右孩子(14)将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点编号,根结点的编号为1,则编号为45的结点的左孩子编号为(B)。:..(15)将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点编号,根结点的编号为1,则编号为49的结点的右孩子编号为(B)。(16)二叉树按某种顺序线索化后,任一结点均有指向其前驱和后继的线索,这种说法(B)。(17)下列陈述正确的是(D)。,(18)用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是(B)。(先构造哈夫曼树,WPL=(1+2)*3+(3+4+5)*2=33):..(19)在树结构中,若结点B有4个兄弟,A是B的父亲结点,则A的度为为(C)。(20)二叉树的叶结点个数比度为2的结点的个数(C)。,请画出此树,并回答问题。{(L,M),(L,N),(E,L),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(H,I),(C,H),(A,C)}(1)哪个是根结点?(2)哪些是叶结点?(3)哪个是G的双亲?(4)哪些是G的祖先?(5)哪些是G的孩子?(6)哪些是E的子孙?(7)哪些是E的兄弟?哪些是F的兄弟?(8)结点B和N的层次各是多少?(9)树的深度是多少?(10)以结点C为根的子树的深度是多少?(11)树的度数是多少?答:(1)A是根结点。(2)叶结点:M,N,D,J,K,F,I。(3)G的双亲:C。(4)G的祖先:A,C。(5)G的孩子:J,K。(6)E的子孙:L,M,N。(7)E的兄弟:D;F的兄弟:G,H。(8)结点B的层次为2;结点N的层次是5。(9)树的深度是5。(10)以结点C为根的子树的深度是3。(11)树的度数是3。,试回答下列问题。DAB(1)森林中有几棵树?:..(2)每一棵树的根结点分别是什么?(3)第一棵树有几个结点?(4)第二棵树有几个结点?CEFG(5)森林中有几个叶结点?HIJLK解:(1)4(2)A,C,G,K(3)6(4)2(5):ABC,试问有几种不同形态的二叉树可以得到这一遍历结果?并画出这些二叉树。答:(1)5种。(2)。答:(1)三个结点的树(2)三个结点的二叉树树感谢您的阅读,祝您生活愉快。