1564: 二叉树习题(2)

1. 设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有(      )个结点。

(A) 2n (B) n+l (C) 2n-1 (D) 2n+l

2. 完全二叉树共有2N-1个结点，则它叶子节点的个数为(  )。

(A)N-1     (B) N     (C) 2N     (D)  2N-1

3. 完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为(   )。

(A) 2 * N (B) 2 * N -1   (C) 2 * N + 1 (D) 2 * N - 2   (E) 2 * N + 2

4. 满二叉树的叶结点个数为N，则它的结点总数为（ ）。

(A) N   (B) 2 * N   (C) 2 * N – 1   (D) 2 * N + 1   (E) 2N – 1

5. 设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有( )个叶子结点。

(A) N1+N2+N3+……+Nm (B) m2 (C) 2*m+1 (D) 1+N2+2*N3+……+(m-1)Nm

6. 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为(               )。

7. 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个节点。(填写T或F)

8. 二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F的父结点是（  ）。

(A) 无法确定 (B) B (C) C (D) D (E) E

9. 二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为(   )。

(A) 4 2 5 7 6 3 1  

(B) 4 2 7 5 6 3 1  

(C) 4 2 7 5 3 6 1  

(D) 4 7 2 3 5 6 1  

(E) 4 5 2 6 3 7 1

10. 设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为 ( )。

(A) 3   (B) 4   (C) 5   (D) 6   (E)7

11. 二叉排序树中左子树上所有结点的值均(  )根结点的值。

(A) < (B) > (C) = (D) !=

12. 设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较(  )次。

(A) h  (B) 2*h-1  (C) 2*h+1  (D) logh