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