數(shù)據(jù)結(jié)構(gòu)Ch6習(xí)題答案

1、Ch6樹一、選擇題：1下列關(guān)于哈夫曼樹的敘述，錯誤的是( C )。A哈夫曼樹根結(jié)點的權(quán)值等于所有葉結(jié)點權(quán)值之和。B具有n個葉結(jié)點的哈夫曼樹共有2n-1個結(jié)點。C哈夫曼樹是一棵二叉樹，因此它的結(jié)點的度可以為0，1，2。 D哈夫曼樹是帶權(quán)路徑長度最短的二叉樹。2由3個結(jié)點可以構(gòu)成多少棵不同形態(tài)的二叉樹( C )。 A3 B4 C5 D6 3如果一棵二叉樹結(jié)點的前序序列是A，B，C，后序序列是C，B，A，則該二叉樹結(jié)點的中序序列是( D )。 AA，B，C BA，C，B CB，C，A D不能確定4如圖所示的4棵二叉樹中，( B )不是完全二叉樹。 A B C D5二叉樹按某種順序線索化后，任一結(jié)點均

2、有指向其前趨和后繼的線索，這種說法( B )A正確 B錯誤若結(jié)點有左子樹，則令其lchild指針指示其左孩子；若結(jié)點沒有左子樹，則令其lchild指針指示其前驅(qū)；若結(jié)點有右子樹，則令其rchild指針指示其右孩子；若結(jié)點沒有右子樹，則令其rchild指針指示其后繼。6二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女結(jié)點的前面，這種說法( A )。A正確 B錯誤7對一棵70個結(jié)點的完全二叉樹，它有( A )個葉子結(jié)點。A35 B40 C30 D448設(shè)一棵二叉樹中，度為1的結(jié)點數(shù)為9，則該二叉樹的葉子結(jié)點的數(shù)目為( D )。A10 B11 C12 D不確定n0=n2+19假定根結(jié)點的層次為0，含

3、有15個結(jié)點的二叉樹最小高度為( A )。 A3 B4 C5 D6假定根結(jié)點的層次為1，含有15個結(jié)點的二叉樹最小高度為410若一棵二叉樹中，度為2的結(jié)點數(shù)為9，該二叉樹的葉子結(jié)點的數(shù)目為( A )。A10 B11 C12 D不確定n0=n2+111設(shè)根結(jié)點的層次為0，則高度為k的二叉樹的最大結(jié)點數(shù)為(C )。 A2k-1 B2k C2k+1-1 D2k+1若設(shè)根結(jié)點的層次為1，則這棵樹的高度為k+1，高度為k+1的二叉樹的最大結(jié)點數(shù)為2k+1-112以知某二叉樹的后序遍歷序列為abdec，先序遍歷序列為cedba，它的中序遍歷序列為( D )。 Adebac Bacbed Cdecba D不

4、確定13設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點,則此二叉樹所包含的結(jié)點數(shù)至少為( B )。 A2h B2h-1 C2h+1 Dh+114設(shè)n,m為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前的條件是( C )。An在m右方 Bn是m祖先 Cn在m左方 Dn是m子孫15將一棵有100個結(jié)點的完全二叉樹從上到下,從左到右依次對結(jié)點進行編號,根結(jié)點的編號為49的結(jié)點的左孩子編號為( A )。 A98 B99 C50 D4816某二叉樹的前序和后序序列正好相反,則該二叉樹一定是( B )二叉樹。A 空或只有一個結(jié)點 B高度等于其結(jié)點數(shù) C任一結(jié)點無左孩子 D任一結(jié)點無右孩子17對于一棵滿二叉樹

5、，m個樹葉，n個結(jié)點，深度為h，則( C )。Ah+m=2n Bm=h-1 Cn=2h-1 Dn=h+m18判斷線索二叉樹中某結(jié)p有左孩子的條件是( C )。Ap!=null Bp->lchild!=null Cp->ltag=0 Dp->ltag=119實現(xiàn)任意二叉樹的后序非遞歸算法而不使用堆棧結(jié)構(gòu)，最佳方案是二叉樹采用( C )存儲結(jié)構(gòu)。A二叉鏈表 B廣義存儲結(jié)構(gòu) C三叉鏈表 D順序存儲結(jié)構(gòu)20在一棵二叉樹結(jié)點的先序遍歷序列，中序遍歷序列和后序遍歷序列中，所有的葉子結(jié)點的先后順序( B )。A都不相同 B完全相同 C先序和中序相同，而與后序不同 D中序和后序相同，而與先序

6、不同21下圖所示FF是森林F轉(zhuǎn)換而來的二叉樹，那么F 一共有( C )個葉子結(jié)點。A4 B5 C6 D722在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊( A )。A只有右子樹上的所有結(jié)點 B只有右子樹上的部分結(jié)點 C只有左子樹上的所有結(jié)點 D只有左子樹上的部分結(jié)點23設(shè)森林F中有3棵樹，其第一，第二和第三棵樹的結(jié)點個數(shù)分別是n1，n2和n3，則與森林F相對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是( D )。 An1 Bn1+n2 Cn3 Dn2+n324假定一棵二叉樹的結(jié)點數(shù)為18，則它的最小高度為(C )。A18 B8 C5 D4第1層 第2層 第3層 第4層 第5層1 2 4 8 325樹

7、最合適用來表示(C )。A有序數(shù)據(jù)元素 B無序數(shù)據(jù)元素 C元素之間具有分支層次關(guān)系的數(shù)據(jù) D元素之間無聯(lián)系的數(shù)據(jù)26以下有關(guān)數(shù)據(jù)結(jié)構(gòu)的敘述正確的是(C )。 A線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)B二叉樹的第i層上有 2i-1個結(jié)點，深度為k的二叉樹上有2k-1個結(jié)點。C二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。 D棧的操作方式是先進先出。二填空題1有一棵樹如圖示，回答下面問題：(1) 這棵樹的根結(jié)點是(A)；(2)這棵樹的葉子結(jié)點是(B,E,H,G)；(3)結(jié)點C的度是(2)；(4)這棵樹的度是(3)；(5)這棵樹的深度是(4)；(6)結(jié)點C的孩子是(E,F),子孫是(E,F,H);(7)結(jié)點F

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

9、一棵含有n個結(jié)點的完全二叉樹，它的高度是(log2n+1)。 h-1層最后一個結(jié)點的編號2h-1-1 h層第一個結(jié)點的編號2h-1 h層最后一個結(jié)點的編號2h-1 2h-1n2h-1n2h-1hlogn+1h= logn+1n=2k-1=>k= log2(n+1)9深度為k的二叉樹至多有(2k-1)個結(jié)點。10含有n個結(jié)點的二叉樹用二叉鏈表表示，有(n+1)個空鏈域。有2n個鏈域有n-1個非空鏈域11哈夫曼樹是帶權(quán)路徑長度(最短)的二叉樹。 12具有m個葉子結(jié)點的哈夫曼樹共(2m-1)個結(jié)點。13前序為a，b，c且后序為c，b，a的二叉樹有(4)棵。14樹和二叉樹從定義上說是兩種不同的數(shù)

10、據(jù)結(jié)構(gòu)，那么將樹轉(zhuǎn)化為二叉樹的基本目的是(利用已有的二叉樹的算法來解決樹的有關(guān)問題)。15深度為k的完全二叉樹至多有(2k-1)個結(jié)點；至少有(2k-1)個結(jié)點，若按自上而下，從左到右的次序給結(jié)點編號(從1開始)，則編號最小的葉子結(jié)點的編號是(2k-2+1)。16已知完全二叉樹的第8層有8個結(jié)點，則其葉子結(jié)點數(shù)為(68)個。第7層的葉結(jié)點總數(shù)：26-4第8層的葉結(jié)點總數(shù)：817已知完全二叉樹的第7層有10個葉子結(jié)點，則整個二叉樹的結(jié)點個數(shù)最多為(235)個。18已知二叉樹有50個葉子結(jié)點，且僅有一個孩子的結(jié)點數(shù)為30，則總結(jié)點數(shù)為(129)。設(shè)度為i的結(jié)點有ni個，共n個結(jié)點有n0+n1+n2

11、=n(結(jié)點總數(shù))0*n0+1*n1+2*n2=n-1(邊數(shù))所以：n0=n2+1n1=3019用數(shù)組A1n順序存儲完全二叉樹的各結(jié)點，則當(dāng)i (n-1)/2時，結(jié)點Ai的右孩子是結(jié)點(A2i+1)。20一棵二叉樹結(jié)點的前序序列為A，B，D，E，G，C，F(xiàn)，H，I，中序序列為D，B，G，E，A，C，H，F(xiàn)，I，則該二叉樹結(jié)點的后序序列為(DGEBHIFCA)。21有m個葉子結(jié)點的哈夫曼樹上的結(jié)點數(shù)是(2m-1)。22設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1和1，則T中葉子結(jié)點的個數(shù)為(8)。設(shè)度為i的結(jié)點有ni個n1=4 n2=2 n3=1 n4=1n0+n1+n2+n3

12、+n4=nn-1=0*n0+1*n1+2*n2+3*n3+4*n4236個結(jié)點可構(gòu)造出 132 種不同形態(tài)的二叉樹。 高度：6高度：5高度：4高度：324在一棵高度為3的四叉樹中，最多含有 21 結(jié)點。 1+1*4+1*4*425一棵樹的廣義表表示為a (b (c, d (e, f), g (h) ), i(j, k (x, y) ) )，結(jié)點f的層數(shù)為 3 。假定根結(jié)點的層數(shù)為0。 26一棵樹的廣義表表示為a (b (c, d (e, f), g (h) ), i(j, k (x, y) ) )，結(jié)點k的所有祖先的結(jié)點數(shù)為 2 個。 27假定一棵三叉樹(即度為3的樹)的結(jié)點個數(shù)為50，則它的

13、最小高度為 4 。假定根結(jié)點的高度為0。 第一層：30=1個結(jié)點第二層：1×3=31=3個結(jié)點第三層：1×3×3=32=9個結(jié)點第四層：1×3×3×3=33=27個結(jié)點-前四層，共40個結(jié)點第五層：50-40=10個結(jié)點28對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為 n-1 。 即求邊數(shù)29設(shè)二叉樹根的高度為1，則：高度為h的完全二叉樹的不同二叉樹棵數(shù)： 2h-1 ，(即最后一層分別有1，2，2h-1個結(jié)點的完全二叉樹)高度為h的滿二叉樹的不同二叉樹棵數(shù)： 1 。三判斷題1(×)二叉樹是一棵無序樹。 2(×

14、;)若有一個結(jié)點是二叉樹中某個子樹的前序遍歷結(jié)果序列的最后一個結(jié)點，則它一定是該子樹的中序遍歷結(jié)果序列的最后一個結(jié)點。 3()在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進行中序遍歷和后序遍歷，則具有相同的遍歷結(jié)果。 4()在樹的存儲中，若使每個結(jié)點帶有指向前驅(qū)結(jié)點的指針，將在算法中為尋找前驅(qū)結(jié)點帶來方便。 5()二叉樹是樹的特殊情形。 6(×)對于一棵具有n個結(jié)點的任何二叉樹，進行前序、中序或后序的任一種次序遍歷的空間復(fù)雜度為O(log2n)。 7(×)對于一棵具有n個結(jié)點，其高度為h的二叉樹，進行任一種次序遍歷的時間復(fù)雜度為O(h)。 8(×)

15、若有一個葉子結(jié)點是二叉樹中某個子樹的前序遍歷結(jié)果序列的最后一個結(jié)點，則它一定是該子樹的中序遍歷結(jié)果序列的最后一個結(jié)點。 9()線索化二叉樹中的每個結(jié)點通常包含有5個數(shù)據(jù)成員。 10(×)若有一個結(jié)點是二叉樹中某個子樹的中序遍歷結(jié)果序列的最后一個結(jié)點，則它一定是該子樹的前序遍歷結(jié)果序列的最后一個結(jié)點。 四其他1二叉樹的遍歷方法有哪幾種，分別簡訴其遍歷步驟。二叉樹的遍歷方法有先序遍歷、中序遍歷、后序遍歷三種。(1)先序遍歷二叉樹算法是：若二叉樹為空，則空操作；否則訪問根結(jié)點(D)；先序遍歷左子樹(L)；先序遍歷右子樹(R)。(2)中序遍歷二叉樹算法是：若二叉樹為空，則空操作；否則中序遍歷

16、左子樹(L)；訪問根結(jié)點(D)；中序遍歷右子樹(R)。(3)后序遍歷二叉樹算法是：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結(jié)點(D)。2若按中序遍歷二叉樹的結(jié)果為A，C，B。作出所有能得到這一遍歷結(jié)果的二叉樹。3二叉樹結(jié)點數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲數(shù)組中，如圖所示，畫出該二叉樹的二叉鏈?zhǔn)奖硎拘问健?1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21eafdgcjhib4已知一棵樹的雙親表示如下，其中各兄弟結(jié)點是從左到右依次出現(xiàn)的，畫出該樹及對應(yīng)的二叉樹。5寫出二叉樹的先序，中序和后序遍歷序列，并將該二

17、叉樹分解為森林。二叉樹的先序遍歷序列：ABCDEFGHI二叉樹的中序遍歷序列：BDCAFEHIG二叉樹的后序遍歷序列：DCBFIHGEA對應(yīng)的森林：6以知一棵二叉樹的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫出這棵二叉樹，并寫出其后序遍歷序列。后序遍歷序列為：EDCBIHJGFA7畫以數(shù)據(jù)集4，5，6，7，10，12，18為結(jié)點權(quán)值所構(gòu)造的哈夫曼樹，并求其帶權(quán)路徑長度WPL。8設(shè)用于通訊的電文僅有8個字母組成，字母在電文中出現(xiàn)的頻率分別為7，19，2，6，32，3，21，10。試為這8個字母設(shè)計哈夫曼編碼。9有一棵二叉樹，其中序和后序遍歷序列分別為dgbaec

18、hif，gdbeihfca。畫出該二叉樹，對該二叉樹進行先序線索化，并求該二叉樹所對應(yīng)的森林。10二叉樹以二叉鏈表結(jié)構(gòu)存儲，在下列中序遍歷序列算法中填上正確的語句。 Status in_order (BiTree p)if ( p !=NULL) (1)in_order(p->lchild) ; printf ( p->data); (2)in_order(p->rchild) ; 11以二叉鏈表作為存儲結(jié)構(gòu)，試完成下列程序(1)下列函數(shù)是中序輸出二叉樹的各結(jié)點，讀程序并在每一個空格初填寫一個語句或表達式。 void printtree (BiTree BT) BiTnode

19、 *p;InitStack (s ); /構(gòu)造棧sp=(1) BT ; s.top=0;while (p | s.top!=0) while (2) p!=NULL ) s.elems.top+=p; (3) p=p->lchild ; if (s.top>0)(4)p=s.elem-top ; printf (“%d”, p->data); (5)p=p->rchild ; (2)所謂二叉樹T1和T2是等價的，那就是說，或者T1和T2都是空的二叉樹；或者T1和T2都是非空的二叉樹，且T1和T2的根結(jié)點的值相同，同時T1和T2的根結(jié)點的左子樹是等價的，且T1和T2的根結(jié)

20、點的右子樹也是等價的。下面給出了判斷二叉樹T1和T2是否等價的程序。讀程序并在每一個空格初填寫一個語句或表達式。 int equalbitre (BiTree t1, BiTree t2 ) int equal=0; if (t1= =null &&(1) t2=null ) equal=1; else if (t1!= null &&(2) t2!=null) if (t1->data= =t2->data) if (equalbitre ( t1->lchild, t2->lchild) (3) if (equalbitre ( t1

21、->rchild, t2->rchild)equal=1; return equal; 12一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹結(jié)點數(shù)目的算法。答案一：int Size(BiTree T) if(T=NULL) return 0; else return(1+Size(T->lchild)+Size(T->rchild);答案二：i=0;int in_order (BiTree p)if ( p !=NULL) in_order(p->lchild) ; printf ( p->data); i+; in_order(p->rchild) ; return i;答案三：void printtree (BiTree BT) BiTnode *p; i=0；InitStack (s ); /構(gòu)造棧sp=(1) BT ; s.top=0;while (p | s.top!=0) while (p!=NULL ) s.elems.top+=p; p=p->lchild ; if (s.top>0)(4)p=s.elem-top ; printf (“%d”, p->data); i+；