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