二叉树试题解析

一、单项选择题
01.下列关于二叉树的说法中，正确的是( C  ).
A.度为2的有序树就是二叉树
B.含有n个结点的二叉树的高度为
C.在完全二叉树中，若一个结点没有左孩子，则它必是叶结点
D.含有n个结点的完全二叉树的高度为
解析：A 二叉树中，若某结点只有一个孩子，则这个孩子的左右次序是确定的，而在度为2 的有序树中，若某节点只有一个孩子，则这个孩子就无需区分其左右次序
B仅当是完全二叉树时才有意义，对于任意一颗二叉树，高度可能为~n
C在完全二叉树中，若有度为1的结点，则只可能有一个，且该结点只有左孩子而没有右孩子
D完全二叉树的高度为或

02.“二叉树为空”意味着二叉树(  C ).
A.根结点没有子树                                         B.不存在
C.没有结点                                                    D.由一些没有赋值的空结点构成

03.以下说法中，正确的是（ A)。
A.在完全二叉树中，叶结点的双亲的左兄弟（若存在）一定不是叶结点
B.任何一棵二叉树中，叶结点数为度为2的结点数减1，即n0=n2-1
C.完全二叉树不适合顺序存储结构，只有满二叉树适合顺序存储结构
D.结点按完全二叉树层序编号的二叉树中，第i个结点的左孩子的编号为2i
解析：在完全二叉树中，叶结点的双亲的左兄弟的孩子一定在其前面（且一定存在)，所以双亲的左兄弟（若存在)一定不是叶结点，选项A正确。n应等于n2+ 1，选项B错误。完全二叉树和满二叉树均可以采用顺序存储结构，选项C错误。第i个结点的左孩子不一定存在，选项D错误。

04．具有10个叶结点的二叉树中有( B )个度为2的结点。
A.8                              B.9                                 C. 10                                D.11
解析：由二叉树的性质n0=n2+1,得n2=n0-1=10-1=9

05.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至
少为( B ).
A. h                              B.2h-1                           C. 2h+1                           D.h+1
解析：结点最少的情况如下图所示。除根结点层只有1个结点外，其他h-1层均有两个结点,点总数=2(h-1)+1= 2h-1。

06.具有n个结点且高度为n的二叉树的数目为( D )。
A.logn                          B.n/2                             C. n                                 D.2n-1
解析：除根结点外，在其余n -1个结点中，每个结点要么是其父结点的左孩子，要么是其父结点的右孩子，每个结点都有两种可能，n-1个结点共有2^n-1种不同的组合形态。

07．假设一棵二叉树的结点个数为50，则它的最小高度是（C).
A.4                                B.5                                C. 6                                D.7
解析：第一层1个，第二层2个，第三层4个，第四层8个，第五层16个，第六层50-31=19个

08．设二叉树有2n个结点，且m<n，则不可能存在（C)的结点。
A. n个度为0                  B.2m个度为0               C. 2m个度为1                 D. 2m个度为2
解析：由二叉树的性质1可知n0=n2+1,结点总数=2n=n0+n1+n2=n1+2n2+1,则n1=2(n-n2)-1,所以n1为奇数，说明该二叉树中不可能有2m个度为1的结点

09.一个具有1025个结点的二叉树的高h为( C )。
A.11                               B.10                              C.11 ~1025                    D.10~1024
解析：j当二叉树为单支树时具有最大高度，即每层上只有一个结点，最大高度为1025。而当树为完全二叉树时，其高度最小，最小高度为log2n+1= 11。

10.设二叉树只有度为0和2的结点，其结点个数为15，则该二叉树的最大深度为(  C  )
A.4                                 B.5                                C.8                                 D.9
解析：最大深度即第一层有一个结点，其余h-1层都有2个结点，结点总数=1+2(h-1)=15,h=8

11．高度为h的完全二叉树最少有(  C )个结点。
A.2^h                               B.2^h+1                          C. 2^(h-1)                              D.2^h-1

12.已知一棵完全二叉树的第6层（设根为第1层)有8个叶结点，则完全二叉树的结点
数最少是( A )。
A.39                               B.52                               C.111                             D.119
解析：第6层有叶结点说明完全二叉树的高度可能为6或7，显然树的高度为6时结点最少，若第六层有8个叶结点，则前面5层为满二叉树，所以完全二叉树的结点个数最少为2^5-1+8=39个结点

13.若一棵深度为6的完全二叉树的第6层有3个叶结点，则该二叉树共有(  A )个叶结点
A.17                               B.18                                C. 19                            D.20
解析：第五层共有2^4=16个结点，第六层的3个叶结点对应第五层最左边的两个结点，所以第五层剩下的14个结点都是叶结点，加上第六层的3个一共17个叶结点

14.一棵完全二叉树上有1001个结点，其中叶结点的个数是( D )。
A.250                             B.500                              C. 254                           D.501
解析：完全二叉树叶子结点>1001/2 

15．若一棵二叉树有126个结点，在第7层（根结点在第1层）至多有（ C )个结点。
A.32                              B．64                               C. 63                             D、不存在第7层
解析：第七层最多2^6-1 = 63个结点，七层满二叉树共2^7-1=127个结点 所以第七层只少一个结点

16.一棵有124个叶结点的完全二叉树,最多有（ B )个结点。
A.247                            B．248                            C.249                                D.250
解析：非空二叉树度为0和2的结点数关系n0=n2+1，n2=123,总结点数n=n0+n1+n2=124+n1+123,根据完全二叉树的特性，n1等于0或1，n1=1时结点最多，所以最多248个结点

17．一棵有n个结点的二叉树采用二叉链存储结点，其中空指针数为（ B )。
A. n                                B.n+1                              C. n-1                               D. 2n
解析：树中1个指针对应1个分支，n个结点的树共n-1个分支，即n-1个非空指针，每个结点都有两个指针域，所以空指针的个数为2n-(n-1)=n+1

18．设有n(n≥1)个结点的二叉树采用三叉链表表示，其中每个结点包含三个指针，分别
指向其左孩子、右孩子及双亲(若不存在，则置为空)，则下列说法中正确的是 （  A  )
Ⅰ树中空指针的数量为n+2
Ⅱ.所有度为2的结点均被三个指针指向
Ⅲ每个叶结点均被一个指针所指向
A. I                                B. I、Ⅱ                                C.I、Ⅲ                               D.II、Ⅲ
解析：二叉链表表示的二叉树空指针数量为n+1,三叉链表表示的二叉树多了一个根节点指向双亲的空指针，所以树中空指针的数量为n+2，Ⅰ正确。若根结点的度为2，则只有左右两个孩子指向它，Ⅱ错，若整棵树只有一个根结点，则没有指针指向它，Ⅲ错

19.在一棵完全二叉树中，其根的序号为1，( A ) 可判定序号为p和q的两个结点是否在同一层。

20.在一个用数组表示的完全二叉树中，根结点的下标为[i/2]，那么下标为17和19的结点的最近公共祖先的下标是( C ).
A.1                                 B.2                                 C.4                                   D.8
解析：下标为17的祖先有8、4、2、1。下标为19的祖先有9、4、2、1，最近的为4

21．假定一棵三叉树的结点数为50，则它的最小高度为( C ).
A.3                                 B.4                                C.5                                     D. 6
解析：假设满足条件的是一颗完全三叉树，这棵树第i层最多3^(i-1)个结点。第一层1个，第二层3个，第三层9个，第四层27个，总结点为50，第五层10个

22．具有n个结点的三叉树用三叉链表表示，则树中空指针域的个数为（ B )
A. 3n+ 1                         B.2n+1                          C.3n - 1                             D. 3n
解析：三叉树用三叉链表表示，每个结点均有3个指针域指向3个孩子，共有3n个指针域，n个结点构成的一棵树只需要n-1个指针，所以空指针域=3n-(n-1)=2n+1

23.对于一棵满二叉树，共有n个结点和m个叶结点，高度为h，则（ D )
A. n=h+m                       B. n+m=2h                    C. m=h-1                           D. n=2^h-1
解析：高度为h的二叉树总结点树n=2^0+2^1+...+2^(h-1)，m=2^(h-1)

24.【2009统考真题】已知一棵完全二叉树的第6层（设根为第1层)有8个叶结点，则该
完全二叉树的结点个数最多是( C ).
A. 39                               B.52                              C.111                                D.119
解析：完全二叉树的叶结点在最后两层，第六层8个叶结点，最多情况下第七层也有叶结点,缺少第六层的16个叶节点，结点个数最多为2^7-1-2*8=111

25.【2011统考真题】若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是(  C  )
A.257                              B.258                            C.384                               D.385
解析：最后一个分支结点的编号为[768/2]=384,所以叶结点的个数为768-384

26.【2018统考真题】设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结
点都有2个子结点。若T有k个叶结点，则T的结点总数是( A )。
A.2k-1                             B.2k                              C.R                                  D.2^k-1
解析：每个叶结点都有两个子结点，说明结点个数为奇数

27.【2020统考真题】对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元(仅存放结点的数据信息)，则存放该二叉树需要的存储单元数量至少是（A)。
A.31                                B.16                              C.15                                D. 10
解析：二叉树用顺序存储时需要用数组来表示结点间的父子关系，所以高度为5的二叉树，前五层的结点都要存起来，需要存储的数量为1+2+4+8+16=31，或2^5-1

28.【2022统考真题】若三叉树T中有244个结点(叶结点的高度为1)，则T的高度至少是( C )。
A.8                                  B.7                                C. 6                                 D.5
解析：高度为5的满三叉树的结点个数为1+3+9+27+81=121，所以至少要6层