北邮C++数据结构课后习题-习题4参考答案.doc

(完整word)北邮C++数据结构课后习题 习题4参考答案
习题4
1. 填空题
（1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（___________)。
答案：129
(2)4个结点可构成（___________)棵不同形态的二叉树。
答案:12
(3） 设树的度为5，其中度为1～5的结点数分别为6、5、4、3、2个,则该树共有（___________）个叶子。
答案：31
(4）在结点个数为n(n〉1）的各棵普通树中，高度最小的树的高度是(___________），它有（___________）个叶子结点，（___________）个分支结点。高度最大的树的高度是（___________）,它有（___________）个叶子结点，（___________）个分支结点。
答案：2 n—1 1 n 1 n-1
（5）深度为k的二叉树，至多有（___________）个结点。
答案:2k-1
（6）有n个结点并且其高度为n的二叉树的数目是（___________）。
答案:2n—1
(7）设只包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为（___________)，最小结点数为（___________）。
答案：2k-1 k
（8）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT（X）的编号为(）.
答案：24
（9）已知一棵完全二叉树中共有768个结点，则该树中共有（___________)个叶子结点。
答案：384
（10）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是(___________）.
答案：68
（11）深度为8（根的层次号为1)的满二叉树有（___________)个叶子结点。
答案：128
（12）一棵二叉树的前序遍历是FCABED,中序遍历是ACBFED，则后序遍历是（___________）.
答案：ABCDEF
（13）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为(___________）,该二叉树对应的树林包括（___________)棵树。
答案：EACBDGF 2

2. 选择题
（1）在一棵度为3的树中，度为3的结点的个数为2,度为2的结点个数为1，则度为0的结点个数为( ）。
A。 4 B. 5 C。 6 D。 7
(2）下列陈述中正确的是（ ）。
A. 二叉树是度为2的有序数
B。 二叉树中结点只有一个孩子时无左右之分
C. 二叉树中必有度为2的结点
D。 二叉树中最多只有两棵子树,并且有左右之分
（3)树中如果结点M有3个兄弟，而且N是M的双亲，则N的度是（ ）
A. 3 B。 4 C。 5 D. 1
(4）设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ).
A。 2h B。 2h－1 C. 2h+1 D。 h+1
(5）高度为5的完全二叉树至少有（ )个结点。
A。 16 B. 32 C. 31 D. 5
（6）具有65个结点的完全二叉树的高度为( ）。(根的层次号为0）
A。 8 B. 7 C.6 D。 5
（7）对一个满二叉树，m个树叶，n个结点，深度为h，则（ 无 ）。
A。 n=h+m B. h+m=2n
C。 m=h—1 D。 n=2h—1
（8）任一棵二叉树，其叶子结点数为n0，度为2的结点数为n2，则存在关系（ ）。
A. n2 +1=n0 B。 n0 +1=n2
C. 2n2 +1=n0 D。 n2 =2n0 +1
(9）某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（ ）.
A. bdgcefha B。 gdbecfha C。 bdgaechf D. 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。 abcdefg B。 cbdaegf C. cdbgfea D. abecdfg
（12） 将一棵树t转换为二叉树h,则t的后序遍历是h的（　　)。
A。中序遍历 B.前序遍历 C。后序遍历 D.层序遍历
(13)对二叉树进行（ ）遍历，可以得到该二叉树所有结点构成的排序序列。
A。 前序 B。 中序 C. 后序 D。 层序
(14）设F是一个森林，B是由F转换得到的二叉树,F中有n个非叶结点,则B中右指针域为空的结点有（ )个。
A. n-1 B. n C. n+1 D. n+2
(15）利用3，6,8，12，5，7这6个值作为叶子结点的权,生成一棵哈夫曼树，该树的深度为( ）。
A。3 B. 4 C.5 D. 6
（16)若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）.
A. n—1 B. ［n/m]—1
C。 ［(n—1）/（m—1）］ D。 ［n/(m—1）]—1
说明:在这里度为m的哈夫曼树是指仅含有度为0和m的结点的m叉树.因此有：
　　　　　（1) Ｎ＝n+nm
(2) N = 1 + mnm

3. 试分别画出具有3个结点的树和二叉树的所有不同形态。
答案：树：

二叉树：

4． 试找出分别满足下面条件的所有二叉树:
(1）前序序列和中序序列相同；
答案： 右斜树
(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!=0 i+1
（5)叶子结点数n0和非叶子结点数nk之间满足的关系。
答案：nk*(k—1)=n0—1
6．若一棵二叉树的前序序列为abdgcefh，中序序列为dgbaechf，请画出该二叉树，并写出其后序序列。
答案：gdbehfca

7．请将图5－44所示树T转换为二叉树T′。

答案：

8. 对于图5－45所示的二叉树,该树的三种遍历分别是什么?

答案:
前序 -+a＊b—cd/ef
中序 a+b＊c—d-e/f
后序 abcd-＊+ef/-

9. 对于图5－46所示的二叉树,请画出和其对应的森林。

答案:

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）：
（1)画出哈夫曼树；
（2)每个字符的哈夫曼编码；
（3）计算其带权路径长度；
（4）如果电文是“ABCDEFGH”压缩前每个字符使用8bit的ASCII编码，则采用上面的哈夫曼编码，其压缩比是多少？