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

1、習(xí)題六習(xí)題六樹和二叉樹樹和二叉樹一、單項選擇題一、單項選擇題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)E任何只含一個結(jié)點(diǎn)的集合是一棵樹2下列說法中正確的是()A任何一棵二叉樹中至少有一個結(jié)點(diǎn)的度為2B任何一棵二叉樹中每個結(jié)點(diǎn)的度都為2C任何一棵二叉樹中的度肯定等于2D任何一棵二叉樹中的度可以

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

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

4、最少有()結(jié)點(diǎn)A2hB2h1C2h1Dh111.利用二叉鏈表存儲樹，則根結(jié)點(diǎn)的右指針是（）。A指向最左孩子B指向最右孩子C空D非空12已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF中序遍歷結(jié)果為CBAEDF則后序遍歷的結(jié)果為（）。ACBEFDABFEDCBACCBEDFAD不定13已知某二叉樹的后序遍歷序列是dabec中序遍歷序列是debac它的前序遍歷是（）。4.一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍

5、歷是一致的。()5.用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點(diǎn)。()6中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。()7完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必是樹葉。()8.二叉樹只能用二叉鏈表表示。()9.給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。()10.用鏈表(llinkrlink)存儲包含n個結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個指針區(qū)域中有n1個空指針。()11樹形結(jié)構(gòu)中元素之間存在一個對多個的關(guān)系。()12將一

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

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