【正文】 優(yōu)先遍歷序列為 ABDCEF 5．已知下面是某無(wú)向圖的鄰接表，畫(huà)出該無(wú)向圖，并分別給出從 A 出發(fā)的深度優(yōu)先搜索生成樹(shù)和廣度優(yōu)先搜索生成樹(shù)。 （ 2）鄰接矩陣 中如果第 i 行第 j 列的元素非 0 則表示頂點(diǎn) i 與頂點(diǎn) j 相連。并說(shuō)明在 n 個(gè)頂 點(diǎn)的無(wú)向完全圖中，邊的條數(shù)為 n(n1)/2。其中， V={ v1, v2, v3, v4, v5}， E={v2, v1, v3, v2, v4, v3, v4, v2, v1, v4, v4, v5, v5, v1}，請(qǐng)畫(huà)出該有向圖并判斷是否是強(qiáng)連通圖。（ ） 【答案】 12．假設(shè)一個(gè)有 n 個(gè)頂點(diǎn)和 e 條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn) vi 相關(guān)的所有弧的時(shí)間復(fù)雜度是 O(n*e) 。（ ） 【答案】√ 8．任何一個(gè)關(guān)鍵活動(dòng)提前完成 , 那么整個(gè)工程將會(huì)提前完成。（ ） 【答案】√ 4．有 n1 條邊的圖一定是生成樹(shù)。 【答案】設(shè)邊的信息表示為（始點(diǎn)，終點(diǎn)，權(quán)值），則在 Kruscal 算法構(gòu)造最小生成樹(shù)過(guò)程中順序選出的各條邊為：（ 3 ， 5， 1），（ 2， 4， 2），（ 1， 5， 3），（ 1， 2， 3）。 【答案】（ 1）出邊 （ 2） 入邊 8． 對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的無(wú)向圖，當(dāng)分別采用鄰接矩陣、鄰接表表示時(shí)，求任一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度依次為 _____________和 _____________。 【答案】 n1 4．假定一個(gè)圖具有 n 個(gè)頂點(diǎn)和 e 條邊，則采用鄰接矩陣、鄰接表表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為_(kāi)____________和 _____________。 A） n1 B） n(n1)/2 C） n(n+1)/2 D） n2 【答案】 B 3．連通分量指的是（ ） A） 無(wú)向圖中的極小連通子圖 B） 無(wú)向圖中的極大連通子圖 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 條邊的無(wú)向圖，若用鄰接表存儲(chǔ)，表中有（ ）邊結(jié)點(diǎn)?！敬鸢浮孔址?A， B， C， D 出現(xiàn)的次數(shù)為 9， 1， 5， 3。 9．已知一個(gè)森林的先序序列和后序序列如下，請(qǐng)構(gòu)造出該森林。 【答案】按層次遍歷，第一個(gè)結(jié)點(diǎn)（若樹(shù)不空）為根，該結(jié)點(diǎn)在中序序列 中把序列分成左右兩部分：左子樹(shù)和右子樹(shù)。 （ 4）若中序序列與層次遍歷序列相同，則 或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù) 6．已知一棵二叉樹(shù)的中序序列和后序序列分別為 GLDHBEIACJFK 和 LGHDIEBJKFCA （ 1）給出這棵二叉樹(shù)；（ 2）轉(zhuǎn)換為對(duì)應(yīng)的森林。三種遍歷中只是訪(fǎng)問(wèn)“根”結(jié)點(diǎn)的時(shí)機(jī)不同，對(duì)左右子樹(shù)均是按左右順序來(lái)遍歷的，因此所有葉子都按相同的相對(duì)位置出現(xiàn)。要求寫(xiě)出簡(jiǎn)要步驟。 樹(shù)和二叉樹(shù)的區(qū)別有 3：一是二叉樹(shù)的度至多為 2，樹(shù)無(wú)此限制；二是二叉樹(shù)有左右子樹(shù)之分，即使在只有一個(gè)分支的情況下， 也必須指出是左子樹(shù)還是右子樹(shù)，樹(shù)無(wú)此限制；三是二叉樹(shù)允許為空，樹(shù)一般不允許為空（個(gè)別書(shū)上允許為空）。 【答案】（ 1） 2 （ 2） n1 （ 3） 1 （ 4） n （ 5） 1 （ 6） n1 判斷題 1．二叉樹(shù)是度為 2 的有序樹(shù)（ ） 【答案】 2．完全二叉樹(shù)一定存在度為 1 的結(jié)點(diǎn)（ ） 【答案】 3．深度為 K 的二叉樹(shù)中 結(jié)點(diǎn)總數(shù)≤ 2k1（ ） 【答案】 √ 4．由一棵二叉樹(shù)的先序序列和后序序列可以惟一確定它（ ） 【答案】 5．完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是樹(shù)葉（ ） 【答案】 √ 6．用二叉鏈表存儲(chǔ) n 個(gè)結(jié)點(diǎn)的二叉樹(shù)時(shí)，結(jié)點(diǎn)的 2n 個(gè)指針中有 n+1 個(gè)空指針（ ） 【答案】 √ 7．完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)通常采用順序存儲(chǔ)結(jié)構(gòu)（ ） 【答案】 √ 8．哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近（ ） 【答案】 √ 9．在中序線(xiàn)索二叉樹(shù)中，每一非空 的線(xiàn)索均指向其祖先結(jié)點(diǎn)（ ） 【答案】 √ 【解析】在二叉樹(shù)上，對(duì)有左右子女的結(jié)點(diǎn)，其中序前驅(qū)是其左子樹(shù)上按中序遍歷的最右邊的結(jié)點(diǎn)（該結(jié)點(diǎn)的后繼指針指向祖先），中序后繼是其右子樹(shù)上按中序遍歷的最左邊的結(jié)點(diǎn)（該結(jié)點(diǎn)的前驅(qū)指針指向祖先）。 【答案】（ 1） 128（第 7 層滿(mǎn)，加第 8 層１個(gè)） （ 2） 7 17．一棵樹(shù) 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ù)為 _____________。 【答案】（ 1） 6 （ 2） 261 14．有一份電文中共使用 6 個(gè)字符： a， b， c， d， e， f，它們的出現(xiàn)頻率依次為 2， 3， 4， 7， 8， 9，試構(gòu)造一棵哈夫曼樹(shù)，則其加權(quán)路徑長(zhǎng)度 WPL 為 _____________，字符 c 的編碼 是 _____________。 12．某二叉樹(shù)有 20 個(gè)葉子結(jié)點(diǎn)，有 30 個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)為 _____________。 【答案】 （ 1） FEGHDCB （ 2） BEF（該二叉樹(shù)轉(zhuǎn)換成森林，含三棵樹(shù)，其第一棵樹(shù)的先根次 序是 BEF） 9．已知一棵二叉樹(shù)的先序序列為 ABDECFHG，中序序列為 DBEAHFCG，則該二叉樹(shù)的根為_(kāi)____________，左子樹(shù)中有 _____________， 右子樹(shù)中有 _____________。 7．具有 n 個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)，其葉結(jié)點(diǎn)的個(gè)數(shù)是 _____________。 【答案】（ 1）完全二叉樹(shù) （ 2）單支樹(shù)，樹(shù)中任一結(jié)點(diǎn)（除最后一個(gè)結(jié)點(diǎn)是葉子外），只有左子女或只有右子女。amp。與森林 F 對(duì)應(yīng)的二叉 樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（ ） A） M1 B） M1+M2 C） M3 D） M2+M3 【答案】 D 【解析】當(dāng)森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)時(shí)，二叉樹(shù)的根結(jié)點(diǎn)及其左子樹(shù)是由森林的第一棵樹(shù)轉(zhuǎn)化而來(lái)，二叉樹(shù)的右子樹(shù)是由森林的其余樹(shù)轉(zhuǎn)化而來(lái)。 【答案】 42 6．廣義表運(yùn)算式 HEAD（ TAIL（（ a， b， c），（ x， y， z）））的結(jié)果為 _____________。 【答案】（ 1）線(xiàn)性結(jié)構(gòu) （ 2）順序結(jié)構(gòu) 2．對(duì)于二維數(shù)組或多維數(shù)組，分為按 _____________和按 _____________兩種不同的存儲(chǔ)方式存儲(chǔ)。 【答案】任意個(gè)連續(xù)的字符組成的子序列 判斷題 1． KMP 算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)變?。? ） 【答案】√ 【解析】 KMP 算法的改進(jìn)在于：每當(dāng)一趟匹配過(guò)程中出現(xiàn)字符比較不相等時(shí)，不需回溯主串指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。),length(S2)))=concat(ABCG, 1234)= ABCG1234 3．設(shè)正文串長(zhǎng)度為 n，模式串長(zhǎng)度為 m，則串匹配的 KMP 算法的時(shí)間復(fù)雜度為_(kāi)____________。839。 replase(s,t,v)用 v 替換 s 中出現(xiàn)的所有與 t 相等的子串 ,index(s,t,i)當(dāng) s 中存在與 t 值相同的子串時(shí)，返回它在 s 中的第 i 個(gè)字符之后第一次出現(xiàn)的位置。 【答案】（ 1）滿(mǎn) （ 2）空 （ 3） n （ 4）棧底 （ 5）兩棧頂指針相鄰 13．無(wú)論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來(lái)說(shuō)，進(jìn)行插入和刪除運(yùn)算的時(shí)間復(fù)雜度均相同為 _____________。 8．用下標(biāo) 0 開(kāi)始的 N 元數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，為實(shí)現(xiàn)下標(biāo)變量 M 加 1 后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)，可采用的表達(dá)式是： M=_____________。 sdata=x。 【答案】假溢出時(shí)大量移動(dòng)數(shù)據(jù)元素。 【答案】（ 1）操作受限（或限定僅在表尾進(jìn)行插入和刪除操作） （ 2）后進(jìn)先出 2．設(shè)有一個(gè)空棧，棧頂指針為 1000H(十六進(jìn)制 )，現(xiàn)有輸入序列為 1， 2， 3， 4， 5，經(jīng)過(guò)PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，輸出序列是 _____________，而棧頂指針值是 _____________H。rear=s。front=s。 【答案】 Lnextnext==L 第 3 章 桟和隊(duì)列 選擇題 1．一個(gè)棧的輸入序列為 123? n，若輸出序列的第一個(gè)元素是 n，輸出第 i（ 1≤ i≤ n）個(gè)元素是（ ） A）不確定 B） ni+1 C） i D） ni 【答案】 B 2．設(shè)棧 S 和隊(duì)列 Q 的初始狀態(tài)為空，元素 e1， e2， e3， e4， e5 和 e6 依次通過(guò)棧 S，一個(gè)元素出棧后即進(jìn)隊(duì)列 Q，若 6 個(gè)元素出隊(duì)的序列是 e2， e4， e3， e6， e5， e1 則棧 S 的容量至少應(yīng)該是（ ） A） 6 B） 4 C） 3 D） 2 【答案】 C 【答案】 B 【解析】循環(huán)隊(duì)列是解決假溢出的問(wèn)題，通常把一維數(shù)組看成首尾相接。 pdata= _____________。 【答案】從任一結(jié)點(diǎn)出發(fā)都可訪(fǎng)問(wèn)到鏈表中每一個(gè)元素。 3．線(xiàn)性表的順序存儲(chǔ)是通過(guò) _____________來(lái)反應(yīng)元素之間的邏輯關(guān)系，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò) _____________來(lái)反應(yīng)元素之間的邏輯關(guān)系。 【答案】 A 填空題 1．線(xiàn)性表 L=（ a1， a2，?， an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是 _____________。 pprior=q。 qnext=p。 pprior=qnext。 qprior=pprior。 【答案】 O(n) 第 2 章 線(xiàn)性表 2．若長(zhǎng)度為 n 的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第 i 個(gè)位置插入一個(gè)新元素的算法時(shí)間復(fù)雜度為（ ） (1≤ i≤ n+1)。 (n1) sum=1。i++) for(j=n。 while(in) i=i*2。kj。in。j=i。 9．已知如下程序段 for(i=n。 5. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的 _____________和 _____________，以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的 _____________，設(shè)計(jì)出相應(yīng)的 _____________。j=i。j++) x=x+1。 A）動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B）順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C）線(xiàn)性結(jié)構(gòu)、非線(xiàn)性結(jié)構(gòu) D）初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu) 【答案】 C 6．在下面的程序段中，對(duì) x 的賦值的語(yǔ)句頻度為（ ） for(i=0。 A）可執(zhí)行性、可移植性、可擴(kuò)充性 B） 可執(zhí)行性、確定性、有窮性 C） 確定性、有窮性、穩(wěn)定性 D） 易讀性、穩(wěn)定性、安全性 【答案】 B 5．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類(lèi)。jn。i) for(j=1。 【答案】算法的時(shí)間復(fù)雜度和空間復(fù)雜度。 【答案】（ 1）有窮性 （ 2）確定性 （ 3）可行性。 {語(yǔ)句 2} for(j=n。 【答案】（ 1） n+1 （ 2） n （ 3） n(n+3)/2 （ 4） n(n+1)/2 10．在下面的程 序段中，對(duì)ｘ的賦值語(yǔ)句的頻度為 _____________（表示為 n 的函數(shù)） for(i=0。j++) for(k=0。 i=1。inl。 【答案】 (n+3)(n2)/2 13. 下面程序段的時(shí)間復(fù)雜度為 _____________。i++) sum+=1。 ppriornext=q。 qnext=p。 ppriornext=q。 q