計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)圖歷年真題試卷匯編3

1、計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)（圖）歷年真題試卷匯編（總分：58.00 ,做題時間：90分鐘）綜合題（總題數(shù)：23,分?jǐn)?shù)：58.00）1.下面的鄰接表表示一個給定的無向圖。（1）給出從頂點v1開始，對圖G用深度優(yōu)先搜索法進(jìn)行遍【復(fù)旦大學(xué)歷時的頂點序列；（2）給出從頂v1, 1開始，對圖G用廣度優(yōu)先搜索法進(jìn)行遍歷時的頂點序歹U。1998 六（10 分）（分?jǐn)?shù)：2.00） 正確答案：(正確答案：(1)v 1 V 2 v 4 v 3 v 5 v 6 v 1 V 2 v 3 V 4 V 5 V s) 解析：給出圖G: | （分?jǐn)?shù)：4.00）.畫出G的鄰接表表示圖；（分?jǐn)?shù)： 2.00）正確答案：（正確答案:

2、 解析:.根據(jù)你畫出的鄰接表，以頂點為根，畫出G的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。【南開大學(xué) 1997五（14分）】【煙臺大學(xué)2007四、3（15分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：廣度優(yōu)先生成樹，深度優(yōu)先生成樹，為節(jié)省篇幅，生成樹橫畫，下同。II）解析：寫出所有可能得到的DFS序列。正確答案：（正確答案：因未確定存儲結(jié)構(gòu)，從頂點1開始的DFS樹不唯一，現(xiàn)列出兩個:口）2.已知一個有向圖如圖所示， 則從頂點a出發(fā)進(jìn)行深度優(yōu)先遍歷, 京交通大學(xué)2006四、4（5分）】（分?jǐn)?shù)：2.00） 正確答案：（正確答案：共 8 個：adbcfe , adbfce , adcbfe , adcebf

3、 adcefb , adebcj,adebfc , adefbc） 解析：解答下面的問題：【西安電子科技大學(xué) 2000計算機應(yīng)用六（10分）】（分?jǐn)?shù)：4.00）.如果每個指針需要4字節(jié)，每個頂點的標(biāo)號占2字節(jié)，每條邊的權(quán)值占2字節(jié)。下圖采用哪種表示法所需的空間較多？為什么？（分?jǐn)?shù)：2.00）正確答案：（正確答案：鄰接矩陣：（6*6個元素）*2字節(jié)/元素=72字節(jié) 鄰接表：表頭向量6*（4+2）+邊結(jié) 點9*（2+2+4）*2=180 字節(jié) 鄰接多重表：表頭向量 6*（4+2）+邊結(jié)點9*（2+2+2+4+4）=162字節(jié) 鄰接表占用空 間較多，因為邊較多，邊結(jié)點又是邊數(shù)的2倍，一般來說，鄰接矩

4、陣所占空間與邊個數(shù)無關(guān)（不考慮壓縮存儲），適合存儲稠密圖，而鄰接表適合存儲稀疏圖。鄰接多重表邊結(jié)點個數(shù)等于邊數(shù)，但結(jié)點中增加了一個 頂點下標(biāo)域和一個指針域。） 解析：.寫出下圖從頂點1開始的：DFS樹。（分?jǐn)?shù)：2.00）解析：下所示的連通圖，請畫出：（1）以頂點為根的深度優(yōu)先生成樹；（5分）（2）如果有關(guān)節(jié)頂點，請找出所有的關(guān)節(jié)頂點（分?jǐn)?shù):2.00）（5分）【清華大學(xué)l 998七（10分）】正確答案：（正確答案：（1）未確定存儲結(jié)構(gòu), 關(guān)節(jié)頂點有3, 1, 8, 7, 2。）解析：其DFS樹不唯一，其中之一（按鄰接點逆序排列)是:某田徑賽中各選手的參賽項目表如下:設(shè)項目A, B,F各表示一數(shù)據(jù)

5、元素，若兩項目不能同時舉行，則將其連線（約束條件）。（分?jǐn)?shù)：4.00）.根據(jù)此表及約束條件畫出相應(yīng)的圖狀結(jié)構(gòu)模型，并畫出此圖的鄰接表結(jié)構(gòu)；（分?jǐn)?shù)：2.00 ）正確答案：（正確答案:解析:【北京科技大學(xué) 1999五2000五（12.寫出從元素A出發(fā)按“廣度優(yōu)先搜索”算法遍歷此圖的元素序列分）】（分?jǐn)?shù)：2.00） 正確答案：（正確答案：AFEDBC）解析：.考慮下圖：|1（1）從頂點A出發(fā)，求它的深度優(yōu)先生成樹。（2）從頂點E出發(fā)，求它的廣度優(yōu)先生成樹。（3）根據(jù)普利姆（Prim）算法，求它的最小生成樹?！旧虾＝煌ù髮W(xué)1999六（12分）】(1)ABGFDEC（分?jǐn)?shù)：2.00） 正確答案：（正確答

6、案：設(shè)該圖用鄰接表存儲結(jié)構(gòu)存儲，頂點的鄰接點按頂點編號升序排列(2)EACFBDG (3)解析:.在什么情況下，Prim算法與Kruskual算法生成不同的 MST?西安電子科技大學(xué) 2000計算機應(yīng)用一、11（5分）1（分?jǐn)?shù)：2.00）正確答案：（正確答案：在邊有相等權(quán)值 解析：（特別是邊的權(quán)值較小且相等）時可能會生成不同的 MST ）6.已知一個無向圖如下圖所示，要求分別用出構(gòu)造過程）?！竟枮I工業(yè)大學(xué)Prim和Kruskal算法生成最小生成樹（假設(shè)以為起點，試畫2000九（8分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：設(shè)連通網(wǎng)N=（V,E），設(shè)V是N的頂點的集合，E是N上邊的集合。Pr

7、im算法從U=u 0 u 0 GV）, TE=開始，重復(fù)執(zhí)行下述操作：在所有uU, vGV- U的邊（u , v） G E中找一條代價最小的邊（u 0 , v 0 ）并入集合TE,同時v 0并入U,直至U=V為止。此時，TE中必有n 1條邊，則T=（U, | TE| ）為N的最小生成樹。Prim算法適合邊稠密的情況，算法的時間復(fù)雜度為O（n 2 ）。Kruskal算法：開始令最小生成樹的初始狀態(tài)為只有刀個頂點而無邊的非連通圖T=（V,），圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入T中，否則舍去此邊而選擇下一條代價最小的邊，直到O

8、(eloge),適合于求稀疏網(wǎng)的最小生成樹。T中所有頂點都在同一連通分量上為止。算法的時間復(fù)雜度為Prim算法構(gòu)造最小生成樹的步驟如這里不再用Prim方法做，而是用 Kruskal算法來構(gòu)造最小生成樹，過程過程如下26題所示，為節(jié)省篇幅，(下圖也可選(2 , 4)代替(3, 4),選(5, 6) o 代替(1 , 5):解析：. 一帶權(quán)無向圖的鄰接矩陣如下，試畫出它的一棵最小生成樹。(分?jǐn)?shù)：2.00)【浙江大學(xué)1994五(8分)】正確答案：(正確答案：設(shè)頂點集合為5, 6回路中，各任選兩條邊，加上邊 解析：1 , 2, 3, 4, 5, 6,由下邊的邏輯圖可以看出，在1,2, 3和4,(2,

9、4),則可構(gòu)成9棵不同的最小生成樹.已知頂點16和輸入邊與權(quán)值的序列(如右圖所示)：每行三個數(shù)表示一條邊的兩個端點和其權(quán)值，共11行。請你:采用鄰接多重表表示該無向網(wǎng)，用類Pascal語言描述該數(shù)據(jù)結(jié)構(gòu)，畫出存儲結(jié)構(gòu)示意圖，要求符合在邊結(jié)點鏈表頭部插入的算法和輸入序列的次序。(2)分別寫出從頂點1出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷頂點序列，以及相應(yīng)的生成樹。(3)按Prim算法列表計算，從頂點1始求最小生成樹，并圖示該樹?！颈本┕I(yè)大學(xué) 1999四(20分)】(分?jǐn)?shù)：2.00)正確答案：(正確答案：(1) |(2)深度優(yōu)先遍歷序列:1, 4, 6, 5, 3, 2;深度優(yōu)先生成樹的邊集合：(1 ,

10、4) , (4 , 6) , (6 , 5) , (5 , 3) , (3, 2) (3)廣度優(yōu)先遍歷序列：1 4 3 2 6 5 ;廣度優(yōu)先生成樹的邊 集合：(1 , 4) , (1 , 3) , (1 , 2) , (4 , 6) , (4 , 5) : (4)按：Prim構(gòu)造過程只畫出最小生成樹的邊和權(quán)值：E(G尸(1 , 4, 3), (4, 3, 4), (3, 5, 1), (3, 2, 2), (3, 6, 10) 解析：.下圖表示一個地區(qū)的通信網(wǎng)，邊表示城市間的通信線路，邊上的權(quán)表示架設(shè)線路花費的代價，如何選擇能溝通每個城市且總代價最省的1條線路，畫出所有可能的選擇?！緰|北大學(xué)

11、2000 、4(4分)】(分?jǐn)?shù)：2.00) 正確答案：(正確答案：最小生成樹的頂點集合：6)=1,2,3,4,5,6,下面兩個邊的集合都可以。E1(G)=(1 ,2, 16), (2, 3, 5), (2, 6, 6), (2, 4, 11), (6, 5, 18) , E2(G)=(1 , 2, 16), (2, 3, 5), (3, 6, 6) , (2 , 4, 11) ,(6,5, 18)II【中國海洋大學(xué)2007 、2(8分)】解析：.試列出下圖中全部可能的拓?fù)渑判蛐蛄?分?jǐn)?shù)：2.00)正確答案：(正確答案：7 個：561234, 516234, 512634, 512364, 15

12、6234, 152364, 152634)解析：11.試給出有向圖的所有拓?fù)湫蛄小颈本┙煌ù髮W(xué)2005五、3(5分)】(分?jǐn)?shù)：2.00) 正確答案：(正確答案：3個：23 1546, 213546, 123546)解析：.對于一個有向圖，不用拓?fù)渑判?，如何判斷圖中是否存在環(huán)？【廈門大學(xué)2006三、3（25/3分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：圖的深度優(yōu)先遍歷可用于拓?fù)渑判?，使用dfs遍歷所得頂點序列是逆拓?fù)湫蛄小＃┙馕觯?對于一個有向圖，除了進(jìn)行拓?fù)渑判?，還可以采用什么辦法判斷圖中是否存在回路？請簡述判斷原則?！颈本┖娇蘸教齑髮W(xué) 2007 、2（3分）】（分?jǐn)?shù)：2.00）正確答案：

13、（正確答案：圖的深度優(yōu)先遍歷可用于判斷圖中是否存在回路。若從有向圖某頂點V出發(fā)進(jìn)行遍歷，在dfs（v）結(jié)束之前出現(xiàn)從頂點 W到頂點V的回邊，由于 W在生成小上是V的子孫，則有向圖中必定存 在包含頂點V和W的環(huán)。） 解析：下圖所示是一帶權(quán)有向圖的鄰接表法存儲表示。其中出邊表中的每個結(jié)點均含有三個字段，依次為邊的另rwrn一個頂點在頂點表中的序號、邊上的權(quán)值和指向下一個邊結(jié)點的指針。試求：I I （分?jǐn)?shù)：8.00）.該帶權(quán)有向圖的圖形；（分?jǐn)?shù)：2.00）|刖石正確答案：（正確答案：I）解析：.從頂點V1為起點的廣度優(yōu)先周游的頂點序列及對應(yīng)的生成樹（即支撐樹）；（分?jǐn)?shù)：2.00）正確答案：（正確答案

14、：V1, V2, V4, V6, V3, V5|_|）解析：.以頂點V1為起點的深度優(yōu)先周游生成樹；（分?jǐn)?shù)：2.00）正確答案：（正確答案：頂點集合 V（G）=V1 , V2, V3, V4, V5, V6邊的集合E（G）=，）解析：.由頂點V1到頂點V3的最短路徑。【中山大學(xué) 1994四（12分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：V1到V3最短路徑（V1 一 V4 V3）為67。）解析：.已知一有向網(wǎng)的鄰接矩陣如下，如需在其中一個結(jié)點建立娛樂中心，要求該結(jié)點距其他各結(jié)點的最長往電大學(xué)2002四、1（10分）（分?jǐn)?shù)：2.00）正確答案：（正確答案：下面用Floyd算法求出任意兩頂點的最

15、短路徑（如圖A （b）所示）。題目要求娛樂中 心“距其他各結(jié)點的最長往返路程最短”，結(jié)點V1和V3最長往返路徑最短都是 9。按著“相同條件下總的往返路徑越短越好”，選頂點V5,總的往返路徑是 34o II）解析:【廈門大學(xué)2002八、2（5分）】.求出下圖中頂點1到其余各頂點的最短路徑。（分?jǐn)?shù)：2.00）正確答案：（正確答案：本表中 DIST中各列最下方的數(shù)字是頂點 1到頂點的最短路徑。頂點1到其他頂點的最短H徑依次是20, 31 , 28, 10, 17, 25, 35。按Dijkstra算法所選頂點依次是 5, 6, 2, 7, 4, 3, 8。）解析：.有一圖的鄰接矩陣如下，試給出用弗洛

16、伊德算法求各點間最短距離的矩陣序列【北京郵電大學(xué)2001四、5（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：解析：.試?yán)肈ijkstra 算法求下圖中從頂點a到其他各頂點間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)?！緰|南大學(xué)2000四（10分）】（分?jǐn)?shù)：2.00） 正確答案：（正確答案：求解過程略。頂點 a到頂點b, c, d, e, f, g間的最短路徑分別是15, 2, 11,10, 6, 13o ）解析：18.對于如下的加權(quán)有向圖，給出算法Dijkstra 產(chǎn)生的最短路徑的支撐樹，設(shè)頂點A為源點，并寫出生成過程?！炯执髮W(xué)1999 一、2（4分）】（分?jǐn)?shù)：2.00） 正確答案：（正確答案：頂點 A到頂點B, C, D, E的最短路徑依次是 3, 1 8, 38, 43,按Dijkstra 所選 頂點過程是B, C, D, Eo支撐樹的邊集合為, , , 。） 解析：19.已知圖的鄰接矩陣為:當(dāng)用鄰接表作為圖的存儲結(jié)構(gòu)，且鄰接點都按序號從大到小排列時，