數(shù)據(jù)結構第六章樹和二叉樹習題及答案

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

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

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

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

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

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

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