【文章內(nèi)容簡介】 分結(jié)點(diǎn)C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn)13. 。A. abcdgef B. dfebagc C. dbaefcg D. defbagcgcefdbaagedbchf a14. ，其中序遍歷的序列為__ __。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgha15．設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是 。A．a(chǎn)在b的右方 B．a(chǎn)在b的左方C．a(chǎn)是b的祖先 D．a(chǎn)是b的子孫16. 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是____。 A. acbed B. decab C. deabc D. cedba17. 實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉樹采用____存儲(chǔ)結(jié)構(gòu)。A. 二叉鏈表 B. 廣義表存儲(chǔ)結(jié)構(gòu) C. 三叉鏈表 D. 順序存儲(chǔ)結(jié)構(gòu)18. ，____不是完全二叉樹。(A) (B) (C) (D)20. 在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是____。A. t—＞left=NULL B. t—＞ltag=1C. t—＞ltag=1且t—＞left=NULL D. 以上都不對(duì)21. 二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后續(xù)的線索，這種說法____。 A. 正確 B. 錯(cuò)誤22. 二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法____。 A. 正確 B. 錯(cuò)誤23. 具有五層結(jié)點(diǎn)的二叉平衡樹至少有____個(gè)結(jié)點(diǎn)。A. 10 B. 12 C. 15 D. 1724. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵數(shù)對(duì)應(yīng)的二叉樹。結(jié)論____是正確的。25. 樹最適合用來表示____。A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無聯(lián)系的數(shù)據(jù) 填空題（將正確的答案填在相應(yīng)的空中）1. ，回答下面的問題：k1 11kkkkkk21 4356 7⑴ 這棵樹的根結(jié)點(diǎn)是____；⑵ 這棵樹的葉子結(jié)點(diǎn)是____；⑶ 結(jié)點(diǎn)k3的度是____； 一棵樹⑷ 這棵樹的度是____；⑸ 這棵樹的深度是____；⑹ 結(jié)點(diǎn)k3的子女是____；⑺ 結(jié)點(diǎn)k3的父結(jié)點(diǎn)是__ 2. 指出樹和二叉樹的三個(gè)主要差別____、____、____。__；3. 從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是___ _。123456789101112131415161718192021eafdgcjlhb 一棵二叉樹的順序存儲(chǔ)數(shù)組t4. 一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組t中，則該二叉樹的鏈接表示形式為__ __。5. 深度為k的完全二叉樹至少有____個(gè)結(jié)點(diǎn)。至多有____個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)（從1開始），則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是____。6. 在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n 0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為 n 2，則有n0=____。7. 一棵二叉樹的第i（i≥1）層最多有____個(gè)結(jié)點(diǎn)；一棵有n（n0）個(gè)結(jié)點(diǎn)的滿二叉樹共有____個(gè)葉子和____個(gè)非終端結(jié)點(diǎn)。8. 結(jié)點(diǎn)最少的樹為____，結(jié)點(diǎn)最少的二叉樹為____。9. 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有____種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是____。10. ，回答以下問題：iae d bchHf 一棵二叉樹i⑴ 其中序遍歷序列為____；⑵ 其前序遍歷序列為____；⑶ 其后序遍歷序列為____； 簡答題1. 根據(jù)二叉樹的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹有5種不同的形態(tài)，請(qǐng)將它們分別畫出。2. 假設(shè)一棵 二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。gcefdba 一棵樹請(qǐng)畫出該樹。3. ，回答以下問題：（1）畫出該二叉樹的中序線索二叉樹；（2）畫出該二叉樹的后序線索二叉樹；（3）畫出該二叉樹對(duì)應(yīng)的森林。4. ，轉(zhuǎn)化為一棵二叉樹，表示為____。5. 以數(shù)據(jù)集{4，5，6，7，10，12，18}為結(jié)點(diǎn)權(quán)值，畫出構(gòu)造Huffman樹的每一步圖示，計(jì)算其帶權(quán)路徑長度為。6. 一棵含有N個(gè)結(jié)點(diǎn)的k叉樹,可能達(dá)到的最大深度和最小深度各為多少?7. 證明:一棵滿k叉樹上的葉子結(jié)點(diǎn)數(shù)n和非葉子結(jié)點(diǎn)數(shù)n之間滿足以下關(guān)系: n=(k1)n+1 算法設(shè)計(jì)題1. 編寫按層次順序（同一層自左至右）遍歷二叉樹的算法。2．試編寫算法，對(duì)一棵二叉樹,統(tǒng)計(jì)葉子的個(gè)數(shù)。3．試編寫算法，對(duì)一棵二叉樹根結(jié)點(diǎn)不變，將左、右子樹進(jìn)行交換，樹中每個(gè)結(jié)點(diǎn)的左、右子樹進(jìn)行交換。7. 假設(shè)用于通訊的電文僅有八個(gè)字母(a,b,c,d,e,f,g,h)組成，, , , , , , , 。試為這八個(gè)字母設(shè)計(jì)哈夫曼編碼。使用07的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。8. 試編寫算法，對(duì)一棵以孩子兄弟鏈表表示的樹統(tǒng)計(jì)葉子的個(gè)數(shù)。假設(shè)一棵 二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請(qǐng)畫出該樹。 習(xí)題答案 1. B 2. B 3. C 4. C 5. C 6. A 7. D 8. A 9. C 10. A11. D 2. A 13. B 14. B 15. B 16. D 17. C 18. C 19. B 20. B 21. B 22. B 23. B 24. A 25. C 1. ⑴ k1 ⑵ k2,k5,k7,k4 ⑶ 2 ⑷ 3 ⑸ 4 ⑹ k5,k6 ⑺ k1 eaEfjcdlghb2. 樹的結(jié)點(diǎn)個(gè)數(shù)至少為1(不同教材規(guī)定不同)，而二叉樹的結(jié)點(diǎn)個(gè)數(shù)可以為0；樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2；樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分；3. 樹可采用孩子兄弟鏈表（二叉鏈表）做存儲(chǔ)結(jié)構(gòu)，目的并利用二叉樹的已有算法解決樹的有關(guān)問題。4. 5. 2 k1 、 2 k1 、 2 k2+1 6. n2+1 7. 2 i1 2[log2n+1]1 2[log2n+1] –1 8. 只有一個(gè)結(jié)點(diǎn)的樹；空的二叉樹9. 5；a 樹形5種aaaacccccbbbbbb10. dgbaechif 、abdgcefhi 、gdbeihfca 、 1. 5種, EBEFAECDKGHIJ 樹形5種2. 。3. （左）所示；（右）所示；。a 11dhjbkc 圖 對(duì)應(yīng)的森林iefabcedig圖 一棵樹的孩子兄弟表示4. ，：5. ，計(jì)算其帶權(quán)路徑長度為 。6. 一棵含有N個(gè)結(jié)點(diǎn)的k叉樹,可能達(dá)到的最大深度 h=Nk+1 ，最小深度各為: logkN+1。623725191813121096745 Huffman樹習(xí)題7 圖 單項(xiàng)選擇題1．在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的____倍。A. 1/2 B. 1 C. 2 D. 4 2．任何一個(gè)無向連通圖的最小生成樹 。 3．在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的____倍。A. 1/2 B. 1 C. 2 D. 44．一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有____條邊。A. n B. n(n1) C. n(n1)/2 D. 2n5．具有4個(gè)頂點(diǎn)的無向完全圖有____條邊。A. 6 B. 12 C. 16 D. 206．具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有____條邊才能確保是一個(gè)連通圖。A. 5 B. 6 C. 7 D. 87．在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要____條邊。A. n B. n+1 C. n1 D. n/28．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是____。A. n B. (n1)2 C. n1 D. n29．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為_①___；所有鄰