第六章樹和二叉樹習(xí)題數(shù)據(jù)結(jié)構(gòu)

1、習(xí)題六習(xí)題六樹和二叉樹樹和二叉樹一、單項(xiàng)選擇題一、單項(xiàng)選擇題1以下說法錯(cuò)誤的是()A樹形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨B線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼C樹形結(jié)構(gòu)可以表達(dá)(組織)更復(fù)雜的數(shù)據(jù)D樹(及一切樹形結(jié)構(gòu))是一種“分支層次“結(jié)構(gòu)E任何只含一個(gè)結(jié)點(diǎn)的集合是一棵樹2下列說法中正確的是()A任何一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2B任何一棵二叉樹中每個(gè)結(jié)點(diǎn)的度都為2C任何一棵二叉樹中的度肯定等于2D任何一棵二叉樹中的度可以

2、小于23討論樹、森林和二叉樹的關(guān)系，目的是為了（）A借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹的一些運(yùn)算B將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)行存儲(chǔ)C將樹、森林轉(zhuǎn)換成二叉樹D體現(xiàn)一種技巧，沒有什么實(shí)際意義4樹最適合用來表示()A有序數(shù)據(jù)元素B無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無聯(lián)系的數(shù)據(jù)5若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）A9B11C15D不確定6設(shè)森林F中有三棵樹，第一，第二，第三棵樹的

3、結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（）。AM1BM1M2CM3DM2M37一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）A250B500C254D505E以上答案都不對(duì)8.設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為()A不確定B2nC2n1D2n19二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（）A2IB2I11C2I1D2I110一棵二叉樹高度為h所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹

4、最少有()結(jié)點(diǎn)A2hB2h1C2h1Dh111.利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（）。A指向最左孩子B指向最右孩子C空D非空14在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）A都不相同B完全相同C先序和中序相同，而與后序不同D中序和后序相同，而與先序不同15在完全二叉樹中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒（）。空指針。()11樹形結(jié)構(gòu)中元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。()12將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有左子樹。

5、()13度為二的樹就是二叉樹。()14.二叉樹中序線索化后，不存在空指針域。()15霍夫曼樹的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。()16哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。()三、填空題三、填空題1在二叉樹中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是______。2深度為k的完全二叉樹至少有_______個(gè)結(jié)點(diǎn)，至多有_______個(gè)結(jié)點(diǎn)。3高度為8的完全二叉樹至少有______個(gè)葉子結(jié)點(diǎn)。4.具有n個(gè)結(jié)點(diǎn)的二叉樹中一共有_____

6、___個(gè)指針域其中只有________個(gè)用來指向結(jié)點(diǎn)的左右孩子，其余的________個(gè)指針域?yàn)镹ULL。5樹的主要遍歷方法有________、________、________等三種。6一個(gè)深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)最小的葉子的序號(hào)是___；編號(hào)是i的結(jié)點(diǎn)所在的層次號(hào)是___（根所在的層次號(hào)規(guī)定為1層）。7如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B是A的雙親，則B的度是______

7、。8二叉樹的先序序列和中序序列相同的條件是______。9一個(gè)無序序列可以通過構(gòu)造一棵______樹而變成一個(gè)有序序列，構(gòu)造樹的過程即為對(duì)無序序列進(jìn)行排序的過程。10若一個(gè)二叉樹的葉子結(jié)點(diǎn)是某子樹的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹的______序列中的最后一個(gè)結(jié)點(diǎn)。11若以4，5，6，7，8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長(zhǎng)度是______。12以下程序段采用先根遍歷方法求二叉樹的葉子數(shù)，請(qǐng)?jiān)跈M線處填充適當(dāng)?shù)恼Z句