第六部分 圖一、選擇題1n 個(gè)頂點(diǎn)的帶權(quán)無(wú)向連通圖的最小生成樹(shù)包含( B )個(gè)頂點(diǎn)。A.n-1 B.n C.n/2 D.n+12無(wú)向完全圖的鄰接矩陣是( A )矩陣。A. 對(duì)稱 B. 上三角 C. 下三角 D. 稀疏3. 若采用鄰接矩陣法存儲(chǔ)一個(gè)n個(gè)頂點(diǎn)的無(wú)向圖，則該鄰接矩陣是一個(gè)( D )。A. 上三角矩陣  B. 稀疏矩陣 C. 對(duì)角矩陣     D. 對(duì)稱矩陣4. 具有 n 個(gè)頂點(diǎn)的有向完全圖有( B)條弧。A. n          B. n*(n-1)    C. n*(n+1)       D. n*n5. n 個(gè)頂點(diǎn)的連通圖至少有( A )條邊。A. n-1 B. nC. n+1 D. 06在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的(  B  )倍。A1/2B1C2D47在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中,零元素的個(gè)數(shù)為( D )Ae           B2e           Cn2e       Dn22e8假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示,則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是(  C  )AO(n)        BO(e)         CO(n+e)     DO(n*e)9對(duì)于一個(gè)無(wú)向圖，下面( A )的說(shuō)法是正確的。A. 每個(gè)頂點(diǎn)的入度等于出度B. 每個(gè)頂點(diǎn)的度等于其入度與出度之和C. 每個(gè)頂點(diǎn)的入度為0D. 每個(gè)頂點(diǎn)的出度為0二、填空題1具有10個(gè)頂點(diǎn)的無(wú)向圖,邊的總數(shù)最多為 _45_ 。2在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá) 2(n-1) 。3有向圖g用鄰接矩陣a1m,1m來(lái)存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的出度之和。4關(guān)鍵路徑是 指途中從原點(diǎn)到匯點(diǎn)的路徑長(zhǎng)度最長(zhǎng)的路徑 。5請(qǐng)給出對(duì)于下面AOV網(wǎng)絡(luò)，使用上述算法進(jìn)行拓?fù)渑判虻慕Y(jié)果，以及在count數(shù)組中建立的鏈?zhǔn)綏５淖兓?。（top是棧頂指針）top                                                                                          A                 B                 C                 D                 E                 F             初始    6有n個(gè)球隊(duì)參加的足球聯(lián)賽按主客場(chǎng)制進(jìn)行比賽，共需進(jìn)行 n(n-1) 場(chǎng)比賽。7帶權(quán)連通圖G=<V,E>，其中V=v1,v2,v3,v4,v5,E=(v1,v2)7,(v1,v4)6，(v1,v4)9，(v2,v3)8，(v2,v4)4，(v2,v5)4，(v3,v4)6，(v4,v5)2，(注：頂點(diǎn)偶對(duì)右下角的數(shù)據(jù)為邊上的權(quán)值)，G的最小生成樹(shù)的權(quán)值之和為_(kāi) 。8若AOE圖中有 環(huán)路 ，則對(duì)該圖求關(guān)鍵路徑不成功。9n(n>0) 個(gè)結(jié)點(diǎn)、 (n-1) 條邊的連通無(wú)向圖中，頂點(diǎn)度數(shù)最大值為 _2_ 。三、判斷題1有向圖是一種非線性結(jié)構(gòu)。( R )2帶權(quán)連通圖的最小生成樹(shù)的權(quán)值之和一定小于它的其它生成樹(shù)的權(quán)值之和。( R )3AOE 網(wǎng)是一種帶權(quán)的無(wú)環(huán)連通圖。( R )四、操作題1圖的鄰接矩陣:2有向圖的逆鄰接表: 3找出下面網(wǎng)絡(luò)的最小生成樹(shù)（WPL=23）。 4找出下面網(wǎng)絡(luò)的最小生成樹(shù)(WPL=33):5試畫(huà)出下列圖的鄰接表。 圖6對(duì)下面的帶權(quán)無(wú)向圖采用prim算法從頂點(diǎn) 開(kāi)始構(gòu)造最小生成樹(shù)。（寫(xiě)出加入生成樹(shù)頂點(diǎn)集合S和選擇邊Edge的順序）S:頂點(diǎn)號(hào) Edge:(頂點(diǎn)，頂點(diǎn)，權(quán)值)   (  ，9)   (  ， ，5)   (    ， ，7)   (  ， ，6)   (    ，7 )    7對(duì)圖所示有向圖，試用Dijkstra算法求出從源點(diǎn)1到其它各頂點(diǎn)的最短路徑，并寫(xiě)出執(zhí)行算法過(guò)程中擴(kuò)充結(jié)點(diǎn)的每次循環(huán)狀態(tài)。D2D3D4D5D6V12015V1，V319#25V1，V3,V2#2925V1，V3,V2,V6#2929#V1，V3,V2,V6,V4#29#V1，V3,V2,V6,V4,V5#8. 已某個(gè)不帶權(quán)的無(wú)向圖采用鄰接矩陣存儲(chǔ)方法依次將頂點(diǎn)的數(shù)據(jù)信息存放于一維數(shù)組ABCDEFGH中，邊的信息存放于鄰接矩陣中，鄰接矩陣為請(qǐng)寫(xiě)出從頂點(diǎn)A出發(fā)對(duì)該圖進(jìn)行深度有限搜索后得到的頂點(diǎn)序列。ACDFBEGH0 1 1 0 0 0 0 01 0 0 0 1 0 1 11 0 0 1 0 1 0 00 0 1 0 0 1 0 00 1 0 0 0 0 0 10 0 1 1 0 0 0 00 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0