數(shù)據(jù)結(jié)構(gòu)（樹）習(xí)題與答案

一、單選題

1、樹最適合用來表示（）。

A.元素之間具有分支層次關(guān)系的數(shù)據(jù)

B.有序數(shù)據(jù)元素

C.元素之間無聯(lián)系的數(shù)據(jù)

D,無序數(shù)據(jù)元素

正確答案：A

2、在樹結(jié)構(gòu)中，若結(jié)點(diǎn)A有三個(gè)兄弟，且B是A的雙親，則B的度是（）。

A.5

B.4

C.3

D.2

正確答案：B

3、下列陳述中正確的是（）。

A.二叉樹是度為2的有序樹

B.二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分

C.二叉樹中每個(gè)結(jié)點(diǎn)最多只有兩棵子樹，并且有左右之分

D.二叉樹中必有度為2的結(jié)點(diǎn)

正確答案：C

4、設(shè)深度為h的二叉樹中只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含結(jié)點(diǎn)數(shù)

至少為（）。

A.2h-1

B.2h+1

C.h+1

D.2h

正確答案：A

解析：A、除根之外，每層只有兩個(gè)結(jié)點(diǎn)，且互為兄弟。

5、設(shè)深度為h的二叉樹中只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含結(jié)點(diǎn)數(shù)

至多為()O

A.2M

B.2h+1-l

C.2h4-l

D.2h+l

正確答案：A

解析：A、構(gòu)成完全二叉樹。

6、具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為()。

A.llog2(n)J+1

B.[log2(n)l

C.llog2(n)J

D.[log2(n)+1]

正確答案：A

7、具有32個(gè)結(jié)點(diǎn)的完全二叉樹有()個(gè)葉子結(jié)點(diǎn)。

A.16

B.14

C.15

D.17

正確答案：A

解析：A、對(duì)結(jié)點(diǎn)按層序編號(hào)，32號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為16，則17至32號(hào)結(jié)點(diǎn)

都為葉子，共16個(gè)。

8、一棵完全二叉樹的第6層上有23個(gè)葉子結(jié)點(diǎn)，則此二叉樹最多有()結(jié)點(diǎn)。

A.81

B.78

C.80

D.79

正確答案：A

解析：A、完全二叉樹的葉子結(jié)點(diǎn)只能在最下兩層，要使結(jié)點(diǎn)最多，這棵二叉樹深度

為7,前6層結(jié)點(diǎn)數(shù)共為63,第6層有32個(gè)結(jié)點(diǎn)，其中葉子為23個(gè)，非葉子為9個(gè),

它們的度都為2,第7層只有18個(gè)結(jié)點(diǎn)，故整棵二叉樹結(jié)點(diǎn)數(shù)為81.

9、具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。

A.6

B.3

C.5

D.4

正確答案：C

10、若一棵二叉樹有9個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)的個(gè)數(shù)為

（）。

A.15

B.10

C.9

D.不確定

正確答案：B

11、一棵二叉樹有35個(gè)結(jié)點(diǎn)，則所有結(jié)點(diǎn)的度之和為（）。

A.16

B.35

C.34

D.33

正確答案：C

12、二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以（）。

A.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)

B.順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)都不能使用

C.它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)

D.它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)

正確答案：A

13、用順序存儲(chǔ)的方法將n個(gè)結(jié)點(diǎn)的完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)依從左至右的次

序存放在一維數(shù)組R[l：n]中，若結(jié)點(diǎn)R[i]有左孩子，則左孩子是（）。

A.R[2i+2]

B.R[2i]

C.R[2i-l]

D.R[2i+l]

正確答案：B

14、一棵深度為k且只有k個(gè)結(jié)點(diǎn)的二叉樹按照完全二叉樹順序存儲(chǔ)的方式存放于一

個(gè)一維數(shù)組R[n]中，則n至少是（）才能確保正確存儲(chǔ)。

A.2k

B.2k+1

C.2k-l

D.2k

正確答案：C

15、以下存儲(chǔ)結(jié)構(gòu)中，不是樹的存儲(chǔ)結(jié)構(gòu)是（）。

A.孩子兄弟鏈表

B.雙親表示法

C.廣義表

D.孩子鏈表存儲(chǔ)結(jié)構(gòu)

正確答案：C

16、用二叉鏈表表示具有n個(gè)結(jié)點(diǎn)的二叉樹時(shí)，值為空的指針域的個(gè)數(shù)為（）。

A.n

B.n-1

C.2n

D.n+I

正確答案：D

17、二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定滿足的條件是

（）.

A.空或只有一個(gè)結(jié)點(diǎn)

B.任一結(jié)點(diǎn)無左孩子

C.高度等于其結(jié)點(diǎn)數(shù)

D.任一結(jié)點(diǎn)無右孩子

正確答案：C

18、下列二叉樹，其后序遍歷序列與層次遍歷序列相同的非空二叉樹是（）。

A.滿二叉樹

B.完全二叉樹

C.單支樹

D.只有根結(jié)點(diǎn)的二叉樹

正確答案：D

19、對(duì)二叉樹的結(jié)點(diǎn)從1開始連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右子女的編號(hào),

同一結(jié)點(diǎn)的左、右子女中，其左子女的編號(hào)小于其右子女的編號(hào)，則可采用（）遍

歷實(shí)現(xiàn)二叉樹的這種結(jié)點(diǎn)編號(hào)。

A.先序

B.中序

C.層序

D后序

正確答案：D

20、在二叉樹中有兩個(gè)結(jié)點(diǎn)m和n,如果m是n的祖先，使用（）非遞歸過程更方便

找到從m到n的路徑。

A.后序遍歷

B.先序遍歷

C.層次遍歷

D.中序遍歷

正確答案：A

21、不使用棧實(shí)現(xiàn)二叉樹后序遍歷的非遞歸算法，最佳方案是二叉樹的存儲(chǔ)結(jié)構(gòu)采用

（）表

A.三叉鏈表

B.廣義表

C.二叉鏈表

D.順序表

正確答案：A

22、在一個(gè)非空二叉樹的中序序列中，根結(jié)點(diǎn)的右邊是（）。

A.只有左子樹上的部分結(jié)點(diǎn)

B.只有左子樹上的所有結(jié)點(diǎn)

C.只有右子樹上的所有結(jié)點(diǎn)

D.只有右子樹上的部分結(jié)點(diǎn)

正確答案：C

23、設(shè)某棵二叉樹的中序遍歷序列為ABCD,先序遍歷序列為CABD,則后序遍歷該二

叉樹得到序列為（）。

A.CBDA

B.CDAB

C.BADC

D.BCDA

正確答案：C

24、先序遍歷序列為ABC,后序遍歷序列為CBA的二叉樹共有（）棵。

A.4

B.2

C.3

D.l

正確答案：A

25、若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換所有分支結(jié)點(diǎn)的左右子樹的位置，利用

基于（）遍歷的遞歸算法最合適。

A后序

B中序

C.層次

D.逆中序

正確答案：A

26、一棵二叉樹的先序遍歷序列為EFHIGJK,中序遍歷序列為HFIEJKG,則該二叉樹根

結(jié)點(diǎn)的右孩子為（）。

A.G

B.E

C.H

D.F

正確答案：A

27、一棵二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，根指針為t,下列遞歸算法求其先序序列

中第k（以右二叉樹中結(jié)點(diǎn)的個(gè)數(shù)）個(gè)結(jié)點(diǎn)的值，算法的畫線處應(yīng)填的語句是（）。

intn=l;〃全局變量

TElemTspePreNode（BiTNodeintk）

{TElemTypech;

if(t?NULL)return…；當(dāng)t-NULL時(shí)返回特殊字符一

if(n=k)retum(t->data);

ch=PreNode(t->lchilik):〃遍蘇左子樹

if(ch!=retum(ch);在左子樹中找到后返回

ch=PreNode(t->Tchild.k);遍歷右子樹

retum(ch):返回右子樹中的遍歷結(jié)果

A.n++

B.t=t->rchild

C.k—

D.t=t->lchild

正確答案：A

28、二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，根指針為t,下列遞歸算法求其葉子結(jié)點(diǎn)的個(gè)

數(shù),算法的畫線處應(yīng)填的語句是()O

intLeafNodes(BiTNode*t)

{intnuml.numn

if(t=NULL)return0;〃空二叉樹時(shí)

elseif()return1;

else

{numl=LeafNodes(t->lchild);

numr=LeafNodes(t->rchild);

return(numl+numr);

}

A.t->lchild==NULL&&t->rchild!=NULL

B.t->lchild==NULL&at->rchild==NULL

C.t->lchild==NULL

D.t->rchild==NULL

正確答案：B

29、判斷線索二叉鏈表中*p結(jié)點(diǎn)有右孩子結(jié)點(diǎn)的條件是()?

A.p->rchild!=NULL

B.p->rtag==l

C.p!=NULL

D.p->rtag==0

正確答案：D

30、將下圖所示的二叉樹按中序線索化，結(jié)點(diǎn)c的左指針與結(jié)點(diǎn)h的右指針分別指向

()。

A.a,g

B.a,c

C.h,g

D.g,c

正確答案：A

31、二叉樹線索化后，仍不能有效求解的問題是（）。

A.中序線索二叉樹中求中序前驅(qū)

B.中序線索二叉樹中求中序后繼

C.先序線索二叉樹中求先序后繼

D.后序線索二叉樹中求后序后繼

正確答案：D

32、基于中序線索化鏈表，其頭結(jié)點(diǎn)指針為head,對(duì)應(yīng)的二叉樹為空的判斷條件是

（）?

A.head->ltag==O

B.head==NULL

C.head->lchild==head&&head->rchild==head

D.head->rtag==l

正確答案：C

33、討論樹、森林和二叉樹的關(guān)系，目的是（）。

A.只是為了方便定義樹、森林的遍歷方法

B,將樹、森林轉(zhuǎn)化成二叉樹，統(tǒng)一邏輯表示形式

C.體現(xiàn)一種技巧，沒有什么實(shí)際意義

D.將樹、森林按二叉樹的存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，并利用二叉樹的算法解決樹與森林的有

關(guān)問題

正確答案：D

34、設(shè)森林F有3棵樹,分別有9、8和7個(gè)結(jié)點(diǎn)，則F此排列次序轉(zhuǎn)換成二叉樹后根

結(jié)點(diǎn)的右子樹上結(jié)點(diǎn)的個(gè)數(shù)是（）。

A.15

B.17

C.16

D.7

正確答案：A

35、如果二叉樹T2是由一棵樹T1轉(zhuǎn)換而來的二叉樹，那么T1結(jié)點(diǎn)的先根遍歷序列

對(duì)應(yīng)丁2的（）序列。

A.先序遍歷

B.中序遍歷

C.層次遍歷

D.后序遍歷

正確答案：A

36、給定一棵樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)，把這棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)

是（）。

A.唯一的

B.有多種，但根結(jié)點(diǎn)都沒有右孩子

C.有多種，但根結(jié)點(diǎn)都沒有左孩子

D.有多種

正確答案：A

37、由樹轉(zhuǎn)換成的二叉樹里，一個(gè)結(jié)點(diǎn)N的左孩子是N在原樹里對(duì)應(yīng)結(jié)點(diǎn)的（）。

A.最鄰近的左兄弟

B.最左孩子結(jié)點(diǎn)

C.最鄰近的右兄弟

D.最右孩子結(jié)點(diǎn)

正確答案：B

38、用13個(gè)權(quán)值構(gòu)造哈夫曼樹，則該哈夫曼樹共有（）個(gè)結(jié)點(diǎn)。

A.26

B.13

C.12

D.25

正確答案：D

39、對(duì)n（咫2）個(gè)權(quán)值不同的字符依哈夫曼算法構(gòu)造哈夫曼樹，下面關(guān)于該哈夫曼樹

的敘述中錯(cuò)誤的是（）。

A.樹中一定沒有度為1的結(jié)點(diǎn)

B.該樹一定是一棵完全二叉樹

C.樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)

D.樹中任何一個(gè)非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任意一個(gè)結(jié)點(diǎn)的權(quán)值

正確答案：B

40、設(shè)一組權(quán)值集合W=（2,4,5,7）,要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，

則這棵哈夫曼樹的帶權(quán)路徑長度為（