【正文】 (設(shè)圖G已用鄰接表存儲)【南京航空航天大學 1?！緰|北大學 2001 五 (15分)】17．試編寫求無向圖G的連通分量的算法?！颈本┕ど檀髮W 1999 四 （12分）】16．在有向圖G中，如果r到G中的每個結(jié)點都有路徑可達，則稱結(jié)點r為G的根結(jié)點?！炯执髮W 1997 五 (16分)】14．假設(shè)一個有向圖G已經(jīng)以十字鏈表形式存儲在內(nèi)存中，試寫一個判斷該有向圖中是否有環(huán)路（回路）的算法。（注：圖中不存在頂點到自己的?。厩迦A大學 1994 六 （15分）】類似本題的另外敘述有：（1）假定G=（V，E）是有向圖，V={1，2，…，n }，n=1，G以鄰接矩陣方式存儲，G的鄰接矩陣為A，即A是一個二維數(shù)組，如果i到 j有邊，則A[ i,j]=1，否則A[ i,j]=0?！颈本┹p工業(yè)學院 1998 四 （14分）】12．設(shè)有向圖用鄰接表表示,圖有n個頂點,表示為1至n,試寫一個算法求頂點k的入度(1kn)?！厩鄭u海洋大學 1999 五（13分）】10．假設(shè)有向圖以鄰接表存儲，試編寫算法刪除弧Vi，Vj的算法。試編寫算法在該鄰接表上操作，刪除從頂點I到頂點J之間的一條邊。 【東南大學 1999 三 （10分）】類似本題的另外敘述有：（1）一個無向連通圖的存儲結(jié)構(gòu)以鄰接表的形式給定，設(shè)計算法刪除該圖中的一條邊(i,j)。寫算法判別以鄰接方式存儲的無向圖中是否存在由頂點Vi到頂點Vj的路徑(i≠j)?！局猩酱髮W 1999數(shù) 四 （15分）】（2）按圖的寬度優(yōu)先搜索法寫一算法判別以鄰接矩陣存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑（i≠j）。注意：算法中涉及的圖的基本操作必須在存儲結(jié)構(gòu)上實現(xiàn)?！灸祥_大學2000三3】（2）編寫算法，將圖的鄰接矩陣存儲改為鄰接表的存儲?！咎旖虼髮W 1999 五】7．設(shè)已給出圖的鄰接矩陣，要求將鄰接矩陣轉(zhuǎn)換為鄰接表，用類pascal語言寫為過程形式。【東南大學 1992 六（18分）】6．寫出從圖的鄰接表表示轉(zhuǎn)換成鄰接矩陣表示的算法，用類PASCAL語言（或C語言）寫成過程形式。【東南大學 1996 三 （13分）】類似本題的另外敘述有：（1）下圖（編者略）是有向圖按出度建立的鄰接表，試寫一算法，將此出度鄰接表改成入度建立的鄰接表。【東南大學 1995 六（16分） 1997 二 （15分）】4．給出以十字鏈表作存儲結(jié)構(gòu)，建立圖的算法，輸入(i,j,v)其中i,j為頂點號，v為權(quán)值。提示：先產(chǎn)生鄰接表的n個頭結(jié)點（其結(jié)點數(shù)值域從1到n）。已知有向圖有n個頂點,請寫算法,根據(jù)用戶輸入的偶對建立該有向圖的鄰接表。試編寫用鄰接表存儲該圖的算法。關(guān)鍵路徑上的事件的充裕天數(shù)是（E）。用事件編號的序列（例如027911）表示進行作業(yè)的路徑。某一工程作業(yè)的網(wǎng)絡(luò)圖如圖所示，其中箭頭表示作業(yè)，箭頭邊的數(shù)字表示完成作業(yè)所需的天數(shù)。 【華南師范大學 1999 三 (20分)】50．何為AOE網(wǎng)的始點和終點，一個正常的AOE網(wǎng)是否只有一個始點和一個終點？【首都經(jīng)貿(mào)大學 1997 一、4 （4分）】51．下表給出了某工程各工序之間的優(yōu)先關(guān)系和各工序所需時間（1）．畫出相應(yīng)的AOE網(wǎng) （2）．列出各事件的最早發(fā)生時間,最遲發(fā)生時間（3）．找出關(guān)鍵路徑并指明完成該工程所需最短時間. 【武漢交通科技大學 1996 二、6 (7分)】工序代號 A B C D E F G H I J K L M N 所需時間 15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驅(qū)工作 A,B B C,D B E G,I E I F,I H,J,K L G 52．對圖示的AOE網(wǎng)絡(luò)，計算各活動弧的e(ai)和l(ai)的函數(shù)值，各事件（頂點）的ve（Vj）和vl (Vj)的函數(shù)值，列出各條關(guān)鍵路徑?！灸祥_大學 1998 二 (12分)】 47．有向圖的拓撲排序能否用圖的深度搜索模式來查找?若能，請簡述方法，若不能，請簡述原因 【西北大學 2000 二、8 (5分)】48．下圖是帶權(quán)的有向圖G的鄰接表表示法，求：（1）．以結(jié)點V1出發(fā)深度遍歷圖G所得的結(jié)點序列；（2）．以結(jié)點V1出發(fā)廣度遍歷圖G所得的結(jié)點序列；（3）．從結(jié)點V1到結(jié)點V8的最短路徑；（4）．從結(jié)點V1到結(jié)點V8的關(guān)鍵路徑。【同濟大學 1998 一 (12分 )】45．已知一圖如下圖所示：（1）．寫出該圖的鄰接矩陣；（2）．寫出全部拓撲排序；（3）．以v1為源點,以v8為終點，給出所有事件允許發(fā)生的最早時間和最晚時間，并給出關(guān)鍵路徑；（4）．求V1結(jié)點到各點的最短距離?！緰|南大學 2000 四（10分）】43．對于如下的加權(quán)有向圖，給出算法Dijkstra產(chǎn)生的最短路徑的支撐樹，設(shè)頂點A為源點，并寫出生成過程。 第41題圖【北京郵電大學 2002 四、1 （10分）】 41．求出下圖中頂點1到其余各頂點的最短路徑?！局猩酱髮W 1994 四 （12分）】65ced4bfghijza2249614223123459829第39題圖 39．用最短路徑算法，求如下圖中a到z的最短通路。其中出邊表中的每個結(jié)點均含有三個字段，依次為邊的另一個頂點在頂點表中的序號、邊上的權(quán)值和指向下一個邊結(jié)點的指針?！颈本┛萍即髮W 2001 五 (12分)】37．有一圖的鄰接矩陣如下，試給出用弗洛伊德算法求各點間最短距離的矩陣序列A1，A2，A3，A4?！颈本┕I(yè)大學 1999 四(20分)】35．下圖表示一個地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費的代價，如何選擇能溝通每個城市且總代價最省的n1條線路，畫出所有可能的選擇。 （2）．分別寫出從頂點1出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷頂點序列，以及相應(yīng)的生成樹。（3）．畫出該圖按權(quán)值遞增的順序來構(gòu)造的最小(代價)生成樹.【上海海運學院1995 六（9分） 1999 五 （14分）】34．已知頂點16和輸入邊與權(quán)值的序列（如右圖所示）：每行三個數(shù)表示一條邊的兩個端點和其權(quán)值，共11行。 （1）．寫出它的鄰接矩陣（ 5分）（2）．按Prim算法求其最小生成樹，并給出構(gòu)造最小生成樹過程中輔助數(shù)組的各分量值（15分）輔助數(shù)組內(nèi)各分量值：【華北計算機系統(tǒng)工程研究所 1999 四 （20分）】YClosedge2345678 U VexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcostVexLowcost33．已知世界六大城市為:北京(Pe)、紐約(N)、巴黎(Pa)、 倫敦(L) 、 東京(T) 、 墨西哥(M),下表給定了這六大城市之間的交通里程: 世界六大城市交通里程表(單位:百公里) PENPALTMPE109828121124N109585510832PA825839792L815539589T211089795113M1243292891131 2 51 3 8 1 4 32 4 62 3 2 3 4 43 5 13 6 104 5 74 6 115 6 15（1）．畫出這六大城市的交通網(wǎng)絡(luò)圖。【合肥工業(yè)大學 1999 四、2 （5分）】 第30題圖 31．一帶權(quán)無向圖的鄰接矩陣如下圖 ，試畫出它的一棵最小生成樹。【北方交通大學 1993 二 （12分）】29．試寫出用克魯斯卡爾（Kruskal）算法構(gòu)造下圖的一棵最小支撐（或生成）樹的過程。【北京郵電大學 1999 五 （10分）】27．已知一個無向圖如下圖所示，要求分別用Prim和Kruskal算法生成最小樹（假設(shè)以①為起點，試畫出構(gòu)造過程）。（8分） 【山東大學 1998 六、18分】24．考慮右圖：(1)從頂點A出發(fā)，求它的深度優(yōu)先生成樹(2)從頂點E出發(fā)，求它的廣度優(yōu)先生成樹（3）根據(jù)普利姆(Prim) 算法，求它的最小生成樹【上海交通大學 1999 六 (12分)】，Prim算法與Kruskual算法生成不同的MST？【西安電子科技大學 2000計應(yīng)用 一、11 （5分）】26．下面是求無向連通圖最小生成樹的一種方法。（2）．寫出從元素A出發(fā)按“廣度優(yōu)先搜索”算法遍歷此圖的元素序列.【北京科技大學 1999 五 2000 五 （12分）】22．已知無向圖如下所示：（1）．給出從V1開始的廣度優(yōu)先搜索序列；（2）．畫出它的鄰接表；（3）．畫出從V1開始深度優(yōu)先搜索生成樹。【西安電子科技大學 2000計應(yīng)用 六 （10分）】20．如下所示的連通圖，請畫出：（1）．以頂點①為根的深度優(yōu)先生成樹；（5分）（2）．如果有關(guān)節(jié)點，請找出所有的關(guān)節(jié)點?！颈本┹p工業(yè)學院 1998 八 （6分）】18．對一個圖進行遍歷可以得到不同的遍歷序列，那么導(dǎo)致得到的遍歷序列不唯一的因素有哪些？【北京航空航天大學 1998 一、7 （4分）】19．解答下面的問題2146351020105231511398712456310（1）．如果每個指針需要4個字節(jié)，每個頂點的標號占2個字節(jié)，每條邊的權(quán)值占2個字節(jié)?！緩?fù)旦大學1998六(10分))36758942131057842169 15題圖 14題圖 16題圖16．給出圖G：（1）．畫出G的鄰接表表示圖；（2）．根據(jù)你畫出的鄰接表，以頂點①為根，畫出G的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。 【吉林大學 1998 三(16分)】14． 首先將如下圖所示的無向圖給出其存儲結(jié)構(gòu)的鄰接鏈表表示，然后寫出對其分別進行深度，廣度優(yōu)先遍歷的結(jié)果。 （3）．其它表示法?！緰|北大學 1997 一、5 (5分)】10．試用下列三種表示法畫出網(wǎng)G 的存儲結(jié)構(gòu)，并評述這三種表示法的優(yōu)、缺點：（1）．鄰接矩陣表示法。（4分）（4）．分別畫出該邏輯結(jié)構(gòu)的正向鄰接表和逆向鄰接表。（3分）（2）．相對于關(guān)系r, 指出所有的開始接點和終端結(jié)點?！颈本┼]電大學 2002 三 （10分）】6．用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關(guān)？與邊的條數(shù)是否有關(guān)？【西安電子科技大學 2000計應(yīng)用 一、6（5分）】7．請回答下列關(guān)于圖(Graph)的一些問題：（每題4分） （1）．有n個頂點的有向強連通圖最多有多少條邊?最少有多少條邊? （2）．表示有1000個頂點、l000條邊的有向圖的鄰接矩陣有多少個矩陣元素？是否稀疏矩陣？ （3）．對于一個有向圖，不用拓撲排序，如何判斷圖中是否存在環(huán)？【清華大學2000一(12分）】8．解答問題。 } } } } 【浙江大學 2000 六(15分)】四、 應(yīng)用題1．（1）