【正文】 19．設計一個算法，判斷有向圖是否存在回路。10．假設圖G采用鄰接表存儲，設計一個算法，輸出圖G中從頂點u到v的所有簡單路徑。（2）完成此工程最少需要多少天（設邊上權值為天數(shù)）。27．關鍵活動不按期完成就會影響整個工程的完成時間。11．連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫時剛訪問過的頂點。 13．Prim算法適用于求_________的網(wǎng)的最小生成樹，Kruskal算法適用于求________的網(wǎng)的最小生成樹。A．O(n) B．O(n+e)C．O(n2) D．O(ne)28．求最短路徑的Floyd算法的時間復雜度為______。A．G肯定不是完全圖 B．G一定不是連通圖C．G中一定有回路 D．G有二個連通分量16．下列有關圖遍歷的說法不正確的是______。第7章 圖一、單項選擇題1．在一個無向圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的______倍。A．連通圖的深度優(yōu)先搜索是一個遞歸過程 B．圖的廣度優(yōu)先搜索中鄰接點的尋找具有“先進先出”的特征 C．非連通圖不能用深度優(yōu)先搜索法 D．圖的遍歷要求每一頂點僅被訪問一次17．下列說法中不正確的是______。A．O(n) B．O(ne)C．O(n2) D．O(n3) 29．關鍵路徑是事件結(jié)點網(wǎng)絡中______。 14．在AOV圖中，頂點表示________,有向邊表示________。12．圖的深度優(yōu)先搜索中一般要采用棧來暫時剛訪問過的頂點。28．所有關鍵活動都提前完成，則整個工程將提前完成。（3）哪些是關鍵活動a13=2a1=5a2=6a3=3a4=6a5=3a6=3a7=4a12=4a11=2a10=5a9=4a8=113425678910（4）是否存在某項活動，當其提高速度后能使整個工程縮短工期？圖79五、算法設計題1．假設圖G采用鄰接表存儲，分別設計實現(xiàn)以下要求的算法：（1）求出圖G中每個頂點的入度。11．假設圖G采用鄰接表存儲，設計一個算法，從如圖710所示的無向圖G中找出滿足如下條件的一條路徑：（1）給定起點vi和終點vj。20．對于一個使用鄰接表存儲的帶權有向圖G。若有向圖中存在一個頂點v，從v可以通過路徑到達圖中其他所有頂點，則稱v為該有向圖的根。9．假設圖G采用鄰接表存儲，設計一個算法，輸出圖G中從頂點u到v的長度為1的所有簡單路徑。14．如圖79所示的AOE網(wǎng)，求：（1）每項活動ai最早開始時間e(ai)和最遲開始時間l(ai)。26．在關鍵路徑的活動都是關鍵活動，而關鍵活動未必在關鍵路徑上。10．對有向圖G，如果以任一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每一個頂點，則該圖一定是完全圖。12．一個連通圖的___________是一個極小連通子圖。A．求關鍵路徑的方法 B．求最短路徑的Dijkstra算法C．廣度優(yōu)先遍歷算法 D．深度優(yōu)先遍歷算法27．求最短路徑的Dijkstra算法的時間復雜度為______。A．先序遍歷 B．中序遍歷C．后序遍歷 D．按層遍歷15．如果無向圖G必須進行二次廣度優(yōu)先搜索才能訪問其所有頂點，則下列說法中不正確的是______。 A．l/2 B．1 C．2 D．42．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的______倍。A．無向圖中的極大連通子圖稱為連通分量 B．連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點 C．圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點 D．有向圖的遍歷不可采用廣度優(yōu)先搜索方法18．一個有向圖G的鄰接表存儲如下圖71所示，現(xiàn)按深度優(yōu)先搜索遍歷，從頂點v1出發(fā)，所得到的頂點序列是______