【正文】 . 二叉樹(shù)等價(jià)于度為2的樹(shù)C. 完全二叉樹(shù)必為滿二叉樹(shù)D. 二叉樹(shù)的左右子樹(shù)有次序之分13. 任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ ）。A. 不發(fā)生改變 B. 發(fā)生改變C. 不能確定 D. 以上都不對(duì)14. 已知一棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（ ）。A. 1 B. 2 C. 3 D. 415. 根據(jù)先序序列ABDC和中序序列DBAC確定對(duì)應(yīng)的二叉樹(shù)，該二叉樹(shù)（ ）。A. 是完全二叉樹(shù) B. 不是完全二叉樹(shù)C. 是滿二叉樹(shù) D. 不是滿二叉樹(shù)二、判斷題1. 二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度不能超過(guò)2，所以二叉樹(shù)是一種特殊的樹(shù)。 （?。?. 二叉樹(shù)的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。 （?。?. 線索二叉樹(shù)是一種邏輯結(jié)構(gòu)。 （?。?. 哈夫曼樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)（多于1時(shí)）不能為偶數(shù)。 （?。?. 由二叉樹(shù)的先序序列和后序序列可以唯一確定一顆二叉樹(shù)。 （　）6. 樹(shù)的后序遍歷與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同。 （　）7. 根據(jù)任意一種遍歷序列即可唯一確定對(duì)應(yīng)的二叉樹(shù)。 （　）8. 滿二叉樹(shù)也是完全二叉樹(shù)。 （　）9. 哈夫曼樹(shù)一定是完全二叉樹(shù)。 （　）10. 樹(shù)的子樹(shù)是無(wú)序的。 （?。┤?、填空題1. 假定一棵樹(shù)的廣義表表示為A（B（E），C（F（H，I，J），G），D），則該樹(shù)的度為_(kāi)____，樹(shù)的深度為_(kāi)____，終端結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)_____，單分支結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)_____，雙分支結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)_____，三分支結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)______，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_(kāi)______，其孩子結(jié)點(diǎn)為_(kāi)______和_______結(jié)點(diǎn)。2. 設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹(shù)，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有_______個(gè)。3. 對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)它為一棵________二叉樹(shù)時(shí)具有最小高度，即為_(kāi)______，當(dāng)它為一棵單支樹(shù)具有_______高度，即為_(kāi)______。4. 由帶權(quán)為3，9，6，2，5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹(shù)，則帶權(quán)路徑長(zhǎng)度為_(kāi)__。5. 在一棵二叉排序樹(shù)上按_______遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。6. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為_(kāi)______個(gè)，其中_______個(gè)用于鏈接孩子結(jié)點(diǎn)，_______個(gè)空閑著。7. 在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=______。8. 一棵深度為k的滿二叉樹(shù)的結(jié)點(diǎn)總數(shù)為_(kāi)______，一棵深度為k的完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)的最小值為_(kāi)____，最大值為_(kāi)_____。9. 由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，共有____種不同的形態(tài)。10. 設(shè)高度為h的二叉樹(shù)中只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為_(kāi)___。11. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)，______形態(tài)達(dá)到最大深度，____形態(tài)達(dá)到最小深度。12. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，若一個(gè)結(jié)點(diǎn)的編號(hào)為i(1≤i≤n)，則它的左孩子結(jié)點(diǎn)的編號(hào)為_(kāi)_______，右孩子結(jié)點(diǎn)的編號(hào)為_(kāi)_______，雙親結(jié)點(diǎn)的編號(hào)為_(kāi)_______。13. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用二叉鏈表存儲(chǔ)時(shí)，鏈表中指針域的總數(shù)為_(kāi)________個(gè)，其中___________個(gè)用于鏈接孩子結(jié)點(diǎn)，_____________個(gè)空閑著。14. 哈夫曼樹(shù)是指________________________________________________的二叉樹(shù)。15. 空樹(shù)是指________________________，最小的樹(shù)是指_______________________。16. 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有______________和_______________兩種。17. 三叉鏈表比二叉鏈表多一個(gè)指向______________的指針域。18. 線索是指___________________________________________。19. 線索鏈表中的rtag域值為_(kāi)____時(shí)，表示該結(jié)點(diǎn)無(wú)右孩子，此時(shí)______域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。20. 本節(jié)中我們學(xué)習(xí)的樹(shù)的存儲(chǔ)結(jié)構(gòu)有_____________、___________和___________。四、應(yīng)用題1. 已知一棵樹(shù)邊的集合為{i，m，i，n，e，i，b，e，b，d，a，b，g，j，g，k，c，g，c，f，h，l，c，h，a，c}，請(qǐng)畫(huà)出這棵樹(shù)，并回答下列問(wèn)題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）哪個(gè)是結(jié)點(diǎn)g的雙親？（4）哪些是結(jié)點(diǎn)g的祖先？（5）哪些是結(jié)點(diǎn)g的孩子？（6）哪些是結(jié)點(diǎn)e的孩子？（7）哪些是結(jié)點(diǎn)e的兄弟？哪些是結(jié)點(diǎn)f的兄弟？（8）結(jié)點(diǎn)b和n的層次號(hào)分別是什么？（9）樹(shù)的深度是多少？（10）以結(jié)點(diǎn)c為根的子樹(shù)深度是多少？2. 一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別。3. 試分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和二叉樹(shù)的所有不同形態(tài)？4. 已知用一維數(shù)組存放的一棵完全二叉樹(shù)：ABCDEFGHIJKL，寫出該二叉樹(shù)的先序、中序和后序遍歷序列。5. 一棵深度為H的滿k叉樹(shù)有如下性質(zhì)：第H層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹(shù)，如果按層次自上至下，從左到右順序從1開(kāi)始對(duì)全部結(jié)點(diǎn)編號(hào)，回答下列問(wèn)題：（1）各層的結(jié)點(diǎn)數(shù)目是多少？（2）編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號(hào)是多少？（3）編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號(hào)是多少？（4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？6. 找出所有滿足下列條件的二叉樹(shù)：（1）它們?cè)谙刃虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；（2）它們?cè)诤笮虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；（3）它們?cè)谙刃虮闅v和后序遍歷時(shí)，得到的遍歷序列相同；7. 假設(shè)一棵二叉樹(shù)的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請(qǐng)寫出該二叉樹(shù)的后序遍歷序列。8. 假設(shè)一棵二叉樹(shù)的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請(qǐng)寫出該二叉樹(shù)的后序遍歷序列。9. 給出如圖514所示的森林的先根、后根遍歷結(jié)點(diǎn)序列，然后畫(huà)出該森林對(duì)應(yīng)的二叉樹(shù)。10．給定一組權(quán)值（5，9，11，2，7，16），試設(shè)計(jì)相應(yīng)的哈夫曼樹(shù)。 五、算法設(shè)計(jì)題1. 一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)對(duì)該完全二叉樹(shù)進(jìn)行先序遍歷的算法。2. 給定一棵用二叉鏈表表示的二叉樹(shù)，其中的指針t指向根結(jié)點(diǎn)，試寫出從根開(kāi)始，按層次遍歷二叉樹(shù)的算法，同層的結(jié)點(diǎn)按從左至右的次序訪問(wèn)。3. 寫出在中序線索二叉樹(shù)中結(jié)點(diǎn)P的右子樹(shù)中插入一個(gè)結(jié)點(diǎn)s的算法。4. 給定一棵二叉樹(shù)，用二叉鏈表表示，其根指針為t，試寫出求該二叉樹(shù)中結(jié)點(diǎn)n的雙親結(jié)點(diǎn)的算法。若沒(méi)有結(jié)點(diǎn)n或者該結(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)，分別輸出相應(yīng)的信息；若結(jié)點(diǎn)n有雙親，輸出其雙親的值。習(xí)題5參考答案一、單項(xiàng)選擇題1. C 2. B 3. C 4. D 5. B 6. D 7. C 8. B 9. B 10. B 11. A 12. D 13. A 14. B 15. A二、判斷題1. 2.√ 3. 4.√ 5. 6.√ 7.√ 8.√ 9. 10.三、填空題1. 3，4，6，1，1，2，A，F(xiàn)，G2. n+13. 完全， ，最大，n4. 555. 中序6. 2n，n1，n+17. n2+18. 2k1，2k1，2k19. 510. 2h111. 單支樹(shù)，完全二叉樹(shù)12. 2i，2i+1，i/2（或?i/2?）13. 2n，n1，n+114. 帶權(quán)路徑長(zhǎng)度最小15. 結(jié)點(diǎn)數(shù)為0，只有一個(gè)根結(jié)點(diǎn)的樹(shù)16. 二叉鏈表，三叉鏈表17. 雙親結(jié)點(diǎn)18. 指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針19. 1，RChild20. 孩子表示法，雙親表示法，長(zhǎng)子兄弟表示法四、應(yīng)用題1. 解答：根據(jù)給定的邊確定的樹(shù)如圖515所示。其中根結(jié)點(diǎn)為a；葉子結(jié)點(diǎn)有：d、m、n、j、k、f、l；c是結(jié)點(diǎn)g的雙親；a、c是結(jié)點(diǎn)g的祖先；j、k是結(jié)點(diǎn)g的孩子；m、n是結(jié)點(diǎn)e的子孫；e是結(jié)點(diǎn)d的兄弟；g、h是結(jié)點(diǎn)f的兄弟；結(jié)點(diǎn)b和n的層次號(hào)分別是2和5；樹(shù)的深度為5。2. 解答：度為2的樹(shù)有兩個(gè)分支，但分支沒(méi)有左右之分；一棵二叉樹(shù)也有兩個(gè)分支，但有左右之分，左右子樹(shù)不能交換。3. 解答：　略4. 解答：　先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA5. 解答：（1）第i層上的結(jié)點(diǎn)數(shù)目是mi1。（2）編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號(hào)是((n2)/m)+1。（3）編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號(hào)是(n1)*m+i+1。（4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是(n1)%m≠0。其右兄弟的編號(hào)是n+1。6. 解答：（1）先序序列和中序序列相同的二叉樹(shù)為：空樹(shù)或者任一結(jié)點(diǎn)均無(wú)左孩子的非空二叉樹(shù)；（2）中序序列和后序序列相同的二叉樹(shù)為：空樹(shù)或者任一結(jié)點(diǎn)均無(wú)右孩子的非空二叉樹(shù)；（3）先序序列和后序序列相同的二叉樹(shù)為：空樹(shù)或僅有一個(gè)結(jié)點(diǎn)的二叉樹(shù)。7. 解答：后序序列：ACDBGJKIHFE8. 解答：先序序列：ABCDGEIHFJK9. 解答：先根遍歷：ABCDEFGHIJKLMNO后根遍歷：BDEFCAHJIGKNOML森林轉(zhuǎn)換成二叉樹(shù)如圖516所示。10. 解答：構(gòu)造而成的哈夫曼樹(shù)如圖517所示。試題及答案一、 單選題（每題 2 分，共20分）1. 1. 對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（B ）方面的內(nèi)容。 A．健壯性和可讀性 B．并行性 C．正確性 D．時(shí)空復(fù)雜度2. 2. 在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 A. pnext=HLnext。 HLnext=p。 B. pnext=HL。 HL=p。 C. pnext=HL。 p=HL。 D. HL=p。 pnext=HL。3. 3. 對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( ) 4. 4. 一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. AOV網(wǎng)是一種（ ）。 A．有向圖 B．無(wú)向圖 C．無(wú)向無(wú)環(huán)圖 D．有向無(wú)環(huán)圖6. 6. 采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（ ）。A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. 若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為（ ）參數(shù)。A．值 B．函數(shù) C．指針 D．引用8. 8. 在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。A．行號(hào) B．列號(hào) C．元素值 D．非零元素個(gè)數(shù)9. 9. 快速排序在最壞情況下的時(shí)間復(fù)雜度為（ ）。A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)二、 二、 運(yùn)算題（每題 6 分，共24分）1. 1. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_(kāi)____________________。2. 2. 隊(duì)列的插入操作是在隊(duì)列的___尾______進(jìn)行，刪除操作是在隊(duì)列的____首______進(jìn)行。3. 3. 當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？眨瑒t表示棧滿的條件是___top==0___(要超出才為滿)_______________。4. 4. 對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_(kāi)________，在表尾插入元素的時(shí)