第六部分 圖練習(xí)題帶答案

《第六部分 圖練習(xí)題帶答案》由會員分享，可在線閱讀，更多相關(guān)《第六部分 圖練習(xí)題帶答案（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第六部分 圖 一、選擇題 1．n 個頂點的帶權(quán)無向連通圖的最小生成樹包含(?B?)個頂點。 A.n-1 B.n C.n/2 D.n+1 2．無向完全圖的鄰接矩陣是(?A?)矩陣。 A. 對稱 B. 上三角 C. 下三角 D. 稀疏 3. 若采用鄰接矩陣法存儲一個n個頂點的無向圖，則該鄰接矩陣是一個(?D?)。 A. 上三角矩陣? B. 稀疏矩陣 C. 對角矩陣?????D. 對稱矩陣 4. 具有 n 個頂點的有向完全圖有(?B)條弧。 A. n????????? B. n*(n-1)??? C. n*(n+1)??????

2、 D. n*n 5. n 個頂點的連通圖至少有(?A?)條邊。 A. n-1 B. n C. n+1 D. 0 6．在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的(??B??)倍。 A．1/2 B．1 C．2 D．4 7．在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為(?D?) A．e?????????? B．2e?????????? C．n2－e?????? D．n2－2e 8．假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關(guān)的所有弧的時間復(fù)雜度是(??C??) A．O(n)????????B．O(e)??????

3、?? C．O(n+e)???? D．O(n*e) 9．對于一個無向圖，下面(?A?)的說法是正確的。 A. 每個頂點的入度等于出度 B. 每個頂點的度等于其入度與出度之和 C. 每個頂點的入度為0 D. 每個頂點的出度為0 二、填空題 1．具有10個頂點的無向圖,邊的總數(shù)最多為 ___45__________ 。 2．在有n個頂點的有向圖中，每個頂點的度最大可達(dá) 2(n-1) 。 3．有向圖g用鄰接矩陣a［1…m,1…m］來存儲，其第i行的所有元素之和等于頂點i的　出度之和　　。 4．關(guān)鍵路徑是 指途中從原點到匯點的路徑長度最長的路

4、徑 。 5．請給出對于下面AOV網(wǎng)絡(luò)，使用上述算法進(jìn)行拓?fù)渑判虻慕Y(jié)果，以及在count數(shù)組中建立的鏈?zhǔn)綏５淖兓＃╰op是棧頂指針） top→??????????????????????????????????????????????????????????????????????????? ????? ??? ??? A ? ? ? ? ? ? ? ? ? ? ? ? ? ??? B ? ? ? ? ? ? ? ? ? ? ? ? ? ??? C ? ? ? ? ? ? ? ? ? ? ? ? ?

5、 ??? D ? ? ? ? ? ? ? ? ? ? ? ? ? ??? E ? ? ? ? ? ? ? ? ? ? ? ? ? ??? F ? ? ? ? ? ? ? ? ? ? ? ? ? 初始??? 6．有n個球隊參加的足球聯(lián)賽按主客場制進(jìn)行比賽，共需進(jìn)行 n(n-1) 場比賽。 7．帶權(quán)連通圖G=，其中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、)6，(v4,v5)2，(注：頂點偶對右下角的數(shù)據(jù)為邊上的權(quán)值)，G的最小生成樹的權(quán)值之和為__________________ 。 8．若AOE圖中有 環(huán)路 ，則對該圖求關(guān)鍵路徑不成功。 9．n(n>0) 個結(jié)點、 (n-1) 條邊的連通無向圖中，頂點度數(shù)最大值為 _2___ 。 三、判斷題 1．有向圖是一種非線性結(jié)構(gòu)。( R ) 2．帶權(quán)連通圖的最小生成樹的權(quán)值之和一定小于它的其它生成樹的權(quán)值之和。( R ) 3．AOE 網(wǎng)是一種帶權(quán)的無環(huán)連通圖。( R ) 四、操作題 1．圖的鄰接矩陣: 2．有向圖的逆鄰接表: 3．找出下

7、面網(wǎng)絡(luò)的最小生成樹（WPL=23）。 4．找出下面網(wǎng)絡(luò)的最小生成樹(WPL=33): 5．試畫出下列圖的鄰接表。 圖 6．對下面的帶權(quán)無向圖采用prim算法從頂點 ① 開始構(gòu)造最小生成樹。（寫出加入生成樹頂點集合S和選擇邊Edge的順序） S: 頂點號 ? Edge: (頂點，頂點，權(quán)值) ? ① ? ? (??①，②，9) ? ①② ? ? (?②?，④?，5) ? ①②④ ? ? (??②? ，③?，7) ? ①②④③ ? ? (??③，⑤?，6) ? ①②④③⑤ ? ?

8、 (???③ ，⑥，7?) ? ①②④③⑤⑥ ? ? ? 7．對圖所示有向圖，試用Dijkstra算法求出從源點1到其它各頂點的最短路徑，并寫出執(zhí)行算法過程中擴(kuò)充結(jié)點的每次循環(huán)狀態(tài)。 D[2] D[3] D[4] D[5] D[6] V1 20 15 ∞ ∞ ∞ V1，V3 19 # ∞ ∞ 25 V1，V3,V2 # # ∞ 29 25 V1，V3,V2,V6 # # 29 29 # V1，V3,V2,V6,V4 # # # 29 # V1，V3,V2,V6,V4,V5 # # # #

9、 # 8. 已某個不帶權(quán)的無向圖采用鄰接矩陣存儲方法依次將頂點的數(shù)據(jù)信息存放于一維數(shù)組ABCDEFGH中，邊的信息存放于鄰接矩陣中，鄰接矩陣為 請寫出從頂點A出發(fā)對該圖進(jìn)行深度有限搜索后得到的頂點序列。 ACDFBEGH 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0