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

(完整word)北邮C+数据结构课后习题 习题4参考答案习题41. 填空题（1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（_)。答案：129(2)4个结点可构成（_)棵不同形态的二叉树。答案:12(3） 设树的度为5，其中度为15的结点数分别为6、5、4、3、2个,则该树共有（_）个叶子。答案：31(4）在结点个数为n(n1）的各棵普通树中，高度最小的树的高度是(_），它有（_）个叶子结点，（_）个分支结点。高度最大的树的高度是（_）,它有（_）个叶子结点，（_）个分支结点。答案：2 n1 1 n 1 n-1（5）深度为k的二叉树，至多有（_）个结点。答案:2k-1（6）有n个结点并且其高度为n的二叉树的数目是（_）。答案:2n1 (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 22. 选择题（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。 2hB。 2h1 C. 2h+1 D。 h+1(5）高度为5的完全二叉树至少有（ )个结点。A。 16B. 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=2nC。 m=h1 D。 n=2h1（8）任一棵二叉树，其叶子结点数为n0，度为2的结点数为n2，则存在关系（ ）。A. n2 +1=n0 B。 n0 +1=n2C. 2n2 +1=n0 D。 n2 =2n0 +1 (9）某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（ ）.A. bdgcefhaB。 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-1B. 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. n1 B. n/m1C。 (n1）/（m1） D。 n/(m1）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层的结点个数为kn1(2）编号为i的结点的父结点（若存在）的编号是多少？答案：|（i-1）/k (|表示取下整)（3）编号为i的结点的第m个孩子结点（若存在）的编号是多少？答案：ki+m(4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？答案：i%k!=0 i+1（5)叶子结点数n0和非叶子结点数nk之间满足的关系。答案：nk*(k1)=n016若一棵二叉树的前序序列为abdgcefh，中序序列为dgbaechf，请画出该二叉树，并写出其后序序列。答案：gdbehfca7请将图544所示树T转换为二叉树T。答案：8. 对于图545所示的二叉树,该树的三种遍历分别是什么?答案:前序 -+abcd/ef中序 a+bcd-e/f后序 abcd-+ef/-9. 对于图546所示的二叉树,请画出和其对应的森林。答案: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编码，则采用上面的哈夫曼编码，其压缩比是多少？