1設(shè)無向圖頂點個數(shù)為n

《1設(shè)無向圖頂點個數(shù)為n》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第7章圖一、選擇題1．設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（）條邊。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n22．一個具有n個頂點的連通無向圖，其邊的個數(shù)至少為（）。A．n-1B．nC．n+1D．nlogn；3．要連通具有n個頂點的有向圖，至少需要（）條邊。A．n-lB．nC．n+lD．2n4．n個結(jié)點的完全有向圖含有邊的數(shù)目（　　?。．n*nＢ．n（n＋１）C．n／2D．n*（n－l）5．一個有n個結(jié)點的圖，最少有（）個連通分量，最多有（）個連通分量。A．0B．1C．n-1D．n6．在一個無向圖

2、中，所有頂點的度數(shù)之和等于所有邊數(shù)（）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（）倍。A．1/2B．2C．1D．47．下列哪一種圖的鄰接矩陣是對稱矩陣？（）A．有向圖B．無向圖C．AOV網(wǎng)D．AOE網(wǎng)8.下列說法不正確的是（）。A．圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次B．圖的深度遍歷不適用于有向圖C．遍歷的基本算法有兩種：深度遍歷和廣度遍歷D．圖的深度遍歷是一個遞歸過程9．下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）：A．深度優(yōu)先遍歷B.拓?fù)渑判駽.求最短路徑D.求關(guān)鍵路徑10．已知有向

3、圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,},G的拓?fù)湫蛄惺牵ǎ?。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V711．一個有向無環(huán)圖的拓?fù)渑判蛐蛄校ǎ┦俏ㄒ坏摹．一定B．不一定12.在有向圖G的拓?fù)湫蛄兄?，若頂點Vi在

4、頂點Vj之前，則下列情形不可能出現(xiàn)的是（）。A．G中有弧B．G中有一條從Vi到Vj的路徑C．G中沒有弧D．G中有一條從Vj到Vi的路徑13.關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（）。A．從源點到匯點的最長路徑B．從源點到匯點的最短路徑C．最長回路D．最短回路三、填空題1.判斷一個無向圖是一棵樹的條件是______。2．有向圖G的強(qiáng)連通分量是指______。4．具有10個頂點的無向圖，邊的總數(shù)最多為______。5．若用n表示圖中頂點數(shù)目，則有_______條邊的無向圖成為完全圖。6.設(shè)無向圖G有n個頂點和e

5、條邊，每個頂點Vi的度為di（1<=i<=n〉，則e=______7．G是一個非連通無向圖，共有28條邊，則該圖至少有______個頂點。8.在有n個頂點的有向圖中，若要使任意兩點間可以互相到達(dá)，則至少需要______條弧。9．在有n個頂點的有向圖中，每個頂點的度最大可達(dá)______。10．設(shè)G為具有N個頂點的無向連通圖，則G中至少有______條邊。11．n個頂點的連通無向圖，其邊的條數(shù)至少為______。12．在圖G的鄰接表表示中，每個頂點鄰接表中所含的表結(jié)點數(shù)，對于無向圖來說等于該頂點的______；對于有向圖來說等

6、于該頂點的______。14．構(gòu)造連通網(wǎng)最小生成樹的兩個典型算法是______和_________。15.有向圖G=(V,E),其中V(G)={0,1,2,3,4,5}，用三元組表示弧及弧上的權(quán)d。E(G)為{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，則從源點0到頂點3的最短路徑長度是______，經(jīng)過的中間頂點是______。16.上面的圖去掉有向弧看成無向圖則對應(yīng)的最小生成樹的邊權(quán)之和為______。17

7、．設(shè)有向圖有n個頂點和e條邊，進(jìn)行拓?fù)渑判驎r，總的計算時間為______。18．AOV網(wǎng)中,結(jié)點表示______,邊表示______。AOE網(wǎng)中,結(jié)點表示______,邊表示______。19．在AOE網(wǎng)中，從源點到匯點路徑上各活動時間總和最長的路徑稱為______。20.當(dāng)一個AOV網(wǎng)用鄰接表表示時，可按下列方法進(jìn)行拓?fù)渑判?。?）．查鄰接表中入度為______的頂點，并進(jìn)棧；（2）．若棧不空，則①輸出棧頂元素Vj，并退棧；②查Vj的直接后繼Vk，對Vk入度處理，處理方法是______；（3）．若棧空時，輸出頂點數(shù)小于圖

8、的頂點數(shù)，說明有______，否則拓?fù)渑判蛲瓿?。四、?yīng)用題367589421310578421691．首先將如下圖所示的無向圖給出其存儲結(jié)構(gòu)的鄰接鏈表表示，然后寫出對其分別進(jìn)行深度，廣度優(yōu)先遍歷的結(jié)果。2．給出圖G：（1）．畫出G的鄰接表表示圖；（2）．根據(jù)你畫出的鄰接表，以頂點①為根，畫出G的深度優(yōu)先