數(shù)據(jù)結(jié)構(gòu)第6章 樹和二叉樹

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)第6章樹和二叉樹

第6章樹和二叉樹

一、單項(xiàng)選擇題

1．樹最適合用來(lái)表示_______。

A．有序數(shù)據(jù)元素

B．無(wú)序數(shù)據(jù)元素

C．元素之間具有分支層次關(guān)系的數(shù)據(jù)D．元素之間無(wú)關(guān)系的數(shù)據(jù)2．以下存儲(chǔ)結(jié)構(gòu)中，不是樹的存儲(chǔ)結(jié)構(gòu)的是_______。

A．雙親存儲(chǔ)結(jié)構(gòu)B．孩子兄弟存儲(chǔ)結(jié)構(gòu)C．孩子鏈存儲(chǔ)結(jié)構(gòu)D．順序存儲(chǔ)結(jié)構(gòu)3．依照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有_______種。A．3

B．4

C．5D．6

4．若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)為______。

A．9C．15

B．11D．不確定

5．具有10個(gè)葉子結(jié)點(diǎn)的二叉樹中有_______個(gè)度為2的結(jié)點(diǎn)。A．8

C．10

B．9D．11

6．一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是_______。A．250B．500C．505D．5017．一棵高度為h的完全二叉樹至多有_______個(gè)結(jié)點(diǎn)。A．2h-1B．2h-1-1C．2h-1

8．深度為5的二叉樹至多有_______個(gè)結(jié)點(diǎn)。A．16C．31

B．32D．10D．2h

9．設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_______。

A．2h

C．2h+1

B．2h-1D．h+1

10．一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為_______。A．11B．10C．11~1025D．12~1024

11．對(duì)一棵滿二叉樹，共有n個(gè)結(jié)點(diǎn)和m個(gè)葉子結(jié)點(diǎn)，深度為h，則_______。A．n=h+m

C．m=h-1

B．h+m=2nD．n=2h-1

12．如圖7-1所示的二叉樹T2是由森林T1轉(zhuǎn)換而來(lái)的二叉樹，那么森林T1有

_______個(gè)葉子結(jié)點(diǎn)。

A．4B．5C．6D．7

圖7-1二叉樹T2

13．假使二叉樹T2是由有序二叉樹T1轉(zhuǎn)換而來(lái)的二叉樹，那么T1中結(jié)點(diǎn)的先

序就是T2中結(jié)點(diǎn)的_______。

A．先序B．中序C．后序

D．層次序

CDGIJFHBAE14．某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是_______。

A．空樹或只有一個(gè)結(jié)點(diǎn)C．二叉有序樹

B．完全二叉樹D．高度等于其結(jié)點(diǎn)數(shù)

15．在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_______。A．只有右子樹上的所有結(jié)點(diǎn)C．只有左子樹上的部分結(jié)點(diǎn)

B．只有右子樹上的部分結(jié)點(diǎn)D．只有左子樹上的所有結(jié)點(diǎn)

16．任何一棵二叉樹的葉子結(jié)點(diǎn)在先序，中序和后序遍歷序列中的相對(duì)次序_______。

A．不發(fā)生改變C．不能確定

B．發(fā)生改變D．以上都不對(duì)

17．設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是_______。

A．n在m右方C．n在m左方

B．n是m祖先D．n是m子孫

18．若二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)的左，右子樹位置，利用_______遍歷方法最適合。

A．先序C．后序

B．中序D．按層次

19．一棵二叉樹的先序遍歷序列為ABCDEFG，它的中序遍歷序列可能是_______。

A．CABDEFGC．DACEFBG

B．ABCDEFGD．ADCFEGB

20．一棵二叉樹的先序遍歷序列為ABCDEF，中序遍歷序列為CBAEDF，則后序遍歷序列為_______。

A．CBEFDAC．CBEDFA

B．FEDCBAD．不確定

21．一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則先序遍歷序列為_______。

A．ACFEDC．DEABC

B．DECABD．CEDBA

22．一棵二叉樹的先序遍歷序列為EFHIGJK，中序遍歷序列為HFIEJKG，則該二叉樹的根結(jié)點(diǎn)的右孩子為_______。

A．EC．G23．引入線索二叉樹的目的是_______。A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)的速度B．為了能在二叉樹的中便利插入和刪除C．為了能便利找到雙親D．使二叉樹的遍歷結(jié)果唯一24．線索二叉樹是一種_______結(jié)構(gòu)。A．規(guī)律C．物理

B．FD．H

B．規(guī)律和存儲(chǔ)D．線性

25．判斷線索二叉樹中*P結(jié)點(diǎn)有右孩子結(jié)點(diǎn)的條件是_______A．P!=NULLC．P->rtag==0

B．P->rchild!=NULLD．P->rtag==1

26．n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為_______。A．2nC．n+1

B．n-1D．n

27．二叉樹在線索后，仍不能有效求解的問(wèn)題是_______。A．先序線索二叉樹中求先序后繼B．中序線索二叉樹中求中序后繼C．中序線索二叉樹中求中序前驅(qū)D．后序線索二叉樹中求后序后繼

28．根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是_______。A．111,110,10,01,00C．100,11,10,1,0

B．000,001,010,011,1D．001,000,01,11,10

29．根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是_______。A．000,001,010,011,1B．0000,0001,001,01,1C．000,001,01,10,11D．10,100,101,110,111

30．設(shè)有13個(gè)值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有_______個(gè)結(jié)點(diǎn)。

A．13C．26

B．12D．25

二、填空題

1．樹中任意結(jié)點(diǎn)允許有_____________孩子結(jié)點(diǎn)，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)_________雙親結(jié)點(diǎn)。

2．若一棵樹的括號(hào)表示為A(B(E,F),C(G(H,I,J,K),L),D(M(N))),則該樹的度為___________,樹的深度為___________，樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為___________。3．在一棵完全二叉樹中，結(jié)點(diǎn)個(gè)數(shù)為n，則編號(hào)最大的分支結(jié)點(diǎn)的編號(hào)為_______。4．在一棵完全二叉樹中，編號(hào)i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是___________。5．在一棵總結(jié)點(diǎn)數(shù)為偶數(shù)的完全二叉樹中，葉子結(jié)點(diǎn)數(shù)為k，最終一層結(jié)點(diǎn)數(shù)大于2，則該二叉樹的高度為_________________。

6．具有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)，共有___________個(gè)空指針域。7．在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0=__________。

8．深度為h的完全二叉樹至少有________個(gè)結(jié)點(diǎn)，至多有________個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開始），則第h層中編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是_________。

9．一棵二叉樹的第i(i>=1)層最多有________個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有_________個(gè)葉子結(jié)點(diǎn)和__________個(gè)非葉子結(jié)點(diǎn)。

10．n個(gè)結(jié)點(diǎn)的二叉樹中假使有m個(gè)樹葉，則一定有_______個(gè)度為1的結(jié)點(diǎn),_________個(gè)度為2的結(jié)點(diǎn)。

11．8層完全二叉樹子至少有________個(gè)結(jié)點(diǎn)，擁有100個(gè)結(jié)點(diǎn)的完全二叉樹的最大層數(shù)為____________。

12．在二叉樹中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是________。