【正文】 。A．從源點(diǎn)到匯點(diǎn)的最長路徑 B．從源點(diǎn)到匯點(diǎn)的最短路徑C．最長的回路 D．最短的回路30．下面說法不正確的是______。15．可以進(jìn)行拓?fù)渑判虻挠邢驁D一定是_________。13．有向圖的遍歷不可采用廣度優(yōu)先搜索方法。29．某些關(guān)鍵活動若提前完成，將可能使整個工程提前完成。（2）求出圖G中每個頂點(diǎn)的出度（3）求出圖G中出度最大的一個頂點(diǎn)，輸出該頂點(diǎn)的編號。（2）給定一組必經(jīng)點(diǎn){7,9}，即輸出的路徑必須包含這些頂點(diǎn)。試?yán)蒙疃葍?yōu)先搜索方法，對該圖中所有頂點(diǎn)進(jìn)行逆向拓?fù)渑判颉?8．假設(shè)圖G采用鄰接矩陣存儲，采用弗洛伊德算法設(shè)計一個求有向圖的根的算法。8．假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，判斷無向圖G是否連通，若連通則返回1；否則返回0。（3）找出關(guān)鍵路徑并指明完成該工程所需的最短時間。25．在AOE網(wǎng)中工程工期為關(guān)鍵活動上權(quán)值之和。9．強(qiáng)連通分量是有向圖的極大連通子圖。v1v2v3v4 ∧v5v6 ∧234 ∧35 ∧6 ∧4 63 ∧圖73 圖G的鄰接表11．n個頂點(diǎn)連通圖的生成樹一定有__________條邊。A．是個有根有向圖 B．是個強(qiáng)連通圖C．含有多個入度為0的頂點(diǎn) D．含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量26．判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用____。A．先序遍歷 B．中序遍歷C．后序遍歷 D．按層遍歷14．采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的______算法。A．l/2 B．1 C．2 D．43．一個具有n個頂點(diǎn)的無向圖最多包含______條邊。A．v1，v2，v3，v4，v5 B．v1，v2，v3，v5，v4C．v1，v2，v4，v5，v3 D．v1，v2，v5，v3，v4 234 ∧35 ∧5 ∧4 ∧v1v2v3v4 ∧v5圖71 一個有向圖的鄰接表19．對圖72所示的無向圖，從頂點(diǎn)1開始進(jìn)行深度優(yōu)先遍歷，可得到頂點(diǎn)訪問序列______。A．在AOE網(wǎng)中，減少任一關(guān)鍵活動的權(quán)值后，整個工期也就相應(yīng)減少B．AOE網(wǎng)工程工期為關(guān)鍵活動的權(quán)值和C．在關(guān)鍵路徑上的活動都是關(guān)鍵活動，而關(guān)鍵活動也必須在關(guān)鍵路徑上D．A和B31．下面說法不正確的是______。16．從源點(diǎn)到匯點(diǎn)長度最長的路徑稱為關(guān)鍵路徑，該路徑上的活動稱為________。14．連通圖的生成樹包含了圖中所有頂點(diǎn)。30．求單源最短路徑的狄克斯特拉算法不適用于有回路的有向網(wǎng)。（4）計算圖G中出度為0的頂點(diǎn)數(shù)。（3）給定一組必避點(diǎn){1,6}，即輸出的路徑不能包含這些頂點(diǎn)。若鄰接表的數(shù)據(jù)類型定義為AGraph，則算法的首部為：void dfs_topsort(AGraph *G) 若拓?fù)渑判虺晒?，表示圖中不存在環(huán)；否則表示圖中存在環(huán)。設(shè)v是有向圖G的一個頂點(diǎn)，把v的偏心度定義為：MAX{從w到v的最短距離|wV(G)}如果v是有向圖G中具有最小偏心度的頂點(diǎn)，則稱頂點(diǎn)v是G的中心點(diǎn)。7．假設(shè)圖采用鄰接表存儲，分別寫出基于DFS和BPS遍歷的算法來判別頂點(diǎn)i和頂點(diǎn)j（i!=j）之間是否有路徑。表2 某工程各工序關(guān)系表工序代號 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完成如下各小題：（1）畫出相應(yīng)的AOE網(wǎng)（2）列出事件的最早發(fā)生時間，最遲發(fā)生時間。24．在AOE網(wǎng)中