第6章习题(带答案).

1、1.在一棵具有 5层的满二叉树中结点总数为 ()。A. 31B. 32C. 33D. 162.深度为 d 的二叉树中第 k（kd）层最多有2k-1个结点，最少有1 个结点。3. 若一棵二叉树中某结点的度为 1，则该结点仅有一棵子树。 （ 对 ）4.一个具有 1025 个结点的二叉树的高 h 为（）A11B10C11 至 1025 之间D 10 至 1024 之间5.一棵完全二叉树上有1001 个结点，其中叶子结点的个数是（）A 250B500 C254 D 505E 以上答案都不对6. 将一棵有 80 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号是1，则编号

2、为 30 的结点的左孩子编号为60，双亲编号为15。7. 在一个非空二叉树的中根遍历序列中，根结点的右边( )A)只有左子树上的所有结点B) 只有左子树上的部分结点C)只有右子树上的所有结点D)只有右子树上的部分结点8. 在一棵二叉树中，第 5 层上的结点数最多为 ( ) 。A）8B） 15C）16D）329. 一棵深度为 h 的完全二叉树的结点总数的最小值为 ( 2h-1 )，从左到右次序给结点编号 ( 从 1开始 ) 则编号最小的叶子结点的编号是 (2h-2 +1 ) ，最大值为(2h-1 ) 。10.在深度为 5 的完全二叉树中，度为 2 的结点数最多为 (15) 个。已知一颗完全二叉树

3、的第6 层( 设根为第 1 层) 有 8 个叶结点， 则该完全二叉树的结点个数最少是 ()。A.39B.52C.111D.11911. 某二叉树中度为2 的结点有 12 个，则该二叉树中有 (13) 个叶子结点。已知二叉树有 50 个叶子结点，则此二叉树至少有99个结点。12. 3 个结点可构成2棵不同形状的树，5棵不同形状的二叉树。13. 设高度为 h 的二叉树上只有度为0 和度为 2 的结点，则此类二叉中包含的结点数至少为。A. h +1B. 2hC.2h-1D. 2h+114. 一棵二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树A空或只有一个结点B高度等于其结点数C任一

4、结点无左孩子D任一结点无右孩子15. 下列关于树的说法中正确的是。A. 可有任意多个孩子、任意多个双亲B.可有一个孩子、任意多个双亲C.可有任意多个孩子、只有一个双亲D. 只有一个孩子、一个双亲16. 若某二叉树的中序序列和后序序列相同，则该二叉树一定满足()。A.该二叉树为空B.其中任意一个结点均无左子树C.只有根结点D. 其中任意一个结点均无右子树17.在有 n 个结点的二叉链表中， 空指针域有 n+1 个，利用这些空指针域， 存放某种遍历序列中直接前驱或直接后继的指针，这种附加的指针称为线索 。18.若已知某二叉树的先序和后序序列相同，则该二叉树一定满足() 。A.其中任意一个结点均无左

5、子树B. 其中任意一个结点均无右子树C.只有根结点D.该二叉树为空19.已知完全二叉树的第6 层有 5 个结点，则其叶子结点数是18。20.树的后根遍历序列等同于该树对应的二叉树的（）。A、先序遍历B 、中序遍历 C、后序遍历 D 、层次遍历21.已知二叉树先根遍历的序列为“CDHAFEGB”,中根遍历的序列为“HDFAECBG”,则后根遍历的序列为 _ HFEADBGC 。22. 若一棵满二叉树深度为 h, 叶子数为 m, 结点数为 n, 则_。A)n = h + mB)h + m = 2nC)m = h - 1D)n = 2 h - 123. 树可以转换成二叉树 , 下面关于树和对应的二叉

6、树的说法 , _ 是正确的。A) 树的先根遍历序列与对应的二叉树的先根遍历序列相同B) 树的先根遍历序列与对应的二叉树的中根遍历序列相同C) 树的后根遍历序列与对应的二叉树的先根遍历序列相同D) 树的后根遍历序列与对应的二叉树的后根遍历序列相同24.n个叶子结点的哈夫曼树,结点总数为_。A)不确定B)2n - 1C)2nD)2n + 125. 在线索二叉树中 , 判断指针 p 所指结点没有左子树的条件是 _。A)p-lch = NULLB)p-ltag = 1C)p-lch = NULLp-ltag = 1D)以上都不对26. 下图所示表达式二叉树的后缀表示式为 _。A) a * b + c - d / eB)+ * a b / - c d eC) a b * c d - e / +D) a b * + c d - e /+*/ab-ecd26. 下面关于树和二叉树的说法中 , _ 是正确的。A)度为 m的树第 ii - 1个结点层至多有 mB)二叉树只能采用链式存