习题五参考答案 备注: 红色字体标明的是与书本内容有改动的内容 一、选择题 1对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（ B ）遍历操作相同。 A 先根 B. 中根 C. 后根 D. 层次 2在哈夫曼树中，任何一个结点它的度都是（ C ） 。 B 0 或 1 B. 1 或 2 C. 0 或 2 D. 0 或 1 或 2 3对一棵深度为 h 的二叉树，其结点的个数最多为（ D ） 。 A 2h B. 2h-1 C. 2h-1 D. 2h-1 4一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足（ A ） A 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵 二叉树 5一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（ B ） B 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树 6假设一棵二叉树中度为 1 的结点个数为 5，度为 2 的结点个数为 3，则这棵二叉树的叶 结点的个数是（ C ） A2 B. 3 C. 4 D. 5 7若某棵二叉树的先根遍历序列为 ABCDEF，中根遍历序列为 CBDAEF，则这棵二叉树 的后根遍历序列为（ B ） 。 AFEDCBA B. CDBFEA C. CDBEFA D. DCBEFA8若某棵二叉树的后根遍历序列为 DBEFCA，中根遍历序列为 DBAECF，则这棵二叉树 的先根遍历序列为（ B ） 。 AABCDEF B. ABDCEF C. ABCDFE D. ABDECF 9根据以权值为2，5，7，9，12构造的哈夫曼树所构造的哈夫曼编码中最大的长度为 （ B ） A2 B. 3 C. 4 D. 5 10在有 n 个结点的二叉树的二叉链表存储结构中有（ C ）个空的指针域。 An-1 B. n C. n+1 D. 0 二、填空题 1. 在一棵度为 m 的树中，若度为 1 的结点有 n1 个，度为 2 的结点有 n2 个，度为 m 的结点有 nm 个，则这 棵树中的叶结点的个数为 1+n2+2n3+3n4+(m-1)nm 。 2. 一棵具有 n 个结点的二叉树，其深度最多为 n ，最少为 log2n+1 。 3. 一棵具有 100 个结点的完全二叉树，其叶结点的个数为 50 。 4. 以5，9，12，13，20，30为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。 5. 有 m 个叶结点的哈夫曼树中，结点的总数是 2m-1 。 6. 若一棵完全二叉树的第 4 层(根结点在第 0 层)有 7 个结点，则这棵完全二叉树的结点总 数是 11 。 7. 在深度为 k 的完全二叉树中至少有 k 个结点，至多有 2k-1 个结点。 8. 对一棵树转换成的二叉树进行先根遍历所得的遍历序列为 ABCDEFGH,则对这棵树进行 先根遍历所得的遍历序列为 ABCDEFGH 。9. 二叉树常用的存储结构是 二叉链式存储结构 ，树常用的存储结构是 孩子兄弟链表存储 结构 。 10. 对森林进行后根遍历操作等同于从左到右对森林中的每一棵树进行 后根 遍历操作，并 且对森林的后根遍历序列与对森林所对应的二叉树的 中根 遍历序列相同。