《数据结构》

1. 把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。

     A.唯一的                                           B.有多种  

     C.有多种，但根结点都没有左孩子    Ｄ.有多种，但根结点都没有右孩子

  【答案】A 。因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。

2. 由 3 个结点可以构造出多少种不同的二叉树？（ ）

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

【答案】D。五种情况如下：

     [附加]用n个结点可以构造出多少种不同的二叉树？

     解：对于本类题型的求解可以利用之前所学的递归思想，设n个结点构成出不同形态的二叉树为h（n），可知h（0）=1：

           ①当n=1时，该二叉树只有一个结点（根节点），因此只有1种形态二叉树，即h（1）=1；

           ②当n=2时，除去根节点后，还有2-1个结点，既可以作为左子树也可以作为右子树；当作为左子树时，只有一个结点，作为左子树的根节点，因此左子树也只有一种形态；右子树同理。即h(2)=h(1)*h(0)+h(0)h(1)=2;

         ③当n=3时，除去根节点后，还有3-1个结点，既可以作为左子树也可以作为右子树；与②中同理，即h(3)=h(2)*h(0)+h(1)*h(1)+h(2)*h(0)=5;

……

    由此，可推出规律如下，当n≥2时，可构成不同形态的二叉树个数h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种，该规律符合数学中catalan序列，化简整理为：h(n)=C(2n,n)/(n+1) (n=1,2,3,...)

3. 一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（ ）。

    A． 250          B . 500          C．254          D．501

【答案】 D 。设度为 0 结点（叶子结点）个数为 N0，度为 1 的结点个数为 N1，度为 2 的结点个数为 N2，有 N0=N2+1， N0+N1+N2=1001 ，可得 2N2+N1=1000 ，由完全二叉树的性质可得 N1只能为0 或 1，又因为结点个数为整数，所以 两式联立得N1=0， N2=500 ， N0=501 ，即有 501 个叶子结点。

4. 一个具有 1025 个结点的二叉树的高 h 为（ ）。

    A．11           B．10        C．11 至 1025之间      D．10 至 1024 之间

【答案】C。若每层仅有一个结点，则树高 h 为 1025 ；且其最小树高为 log2 1025+1=11，即 h 在11至 1025 之间。

5. 利用二叉链表存储树，则根结点的右指针是（ ）。

    A．指向最左孩子     B．指向最右孩子      C．空         D．非空

【答案】C。利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。

6. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。

    A．前序                  B .中序                    C．后序       D. 按层次

【答案】C。后续遍历和层次遍历均可实现左右子树的交换 ，不过层次遍历的实现消耗比后续大，后序遍历方法最合适。

7. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。

   A．所有的结点均无左孩子        B ．所有的结点均无右孩子

   C．只有一个叶子结点               D ．是任意一棵二叉树

【答案】C。因为先序遍历结果是“中左右” ，后序遍历结果是“左右中”,当没有左子树时，就是“中右”和“右中” ；当没有右子树时，就是“中左”和“左中” 。则所有的结点均无左孩子或所有的结点均无右孩子均可，所以 A、B 不能选，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点，故选 C。

8. 设哈夫曼树中有 199 个结点，则该哈夫曼树中有（ ）个叶子结点。

    A．99           B．100        C．101        D．102

【答案】B 。在哈夫曼树中没有度为 1 的结点，只有度为 0（叶子结点）和度为 2 的结点。设叶子结点的个数为 n0，度为 2 的结点的个数为 n2，由二叉树性质 n0=n2+1 ，则总结点数 n= n0+n2=2*n0-1，得到 n0=100 。

9. 若 X 是二叉中序线索树中一个有左孩子的结点， 且 X 不为根， 则 X 的前驱为 （ ）。

    A． X 的双亲                           B． X 的右子树中最左的结点

    C． X 的左子树中最右结点      D． X 的左子树中最右叶结点

【答案】C。此题建议使用画图解决，注意-最右节点不一定是叶节点。

10. （n≥2） 个权值均不相同的字符构成哈夫曼树， 关于该树的叙述中， 错误的是 （ ）。

     A．该树一定是一棵完全二叉树       

     B．树中一定没有度为 1 的结点

     C．树中两个权值最小的结点一定是兄弟结点

     D．树中任一非叶结点的权值一定不小于下一层任一结点的权值

【答案】A。哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为 1 的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。

11. 对于一裸具有n个结点、度为4的树来说，( )。

     A.树的高度至多是n-                           B.树的高度至多是n-4

     C.第i层上至多有4(i- 1)个结点             D. 至少在某一-层上正好有4个结点

【答案】A。要使得具有n个结点、度为4的树的高度最大，就要使得每层的结点数尽可能少，类似图中所示的树，除最后一层外，每层的结点数是1,最终该树的高度为n-3。树的度为4只能说明存在某结点正好(也最多)有4个孩子结点，D错误。

 12. 度为4、高度为h的树，( ).

     A.至少有h+3个结点                     B.至多有4h- 1个结点

     C.至多有4h个结点                       D.至少有h+4个结点,

【答案】A。要使得度为4、高度为h的树的总结点数最少，需要满足以下两个条件:

             ①至少有一个结点有4个分支。

             ②每层的结点数目尽可能少。

           情况类似图中所示的树，结点个数为h+3。要使得度为4、高度为h的树的总结点数最多，应使每个非叶结点的度均为4,即为满树，总结点个数最多为1 +4+42 +...+ 4h-1。

13. 假定一棵度为3的树中，结点数为50，则其最小高度为( ).

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

【答案】要求满足条件的树，那么该树是一棵完全三叉树。在度为3的完全三叉树中，第1层有1个结点，第2层有31=3个结点，第3层有32=9个结点，第4层有3=27个结点，因此结点数之和为1 +3+9+27=40，第5层的结点数=50-40= 10个，因此最小高度为5。

14. 以下说法中，正确的是( )。

     A.在完全二叉树中，叶子结点的双亲的左兄弟(若存在) 一定不是叶子结点

     B.任何一棵二叉树，叶子结点个数为度为2的结点数减1，即N0=N2-1

     C.完全二叉树不适合顺序存储结构，只有满二叉树适合顺序存储结构

     D.结点按完全二叉树层序编号的二叉树中，第i个结点的左孩子的编号为2i

【答案】在完全二叉树中，叶子结点的双亲的左兄弟的孩子一定在其前面(且一定存在)，故双亲的左兄弟(若存在) 一定不是叶结点，A正确。no应等于n2+ 1, B错误。完全二叉树和满二叉树均可以采用顺序存储结构，C错误。第i个结点的左孩子不一定存在，D错误。选项B的这种通用公式适用于所有二叉树。

15. 具有10个叶子结点的二又树中有( ) 个度为2的结点。

     A.8             B. 9            C.10           D. 11

【答案】B。由二叉树的性质no=n2+1,得m2=no- 1=10-1=9。

16.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则该

完全二叉树的结点个数最多是( ).

     A.39            B. 52           C.111             D.119

【答案】C。第6层有叶结点，完全二叉树的高度可能为6或7，显然树高为7时结点最多。完全二叉树与满二叉树相比，只是在最下一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。若第6层上有8个叶结点，则前6层为满二叉树，而第7层缺失了8x2= 16个叶结点，故完全二叉树的结点个数最多为27- 1- 16= 111。

17. 若一棵深度为6的完全二叉树的第6层有3个叶子结点，则该二叉树共有( )个叶子结点.

    A. 17             B.18             C.19             D.20

【答案】A。深度为6的完全二叉树，第5层共有结点2* = 16个。第6层最左边有3个叶子结点，其对应的双亲结点为第5层最左边的两个结点,所以第5层剩余的结点均为叶子结点,共有16-2= 14个，加上第6层的3个，共17个叶子结点。

18. 一棵有124个叶子结点的完全二叉树，最多有( )个结点。

      A. 247         B. 248          C.249            D.250

【答案】B。在非空的二叉树当中，由度为0和2的结点数的关系n0=n2+1可知n2=123;总结点数n= n0+n1+n2=247 +n1,其最大值为248 (n的取值为1或0,当n=1时结点最多)。注意，由完全二叉树总结点数的奇偶性可以确定n的值，但不能根据no来确定的n值。

19. 对于一棵满二叉树，共有n个结点和m个叶子结点，高度为h,则( )。

     A. n=h+m      B. n+m=2h    C. m=h-1       D. n=2^h- 1

【答案】D.对于高度为h的满二叉树，n=2^0+2^1 +...+ 2^h-1=2^h- 1,m=2^h-1，故选D。解法二:特殊值法。如对于高度为3的满二叉树，n=7,m=4,h=3，经检验，仅D正确。

20.对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元(仅存放结点的数据信息)，则存放该二叉树需要的存储单元数量至少是( )。

     A.31             B.16               C.15             D. 10

【答案】A。二叉树采用顺序存储时，用数组下标来表示结点之间的父子关系。对于一棵高度为5的二叉树，为了满足任意性，其1~5层的所有结点都要被存储起来，即考虑为一棵高度为5的满二叉树，共需要存储单元的数量为1+2+4+8+16=31。

21. ①设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是( )。

          A. n在m右方           B.n是m祖先

          C. n在m左方           D. n是m子孙

②设n,m为一棵二叉树上的两个结点，在后序遍历时，n在m前的条件是( )。

          A. n在m右方           B. n是m祖先

          C. n在m左方           D. n是m子孙

【答案】① C；② D。①中序谝历时，先访问左子树，再访问根结点，后访问右子树。n在m前的3种可能性如图所示，从中看出n总是在m的左方。另解:设n和m的最近公共祖先p,则有以下可能:

              情形1, m和n分别在p的左、右(右、左)分支上；

              情形2，m或n为p结点,另一结点在p的分支上。只有n和m分别处于p的左、右分支上，m为祖先结点且n位于m的左分支，n为祖先结点且m位于n的右分支，符合题意。

           ②后序遍历的顺序是LRN,若n在N的左子树，m在N的右子树，则在后序遍历的过程中n在m之前访问:若n是m的子孙，设m在N的位置，则n无论是在m的左子树还是在右子树，在后序遍历的过程中n都在m之前访问。其他都不可以。C要成立，要加.上两个结点位于同一层。

22.若一棵二叉树的前序遍历序列为a,e,b,d,c,后序遍历序列为b,c,d,e,a,则根结点的孩子结点( ).

     A.只有e             B.有e、b               C.有e、c           D.无法确定

【答案】A。前序序列和后序序列不能唯一确定一 棵二叉树，但可以确定二叉树中结点的祖先关系:当两个结点的前序序列为XY、后序序列为YX时，则X为Y的祖先。考虑前序序列a,e, b,d,c、后序序列b,c,d,e,a,可知a为根结点，e为a的孩子结点;此外，由a的孩子结点的前序序列e, b, d,c和后序序列b,c,d,e,可知e是bcd的祖先，故根结点的孩子结点只有e.故选A。

23. 已知一棵二叉树的层次序列为ABCDEF,中序序列为BADCFE,则先序序列为( )。

      A. ACBEDF         B. ABCDEF         C. BDFECA        D. FCEDBA

【答案】B。可构造出二叉树如下图所示。因此，先序序列为ABCDEF.

24. 二叉树在线索化后，仍不能有效求解的问题是( )。

     A.先序线索二叉树中求先序后继          B.中序线索二叉树中求中序后继

     C.中序线索二叉树中求中序前驱          D.后序线索二叉树中求后序后继

【答案】D。后序线索二叉树不能有效解决求后序后继的问题。如图所示，结点E的右指针指向右孩子，而在后序序列中E的后继结点为B,在查找E的后继时后序线索不能起到任何作用，只能按常规方法来查找。

25.下列给定的关键宇输入序列中，不能生成右边二叉排序树的是( ).

      A .4，5，2,  1，3                  B. 4，5,  1,  2，3

     C. 4，2，5,  3，1                   D. 4，2，1,  3,  5

【答案】每个选项都逐一验证，选项B生成二叉排序树的过程如下:

26. 某二叉树结点的中序序列为BDAECF,后序序列为DBEFCA,则该二叉树对应的森林包括( )棵树.

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

【答案】C。根据二叉树的前序遍历序列和中序遍历序列可以唯一确定一棵二叉树。根据后序遍历序列，A是二叉树的根结点。根据中序遍历序列，二叉树的形态如图中所示。

      对于A的左子树，由后序遍历序列可知，因为B比D后被访问,因此B必为D的父结点，又由中序遍历序列可知，D是B的右儿子。对于A的右子树，同理可确定结点E、C、F的关系。此二叉树的形态如图所示。再根据二叉树与森林的对应关系，森林中树的棵数即为其对应二叉树中根结点A的兄弟数,可知此森林中有3棵树,根结点分别为A,C和F。

27.设F是一个森林，B是由F变换来的二叉树。若F中有n个非终端结点，则B中右指针城为空的结点有( )个。

     A. n-1             B. n              C. n+1         D. n+2

【答案】C。根据森林与二叉树转换规则“左孩子右兄弟"。二叉树B中右指针域为空代表该结点没有兄弟结点。森林中每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子，因此最后一棵树的根结点的右指针为空。另外，每个非终端结点，其所有孩子结点在转换之后，最后一个孩子的右指针也为空，故树B中右指针域为空的结点有n+1个。

28.若森林F有15条边、25个结点，则F包含树的个数是( )。

     A.8                 B.9              C.10             D.11

【答案】C。树有一个很重要的性质，即在n个结点的树中有n- 1条边,“那么对于每棵树，其结点数比边数多1”。题中的森林中的结点数比边数多10 (即25- 15= 10),显然共有10棵树。

29. 设X是树T中的一个非根结点，B是T所对应的二叉树.在B中，X是其双亲结点的右

孩子，下列结论中正确的是( ).

    A.在树T中，X是其双亲结点的第一个孩子         B.在树T中，X一定无右边兄弟.

    C.在树T中，X一定是叶子结点                          D.在树T中，X一定有左边兄弟.

【答案】D。在二叉树B中，x是其双亲的右孩子，因此在树T中，X必是其双亲结点的右兄弟，换句话说，X在树中必有左兄弟。

30. 在森林的二叉树表示中，结点M和结点N是同一父结点的左儿子和右儿子，则在该森林中( )。

    A. M和N有同一双亲                                          B. M和N可能无公共祖先

    C.M是N的儿子                                                  D. M是N的左兄弟

【答案】B。在森林的二叉树表示中，当M和N的父结点是二叉树根结点时，M和N在不同的树上。因此M和N可能无公共祖先。