【文章內容簡介】 時，具有最大高度。 【答案】（ 1）完全二叉樹 （ 2）單支樹，樹中任一結點（除最后一個結點是葉子外），只有左子女或只有右子女。 6．已知二叉樹有 50 個葉子結點，則該二叉樹的總結點數(shù)至少是 _____________。 【答案】 99 【解析】在二叉樹中， N0 = N2+1，所以，有 50 個葉子結點的二叉樹，有 49 個度為 2 的結點。若要使該二叉樹的結點數(shù)最少，度為 1 的結點應為 0 個，即總結點數(shù) N= N0 +N1+ N2 =99。 7．具有 n 個結點的滿二叉樹，其葉結點的個數(shù)是 _____________。 【答案】 (n+1） /2 8． 每一棵樹都能惟一的轉換為它所對應的二叉樹。若已知一棵二叉樹的先序序列是 BEFCGDH，中序序列是 FEBGCHD，則它的后序序列是 _____________。設上述二叉樹是由某森林轉換而成，則其第一棵的先根次序序列是 _____________。 【答案】 （ 1） FEGHDCB （ 2） BEF（該二叉樹轉換成森林，含三棵樹，其第一棵樹的先根次 序是 BEF） 9．已知一棵二叉樹的先序序列為 ABDECFHG，中序序列為 DBEAHFCG，則該二叉樹的根為_____________，左子樹中有 _____________， 右子樹中有 _____________。 【答案】（ 1） A （ 2） DBE （ 3） HFCG 10．先根次序周游樹林正好等同于按 _____________周游對應的二叉樹；后根次序周游樹林正好等同于_____________周游對應的二叉樹。 【答案】（ 1）先根次序 （ 2）中根次序 11．一個深度為 k 的，具有最少結點數(shù)的完全二叉樹按 層次，（同層次從左到右）用自然數(shù)依此對結點編號，則編號最小的葉子的序號是 _____________；編號是 i 的結點所在的層次號是 _____________（根所在的層次號規(guī)定為 1 層）。 【答案】（ 1） 2k2+1 （ 2） ?log2i?+1 【解析】第 k 層 1 個結點，總結點個數(shù)是 2k1，其雙親是 2k1/2=2k2。 12．某二叉樹有 20 個葉子結點，有 30 個結點僅有一個孩子，則該二叉樹的總結點數(shù)為 _____________。 【答案】 69 【解析】在二叉樹中， N0 = N2+1，所以，有 20 個葉子結點的二 叉樹，有 19 個度為 2 的結點。又已知該二叉樹中度為 1 的結點有 30 個，則總結點數(shù) N= N0 +N1+ N2 =69。 13．有數(shù)據(jù) WG={7， 19， 2， 6， 32， 3， 21， 10}，則所建 Huffman 樹的樹高是 _____________，帶權路徑長度 WPL 為 _____________。 【答案】（ 1） 6 （ 2） 261 14．有一份電文中共使用 6 個字符： a， b， c， d， e， f，它們的出現(xiàn)頻率依次為 2， 3， 4， 7， 8， 9，試構造一棵哈夫曼樹，則其加權路徑長度 WPL 為 _____________，字符 c 的編碼 是 _____________。 【答案】（ 1） 80 （ 2） 001（不惟一） 15．具有 N 個結點的二叉樹，采用二叉鏈表存儲，共有 _____________個空鏈域。 【答案】 N+1 【解析】在二叉樹中， N= N0 +N1+ N2 ， N0 = N2+1，空分支數(shù)為 2 N0+N1= N0 +N1+ （ N2+1） = N+1。 16． 8 層完全二叉樹至少有 _____________個結點，擁有 100 個結點的完全二叉樹的最大層數(shù)為_____________。 【答案】（ 1） 128（第 7 層滿，加第 8 層１個） （ 2） 7 17．一棵樹 T 中，包括一個度為 1 的結點，兩個度為 2 的結點，三個度為 3 的結點，四個度為 4 的結點和若干葉子結點，則 T 的葉結點數(shù)為 _____________。 【答案】 21 【解析】已知該樹中結點數(shù)和分支數(shù)的關系分別如下： N= N0 +N1+ N2+N3+ N4 （ 1） N1= N1+ 2N2+3N3+ 4N4 （ 2） 由（ 2）式求得 N=（ 1+2*2+3*3+4*4） +1=31，再由（ 1）式求得 N0=21。 18． n（ n 大于 1）個結點的各棵樹中，其深度最小的那棵樹的深度是 _____________。它共有_____________個葉子結點和 _____________個非葉子結點，其中深度最大的那棵樹的深度是_____________，它共有 _____________個葉子結點和 _____________個非葉子結點。 【答案】（ 1） 2 （ 2） n1 （ 3） 1 （ 4） n （ 5） 1 （ 6） n1 判斷題 1．二叉樹是度為 2 的有序樹（ ） 【答案】 2．完全二叉樹一定存在度為 1 的結點（ ） 【答案】 3．深度為 K 的二叉樹中 結點總數(shù)≤ 2k1（ ） 【答案】 √ 4．由一棵二叉樹的先序序列和后序序列可以惟一確定它（ ） 【答案】 5．完全二叉樹中，若一個結點沒有左孩子，則它必是樹葉（ ） 【答案】 √ 6．用二叉鏈表存儲 n 個結點的二叉樹時，結點的 2n 個指針中有 n+1 個空指針（ ） 【答案】 √ 7．完全二叉樹的存儲結構通常采用順序存儲結構（ ） 【答案】 √ 8．哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近（ ） 【答案】 √ 9．在中序線索二叉樹中，每一非空 的線索均指向其祖先結點（ ） 【答案】 √ 【解析】在二叉樹上，對有左右子女的結點，其中序前驅是其左子樹上按中序遍歷的最右邊的結點（該結點的后繼指針指向祖先），中序后繼是其右子樹上按中序遍歷的最左邊的結點（該結點的前驅指針指向祖先）。 10．二叉樹中序線索化后，不存在空指針域（ ） 【答案】 【解析】非空二叉樹中序遍歷第一個結點無前驅，最后一個結點無后繼，這兩個結點的前驅線索和后繼線索為空指針。 應用題 1．從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結構，將樹，森林轉化為二叉 樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。 【答案】樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹惟一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。 樹和二叉樹的區(qū)別有 3：一是二叉樹的度至多為 2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分支的情況下， 也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個別書上允許為空）。 2．若在內存中存放一個完全二叉樹， 在二叉樹上只進行下面兩個操作： （ 1）尋找某個結點雙親 ； （ 2）尋找某個結點的子女； 請問應該用何種結構來存儲該二叉樹？ 【答案】用順序存儲結構存儲 n 個結點的完全二叉樹。編號為 i 的結點，其雙親編號是 ?i/2?(i=1 時無雙親 )，其左子女是 2i(若 2i≤n，否則 i 無左子女 )，右子女是 2i+1(若 2i+1≤n，否則無右子女 )。 3．求含有 n 個結點、采用順序存儲結構的完全二叉樹中的序號最小的葉子結點的下標。要求寫出簡要步驟。 【答案】根據(jù)完全二叉樹的性質，最后一個結點（編號為 n）的雙親結點的編號是 ?n/2?， 這是最后一個分支結點，在它之后是第一個終端（葉子）結點，故序號最小的葉子結點的下標是 ?n/2?+1。 4．試證明，同一棵二叉樹的所有葉子結點，在先序序列、中序序列以及后序序列中都按相同的相對位置出現(xiàn)（即先后順序相同），例如先序 abc，后序 bca，中序 bac。 【答案】先序遍歷是“根左右”，中序遍歷是“左根右”，后序遍歷是“左右根”。三種遍歷中只是訪問“根”結點的時機不同，對左右子樹均是按左右順序來遍歷的，因此所有葉子都按相同的相對位置出現(xiàn)。 5．試找出滿足下列條件的二叉樹： 1）先序序列與后序序列相同； 2）中序序列與后序序列相同； 3）先序序列與中序序列相同； 4）中序序列與層次序列相同； 【答案】先序遍歷二叉樹的順序是“根 — 左子樹 — 右子樹”，中序遍歷“左子樹 — 根 — 右子樹”，后序遍歷順序是：“左子樹 — 右子樹―根”，根據(jù)以上原則，解答如下： 1）若先序序列與后序序列相同，則或為空樹，或為只有根結點的二叉樹。 2）若中序序列與后序序列相同，則或為空樹，或為任一結點至多只有左子樹的二叉樹。 （ 3）若先序序列與中序序列相同，則或為空樹，或為任一結點至多只有右子樹的二叉樹。 （ 4）若中序序列與層次遍歷序列相同，則 或為空樹，或為任一結點至多只有右子樹的二叉樹 6．已知一棵二叉樹的中序序列和后序序列分別為 GLDHBEIACJFK 和 LGHDIEBJKFCA （ 1）給出這棵二叉樹；（ 2）轉換為對應的森林。 7．一棵非空二叉樹其先序序列和后序序列正好相反，畫出二叉樹的形狀。 【答案】先序序列是 “根左右 ” 后序序列是 “左右根 ”，可見對任意結點，若至多只有左子女或至多只有右子女，均可使先序序列與后序序列相反，圖示如下： 8．假設一棵二叉樹的層次次序（按層次遞增順序排列，同一層次自左向右）為 ABECFGDHI,中序序列為BCDAFEHIG。請畫出該二叉樹，并將其轉換為對應的森林。 【答案】按層次遍歷，第一個結點（若樹不空）為根，該結點在中序序列 中把序列分成左右兩部分：左子樹和右子樹。若左子樹不空，層次序列中第二個結點為左子樹的根；若右子樹為空，則層次序列中第三個結點為右子樹的根。對右子樹也作類似的分析。層次序列的特點是，從左到右每個結點或是當前情況下子樹的根或是葉子。 9．已知一個森林的先序序列和后序序列如下，請構造出該森林。 先序序列： ABCDEFGHIJKLMNO 后序序列： CDEBFHIJGAMLONK 【答案】森林的先序序列和后序序列對應其轉換的二叉樹的先序序列和中序序列，應先據(jù)此構造二叉樹，再構造出森林。 10．一棵二叉樹的先序、中序、后序序列如下，其中一部分未標出，請構造出該二叉樹。 先序序列 ： _ _ C D E _ G H I _ K 中序 序列 ： C B _ _ F A _ J K I G 后序序列 ： _ E F D B _ J I H _ A 【答案】 11．設有正文 AADBAACACCDACACAAD，字符集為 A， B， C， D，設計一套二進制編碼，使得上述正文的編碼最短?！敬鸢浮孔址?A， B， C， D 出現(xiàn)的次數(shù)為 9， 1， 5， 3。其哈夫曼編碼如下： A:1， B:000，C:01， D:001 。 12．已知下列字符 A、 B、 C、 D、 E、 F、 G 的權值分別為 1 8， 11，試填寫出其對應哈夫曼樹 HT 的存儲結構的初態(tài)和終態(tài)。 第 7 章 圖 選擇題 1．對于一個具有 n 個頂點和 e 條邊的有向圖，在用鄰接表表示圖時，拓撲排序算法時間復雜度為（ ） A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n) 【答案】 B 2．設無向圖的頂點個數(shù)為 n，則該圖最多有（ ）條邊。 A） n1 B） n(n1)/2 C） n(n+1)/2 D） n2 【答案】 B 3．連通分量指的是（ ） A） 無向圖中的極小連通子圖 B） 無向圖中的極大連通子圖 C） 有向圖中的極小連通子圖 D） 有向圖中的極大連通子圖 【答案】 B 4． n 個結點的完全有向圖含有邊的數(shù)目（ ） A） n*n B） n（ n+1） C） n/2 D） n*（ n1） 【答案】 D 5．關 鍵路徑是（ ） A） AOE 網(wǎng)中從源點到匯點的最長路徑 B） AOE 網(wǎng)中從源點到匯點的最短路徑 C） AOV 網(wǎng)中從源點到匯點的最長路徑 D） AOV 網(wǎng)中從源點到匯點的最短路徑 【答案】 A 6．有向圖中一個頂點的度是該頂點的（ ） A）入度 B） 出度 C） 入度與出度之和 D） （入度 +出度） /2 【答案】 C 7．有 e 條邊的無向圖，若用鄰接表存儲，表中有（ ）邊結點。 A） e B） 2e C） e1 D） 2(e1) 【答案】 B 8．實現(xiàn)圖的廣度優(yōu)先搜索算法需使用的輔助數(shù)據(jù)結構為（ ） A） 棧