Problem C: 二叉树

1、【NOIP2001提高组】一棵二叉树的高度为h（单个节点树高度为1），所有结点的度为0，或为2，则此树

      最少有（     ）个结点。

   A．2^h-1         B．2h-1        C．2h+1        D．h+1

2、【NOIP2003】一个高度为h的二叉树最小元素数目是（     ）。

  A．2h+l       B．h         C．2h-1     D．2h         E．2h-l

3、、【NOIP2003提高组】表达式(1+34)*5-56/7 的后缀表达式为（     ）。

   A．1+34*5-56/7          B．-*+1 34 5/56 7        C．1 34 +5*56 7/-

   D．1 34 5* +56 7/-      E．1 34+5 56 7-*/

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

   A. N        B. 2 * N     C. 2 * N – 1     D. 2 * N + 1    E. 2N– 1

5、【NOIP2004】二叉树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

6、【NOIP2005普及组】完全二叉树的结点个数为11，则它的叶结点个数为（     ）。

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

7. 【NOIP2005普及组】二叉树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

8.【NOIP2006普及组】已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（     ）。

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