数据结构与算法第5章课后答案

上传人:碎****木 文档编号:220862630 上传时间:2021-12-09 格式:DOCX 页数:12 大小:272.63KB
返回 下载 相关 举报
数据结构与算法第5章课后答案_第1页
第1页 / 共12页
数据结构与算法第5章课后答案_第2页
第2页 / 共12页
数据结构与算法第5章课后答案_第3页
第3页 / 共12页
亲,该文档总共12页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数据结构与算法第5章课后答案》由会员分享,可在线阅读,更多相关《数据结构与算法第5章课后答案(12页珍藏版)》请在金锄头文库上搜索。

1、page: 1The Home of jetmambo - 第 5 章 树和二叉树第 5 章 树和二叉树(1970-01-01) -第 5 章 树和二叉树课后习题讲解1. 填空题 树是nn≥0结点的有限集合,在一棵非空树中,有 个根结点,其余的结点分成mm0个 的集合,每个集合都是根结点的子树。【解答】有且仅有一个,互不相交 树中某结点的子树的个数称为该结点的 ,子树的根结点称为该结点的 ,该结点称为其子树根结点的 。【解答】度,孩子,双亲 一棵二叉树的第ii≥1层最多有 个结点;一棵有nn>0个结点的满二叉树共有 个叶子结点和 个非终端结点。【解答】2i-1,(n+1)/2

2、,(n-1)/2【分析】设满二叉树中叶子结点的个数为n0,度为2的结点个数为n2,由于满二叉树中不存在度 为1的结点,所以n=n0+n2;由二叉树的性质n0=n2+1,得n0=(n+1)/2,n2=(n-1)/2。 设高度为h的二叉树上只有度为0和度为2的结点,该二叉树的结点数可能到达的最大值是 ,最小值是。【解答】2h -1,2h-1【分析】最小结点个数的状况是第1层有1个结点,其他层上都只有2个结点。 深度为k的二叉树中,所含叶子的个数最多为 。【解答】2k-1【分析】在满二叉树中叶子结点的个数到达最多。 具有100个结点的完全二叉树的叶子结点数为 。【解答】50【分析】100个结点的完全

3、二叉树中最终一个结点的编号为100,其双亲即最终一个分支结点的编 号为50,也就是说,从编号51开头均为叶子。 一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点。那么该树中有 个叶子结点。【解答】12【分析】依据二叉树性质3的证明过程,有n0=n2+2n3+1n0、n2、n3分别为叶子结点、度为2的 结点和度为3的结点的个数。 某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE,那么其后序遍历序列是 。【解答】CDBGFEA【分析】依据前序遍历序列和后序遍历序列将该二叉树构造出来。page: 2The Home of jetmambo - 第 5 章 树和

4、二叉树 在具有n个结点的二叉链表中,共有 个指针域,其中 个指针域用于指向其左右孩子, 剩下的 个指针域那么是空的。【解答】2n,n-1,n+1 在有n个叶子的哈夫曼树中,叶子结点总数为 ,分支结点总数为 。【解答】n,n-1【分析】n-1个分支结点是经过n-1次合并后得到的。2. 选择题 假设结点A有3个兄弟,B是A的双亲,那么结点B的度是。A 1 B 2 C 3 D 4【解答】D 设二叉树有n个结点,那么其深度为 。A n-1 B n C +1 D 不能确定【解答】D【分析】此题并没有指明是完全二叉树,那么其深度最多是n,最少是 +1。 二叉树的前序序列和后序序列正好相反,那么该二叉树肯定

5、是 的二叉树。A 空或只有一个结点 B 高度等于其结点数C 任一结点无左孩子 D 任一结点无右孩子【解答】B【分析】此题留意是序列正好相反,那么左斜树和右斜树均满足条件。 线索二叉树中某结点R没有左孩子的充要条件是。A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL【解答】C【分析】线索二叉树中某结点是否有左孩子,不能通过左指针域是否为空来推断,而要推断左标 志是否为1。 深度为k的完全二叉树至少有 个结点,至多有 个结点,具有n个结点的完全二叉树按层序从1开头编号,那么编号最小的叶子的序号是 。A 2k-2+1 B 2k-1 C 2k

6、-1 D 2k–1 -1 E 2k+1 F 2k+1 -1 G 2k -1+1 H 2k【解答】B,C,A【分析】深度为k的完全二叉树最少结点数的状况应是第k层上只有1个结点,最多的状况是满二 叉树,编号最小的叶子应当是在结点数最少的状况下,叶子结点的编号。 一个高度为h的满二叉树共有n个结点,其中有m个叶子结点,那么有成立。A n=h+m B h+m=2n C m=h-1 D n=2m-1【解答】D【分析】满二叉树中没有度为1的结点,所以有m个叶子结点,那么度为2的结点个数为m-1。page: 3The Home of jetmambo - 第 5 章 树和二叉树 任何一棵二叉树

7、的叶子结点在前序、中序、后序遍历序列中的相对次序 。A 确定不发生转变 B 确定发生转变 C 不能确定 D 有时发生变化【解答】A【分析】三种遍历次序均是先左子树后右子树。 假设T” 是由有序树T转换而来的二叉树,那么T中结点的前序序列就是T” 中结点的 序列,T中结点的后序序列就是 T” 中结点的序列。A 前序 B 中序 C 后序 D 层序【解答】A,B 设森林中有4棵树,树中结点的个数依次为n1、n2、n3、n4,那么把森林转换成二叉树后,其根结点的右子树上有 个结点,根结点的左子树上有 个结点。A n1-1 B n1 C n1+n2+n3 D n2+n3+n4【解答】D,A【分析】由森林

8、转换的二叉树中,根结点即为第一棵树的根结点,根结点的左子树是由第一棵树 中除了根结点以外其余结点组成的,根结点的右子树是由森林中除第一棵树外其他树转换来的。 争辩树、森林和二叉树的关系,目的是为了 。A 借助二叉树上的运算方法去实现对树的一些运算B 将树、森林按二叉树的存储方式进展存储并利用二叉树的算法解决树的有关问题C 将树、森林转换成二叉树D 表达一种技巧,没有什么实际意义【解答】B3. 推断题 在线索二叉树中,任一结点均有指向其前趋和后继的线索。【解答】错。某结点是否有前驱或后继的线索,取决于该结点的标志域是否为1。 在二叉树的前序遍历序列中,任意一个结点均处在其子女的前面。【解答】对。

9、由前序遍历的操作定义可知。 二叉树是度为2的树。【解答】错。二叉树和树是两种不同的树构造,例如,左斜树是一棵二叉树,但它的度为1。 由树转换成二叉树,其根结点的右子树总是空的。【解答】对。由于根结点无兄弟结点。 用一维数组存储二叉树时,总是以前序遍历存储结点。【解答】错。二叉树的挨次存储构造是按层序存储的,一般适合存储完全二叉树。4. 证明:对任一满二叉树,其分枝数B2(n0-1) 。其中,n0为终端结点数【解答】由于在满二叉树中没有度为1的结点,所以有:n=n0+n2 page: 4The Home of jetmambo - 第 5 章 树和二叉树设B为树中分枝数,那么n=B+1所以B=n

10、0 +n2-1再由二叉树性质:n0=n2+1代入上式有:B=n0+n0-1-1=2(n0-1)5. 证明:一棵二叉树的前序序列和中序序列,那么可唯一确定该二叉树。【解答】证明承受归纳法。设二叉树的前序遍历序列为a1a2a3… an,中序遍历序列为b1b2b3… bn。当n=1时,前序遍历序列为a1,中序遍历序列为b1,二叉树只有一个根结点,所以,a1= b1,可以唯一确定该二叉树;假设当n<=k时,前序遍历序列a1a2a3… ak和中序遍历序列b1b2b3… bk可唯一确定该二叉树,下面证明当n=k+1时,前序遍历序列a1a2a3&

11、hellip; akak+1和中序遍历序列b1b2b3… bk bk+1可唯一确定一棵二叉树。在前序遍历序列中第一个访问的肯定是根结点,即二叉树的根结点是a1,在中序遍历序列中查找 值为a1的结点,假设为bi,那么a1=bi且b1b2… bi-1是对根结点a1的左子树进展中序遍历的结果,前序遍历序列a2a3… ai是对根结点a1的左子树进展前序遍历的结果,由归纳假设,前序遍历序列a2a3… ai和中序遍历序列b1b2… bi-1唯一确定了根结点的左子树,同样可证前序遍历序列ai+1ai+2… ak+1和中序遍历

12、序列bi+1bi+2… bk+1唯一确定了根结点的右子树。6. 一棵度为m的树中有:n1个度为1的结点,n2个度为2的结点,……,nm个度 为m的结点,问该树中共有多少个叶子结点?【解答】设该树的总结点数为n,那么n=n0+n1+n2+……+nm 又:n=分枝数+1=0×n0+1×n1+2×n2+……+m×nm+1由上述两式可得:n0= n2+2n3+……+(m-1)nm+1 7二叉树的中序和后序序列分别为CBEDAFIG

13、H和CEDBIFHGA,试构造该二叉树。【解答】二叉树的构造过程如图5-12 所示。8. 对给定的一组权值W5,2,9,11,8,3,7,试构造相应的哈夫曼树,并计算它的带权 路径长度。【解答】构造的哈夫曼树如图5-13所示。树的带权路径长度为: WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2 page: 5The Home of jetmambo - 第 5 章 树和二叉树=120   9. 某字符串S中共有8种字符,各种字符分别消灭2次、1次、4次、5次、7次、3次、4

14、次和9次,对该字符串用0,1进展前缀编码,问该字符串的编码至少有多少位。【解答】以各字符消灭的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路 径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98,所以,该字符串的编码长度至少为98位。 10. 算法设计 设计算法求二叉树的结点个数。【解答】本算法不是要打印每个结点的值,而是求出结点的个数。所以可将遍历算法中的“ 访问”操作改为“计数操作”,将结点的数目累加到一个全局变量中,每个结点累加一次即完 成了结点个数的求解。具体算法如下:    设计算法按前序次序打印二叉树中的叶子结点。【解答】本算法的要求与前序遍历算法既有一样之处,又有不同之处。一样之处是打印次序均为 前序,不同之处是此处不是打印每个结点的值,而是打印出其中的叶子结点,即为有条件打印。为此,将前序遍 历算法中的访问操作改为条件打印即可。算法如下:page: 6The Home of jetmambo - 第 5 章 树和二叉树  设计算法求二叉树的深度。【解答】当二叉树为空时,深度为0;假设二叉树不为空,深度应是其左右子树深度的最大值

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 行业资料 > 教育/培训

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号