數(shù)據(jù)結構Ch6習題答案

1、Ch6樹一、選擇題：1.下列關于哈夫曼樹的敘述，錯誤的是（C）。A.哈夫曼樹根結點的權值等于所有葉結點權值之和。B.具有n個葉結點的哈夫曼樹共有 2n-1個結點。C.哈夫曼樹是一棵二叉樹，因此它的結點的度可以為0, 1, 2。D.哈夫曼樹是帶權路徑長度最短的二叉樹。2 .由3個結點可以構成多少棵不同形態(tài)的二叉樹（C ）。A. 3B .4 C .5 D . 63 .如果一棵二叉樹結點的前序序列是A, B, C,后序序列是 C, B, A,則該二叉樹結點的中序序列是（D ）。A. A, B, C B . A C, B C . B, C, A D ,不能確定5.二叉樹按某種順序線索化后，任一結點均有

2、指向其前趨和后繼的線索，這種說法A.正確B .錯誤Ichild指針指示其前驅;rchild指針指示其后繼。(A )。若結點有左子樹，則令其 Ichild 指針指示其左孩子；若結點沒有左子樹，則令其 若結點有右子樹，則令其 rchild指針指示其右孩子；若結點沒有右子樹，則令其 6.二叉樹的前序遍歷序列中，任意一個結點均處在其子女結點的前面，這種說法A.正確B .錯誤7.對一棵70個結點的完全二叉樹，它有 （A ）個葉子結點。A. 35 B . 40 C . 30 D . 441個結點第2層2個結點第3層前6層共63個結點8個結點16個結點第5層交個結點共35個葉結點C1112no=n2+10D

3、65假定根結點的層次為110CB1112Dno=n2+1若設根結點的層次為不確定CBacbeddecbaD(A ) 不確定A. debacA. 1013.設高度為9 .假定根結點的層次為A. 10 BA. 3 B . 4 CD .不確定12.以知某二叉樹的后序遍歷序列為abdec,先序遍歷序列為 cedba,它的中序遍歷序列為(D )11.設根結點的層次為A. 2k-1 B . 2k C .A. 2h B2h-1C2h+1Dh+1K兩且點 期有，結 11只點個弟 第層結兩兄 除每個這為14 .設n,m為一棵二叉樹上的兩個結點，在中序遍歷時， n在m前的條件是（C）。A. n在 m右方 B .

4、n是m祖先 C . n在m左方 D . n是 m子孫15 .將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點進行編號，根結點的編號為 49的結點的左孩子編號為（A ）。A. 98 B .99 C .50 D . 4816 .某二叉樹的前序和后序序列正好相反，則該二叉樹一定是（B ）二叉樹。A.空或只有一個結點B .高度等于其結點數(shù)C .任一結點無左孩子D .任一結點無右孩子17 .對于一棵滿二叉樹，m個樹葉，n個結點，深度為h,則（C ）。A. h+m=2n B . m=h-1 C . n=2h-1D . n=h+m18 .判斷線索二叉樹中某結p有左孩子的條件是（C ）。A. p!

5、=null B . p->lchild!=null C. p->ltag=0 D . p->ltag=119 .實現(xiàn)任意二叉樹的后序非遞歸算法而不使用堆棧結構，最佳方案是二叉樹采用（C ）存儲結構。A.二叉鏈表B .廣義存儲結構C .三叉鏈表D.順序存儲結構20 .在一棵二叉樹結點的先序遍歷序列，中序遍歷序列和后序遍歷序列中，所有的葉子結點的先后順序（B ）。A.都不相同B .完全相同C .先序和中序相同，而與后序不同D .中序和后序相同，而與先序不同21 .下圖所示FF是森林F轉換而來的二叉樹，那么 F 一共有（C ）個葉子結點。A. 4 B . 5 C . 6 D .7A

6、22.在一非空二叉樹的中序遍歷序列中，根結點的右邊（A ）A.只有右子樹上的所有結點B .只有右子樹上的部分結點C.只有左子樹上的所有結點D .只有左子樹上的部分結點23 .設森林F中有3棵樹，其第一，第二和第三棵樹的結點個數(shù)分別是ni, n2和小，則與森林F相對應的二叉樹根結點的右子樹上的結點個數(shù)是 （D ）。A. ni B . ni+n2 C . % D .出+%24 .假定一棵二叉樹的結點數(shù)為18,則它的最小高度為（C）。A. 18B . 8 C .5 D . 4第1層第2層 第3層第4層 第5層1 2 48325 .樹最合適用來表示（C）。A.有序數(shù)據(jù)元素B .無序數(shù)據(jù)元素C .元素之

7、間具有分支層次關系的數(shù)據(jù)D .元素之間無聯(lián)系的數(shù)據(jù)26 .以下有關數(shù)據(jù)結構的敘述正確的是（C）。A.線性表的線性存儲結構優(yōu)于鏈式存儲結構B.二叉機勺第i層上有2 i-1個結點，深度為k的二叉樹上有2k“個結點。C.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。D .棧的操作方式是先進先出。.填空題1 .有一棵樹如圖示，回答下面問題: （1）這棵樹的根結點是（A） ; （2）這棵樹的葉子結點是（B,E,H,G） ; （3）結點C的度是（2） ; （4）這棵樹白度是（3） ; （5）這棵結點F的父親是（C）,祖先是（A,C）。樹的深度是（4） ; （6）結點C的孩子是（E,F）,子孫是（E,F,H）;（7

8、）2 .二叉樹的每一個結點至多有 （2）棵子樹，且子樹有（左右）之分。3 .樹的結點包含一個（數(shù)據(jù)元素）及若干指向其（子樹）的分支，結點擁有的子樹數(shù)稱為 （度），度為0的結點稱為（樹葉 或終端結點）,度不為。的結點稱為（非終端結點或分支結點）。4 .對二叉樹來說，第 k層上至多有（2k-1）個結點。5 .前序遍歷序列為 abc的不同二叉樹有（5）種不同形態(tài)。6 .二叉樹的前序遍歷序列為 I J KL MNO,中序遍歷序列為 J LK I NMO,則后序遍歷序列為（LKJNOM）。出7 . 一棵樹轉化為一棵二叉樹后，二叉樹沒有（右）子樹。8 . 一棵含有n個結點的完全二叉樹，它的高度是（log

9、2n+1 ）。一棵含有n個結點的 完全二叉樹，它的高度是（log 2n+1）。h-1層最后一個結點的編號2h-1-1h層第一個結點的編號2h-1h層最后一個結點的編號2h-12h-1 >n>2h-1n > 2h-1h< logn+1h= logn+1n=2k-1=>k= log 2（n+1）9 .深度為k的二叉樹至多有（2k-1 ）個結點。10 .含有n個結點的二叉樹用二叉鏈表表示，有（n+1）個空鏈域。有2n個鏈域 有n-1個非空鏈域11 .哈夫曼樹是帶權路徑長度 （最短）的二叉樹。12 .具有m個葉子結點的口夫曼樹共（2m-1）個結點。13.前序為a, b,

10、c且后序為c, b, a的二叉樹有（4）棵。（利用已有的二叉樹的算法來14.樹和二叉樹從定義上說是兩種不同的數(shù)據(jù)結構，那么將樹轉化為二叉樹的基本目的是 解決樹的有關問題）。15 .深度為k的完全二叉樹至多有（2k-1）個結點；至少有（2k-1）個結點，若按自上而下，從左到右的次序給結點編號（從1開始），則編號最小的葉子結點的編號是（2k-2+1）。第kJ層16.已知完全二叉樹的第 8層有8個結點，則其葉子結點數(shù)為 （68）個。 第7層的葉結點總數(shù)：26-4第8層的葉結點總數(shù)：817.已知完全二叉樹的第 7層有10個葉子結點，則整個二叉樹的結點個數(shù)最多為（235）個。2 -1010個dioooo

11、 ooooooitj002610)*2個30,則總結點數(shù)為（129）。18 .已知二叉樹有50個葉子結點，且僅有一個孩子的結點數(shù)為設度為i的結點有ni個，共n個結點有no+ni+n2=n（結點總數(shù)）0*no+1*n i+2*n 2=n-1（邊數(shù)）所以：no=n2+1 ni=30(A2i+1)。F, I ,則該二叉19 .用數(shù)組A1川順序存儲完全二叉樹的各結點，則當 i w （n-1）/2 時，結點Ai的右孩子是結點20 .一棵二叉樹結點的前序序列為A,B,D, E, GC,F,H,I ,中序序列為D,B,G,E, A,C,H,樹結點的后序序列為（DGEBHIFCA(I有m個葉子結點的哈夫曼樹上

12、的結點數(shù)是(2m-1)。22.設樹T的度為4,其中度為1, 2, 3和4的結點個數(shù)分別為 4, 2, 1和1,則T中葉子結點的個數(shù)為(8)。設度為i的結點有ni個 ni=4 n 2=2 n 3=1 n 4=1no+m+n2+n3+n4=n n-1=0*n o+1*m+2*n2+3*n3+4*n423. 6個結點可構造出132種不同形態(tài)的二叉樹。高度：6高度：5高度：4高度：324. 在一棵高度為3的四叉樹中，最多含有21結點。1+1*4+1*4*425. 一棵樹的廣義表表示為a (b (c, d (e, f), g (h), i(j, k (x, y),結點f的層數(shù)為3 。假定根結點 第五層：

13、50-40=10個結點26. 一棵樹的廣義表表示為a (b (c, d (e, f), g (h) ), i(j, k (x, y),結點k的所有祖先的結點數(shù)為2個。27.假定一棵三叉樹(即度為3的樹)的結點個數(shù)為50,則它的最小高度為 4。假定根結點的高度為0。第一層：30=1個結點第二層：1X3=31=3個結點第三層：1 X 3 X 3=32=9個結點第四層：1 X 3X 3X 3=33=27個結點 前四層，共 40個結點28 .對于一棵具有n個結點的樹，該樹中所有結點的度數(shù)之和為n-1 。即求邊數(shù)29 .設二叉樹根的高度為 1,則：高度為h的完全二叉樹的不同二叉樹棵數(shù)：2h-1 ,(即最

14、后一層分別有1, 2,2h-1個結點的完全二叉樹)高度為h的滿二叉樹的不同二叉樹棵數(shù)：1 q三.判斷題1. ( X )二叉樹是一棵無序樹。2. ( X )若有一個結點是二叉樹中某個子樹的前序遍歷結果序列的最后一個結點，則它一定是該子樹的中序遍歷結果序列的最后一個結點。3. (，)在一棵二叉樹中，假定每個結點只有左子女，沒有右子女，對它分別進行中序遍歷和后序遍歷，則具有相同的 遍歷結果。4. (，)在樹的存儲中，若使每個結點帶有指向前驅結點的指針，將在算法中為尋找前驅結點帶來方便。5. (，)二叉樹是樹的特殊情形。6. (X)對于一棵具有n個結點的任何二叉樹，進行前序、中序或后序的任一種次序遍歷

15、的空間復雜度為O(log2n)。7. (X)對于一棵具有n個結點，其高度為 h的二叉樹，進行任一種次序遍歷的時間復雜度為0(h)。8. ( x)若有一個葉子結點是二叉樹中某個子樹的前序遍歷結果序列的最后一個結點，則它一定是該子樹的中序遍歷結果序列的最后一個結點。9. (V)線索化二叉樹中的每個結點通常包含有5個數(shù)據(jù)成員。10. ( X )若有一個結點是二叉樹中某個子樹的中序遍歷結果序列的最后一個結點，則它一定是該子樹的前序遍歷結果 序列的最后一個結點。四.其他1 .二叉樹的遍歷方法有哪幾種，分別簡訴其遍歷步驟。二叉樹的遍歷方法有先序遍歷、中序遍歷、后序遍歷三種。(1)先序遍歷二叉樹算法是：若二

16、叉樹為空，則空操作；否則訪問根結點(D);先序遍歷左子樹(L);先序遍歷右子樹(R)。(2)中序遍歷二叉樹算法是：若二叉樹為空，則空操作；否則中序遍歷左子樹（L）;訪問根結點（D）;中序遍歷右子樹（R）。（3）后序遍歷二叉樹算法是：若二叉樹為空，則空操作；否則后序遍歷左子樹（L）;后序遍歷右子樹（R）;訪問根結點（D）。2 .若按中序遍歷二叉樹的結果為A, C, Bo作出所有能得到這一遍歷結果的二叉樹。3.二叉樹結點數(shù)據(jù)采用順序存儲結構，存儲數(shù)組中，如圖所示，畫出該二叉樹的二叉鏈式表示形式。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2

17、14.已知一棵樹的雙親表示如下，其中各兄弟結點是從左到右依次出現(xiàn)的，畫出該樹及對應的二叉樹。12 3 4 5 6 7 3gl0 11 12 13 14DATAABCDEFGHIJKLMN0PARENT-1000112233455675.寫出二叉樹的先序，中序和后序遍歷序列，并將該二叉樹分解為森林。二叉樹的先序遍歷序列： ABCDEFGHI 二叉樹的中序遍歷序列： BDCAFEHIG 二叉樹的后序遍歷序列： DCBFIHGEA 對應的森林：6.以知一棵二叉樹的先序遍歷序列為ABECDFGHIJ中序遍歷序列為EBCDAFHIGJ試畫出這棵二叉樹，并寫出其后序遍歷序列。©4G)后序遍歷序列

18、為：EDCBIHJGFA7.畫以數(shù)據(jù)集4, 5, 6, 7, 10, 12, 18為結點權值所構造的哈夫曼樹，并求其帶權路徑長度WPL4 5WPL=12*2+6*3+7*3+18*2+4*4+5*4+10*3=1658.設用于通訊的電文僅有 8個字母組成，字母在電文中出現(xiàn)的頻率分別為 個字母設計哈夫曼編碼。ooO O01 1。、XDii1921一廠,、Ml 00 1011。直飛溫1c(5 On /S61001 7101 oooqj O00012 39.有J棵一叉樹，其中序和后序遍歷序列分別為 dgbaechif , gdbeihfca 。 并求該二叉樹所對應的森林。7, 19, 2, 6, 32, 3, 21, 10。試為這 8畫出該二叉樹，對該二叉樹進行先序線索化，10.二叉樹以二叉鏈表結構存儲，在下列中序遍歷序列算法中填上正確的語句。InitStack (s);(3)給出它的后綴表達式。Status in_order (BiTree p)if ( p !=NULL) (1)in order(p->lchild);printf ( p->data);(2)in order(p->rchild); 11