1565: 二叉树习题(1)

1. 设在一棵度数为3的树中，若有2个度为3的结点，有1个度为2的结点，则有  (   )  个度为0的结点。

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

2. 完全二叉树共有2N-1个结点，则它叶子节点的个数为(  )。若深度（根节点为1）为n的完全二叉树共有2ⁿ-1个结点，则它叶子节点的个数为(  )

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

(A)n-1     (B) n     (C) 2ⁿ     (D)  2^n-1

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

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

4. 满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为 h(h>1)的满二叉树，其结点总数为（    ）。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从 1、2、3、…依次编号，则对于树中编号为 i 的非叶子结点，其右子树的编号为（   ）  （高度为 3 的满二叉树如下图所示）。

           (A)  2       (B). 2^h-1     (C)  2^h-1        (D). 2^h-1+1

           (A). 2i      (B). 2i-1      (C). 2i+1      (D). 2i+2

5. 一棵二叉树的前序序列为ABDECF，中序序列为DBEAFC，则对该树进行后序遍历得到的序列为 (    )  。

   ( A)．DEBAFC     (B)．DEFBCA     ©．DEBCFA     (D)．DEBFCA

6. 由关键字序列（12，7，36，25，18，2）构造一棵二叉排序树（初始为空，第一个关键字作为根结点插入，此后对于任意关键字，若小于根结点的关键字，则插入左子树中，若大于根结点的关键字，则插入右子树中，且左、右子树均为二叉排序树），该二叉排序树的高度（层数）为（   ）。

        A. 6        B. 5        C. 4         D. 3

7. 二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行 （     ）遍历，可得到一个结点元素的递增序列。

A.先序（根、左、右）           B. 中序（左、根、右）

C.后序（左、右、根）           D. 层序（从树根开始，按层次）

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