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

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

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

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

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

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

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

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