【正文】 有 n 個(gè)頂點(diǎn)和 e 條邊，則采用鄰接矩陣、鄰接表表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為_____________和 _____________。 【答案】 2 2．具有 n 個(gè)頂點(diǎn)的無向完全圖中包含有 _____________條邊，具有 n 個(gè)頂點(diǎn)的有向完全圖中包含有_____________條邊。 A） n1 B） n(n1)/2 C） n(n+1)/2 D） n2 【答案】 B 3．連通分量指的是（ ） A） 無向圖中的極小連通子圖 B） 無向圖中的極大連通子圖 C） 有向圖中的極小連通子圖 D） 有向圖中的極大連通子圖 【答案】 B 4． n 個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（ ） A） n*n B） n（ n+1） C） n/2 D） n*（ n1） 【答案】 D 5．關(guān) 鍵路徑是（ ） A） AOE 網(wǎng)中從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B） AOE 網(wǎng)中從源點(diǎn)到匯點(diǎn)的最短路徑 C） AOV 網(wǎng)中從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 D） AOV 網(wǎng)中從源點(diǎn)到匯點(diǎn)的最短路徑 【答案】 A 6．有向圖中一個(gè)頂點(diǎn)的度是該頂點(diǎn)的（ ） A）入度 B） 出度 C） 入度與出度之和 D） （入度 +出度） /2 【答案】 C 7．有 e 條邊的無向圖，若用鄰接表存儲(chǔ)，表中有（ ）邊結(jié)點(diǎn)。 12．已知下列字符 A、 B、 C、 D、 E、 F、 G 的權(quán)值分別為 1 8， 11，試填寫出其對(duì)應(yīng)哈夫曼樹 HT 的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)。【答案】字符 A， B， C， D 出現(xiàn)的次數(shù)為 9， 1， 5， 3。 10．一棵二叉樹的先序、中序、后序序列如下，其中一部分未標(biāo)出，請(qǐng)構(gòu)造出該二叉樹。 9．已知一個(gè)森林的先序序列和后序序列如下，請(qǐng)構(gòu)造出該森林。對(duì)右子樹也作類似的分析。 【答案】按層次遍歷，第一個(gè)結(jié)點(diǎn)（若樹不空）為根，該結(jié)點(diǎn)在中序序列 中把序列分成左右兩部分：左子樹和右子樹。 【答案】先序序列是 “根左右 ” 后序序列是 “左右根 ”，可見對(duì)任意結(jié)點(diǎn)，若至多只有左子女或至多只有右子女，均可使先序序列與后序序列相反，圖示如下： 8．假設(shè)一棵二叉樹的層次次序（按層次遞增順序排列，同一層次自左向右）為 ABECFGDHI,中序序列為BCDAFEHIG。 （ 4）若中序序列與層次遍歷序列相同，則 或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹 6．已知一棵二叉樹的中序序列和后序序列分別為 GLDHBEIACJFK 和 LGHDIEBJKFCA （ 1）給出這棵二叉樹；（ 2）轉(zhuǎn)換為對(duì)應(yīng)的森林。 2）若中序序列與后序序列相同，則或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹的二叉樹。三種遍歷中只是訪問“根”結(jié)點(diǎn)的時(shí)機(jī)不同，對(duì)左右子樹均是按左右順序來遍歷的，因此所有葉子都按相同的相對(duì)位置出現(xiàn)。 4．試證明，同一棵二叉樹的所有葉子結(jié)點(diǎn)，在先序序列、中序序列以及后序序列中都按相同的相對(duì)位置出現(xiàn)（即先后順序相同），例如先序 abc，后序 bca，中序 bac。要求寫出簡(jiǎn)要步驟。編號(hào)為 i 的結(jié)點(diǎn)，其雙親編號(hào)是 ?i/2?(i=1 時(shí)無雙親 )，其左子女是 2i(若 2i≤n，否則 i 無左子女 )，右子女是 2i+1(若 2i+1≤n，否則無右子女 )。 樹和二叉樹的區(qū)別有 3：一是二叉樹的度至多為 2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個(gè)分支的情況下， 也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個(gè)別書上允許為空）。 應(yīng)用題 1．從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉 樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。 【答案】（ 1） 2 （ 2） n1 （ 3） 1 （ 4） n （ 5） 1 （ 6） n1 判斷題 1．二叉樹是度為 2 的有序樹（ ） 【答案】 2．完全二叉樹一定存在度為 1 的結(jié)點(diǎn)（ ） 【答案】 3．深度為 K 的二叉樹中 結(jié)點(diǎn)總數(shù)≤ 2k1（ ） 【答案】 √ 4．由一棵二叉樹的先序序列和后序序列可以惟一確定它（ ） 【答案】 5．完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉（ ） 【答案】 √ 6．用二叉鏈表存儲(chǔ) n 個(gè)結(jié)點(diǎn)的二叉樹時(shí)，結(jié)點(diǎn)的 2n 個(gè)指針中有 n+1 個(gè)空指針（ ） 【答案】 √ 7．完全二叉樹的存儲(chǔ)結(jié)構(gòu)通常采用順序存儲(chǔ)結(jié)構(gòu)（ ） 【答案】 √ 8．哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近（ ） 【答案】 √ 9．在中序線索二叉樹中，每一非空 的線索均指向其祖先結(jié)點(diǎn)（ ） 【答案】 √ 【解析】在二叉樹上，對(duì)有左右子女的結(jié)點(diǎn)，其中序前驅(qū)是其左子樹上按中序遍歷的最右邊的結(jié)點(diǎn)（該結(jié)點(diǎn)的后繼指針指向祖先），中序后繼是其右子樹上按中序遍歷的最左邊的結(jié)點(diǎn)（該結(jié)點(diǎn)的前驅(qū)指針指向祖先）。 18． n（ n 大于 1）個(gè)結(jié)點(diǎn)的各棵樹中，其深度最小的那棵樹的深度是 _____________。 【答案】（ 1） 128（第 7 層滿，加第 8 層１個(gè)） （ 2） 7 17．一棵樹 T 中，包括一個(gè)度為 1 的結(jié)點(diǎn)，兩個(gè)度為 2 的結(jié)點(diǎn)，三個(gè)度為 3 的結(jié)點(diǎn)，四個(gè)度為 4 的結(jié)點(diǎn)和若干葉子結(jié)點(diǎn)，則 T 的葉結(jié)點(diǎn)數(shù)為 _____________。 【答案】 N+1 【解析】在二叉樹中， N= N0 +N1+ N2 ， N0 = N2+1，空分支數(shù)為 2 N0+N1= N0 +N1+ （ N2+1） = N+1。 【答案】（ 1） 6 （ 2） 261 14．有一份電文中共使用 6 個(gè)字符： a， b， c， d， e， f，它們的出現(xiàn)頻率依次為 2， 3， 4， 7， 8， 9，試構(gòu)造一棵哈夫曼樹，則其加權(quán)路徑長(zhǎng)度 WPL 為 _____________，字符 c 的編碼 是 _____________。又已知該二叉樹中度為 1 的結(jié)點(diǎn)有 30 個(gè)，則總結(jié)點(diǎn)數(shù) N= N0 +N1+ N2 =69。 12．某二叉樹有 20 個(gè)葉子結(jié)點(diǎn)，有 30 個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總結(jié)點(diǎn)數(shù)為 _____________。 【答案】（ 1）先根次序 （ 2）中根次序 11．一個(gè)深度為 k 的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹按 層次，（同層次從左到右）用自然數(shù)依此對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)最小的葉子的序號(hào)是 _____________；編號(hào)是 i 的結(jié)點(diǎn)所在的層次號(hào)是 _____________（根所在的層次號(hào)規(guī)定為 1 層）。 【答案】 （ 1） FEGHDCB （ 2） BEF（該二叉樹轉(zhuǎn)換成森林，含三棵樹，其第一棵樹的先根次 序是 BEF） 9．已知一棵二叉樹的先序序列為 ABDECFHG，中序序列為 DBEAHFCG，則該二叉樹的根為_____________，左子樹中有 _____________， 右子樹中有 _____________。若已知一棵二叉樹的先序序列是 BEFCGDH，中序序列是 FEBGCHD，則它的后序序列是 _____________。 7．具有 n 個(gè)結(jié)點(diǎn)的滿二叉樹，其葉結(jié)點(diǎn)的個(gè)數(shù)是 _____________。 【答案】 99 【解析】在二叉樹中， N0 = N2+1，所以，有 50 個(gè)葉子結(jié)點(diǎn)的二叉樹，有 49 個(gè)度為 2 的結(jié)點(diǎn)。 【答案】（ 1）完全二叉樹 （ 2）單支樹，樹中任一結(jié)點(diǎn)（除最后一個(gè)結(jié)點(diǎn)是葉子外），只有左子女或只有右子女。 【答案】（ 1） 2H1 （ 2） 2H1 （ 3） H=?log2N?+1 3．一棵有 n 個(gè)結(jié)點(diǎn)的滿二叉樹有 _____________個(gè)度為 1 的結(jié)點(diǎn)，有 _____________個(gè)分支（非終端）結(jié)點(diǎn)和 _____________個(gè)葉子，該滿二叉樹的深度為 _____________。amp。 填空題 1．在二叉樹中，指針 p 所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是 _____________。與森林 F 對(duì)應(yīng)的二叉 樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（ ） A） M1 B） M1+M2 C） M3 D） M2+M3 【答案】 D 【解析】當(dāng)森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹時(shí)，二叉樹的根結(jié)點(diǎn)及其左子樹是由森林的第一棵樹轉(zhuǎn)化而來，二叉樹的右子樹是由森林的其余樹轉(zhuǎn)化而來。 【答案】 3．稀疏矩陣在用三元組表示法時(shí)，可節(jié)省空間，但對(duì)矩陣的操作會(huì)增加算法的難度及耗費(fèi)更多的時(shí)間（ ） 【答案】√ 3．一個(gè)稀疏矩陣為 ，則對(duì)應(yīng)的三元組線性表是什么？其對(duì)應(yīng)的十字鏈表是什么？ 【答案】由于線性表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)稀疏矩陣的一個(gè)非零元素，其中包括 3 個(gè)字段，分別為該元素的行下標(biāo)、列下標(biāo)和值，結(jié)點(diǎn)間的次序按矩陣的行優(yōu)先順序排列，這個(gè)線 性表用順序的方法存儲(chǔ)在連續(xù)的存儲(chǔ)區(qū)，則對(duì)應(yīng)的三元組為 其十 字鏈表形式為： 第 6 章 樹 選擇題 1．一棵具 有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（ ） A） ?log2n ?+1 B） log2n +1 C） ? log2n ? D） log2n1 【答案】 A 2．有關(guān)二叉樹下列說法正確的是（ ） A）二叉樹的度為 2 B）一棵二叉樹的度可以小于 2 C）二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為 2 D）二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為 2 【答案】 B 3．二叉樹的第 I 層上最多含有結(jié)點(diǎn)數(shù)為（ ） A） 2I B） 2I11 C） 2I1 D） 2I1 【答案】 C 4．具有 10 個(gè)葉結(jié)點(diǎn)的二叉樹中有（ ）個(gè)度為 2 的結(jié)點(diǎn) A） 8 B） 9 C） 10 D） 11 【答案】 B 6．由 3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（ ） A） 2 B） 3 C） 4 D） 5 【答案】 D 8．有 n 個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（ ） A）不確定 B） 2n C） 2n+1 D） 2n1 【答案】 D 9．一棵非空的二叉樹的先序遍歷序列與后序遍歷 序列正好相反，則該二叉樹一定滿足（ ） A）所有的結(jié)點(diǎn)均無左孩子 B）所有的結(jié)點(diǎn)均無右孩子 C）只有一個(gè)葉子結(jié)點(diǎn) D）是任意一棵二叉樹 【答案】 C 10．一棵完全二叉樹上有 1001 個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ） A） 250 B） 500 C） 505 D）以上答案都不對(duì) 【答案】 D 11．已知一棵二叉樹的后序遍歷序列為 DABEC，中序遍歷序列為 DEBAC，則它的先序遍歷序列為（ ） A） ACBED B） DECAB C） DEABC D） CEDBA 【答案】 D 【解析】依據(jù) 后序遍歷序列可確定根結(jié)點(diǎn)為 C；再依據(jù)中序遍歷序列可知其左子樹由 DEBA 構(gòu)成，右子樹為空；又由左子樹的后序遍歷序列可知其根結(jié)點(diǎn)為 E，由中序遍歷序列可知 E 的左子樹為 D，右子樹由 BA構(gòu)成，所以求得該二叉樹的先序遍歷序列為選項(xiàng) D）。 【答案】 42 6．廣義表運(yùn)算式 HEAD（ TAIL（（ a， b， c），（ x， y， z）））的結(jié)果為 _____________。 【答案】（ d1c1+1） *（ d2c2+1） 4．二維數(shù)組 A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，且 A[0][0]的地址是 200，則 A[6][12]的地址是 。 【答案】（ 1）線性結(jié)構(gòu) （ 2）順序結(jié)構(gòu) 2．對(duì)于二維數(shù)組或多維數(shù)組，分為按 _____________和按 _____________兩種不同的存儲(chǔ)方式存儲(chǔ)。 3．一個(gè) n*n 的對(duì)稱矩陣，如果以行或列為主序放入內(nèi)存，則其容量為（ ） A） n*n B） n*n／ 2 C）（ n+1） *n／ 2 D）（ n+1） *（ n+1）／ 2 【答案】 C 【解析】對(duì)稱矩陣可用上（或下）三角矩陣存儲(chǔ)，第一行存 1 個(gè)，第二行存 2 個(gè)，?，第 n行存 n 個(gè)，共 1+2+? +n=（ n+1） *n/2。 【答案】任意個(gè)連續(xù)的字符組成的子序列 判斷題 1． KMP 算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)變小（ ） 【答案】√ 【解析】 KMP 算法的改進(jìn)在于：每當(dāng)一趟匹配過程中出現(xiàn)字符比較不相等時(shí)，不需回溯主串指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。 【答案】?jī)纱拈L(zhǎng)度相等且兩串中對(duì)應(yīng)位置上的字符也相等。),length(S2)))=concat(ABCG,