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