数据结构——二叉树相关练习题
一、单项选择题
1.下列关于二叉树的说法中，正确的是( )。 A.度为2的有序树就是二叉树 B.含有n个结点的二叉树的高度为Llog2n┘+ 1 C.在完全二叉树中，若一个结点没有左孩子，则它必是叶结点 D.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同
2.以下说法中，正确的是( )。 A.在完全二叉树中，叶子结点的双亲的左兄弟(若存在)一定不是叶子结点 B.任何一棵二叉树，叶子结点个数为度为2的结点数减1，即n0=n2- 1 C.完全二叉树不适合顺序存储结构，只有满二叉树适合顺序存储结构 D. 结点按完全二又树层序编号的二叉树中，第i个结点的左孩子的编号为2i
3.具有10个叶子结点的二叉树中有( )个度为2的结点。 A.8 B.9 C.10 D.11
4.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为()。 A. h B.2h- 1 C.2h+ 1 D.h+1
5.假设一棵二叉树的结点个数为50， 则它的最小高度是( )。 A. 4 B.5 C.6 D.7
6.设二叉树有2n个结点，且m<n，则不可能存在( )的结点。 A. n个度为0 B. 2m个度为0 C.2m个度为1 D. 2m个度为2
7.一个具有1025个结点的二叉树的高h为( )。 A.11 B.10 C.11 ~ 1025 D.10~ 1024
8.设二叉树只有度为0和2的结点，其结点个数为15， 则该二叉树的最大深度 为()。 A.4 B.5 C.8 D.9
9.高度为h的完全二叉树最少有( )个结点。 A.2^h B. 2^h+1 C.2^(h-1) D.2^h- 1
10.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则完全二叉树的结点个 数最少是()。 A.39 B.52 C.111 D.119
11.已知一棵完全二叉树的第6层(设根为第1 层)有8个叶结点，则该 完全二叉树的结点个数最多是( )。 A.39 B.52 C. 111 D. 119
12.若一棵深度为6的完全二叉树的第6层有3个叶子结点，则该二叉树共有( ) 个叶子结点。 A.17 B.18 C.19 D.20
13.一棵二叉树上有1001个结点，其中叶结点的个数是( )。 A.250 B.500 C.254 D.501
14.若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是( )。 A.257 B.258 C.384 D.385
15.若一棵二叉树有126个结点，在第7层(根结点在第1层)至多有()个结点。 A.32 B.64 C. 63 D.不存在第7层
16.一棵有124个叶子结点的完全二叉树，最多有( )个结点。 A.247 B.248 C.249 D.250 解析：在非空的二叉树当中，由度为0和2的结点数的关系n0=n2+1可知n2=123;总结点数n=no+n1+n2=247+n1，其最大值为248 (n 的取值为1或0，当n=1时结点最多)。另解: 124< 2^7= 128，故第8层没满，前7层为完全二叉树，由此可推算第8层可能有120个叶子结点，第7层的最右4个为叶子结点，考虑最多的情况，这4个叶子结点中的最左边可以有1个左孩子(不改变叶子结点数)，因此结点总数=2^7-1 + 120+ 1= 248。
17.一棵有n个结点的二叉树采用二叉链存储结点，其中空指针数为( )。 A. n B.n+1 C.n-1 D.2n
18.在一棵完全二叉树中，其根的序号为1, ( )可判定序号为p和q的两个结 点是否在同一层。 A. Llog2p」=Llog2q」 B. log2P = log2q C. Llog2p」+ 1 =Llog2q」 D. Llog2p」=Llog2q」+ 1
19.假定一棵三叉树的结点数为50，则它的最小高度为( )。 A.3 B.4 C.5 D.6
20.已知一棵有2011个结点的树，其叶结点个数是116, 该树对应的二叉树中无右孩子的结点个数是( )。 A.115 B. 116 C.1895 D. 1896
- 对于一棵满二叉树，共有n个结点和m个叶子结点，高度为h，则( )。
A. n=h+ m B.n+m=2h. C. m=h- 1 D. n=2h- 1
22.设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶 结点都有2个子结点。若T有k个叶结点，则T的结点总数是( )。 A.2k-1 B.2k C. k^2 D.2^k-1
