二叉树试题解析

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

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层