資料結構——二叉樹相關練習題

一、單項選擇題

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

1. 對于一棵滿二叉樹，共有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