填空選擇題庫(抓緊看)

1、6選4填*20套一、選擇題（單選）1-1. 完全二叉樹_B_二叉樹。A.一定是滿 B.可能是滿 C.不是 D.一定不是滿答案：B 難度：易1-2滿二叉樹_A_二叉樹。A.一定是完全 B.可能是完全 C.不是 D.一定不是完全 答案：A 難度：易1-3完全二叉樹中，若某個結(jié)點(diǎn)沒有左孩子，則它_C_。 A. 有2個右孩子 B. 一定有右孩子 C. 一定沒有右孩子 D. 不一定有右孩子 答案：C 難度：中2. 設(shè)一個完全二叉樹共有699個結(jié)點(diǎn)，則在該二叉樹中的葉子結(jié)點(diǎn)數(shù)為_。A.349 B.350 C.255 D.3513.深度為n的完全二叉樹的葉子結(jié)點(diǎn)有_A.n B.2n C.2n D. 2n-1

2、4.在一棵完全二叉樹中，若編號為i的結(jié)點(diǎn)存在左子女，則左子女結(jié)點(diǎn)的編號為_C_A.2i B.2i-1 C.2i+1 D.2i+2 5.在有n個結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，空指針數(shù)為（ b ）。    a.不定         b.n+1          c.n            d.n-1

3、6.下列二叉樹中，（ a    ）可用于實(shí)現(xiàn)符號不等長高效編碼。 a.最優(yōu)二叉樹      b.次優(yōu)查找樹      c.二叉平衡樹 d.二叉排序樹7具有m個結(jié)點(diǎn)的二叉排序樹，其最大深度為（ f ），最小深度為（ b ）。 a. log 2 m        b. log2 m +1     c. m/2 d . m/2 -1  

4、0;  e. m/2     一、單項(xiàng)選擇題(1)-(5)BBCDC (6)-(10)BCABC (11)(15)DABBD (16)-(19)CCABB(20)-(24) BBBAC (25)-(27)DBC二、填空題（1）有零個或多個 （2）有且僅有一個（3）根據(jù)樹的廣義表表示，可以畫出這棵村，該樹的度為4。（4）樹的深度為4(5)樹中葉子結(jié)點(diǎn)個數(shù)為8（6）n0=14 (7)n-2m+1 (8)2k-1 (9)2i-1 (10)133 (11)59(12)25=32 (13)élog2(n+1)ù=élog26

5、9ù=7 (14) 25-1+6=37 (15) 19(16)27-1-20=107 (17)右 （18）m+1 (19)n+1 (20) 2m-1 (21)中序 （22）直接前驅(qū)結(jié)點(diǎn) （23）直接后繼結(jié)點(diǎn)1關(guān)于二叉樹的下列說法正確的是 B 。 (1)：A二叉樹的度為2 B二叉樹的度可以小于2 C每一個結(jié)點(diǎn)的度都為2 D至少有一個結(jié)點(diǎn)的度為2 2設(shè)深度為h(h>0)的二叉樹中只有度為0和度為2的結(jié)點(diǎn)，則此二叉樹中所含的結(jié)點(diǎn)總數(shù)至少為 B 。 (2)A2h B2h-1 C2h+1 Dh+1 3在樹中，若結(jié)點(diǎn)A有4個兄弟，而且B是A的雙親，則B的度為 (3) 。 (3)：A3 B4

6、 C5 D6 4若一棵完全二叉樹中某結(jié)點(diǎn)無左孩子，則該結(jié)點(diǎn)一定是 D 。 A.度為1的結(jié)點(diǎn) B度為2的結(jié)點(diǎn) C分支結(jié)點(diǎn) D葉子結(jié)點(diǎn) 5深度為k的完全二叉樹至多有 C 個結(jié)點(diǎn)，至少有 B 個結(jié)點(diǎn)。 A2k-1-1 B2k-1 C2k-1 D2k 6前序序列為ABC的不同二叉樹有 (7) 種不同形態(tài)。 (7)：A3 B4 C5 D6 7若二叉樹的前序序列為DABCEFG，中序序列為BACDFGE，則其后序序列為 (8) ，層次序列為 (9) 。 (8)-(9)：ABCAGFED BDAEBCFG CABCDEFG DBCAEFGD 8在具有200個結(jié)點(diǎn)的完全二叉樹中，設(shè)根結(jié)點(diǎn)的層次編號為1，則層次

7、編號為60的結(jié)點(diǎn)，其左孩子結(jié)點(diǎn)的層次編號為 (10) ，右孩子結(jié)點(diǎn)的層次編號為 (11) ，雙親結(jié)點(diǎn)的層次編號為 (12)。 (10)-(12)：A30 B60 C120 D121 9遍歷一棵具有n個結(jié)點(diǎn)的二叉樹，在前序序列、中序序列和后序序列中所有葉子結(jié)點(diǎn)的相對次序 (13) 。 (13)：A.都不相同 B完全相同 C前序和中序相同 D中序與后序相同 10在由4棵樹組成的森林中，第一、第二、第三和第四棵樹組成的結(jié)點(diǎn)個數(shù)分別為30，10，20，5，當(dāng)把森林轉(zhuǎn)換成二叉樹后，對應(yīng)的二叉樹中根結(jié)點(diǎn)的左子樹中結(jié)點(diǎn)個數(shù)為 （14） ，根結(jié)點(diǎn)的右子樹中結(jié)點(diǎn)個數(shù)為 (15) 。 (14)(15)：A20 B

8、29 C30 D35 11.具有n個結(jié)點(diǎn)(n>1)的二叉樹的前序序列和后序序列正好相反，則該二叉樹中除葉子結(jié)點(diǎn)外每個結(jié)點(diǎn) (16) 。 (16)：A.僅有左孩子 B僅有右孩子 C僅有一個孩子 D都有左、右孩子 12判斷線索二叉樹中p結(jié)點(diǎn)有右孩子的條件是 (17) 。 (17)：A.p!=NULL Bp->rchild!=NULL Cp->rtag=0 Dp->rtag=1 13將一棵樹轉(zhuǎn)換成二叉樹，樹的前根序列與其對應(yīng)的二叉樹的 (18) 相等。樹的后根序列與其對應(yīng)的二叉樹的 (19)相同。(18)(19)：A前序序列 B中序序列 C后序序列 D層次序列14設(shè)數(shù)據(jù)結(jié)構(gòu)(

9、D，R)，D=dl，d2，d3，d4，d5，d6，R=<d4，d2>，<d2，d1>，<d2，d3>，<d4，d6>，<d6，d5>，這個結(jié)構(gòu)的圖形是 (20) ；用 (21) 遍歷方法可以得到序列d1，d2，d3，d4，d5，d6。 (20)：A線性表 B二叉樹C隊(duì)列 D棧 (21)：人前序 B中序 C后序 D層次 15對于樹中任一結(jié)點(diǎn)x，在前根序列中序號為pre(x)，在后根序列中序號為post(x)，若樹中結(jié)點(diǎn)x是結(jié)點(diǎn)y的祖先，下列 （22） 條件是正確的。 (22)：A.pre(x)<pre(y)且post(x)<

10、post(y) Bpre(x)<pre(y)且post(x)>post(y) C. pre(x)>pre(y)且post(x)<post(y) Dpre(x)>pre(y)且post(x)>post(y) 16每棵樹都能惟一地轉(zhuǎn)換成對應(yīng)的二叉樹，由樹轉(zhuǎn)換的二叉樹中，一個結(jié)點(diǎn)N的左孩子是它在原樹對應(yīng)結(jié)點(diǎn)的 (23) ，而結(jié)點(diǎn)N的右孩子是它在原樹里對應(yīng)結(jié)點(diǎn)的 (24) 。 (23)(24)：A最左孩子 B最右孩子 C右鄰兄弟 D左鄰兄弟17二叉樹在線索化后，仍不能有效求解的問題是 (25) 。(25)：A前序線索樹中求前序直接后繼結(jié)點(diǎn) B中序線索樹中求中序直接前

11、驅(qū)結(jié)點(diǎn) C中序線索樹中求中序直接后繼結(jié)點(diǎn) D后序線索樹中求后序直接后繼結(jié)點(diǎn) 18一棵具有124個葉子結(jié)點(diǎn)的完全二叉樹，最多有 (26)個結(jié)點(diǎn)。 (26)：A247 B248 C249 D250 。 19實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最有效的存儲結(jié)構(gòu)是采用 （27） 。 (27)：A. 二叉鏈表 B孩子鏈表 C三叉鏈表 D順序表3二叉樹后序遍歷的次序是什么？ （ ）A 根、左子樹、右子樹 B左子樹、根、右子樹C 左子樹、右子樹、根 D根、右子樹、左子樹FEDBAC4已給如圖二叉樹，它的中序遍歷是哪一項(xiàng)？ （ ）AABECDF BABCDEF CCBDAEF DCDBFEA6

12、已知完全二叉樹有26個結(jié)點(diǎn)，則整棵二叉樹有多少個度為1的結(jié)點(diǎn)？ （ ）A1 B0 C2 D不確定1 以下說法錯誤的是 ( )A.樹形結(jié)構(gòu)的特點(diǎn)是一個結(jié)點(diǎn)可以有多個直接前趨B.線性結(jié)構(gòu)中的一個結(jié)點(diǎn)至多只有一個直接后繼C.樹形結(jié)構(gòu)可以表達(dá)(組織)更復(fù)雜的數(shù)據(jù)D.樹(及一切樹形結(jié)構(gòu))是一種"分支層次"結(jié)構(gòu)任何只含一個結(jié)點(diǎn)的集合是一棵樹2，以下說法錯誤的是 ( ) A.二叉樹可以是空集B.二叉樹的任一結(jié)點(diǎn)都有兩棵子樹C.二叉樹與樹具有相同的樹形結(jié)構(gòu)D.二叉樹中任一結(jié)點(diǎn)的兩棵子樹有次序之分3、以下說法錯誤的是 ( )A.完全二叉樹上結(jié)點(diǎn)之間的父子關(guān)系可由它們編號之間的關(guān)系來表達(dá)B.在

13、三叉鏈表上，二叉樹的求雙親運(yùn)算很容易實(shí)現(xiàn)C.在二叉鏈表上，求根，求左、右孩子等很容易實(shí)現(xiàn)D.在二叉鏈表上，求雙親運(yùn)算的時間性能很好4、以下說法錯誤的是 ( ) A.一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近B.哈夫曼樹中沒有度數(shù)為1的分支結(jié)點(diǎn)C.若初始森林中共有n裸二叉樹，最終求得的哈夫曼樹共有2n-1個結(jié)點(diǎn)D.若初始森林中共有n裸二叉樹，進(jìn)行2n-1次合并后才能剩下一棵最終的哈夫曼樹5深度為6的二叉樹最多有( )個結(jié)點(diǎn) ( )A.64 B.63 C.32 D.316將含有83個結(jié)點(diǎn)的完全二叉樹從根結(jié)點(diǎn)開始編號，根為1號，后面按從上到下、從左到右的順序?qū)Y(jié)點(diǎn)編號，那么編號為41的雙結(jié)點(diǎn)編號為

14、 ( )A.42 B.40 C.21 D.207任何一棵二叉樹的葉結(jié)點(diǎn)在其先根、中根、后跟遍歷序列中的相對位置 ( ) A.肯定發(fā)生變化 B.有時發(fā)生變化C.肯定不發(fā)生變化 D.無法確定8設(shè)二叉樹有n個結(jié)點(diǎn)，則其深度為 ( )A.n-1 B.n C.5floor(log2n) D.無法確定9設(shè)深度為k的二叉樹上只有度為0和度為2的節(jié)點(diǎn)，則這類二叉樹上所含結(jié)點(diǎn)總數(shù)最少（ ）個A.k+1 B.2k C.2k-1 D.2k+110.下列說法正確的是 ( )A.樹的先根遍歷序列與其對應(yīng)的二叉樹的先根遍歷序列相同B.樹的先根遍歷序列與其對應(yīng)的二叉樹的后根遍歷序列相同C.樹的后根遍歷序列與其對應(yīng)的二叉樹的

15、先根遍歷序列相同D.樹的后根遍歷序列與其對應(yīng)的二叉樹的后根遍歷序列相同11下列說法中正確的是 ( )A.任何一棵二叉樹中至少有一個結(jié)點(diǎn)的度為2B.任何一棵二叉樹中每個結(jié)點(diǎn)的度都為2C.任何一棵二叉樹中的度肯定等于2D.任何一棵二叉樹中的度可以小于212一棵二叉樹滿足下列條件：對任意結(jié)點(diǎn)，若存在左、右子樹，則其值都小于它的左子樹上所有結(jié)點(diǎn)的值，而大于右子樹上所有結(jié)點(diǎn)的值?，F(xiàn)采用（ ）遍歷方式就可以得到這棵二叉樹所有結(jié)點(diǎn)的遞增序列。A.先根 B.中根 C.后根 D.層次13設(shè)森林T中有4棵樹，第一、二、三、四棵樹的結(jié)點(diǎn)個數(shù)分別是n1,n2,n3,n4,那么當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹后，且根結(jié)點(diǎn)的右

16、子樹上有（ ）個結(jié)點(diǎn)。A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n4 14森林T中有4棵樹，第一、二、三、四棵樹的結(jié)點(diǎn)個數(shù)分別是n1,n2,n3,n4,那么當(dāng)把森林T轉(zhuǎn)換成一棵二叉樹后，且根結(jié)點(diǎn)的左孩子上有（ ）個結(jié)點(diǎn)。A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n415.對含有（ ）個結(jié)點(diǎn)的非空二叉樹，采用任何一種遍歷方式，其結(jié)點(diǎn)訪問序列均相同。A.0 B.1 C.2 D.不存在這樣的二叉樹16討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）A.借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對樹的一些運(yùn)算B.將樹、森林按二叉樹的存儲方式進(jìn)行存儲C.將樹、森林轉(zhuǎn)換成二叉樹D.體

17、現(xiàn)一種技巧，沒有什么實(shí)際意義 17如圖選擇題17所示二叉樹的中序遍歷序列是（ ）A.abcdgef B. dfebagc C.dbaefcg D.defbagc18.已知某二叉樹的后續(xù)遍歷序列是dabec,中序遍歷序列是deabc,它的前序遍歷序列是（ ）A.acbed B.deabc C.decab D.cedba19.如果T2是由有序樹T轉(zhuǎn)化而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的（ ）A.前序 B.中序 C.后序 D.層次序20如果T2是由有序樹T轉(zhuǎn)化而來的二叉樹，那么T中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的（ ）A.前序 B.中序 C.后序 D.層次序21某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是

18、abdgcefh,中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問順序是 （ ）A.bdgcefha B.gdbecfha C.D. bdgechfa D. gdbehfca22.在圖選擇題22中的二叉樹中，（ ）不是完全二叉樹。 23、二叉樹的前序遍歷序列中，任意一個結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法 ( )A.正確 B.錯誤24、由于二叉樹中每個結(jié)點(diǎn)的度最大為2，所以二叉樹是一種特殊的樹，這種說法 ( )A.五確 B.錯誤25，二叉樹是每個結(jié)點(diǎn)的度不超過2的有序樹的特殊情況，這種說法 ( )A.正確 B.錯誤26·樹最適合用來表示 ( )A.有序數(shù)據(jù)元素 B.無

19、序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)27，深度為5的二叉樹至多有( )個結(jié)點(diǎn)。A.16 B.32 C.31 D.1028、在計(jì)算遞歸函數(shù)時，如不使用遞歸過程，則一般情況下必須借助于（ ）數(shù)據(jù)結(jié)構(gòu)A.棧 B.樹 C.雙向隊(duì)列 D.順序表29.堆(Heap)是 ( )A.完全二叉樹 B.線性表 C.滿二叉樹30、下列說法中正確的是 ( )A.二叉樹中任何一個結(jié)點(diǎn)的度都為2 B.二叉樹的度為2C.任何一棵二叉樹中至少有一個結(jié)點(diǎn)的度為2 D.一棵二叉樹的度可以小于231、設(shè)二叉樹根結(jié)點(diǎn)的層次為0，一棵高度為h的滿二叉樹中的結(jié)點(diǎn)個數(shù)是（ ）A.2h B.2h-1 C.2

20、h-1 D.2h+1-132、設(shè)二叉樹結(jié)點(diǎn)的先根序列、中根序列和后根序列中，所有葉子結(jié)點(diǎn)的先后順序( )A.都不相同 B.完全相同 C.先序和中序相同，而與后序不同 D.中序和后序相同，而與先序不同33·以下說法錯誤的是 ( )A.存在這樣的二叉樹，對它采用任何次序的遍歷，其結(jié)點(diǎn)訪問序列均相同B.二叉樹是樹的特殊情形C.由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的D.在二叉樹只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹34、以下說法正確的是 ( )A.先根遍歷樹和前序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同B.后根遍歷樹和前序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同C.前序遍歷森林和前

21、序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果相同D.后序遍歷森林和中序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果不同35·以下說法正確的是 ( )A.一般來說，若深度為k的n個結(jié)點(diǎn)的二叉樹具有最小路徑長度，那么從根結(jié)點(diǎn)到第k-1層具有最多的結(jié)點(diǎn)數(shù)為2k-1-1余下的n-2k-1+1個結(jié)點(diǎn)在第k層的任一位置上B.若有一個結(jié)點(diǎn)是某二叉樹子樹的前序遍歷序列中的最后一個結(jié)點(diǎn)，則它必是該子樹的前序遍歷序列中的最后一個結(jié)點(diǎn)。C.若一個結(jié)點(diǎn)是某二叉樹子樹的前序遍歷序列中的最后一個結(jié)點(diǎn)，則它必是該子樹的中序遍歷序列中的最后一個結(jié)點(diǎn)。D.在二叉樹中插人結(jié)點(diǎn)，該二叉樹便不再是二叉樹36、以下說法正確的是 ( )A.若一個樹

22、葉是某二叉樹子樹的前序遍歷序列中的最后一個結(jié)點(diǎn)，則它必是該子樹的前序遍歷序列中的最后一個結(jié)點(diǎn)。B.若一個樹葉是某二叉樹子樹的前序遍歷序列中的最后一個結(jié)點(diǎn)，則它必是該子樹的中序離歷序列中的最后一個結(jié)點(diǎn)C.二叉樹中，具有兩個子女的父結(jié)點(diǎn)，在中序遍歷序列中，它的后繼結(jié)點(diǎn)最多只能有一個子女結(jié)點(diǎn)。D.在二叉樹中，具有一個子女結(jié)點(diǎn)，在中序遍歷序列中，它沒有后繼子女結(jié)點(diǎn)。37、以下說法錯誤的是 ( )A.哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。B.若一個二叉樹的樹葉是某子樹的中序遍歷序列中的第一個結(jié)點(diǎn)，則它必是該子樹的后序遍歷序列中的第一個結(jié)點(diǎn)。C.已知二叉樹的前序遍歷和后序遍歷序列并

23、不能惟一地確定這棵樹，因?yàn)椴恢罉涞母Y(jié)點(diǎn)是哪一個。D.在前序遍歷二叉樹的序列中，任何結(jié)點(diǎn)的子樹的所有結(jié)點(diǎn)都是直接跟在該結(jié)點(diǎn)的之后。6.深度為6(根的層次為1)的二叉樹至多有（D ）結(jié)點(diǎn)。 A) 64     B) 32        C) 31      D) 637.將含100個結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層上從左到右依次堆結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為1。編號為49的結(jié)點(diǎn)X的雙親的編號為（ A ）。 A) 24  

24、60;     B) 25        C) 23       D) 無法確定15.設(shè)深度為k的二叉樹上只有度為0和2的結(jié)點(diǎn)，則此類二叉樹中所含的結(jié)點(diǎn)數(shù)至少為（ C ）。 A) k + 1      B) 2k        C) 2k - 1     D) 2k + 15.&

25、#160;    樹最適合用來表示( C )。 A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)6.     二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為( D ). A2k-1 B.2K+1 C.2K-1 D. 2k-14、由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ B ） A 24 B 71 C 48 D 5310在一棵度為3的樹中,度為3的結(jié)點(diǎn)個數(shù)為2,度為2 的結(jié)點(diǎn)個數(shù)為1,則度為0的結(jié)點(diǎn)個數(shù)為( C ) A4 B5 C6 D74二叉樹中第i(i1

26、)層上的結(jié)點(diǎn)數(shù)最多有（ C ）個。(A) 2i(B) 2i(C) 2i-1(D) 2i-19根據(jù)二叉樹的定義可知二叉樹共有（ B ）種不同的形態(tài)。(A) 4(B) 5(C) 6(D) 72設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（ B ）個空指針域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m4設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ A ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA6設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為（ C ）。(A) 9(B) 1

27、0(C) 11(D) 126設(shè)二叉排序樹中有n個結(jié)點(diǎn)，則在二叉排序樹的平均查找長度為（ B ）。(A) O(1)(B) O(log2n)(C)(D) O(n2)2設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（ D ）個結(jié)點(diǎn)。(A) 2k-1(B) 2k(C) 2k-1(D) 2k-19設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（ C ）。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1(D) N0=2N1+l6設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（ B ）。(

28、A) Nl+N2+Nm(B) l+N2+2N3+3N4+(m-1)Nm(C) N2+2N3+3N4+(m-1)Nm(D) 2Nl+3N2+(m+1)Nm5設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ D ）。(A) 空或只有一個結(jié)點(diǎn)(B) 高度等于其結(jié)點(diǎn)數(shù)(C) 任一結(jié)點(diǎn)無左孩子(D) 任一結(jié)點(diǎn)無右孩子7設(shè)某棵三叉樹中有40個結(jié)點(diǎn)，則該三叉樹的最小高度為（ B ）。(A) 3(B) 4(C) 5(D) 610. 深度為k的完全二叉樹中最少有（ B ）個結(jié)點(diǎn)。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D) 2k-114.設(shè)二叉排序樹上有n個結(jié)點(diǎn)，則在二叉

29、排序樹上查找結(jié)點(diǎn)的平均時間復(fù)雜度為（ D ）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)5設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為（ B ）。(A) 2i+1(B) 2i(C) i/2(D) 2i-18設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有（ C ）。(A) 20(B) 256(C) 512(D) 10245.        在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為（ B ）。(A) O(n)(B) O(

30、1og2n)(C) O(nlog2n)(D) O(n2)7.        設(shè)一棵完全二叉樹中有65個結(jié)點(diǎn)，則該完全二叉樹的深度為（ B ）。(A) 8(B) 7(C) 6(D) 58.        設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點(diǎn)，2個度數(shù)為2的結(jié)點(diǎn)，2個度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（ C ）個度數(shù)為0的結(jié)點(diǎn)。(A) 5(B) 6(C) 7(D) 83設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N

31、1、N2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為（ A ）。 (A) N1-1(B) N2-1(C) N2+N3(D) N1+N39設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（ C ）個。(A) 4(B) 5(C) 6(D) 76設(shè)一棵m叉樹中有N1個度數(shù)為1的結(jié)點(diǎn)，N2個度數(shù)為2的結(jié)點(diǎn)，Nm個度數(shù)為m的結(jié)點(diǎn)，則該樹中共有（ D ）個葉子結(jié)點(diǎn)。(A) (B) (C) (D) 7. 二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（ A ）根結(jié)點(diǎn)的值。(A) <(B) >(C) =(D) !=8. 設(shè)一組權(quán)值集合W=(

32、15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（ D ）。(A) 129(B) 219(C) 189(D) 22910.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（ C ）個結(jié)點(diǎn)。(A) 2n(B) n+l(C) 2n-1(D) 2n+l 1假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15個，單分支結(jié)點(diǎn)數(shù)為32個，則葉子結(jié)點(diǎn) 數(shù)為_。A15 B16 C17 D47 答案：B2假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18個，則它的最小高度_。A4 B5 C6 D18 答案：B3在一棵二叉樹中第五層上的結(jié)點(diǎn)數(shù)最多為_。A

33、8 B15 C16 D32 答案：C4在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)總數(shù)為_。A31 B32 C33 D16 答案：A5已知8個數(shù)據(jù)元素為(34、76、45、18、26、54、92、65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹后，最后兩層上的結(jié)點(diǎn)總數(shù)為_。A1 B2 C3 D4 答案：B6 由分別帶權(quán)為9、2、5、7的四個葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為_。A23 B37 C44 D46 答案：C7、在樹中除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)分成m(m0)個_的集合T1,T2,T3.Tm,每個 集合又都是樹，此時結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)(1im)。A互不相交 B可以相交

34、C葉結(jié)點(diǎn)可以相交 D樹枝結(jié)點(diǎn)可以相交 答案：A8、下面答案_是查找二叉樹（又稱二叉排序樹）。A二叉樹中的每個結(jié)點(diǎn)的兩棵子樹的高度差的絕對值不大于。B二叉樹中的每個結(jié)點(diǎn)的兩棵子樹的高度差等于。C二叉樹中的每個結(jié)點(diǎn)的兩棵子樹是有序的。D二叉樹中的每個結(jié)點(diǎn)的關(guān)鍵字大于其左子樹（如果存在）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右子樹（如果存在）所有結(jié)點(diǎn)的關(guān)鍵字值。答案：D9、如果結(jié)點(diǎn)A有三個兄弟，而且B是A的雙親，則B的出度是_。A3 B4 C5 D1 答案：B10、一個深度為L的滿K叉樹有如下性質(zhì)：第L層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每 個結(jié)點(diǎn)都有K棵非空子樹。如果按層次順序從開始對全部結(jié)點(diǎn)編號，編號為n的

35、有右兄弟的條件是_。A(n-1) % k= =0 B(n-1) % k!=0 Cn % k= =0 Dn % k!=0 答案：B11、在完全二叉樹中，當(dāng)i為奇數(shù)且不等于時，結(jié)點(diǎn)i的左兄弟是結(jié)點(diǎn)_，否則沒有左兄弟。A2i-1 Bi+1 C2i+1 Di-1 答案：D12、某二叉樹T有n個結(jié)點(diǎn)，設(shè)按某種遍歷順序?qū)中的每個結(jié)點(diǎn)進(jìn)行編號，編號值為1,2,n且有如下性質(zhì)：T中任一結(jié)點(diǎn)V，其編號等于左子樹上的最小編號減1，而V的右子樹 的結(jié)點(diǎn)中，其最小編號等于V左子樹上結(jié)點(diǎn)的最大編號加1。這時按_編號。A中序遍歷序列 B前序遍歷序列 C后序遍歷序列 D層次遍歷序列 答案：B13、最小代價生成樹_。A是唯

36、一的。 B不是唯一的。 C唯一性不確定。 D唯一性與原因的邊的權(quán)數(shù)有關(guān)。 答案：D14、將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時,通常需要使用_。A棧 B隊(duì)列 C鏈表 D樹 答案：A6、在二叉樹的第4層上至多有多少個結(jié)點(diǎn)： A. 10個 B. 8個 C. 16個 D. 以上都不是。 答案：B7、若一棵二叉樹具有8個度為2的結(jié)點(diǎn)，則該二叉樹的葉子個數(shù)是（ ）A. 9 B. 11 C. 7 D. 不確定 答案：A6、在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加( )。A. 2 B. -1 C. 0 D. 1 答案：D9、某二叉樹進(jìn)行前序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則

37、后序遍歷的結(jié)果為（ ）。A. DBFEAC B. DFEBCAC. BDFECA D. BDEFAC 答案：B1. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種： A）一對多關(guān)系 B）多對多關(guān)系 C）多對一關(guān)系 D）一對一關(guān)系. 答案：（ B ）1. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個結(jié)點(diǎn)的二叉樹鏈表中只有_個非空指針域。A. n B. n-1 C. n+1 D. n+2 答案：B 3. 二叉樹中每個結(jié)點(diǎn)的兩棵子樹是_的。 A. 有序 B. 無序 C. 不確定 D.相同 答案：A9. 用二叉鏈表法（link-rlink）存儲包含n個結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個指針區(qū)域中有n+1個空指針。A. n B.

38、n+2 C. n+1 D. n-1 答案：D 1 不含任何結(jié)點(diǎn)的空樹 。 ）是一棵樹; ）是一棵二叉樹; ）是一棵樹也是一棵二叉樹; ）既不是樹也不是二叉樹 答案：C 2二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。 ）它不能用順序存儲結(jié)構(gòu)存儲; ）它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲; ）順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲; ）順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用 答案：C 4把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是 。 ）唯一的 ）有多種 ）有多種，但根結(jié)點(diǎn)都沒有左孩子 ）有多種，但根結(jié)點(diǎn)都沒有右孩子 答案：A 二、填空題7.        二

39、叉樹是指度為2的_有序_樹。一棵結(jié)點(diǎn)數(shù)為n的二叉樹，其所有結(jié)點(diǎn)的度的總和是_n-1_。9.        對于一棵具有n個結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_2n _個，其中_n-1_個用于指向孩子，_n+1_個指針是空閑的。10.    若對一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點(diǎn)存儲到A0中。其余類推，則A i 元素的左孩子元素為_2i+1_,右孩子元素為_2i+2_，雙親元素為_(i-1)/2_。3.  &#

40、160;      設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_n_次。5.         設(shè)一棵m叉樹脂的結(jié)點(diǎn)數(shù)為n，用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有_ n(m-1)+1_個空指針域。13.     下面程序段的功能是建立二叉樹的算法，請?jiān)谙聞澗€處填上正確的內(nèi)容。typedef struct nodeint data;struct node *lchild;_ struct node *rchild

41、 _ _;bitree;void createbitree(bitree *&bt)scanf(“%c”,&ch);if(ch='#') _ bt=0_;else bt=(bitree*)malloc(sizeof(bitree); bt->data=ch;_createbitree(bt->lchild _;createbitree(bt->rchild);2       設(shè)某棵完全二叉樹中有100個結(jié)點(diǎn)，則該二叉樹中有_50 _個葉子結(jié)點(diǎn)。7   &#

42、160;   設(shè)一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為_ CBDA _。5   設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_ CABD _。6   完全二叉樹中第5層上最少有_1_個結(jié)點(diǎn)，最多有_16_個結(jié)點(diǎn)。5.        設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點(diǎn)，21個度數(shù)為2的結(jié)點(diǎn)，則該二叉樹中度數(shù)為3的結(jié)點(diǎn)數(shù)有_14_個。6.    &

43、#160;   高度為h的完全二叉樹中最少有_2h-1_個結(jié)點(diǎn)，最多有_2h-1_個結(jié)點(diǎn)。9.        設(shè)一棵二叉樹的前序序列為ABC，則有_5_種不同的二叉樹可以得到這種序列。5設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中總共有_129_個結(jié)點(diǎn)數(shù)。7設(shè)二叉樹中結(jié)點(diǎn)的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_ p->lchild=0&&p->rchild=0_。5.  

44、0;      設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為_ ABDECF_，中序遍歷序列為_DBEAFC_，后序遍歷序列為_DEBFCA _。6.         設(shè)一棵完全二叉樹有128個結(jié)點(diǎn)，則該完全二叉樹的深度為_8_，有_64 _個葉子結(jié)點(diǎn)。3    根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為_3_。4    深度為k的完

45、全二叉樹中最少有_2k-1_個結(jié)點(diǎn)。6    設(shè)哈夫曼樹中共有99個結(jié)點(diǎn)，則該樹中有_50_個葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_51_個空指針域。5.         設(shè)哈夫曼樹中共有n個結(jié)點(diǎn)，則該哈夫曼樹中有_0_個度數(shù)為1的結(jié)點(diǎn)。7.         _中序 _遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個遞增的關(guān)鍵字序列（填先序、中序或后序）。10.    

46、 設(shè)有n個結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為_i/2_，右孩子結(jié)點(diǎn)的編號為_2i+1_。3.         中序遍歷二叉排序樹所得到的序列是_有序_序列（填有序或無序）。5.         設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_ N0-1_；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_2N0+N1_個空指針域

47、。3.        設(shè)一棵二叉樹中有n個結(jié)點(diǎn)，則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時，該二叉鏈表中共有_2n_個指針域，_n+1_個空指針域。7.        設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序列為_CBA_。8.        設(shè)一棵完全二叉樹中有21個結(jié)點(diǎn)，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點(diǎn)的編號是_4_，編號為

48、8的左孩子結(jié)點(diǎn)的編號是_16_。21已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有 384 個葉子結(jié)點(diǎn)。1.在一棵高度為h的完全二又樹中，最少含有_2h_個結(jié)點(diǎn)假定樹根結(jié)點(diǎn)的高 度為O2.將二叉樹bt中每一個結(jié)點(diǎn)的左右子樹互換的C語言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)，出隊(duì)和判別隊(duì)列是否為空的函數(shù)，請?zhí)顚懰惴ㄖ械每瞻滋?，完成其功能?typedef struct node int data ; struct node *lchild, *rchild; btnode; void  EXCHANGE(btnode *bt) btnode *

49、p, *q;  if (bt)ADDQ(Q,bt);          while(!EMPTY(Q)           p=DELQ(Q);  q=(1)_; p->rchild=(2)_; (3)_=q; if(p->lchild) (4)_; if(p->rchild) (5)_; 3已知某二叉樹的先序遍歷次序?yàn)閍fbcdeg，中序遍歷次序?yàn)閏edbgfa。 其后序遍歷次序?yàn)閑d cgbfa。層次遍歷次序?yàn)閍fbcgde。4請?jiān)谙聞澗€上填入適