【正文】 出網(wǎng)G的鄰接矩陣、畫出網(wǎng)G 的鄰接表結(jié)構(gòu):（2）．寫出從頂點a出發(fā),按“深度優(yōu)先搜索”和“廣度優(yōu)先搜索”方法遍歷網(wǎng)G所的到的頂點序列：按Prim算法求出網(wǎng)G的一棵最小生成樹。【北京科技大學 2001 五 (12分)】37．有一圖的鄰接矩陣如下，試給出用弗洛伊德算法求各點間最短距離的矩陣序列A1，A2，A3，A4。 A= 【北京郵電大學2001四、5(5分）】38．下圖所示是一帶權(quán)有向圖的鄰接表法存儲表示。其中出邊表中的每個結(jié)點均含有三個字段，依次為邊的另一個頂點在頂點表中的序號、邊上的權(quán)值和指向下一個邊結(jié)點的指針。試求：（1）．該帶權(quán)有向圖的圖形；（2）．從頂點V1為起點的廣度優(yōu)先周游的頂點序列及對應的生成樹（即支撐樹）；（3）．以頂點V1為起點的深度優(yōu)先周游生成樹；（4）．由頂點V1到頂點V3的最短路徑?！局猩酱髮W 1994 四 （12分）】65ced4bfghijza2249614223123459829第39題圖 39．用最短路徑算法，求如下圖中a到z的最短通路?！疚髂县斀?jīng)大學 1999 四】40．已知一有向網(wǎng)的鄰接矩陣如下，如需在其中一個結(jié)點建立娛樂中心，要求該結(jié)點距其它各結(jié)點的最長往返路程最短，相同條件下總的往返路程越短越好，問娛樂中心應選址何處？給出解題過程。 第41題圖【北京郵電大學 2002 四、1 （10分）】 41．求出下圖中頂點1到其余各頂點的最短路徑。【廈門大學 2002 八、2 （5分）】42．試利用Dijkstra算法求下圖中從頂點a到其他個頂點間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。【東南大學 2000 四（10分）】43．對于如下的加權(quán)有向圖，給出算法Dijkstra產(chǎn)生的最短路徑的支撐樹，設頂點A為源點，并寫出生成過程?！炯执髮W 1999 一、2 (4分)】第43題圖15第42題圖 44．已知圖的鄰接矩陣為：V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000當用鄰接表作為圖的存儲結(jié)構(gòu)，且鄰接表都按序號從大到小排序時，試寫出：（1）．以頂點V1為出發(fā)點的唯一的深度優(yōu)先遍歷；（2）．以頂點V1為出發(fā)點的唯一的廣度優(yōu)先遍歷；（3）．該圖唯一的拓撲有序序列?！就瑵髮W 1998 一 (12分 )】45．已知一圖如下圖所示：（1）．寫出該圖的鄰接矩陣；（2）．寫出全部拓撲排序；（3）．以v1為源點,以v8為終點，給出所有事件允許發(fā)生的最早時間和最晚時間，并給出關(guān)鍵路徑；（4）．求V1結(jié)點到各點的最短距離?！颈本┼]電大學 2000 五 （15分）】 21743658 第46題圖V1V2V4V6V8V7V5V33 10 3 2 5 4 6 1 2 3第45題圖46．（1）．對于有向無環(huán)圖，敘述求拓撲有序序列的步驟； （2）．對于以下的圖，寫出它的四個不同的拓撲有序序列。【南開大學 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)鍵路徑。 【青島海洋大學 1999 四（10分）】49．對有五個結(jié)點{ A,B, C, D, E}的圖的鄰接矩陣，（1）．畫出邏輯圖 ；（2）．畫出圖的十字鏈表存儲；（3）．基于鄰接矩陣寫出圖的深度、廣度優(yōu)先遍歷序列；（4）．計算圖的關(guān)鍵路徑。 【華南師范大學 1999 三 (20分)】50．何為AOE網(wǎng)的始點和終點，一個正常的AOE網(wǎng)是否只有一個始點和一個終點？【首都經(jīng)貿(mào)大學 1997 一、4 （4分）】51．下表給出了某工程各工序之間的優(yōu)先關(guān)系和各工序所需時間（1）．畫出相應的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)絡，計算各活動弧的e(ai)和l(ai)的函數(shù)值，各事件（頂點）的ve（Vj）和vl (Vj)的函數(shù)值，列出各條關(guān)鍵路徑。【北京輕工業(yè)學院 1997 四 （15分）】193760251084113227245316334475 第52題圖 第53題 工程作業(yè)的網(wǎng)絡圖53．請寫出應填入下列敘述中（ ）內(nèi)的正確答案。某一工程作業(yè)的網(wǎng)絡圖如圖所示，其中箭頭表示作業(yè)，箭頭邊的數(shù)字表示完成作業(yè)所需的天數(shù)。箭頭前后的圓圈表示事件，圓圈中的數(shù)字表示事件的編號。用事件編號的序列（例如027911）表示進行作業(yè)的路徑。完成此工程的關(guān)鍵路徑是（A）完成此工程所需的最少天數(shù)為（B）天，此工程中具有最大充裕天數(shù)的事件是（C），充裕天數(shù)是（D）。關(guān)鍵路徑上的事件的充裕天數(shù)是（E）?！旧虾４髮W 2002 三 （10分）】五、算法設計題1．（單獨命題考生做）設無向圖G有n個頂點，m條邊。試編寫用鄰接表存儲該圖的算法。（設頂點值用1～n或0～n1編號） 【南京航空航天大學 1996 十二 （10分）】2．請用流程圖或類高級語言(pascal或c)表示算法。已知有向圖有n個頂點,請寫算法,根據(jù)用戶輸入的偶對建立該有向圖的鄰接表。即接受用戶輸入的vi,vj(以其中之一為0標志結(jié)束),對于每條這樣的邊,申請一個結(jié)點,并插入到的單鏈表中,如此反復,直到將圖中所有邊處理完畢。提示：先產(chǎn)生鄰接表的n個頭結(jié)點（其結(jié)點數(shù)值域從1到n）?！旧虾４髮W 2000 四 （16分）】3．設無向圖G有n個點e條邊，寫一算法建立G的鄰接多表，要求該算法時間復雜性為O（n+e），且除鄰接多表本身所占空間之外只用O（1）輔助空間?！緰|南大學 1995 六（16分） 1997 二 （15分）】4．給出以十字鏈表作存儲結(jié)構(gòu)，建立圖的算法，輸入(i,j,v)其中i,j為頂點號，v為權(quán)值?！竞雍４髮W 1998 六 （10分）】5．設有向G圖有n個點(用1,2,…,n表示),e條邊,寫一算法根據(jù)其鄰接表生成其反向鄰接表,要求算法復雜性為O(n+e)?！緰|南大學 1996 三 （13分）】類似本題的另外敘述有：（1）下圖（編者略）是有向圖按出度建立的鄰接表，試寫一算法，將此出度鄰接表改成入度建立的鄰接表?！颈本┼]電大學 1993 五 （15分）】（2）編寫算法實現(xiàn)以下功能：根據(jù)含有n個頂點的有向圖鄰接表，構(gòu)造相應的逆鄰接表。【東南大學 1992 六（18分）】6．寫出從圖的鄰接表表示轉(zhuǎn)換成鄰接矩陣表示的算法，用類PASCAL語言（或C語言）寫成過程形式?！灸祥_大學 1998 四 (16分)】類似本題的另外敘述有：（1）已知某個圖的鄰接表，試建立該圖的相鄰矩陣?！咎旖虼髮W 1999 五】7．設已給出圖的鄰接矩陣，要求將鄰接矩陣轉(zhuǎn)換為鄰接表，用類pascal語言寫為過程形式。【南開大學 1998 四 ( 14分)】類似本題的另外敘述有： （1）設已給出圖的鄰接矩陣，要求將圖的鄰接矩陣轉(zhuǎn)化為鄰接表，試實現(xiàn)其算法?！灸祥_大學2000三3】（2）編寫算法，將圖的鄰接矩陣存儲改為鄰接表的存儲?！局猩酱髮W 1998 五、2 （10分）】8．試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑（ij）。注意：算法中涉及的圖的基本操作必須在存儲結(jié)構(gòu)上實現(xiàn)?！竟枮I工業(yè)大學 2001 九 （12分）】類似本題的另外敘述有：（1）設計一個深度優(yōu)先搜索算法，以判斷用鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj（i≠j）的路徑?！局猩酱髮W 1999數(shù) 四 （15分）】（2）按圖的寬度優(yōu)先搜索法寫一算法判別以鄰接矩陣存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑（i≠j）?！局猩酱髮W 1997 五 （10分）】（3）請用流程圖或類高級語言(pascal或c)表示算法。寫算法判別以鄰接方式存儲的無向圖中是否存在由頂點Vi到頂點Vj的路徑(i≠j)?！旧虾４髮W 1999 三、2 （14分）】9．已知無向圖采用鄰接表存儲方式，試寫出刪除邊（i，j）的算法。 【東南大學 1999 三 （10分）】類似本題的另外敘述有：（1）一個無向連通圖的存儲結(jié)構(gòu)以鄰接表的形式給定，設計算法刪除該圖中的一條邊(i,j)。【北京工業(yè)大學 1996 二 (15分)】（2）無向圖G已按下圖（編者略）鄰接表存儲。試編寫算法在該鄰接表上操作，刪除從頂點I到頂點J之間的一條邊?！旧虾４髮W 1996 六（18分）】（3）設無向圖G用鄰接表表示，（編者略）請寫出在該無向圖中刪除邊 (i,j)的算法?！厩鄭u海洋大學 1999 五（13分）】10．假設有向圖以鄰接表存儲，試編寫算法刪除弧Vi，Vj的算法?！颈本┹p工業(yè)學院 1997 五（10分）】11．假設有向圖以十字鏈表存儲，試編寫算法，插入弧Vi,Vj?！颈本┹p工業(yè)學院 1998 四 （14分）】12．設有向圖用鄰接表表示,圖有n個頂點,表示為1至n,試寫一個算法求頂點k的入度(1kn)?！灸暇├砉ご髮W 1997 四、2（10分）】13．假設以鄰接矩陣作為圖的存儲結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個簡單有向回路，若存在，則以頂點序列的方式輸出該回路（找到一條即可）。（注：圖中不存在頂點到自己的?。厩迦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。請給出一個算法，該算法能判斷G是否是非循環(huán)圖（即G中是否存在回路），要求算法的時間復雜性為O（ n*n ）?！炯执髮W 1997 五 (16分)】14．假設一個有向圖G已經(jīng)以十字鏈表形式存儲在內(nèi)存中，試寫一個判斷該有向圖中是否有環(huán)路（回路）的算法?！緰|北大學 2000 四、3 (12分)】15．用鄰接多重表存儲結(jié)構(gòu)，編寫FIRSTADJ(G,V)函數(shù)，函數(shù)返回值為第一個鄰接點，若V沒有鄰接點，返回零?！颈本┕ど檀髮W 1999 四 （12分）】16．在有向圖G中，如果r到G中的每個結(jié)點都有路徑可達，則稱結(jié)點r為G的根結(jié)點。編寫一個算法完成下列功能：（1）．建立有向圖G的鄰接表存儲結(jié)構(gòu)；（2）．判斷有向圖G是否有根，若有，則打印出所有根結(jié)點的值?！緰|北大學 2001 五 (15分)】17．試編寫求無向圖G的連通分量的算法。要求輸出每一連通分量的頂點值。(設圖G已用鄰接表存儲)【南京航空航天