《数据结构第五章参考答案》由会员分享，可在线阅读，更多相关《数据结构第五章参考答案（19页珍藏版）》请在金锄头文库上搜索。
1、数据结构第五章参考答案习题51. 填空题（1）已知二叉树中叶子数为50,仅有一个孩子的结点数为30,则总结点数为（）。答案：129（2）3个结点可构成（）棵不同形态的二叉树。答案：5（3）设树的度为5,其中度为15的结点数分别为6、5、4、3、2个，则该树共有（）个叶子。答案：31（4）在结点个数为n （n1）的各棵普通树中，高度最小的树的高度是（，它有（个叶子结点，（）个分支结点。高度最大的树的高度是（，它有（个叶子结点，（ 个分支结点。答案：2 n-1 1 n 1 n-1（5）深度为k的二叉树，至多有（）个结点。答案：2k-1（6）（7）有n个结点并且其高度为n的二叉树的数目是（。答案：2
2、n-1（8） 设只包含根结点的二叉树的高度为 0,则 高度为k的二叉树的最大结点数为（）， 最小结点数为（）答案：2k+1-1 k+1（9）将一棵有100个结点的完全二叉树按层编 号，则编号为49的结点为X，其双亲PARENT（X ）的编号为（）。答案：24（10）已知一棵完全二叉树中共有 768个结点，则该树中共有（ 个叶子结点。答案：384（11）（ 12）已知一棵完全二叉树的第 8层有8个结点，则其叶子结点数是（。答案：68（13）深度为8 （根的层次号为1）的满二叉树 有（个叶子结点。答案：128（14） 一棵二叉树的前序遍历是 FCABED，中序遍历是ACBFED ,则后序遍历是（。
3、答案：ABCDEF（15 ）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为（，该二叉树对应的树林包括（棵树。答案：EACBDGF 22. 选择题（1）在一棵度为3的树中，度为3的结点的个数为2，度为2的结点个数为1，则度为0的结点个数为（）。A. 4B. 5C. 6D.7（2）下列陈述中正确的是（）。A. 二叉树是度为2的有序数B. 二叉树中结点只有一个孩子时无左右之分C. 二叉树中必有度为2的结点D. 二叉树中最多只有两棵子树，并且有左右之分（3）在K叉树中，如果结点M有3个兄弟，而且N是M的双亲，则N的度是（）A. 3B. 4C.
4、5D. 1（4）设高度为h的二叉树上只有度为0和度为 2的结点，则此类二叉树中所包含的结点数至少为（）。A. 2hB.2h1C.2h+1D. h+1（5）高度为5的完全二叉树至少有（)个结点。A. 16B. 32C. 31D. 5（6）具有65个结点的完全二叉树的高度为 （）。（根的层次号为0）A. 8B. 7C.6D. 5（7）对一个满二叉树，m个树叶，n个结点， 深度为h，则（无）。A. n=h+mB.h+m=2 nC. m=h-1D. n=2h-1（8） 任一棵二叉树，其叶子结点数为n0,度为B.no2的结点数为n2,则存在关系（A. n2 +1=no+1= n2C. 2n2 +1= n
5、oD. n2=2no+1（9）某二叉 树的前序遍 历结点访问 顺序是 abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（ ）。A. bdgcefha B. gdbecfha C. bdgaechfD. gdbehfca（10）设m、n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（）。A. n在m右方B. n是m祖先C. n在m左方D.n是m子孙（11） 一棵二叉树的广义表表示为 a （b（c，d）， e（ f（ g）,则得到的层序遍历序列为（ ）。A. abcdefgB. cbdaegf C. cdbgfeaD. abecdfg（12） 若
6、二叉树采用二叉链表作为存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。A.前序B.中序C.后序D.层序说明：显然，如果按前序或后序遍历，当访问某 结点时，交换其左右孩子，则可完成要求。进 行层序遍历时，当结点出队时，交换左右孩子， 也可以完成题目要求。因此该题有 3个答案， 谈不上哪个最合适。建议该题目将“最合适” 改为“不合适”，这样答案应该是唯一的。（13）对二叉树进行（）遍历，可以得到该二叉树所有结点构成的排序序列。A.前序B.中序C.后序D.层序（14）设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域 为空的结点有（）个。A. n-1B
7、. nC. n+1D. n+2（15）利用3, 6, 8，12，5, 7这6个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度 为（）。A.3B. 4C.5D. 6(16) 若度为m的哈夫曼树中，其叶结点个数 为n,则非叶结点的个数为()。A. n-1B.n/m-1C. (n-1)/(m-1)D. n/(m-1)-1说明：在这里度为 m的哈夫曼树是指仅含有度 为0和m的结点的m叉树。因此有：(1) N= n+nm(2) N = 1 + mn m3. 试分别画出具有3个结点的树和二叉树的所有 不同形态。答案：树：1二叉树:I4. 试找出分别满足下面条件的所有二叉树：（1）前序序列和中序序列相同；
8、答案：右斜树（2）中序序列和后序序列相同；答案：左斜树（3）前序序列和后序序列相同。答案：只有根结点的树5棵高度为h的满k叉树有如下性质：第h 层上的结点都是叶结点，其余各层上每个结点 都有k棵非空子树，如果按层次自顶向下，同 一层自左向右，顺序从0开始对全部结点进行 编号，试问：（1）各层的结点个数是多少？答案：n层的结点个数为kn-1（2）编号为i的结点的父结点（若存在）的编 号是多少？答案：|（i-1）/k|（| 表示取下整）(3) 编号为i的结点的第m个孩子结点(若存 在)的编号是多少？答案：k*i+m(4) 编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？答案：i%k!
9、=O i+1(5) 叶子结点数no和非叶子结点数nk之间满足 的关系。答案：nk*(k-1)=n o-16. 若一棵二叉树的前序序列为 abdgcefh，中序 序列为dgbaechf，请画出该二叉树，并写出其后 序序列。答案：gdbehfca7. 请将图5-42所示树T转换为二叉树8. 对于图5-43所示的二叉树，该树的三种遍 历分别是什么？答案：前序-+a*b-cd/ef 中序 a+b*c-d-e/f后序 abcd-*+ef/-9. 对于图5-44所示的二叉树，请画出和其对 应的森林。A答案:10. 假设用于通信的电文仅由9个字符组成，并且出现概率为 0.07 （A）、0.19 （B）、0.02 （C）、0.06（ D）、0.32 （E）、0.03（F）、0.21（G）、0.10（H）（I）画出哈夫曼树；答案:(2) 每个字符的哈夫曼编码; 答案：A 0010B 10C 00000D 0001E 01F 00001G 11H 0011(3) 计算其带权路径长度;答案WPL=0.07*4+0.19*2+0.02*5+0.06*4+0.32*2+0.03*5+0.21*2+0.10*4=2.61(4)如果电文是“ ABCDEFGH压缩前每个字符 使用8bit的ASCII编码，则采用上面的哈夫曼 编码，其压缩比是多少？答案：425425240.43758 8
