第5章树与二叉树习题参考答案.doc

习题五参考答案 备注: 红色字体标明的是与书本内容有改动的内容 一、选择题 1．对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（ B ）遍历操作相同。 先根 B. 中根 C. 后根 D. 层次 2．在哈夫曼树中，任何一个结点它的度都是（ C ）。 0或1 B. 1或2 C. 0或2 D. 0或1或2 3．对一棵深度为h的二叉树，其结点的个数最多为（ D ）。 2h B. 2h-1 C. 2h-1 D. 2h-1 4．一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足（ A ） 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树 一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（ B ） A. 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树 6．假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（ C ） A．2 B. 3 C. 4 D. 5 7．若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（ B ）。 A．FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA 8．若某棵二叉树的后根遍历序列为DBEFCA，中根遍历序列为DBAECF，则这棵二叉树的先根遍历序列为（ B ）。 A．ABCDEF B. ABDCEF C. ABCDFE D. ABDECF 9．根据以权值为{2，5，7，9，12}构造的哈夫曼树所构造的哈夫曼编码中最大的长度为（ B ） A．2 B. 3 C. 4 D. 5 10．在有n个结点的二叉树的二叉链表存储结构中有（ C ）个空的指针域。 A．n-1 B. n C. n+1 D. 0 二、填空题 在一棵度为m的树中，若度为1的结点有n1个，度为2的结点有n2个，……，度为m的结点有nm个，则这棵树中的叶结点的个数为 1+n2+2n3+3n4+…+(m-1)nm 。 一棵具有n个结点的二叉树，其深度最多为 n ，最少为 [log2n]+1 。 一棵具有100个结点的完全二叉树，其叶结点的个数为 50 。37 以{5，9，12，13，20，30}为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。 有m个叶结点的哈夫曼树中，结点的总数是 2m-1 。 若一棵完全二叉树的第4层(根结点在第0层)有7个结点，则这棵完全二叉树的结点总数是 11 。22 在深度为k的完全二叉树中至少有 k个结点，至多有 2k-1 个结点。 对一棵树转换成的二叉树进行先根遍历所得的遍历序列为ABCDEFGH,则对这棵树进行先根遍历所得的遍历序列为 ABCDEFGH 。 二叉树常用的存储结构是 二叉链式存储结构 ，树常用的存储结构是 孩子兄弟链表存储结构 。 对森林进行后根遍历操作等同于从左到右对森林中的每一棵树进行 后根 遍历操作，并且对森林的后根遍历序列与对森林所对应的二叉树的 中根 遍历序列相同。 四、算法设计题 编写一个基于二叉树类的统计叶结点数目的成员函数。 参考答案： public int countLeafNode(BiTreeNode T) {// 统计叶结点数目 int count = 0; if (T != null) { if (T.getLchild() == null T.getRchild() == null) { ++count;// 叶结点数增1 } else { count += countLeafNode(T.getLchild()); // 加上左子树上叶结点数 count += countLeafNode(T.getRchild());// 加上右子树上的叶结点数 } } return count; } 编写一个基于二叉树类的查找二叉树结点的成员函数。 参考答案： public BiTreeNode searchNode(BiTreeNode T,Object x)