《第六部分 圖練習題帶答案》由會員分享，可在線閱讀，更多相關《第六部分 圖練習題帶答案（6頁珍藏版）》請在裝配圖網上搜索。
1、第六部分 圖一、選擇題1n 個頂點的帶權無向連通圖的最小生成樹包含(B)個頂點。A.n-1 B.n C.n/2 D.n+12無向完全圖的鄰接矩陣是(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) D. n*n5. n 個頂點的連通圖至少有(A)條邊。A. n-1 B. nC. n+1 D. 06在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和
2、的(B)倍。A1/2B1C2D47在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為(D)Ae B2e Cn2e Dn22e8假設一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關的所有弧的時間復雜度是(C)AO(n)BO(e) CO(n+e) DO(n*e)9對于一個無向圖，下面(A)的說法是正確的。A. 每個頂點的入度等于出度B. 每個頂點的度等于其入度與出度之和C. 每個頂點的入度為0D. 每個頂點的出度為0二、填空題1具有10個頂點的無向圖,邊的總數(shù)最多為 _45_ 。2在有n個頂點的有向圖中，每個頂點的度最大可達 2(n-1) 。3有向圖g用鄰接矩陣a1m,1
3、m來存儲，其第i行的所有元素之和等于頂點i的出度之和。4關鍵路徑是 指途中從原點到匯點的路徑長度最長的路徑 。5請給出對于下面AOV網絡，使用上述算法進行拓撲排序的結果，以及在count數(shù)組中建立的鏈式棧的變化。（top是棧頂指針）top A B C D E F初始 6有n個球隊參加的足球聯(lián)賽按主客場制進行比賽，共需進行 n(n-1) 場比賽。7帶權連通圖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，(v4,v5)2，(注：頂點偶對右下角的數(shù)據(jù)為邊上的權值)，G的最小
4、生成樹的權值之和為_ 。8若AOE圖中有 環(huán)路 ，則對該圖求關鍵路徑不成功。9n(n0) 個結點、 (n-1) 條邊的連通無向圖中，頂點度數(shù)最大值為 _2_ 。三、判斷題1有向圖是一種非線性結構。( R )2帶權連通圖的最小生成樹的權值之和一定小于它的其它生成樹的權值之和。( R )3AOE 網是一種帶權的無環(huán)連通圖。( R )四、操作題1圖的鄰接矩陣:2有向圖的逆鄰接表: 3找出下面網絡的最小生成樹（WPL=23）。 4找出下面網絡的最小生成樹(WPL=33):5試畫出下列圖的鄰接表。 圖6對下面的帶權無向圖采用prim算法從頂點 開始構造最小生成樹。（寫出加入生成樹頂點集合S和選擇邊Edg
5、e的順序）S:頂點號Edge:(頂點，頂點，權值)(，9)(，5)( ，7)(，6)( ，7)7對圖所示有向圖，試用Dijkstra算法求出從源點1到其它各頂點的最短路徑，并寫出執(zhí)行算法過程中擴充結點的每次循環(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. 已某個不帶權的無向圖采用鄰接矩陣存儲方法依次將頂點的數(shù)據(jù)信息存放于一維數(shù)組ABCDEFGH中，邊的信息存放于鄰接矩陣中，鄰接矩陣為請寫出從頂點A出發(fā)對該圖進行深度有限搜索后得到的頂點序列。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
第六部分 圖練習題帶答案
