1、理碩教育專注于北理工考研輔導本資料由理碩教育整理，理碩教育是全國唯一專注于北理工考研輔導的學校，相對于其它機構理碩教育有得天獨厚的優勢。豐富的理工內部資料資源與人力資源確保每個學員都受益匪淺，確保理碩教育的學員初試通過率89%以上，復試通過率接近100%，理碩教育現開設初試專業課VIP一對一，初試專業課網絡小班，假期集訓營，復試VIP一對一輔導，復試網絡小班，考前專業課網絡小班，滿足學員不同的需求。因為專一所以專業，理碩教育助您圓北理之夢。詳情請查閱理碩教育官網第 6 章 圖 課后習題講解 1. 填空題 設無向圖G中頂點數為n，則圖G至少有（ ）條邊，至多有（ ）條邊；若G為有向圖，則至少有（

2、 ）條邊，至多有（ ）條邊。【解答】0，n(n-1)/2，0，n(n-1)【分析】圖的頂點集合是有窮非空的，而邊集可以是空集；邊數達到最多的圖稱為完全圖，在完全圖中，任意兩個頂點之間都存在邊。 任何連通圖的連通分量只有一個，即是（ ）。【解答】其自身 圖的存儲結構主要有兩種，分別是（ ）和（ ）。【解答】鄰接矩陣，鄰接表【分析】這是最常用的兩種存儲結構，此外，還有十字鏈表、鄰接多重表、邊集數組等。 已知無向圖G的頂點數為n，邊數為e，其鄰接表表示的空間復雜度為（ ）。【解答】(n+e)【分析】在無向圖的鄰接表中，頂點表有n個結點，邊表有2e個結點，共有n+2e個結點，其空間復雜度為(n+2e)

3、=(n+e)。 已知一個有向圖的鄰接矩陣表示，計算第j個頂點的入度的方法是（ ）。【解答】求第j列的所有元素之和 有向圖G用鄰接矩陣Ann存儲，其第i行的所有元素之和等于頂點i的（ ）。【解答】出度 圖的深度優先遍歷類似于樹的（ ）遍歷，它所用到的數據結構是（ ）；圖的廣度優先遍歷類似于樹的（ ）遍歷，它所用到的數據結構是（ ）。【解答】前序，棧，層序，隊列 對于含有n個頂點e條邊的連通圖，利用Prim算法求最小生成樹的時間復雜度為（ ），利用Kruskal算法求最小生成樹的時間復雜度為（ ）。【解答】(n2)，(elog2e)【分析】Prim算法采用鄰接矩陣做存儲結構，適合于求稠密圖的最小生

4、成樹；Kruskal算法采用邊集數組做存儲結構，適合于求稀疏圖的最小生成樹。 如果一個有向圖不存在（ ），則該圖的全部頂點可以排列成一個拓撲序列。【解答】回路 在一個有向圖中，若存在弧、，則在其拓撲序列中，頂點vi, vj, vk的相對次序為（ ）。【解答】vi, vj, vk【分析】對由頂點vi, vj, vk組成的圖進行拓撲排序。2. 選擇題 在一個無向圖中，所有頂點的度數之和等于所有邊數的（ ）倍。A 1/2 B 1 C 2 D 4【解答】C【分析】設無向圖中含有n個頂點e條邊，則。 n個頂點的強連通圖至少有（）條邊，其形狀是（ ）。A n B n+1 C n-1 D n×(n

5、-1)E 無回路F 有回路 G 環狀 H 樹狀【解答】A，G 含n 個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過（ ）。A 1 B n/2 C n-1 D n 【解答】C【分析】若超過n-1，則路徑中必存在重復的頂點。 對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則該矩陣的大小是（ ）。A n B (n-1)2 C n-1 D n2【解答】D 圖的生成樹（），n個頂點的生成樹有（ ）條邊。A 唯一 B 不唯一 C 唯一性不能確定D n E n +1 F n-1【解答】C，F 設無向圖G=(V, E)和G' =(V', E' )，如果G' 是G的生成

6、樹，則下面的說法中錯誤的是（ ）。A G' 為 G的子圖 B G' 為 G的連通分量C G' 為G的極小連通子圖且V = V' D G' 是G的一個無環子圖【解答】B【分析】連通分量是無向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點的所有邊都加上，所以，連通分量中可能存在回路。 G是一個非連通無向圖，共有28條邊，則該圖至少有（ ）個頂點。A 6 B 7 C 8 D 9 【解答】D【分析】n個頂點的無向圖中，邊數en(n-1)/2，將e=28代入，有n8，現已知無向圖非連通，則n=9。 最小生成樹指的是（ ） 。A 由連通網所得到的邊數最少的

7、生成樹B 由連通網所得到的頂點數相對較少的生成樹C 連通網中所有生成樹中權值之和為最小的生成樹D 連通網的極小連通子圖 判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以用（ ）。A 求關鍵路徑的方法 B 求最短路徑的方法C 廣度優先遍歷算法 D 深度優先遍歷算法【解答】D【分析】當有向圖中無回路時，從某頂點出發進行深度優先遍歷時，出棧的順序（退出DFSTraverse算法）即為逆向的拓撲序列。 下面關于工程計劃的AOE網的敘述中，不正確的是（ ）?br /> A 關鍵活動不按期完成就會影響整個工程的完成時間B 任何一個關鍵活動提前完成，那么整個工程將會提前完成C 所有的關鍵活

8、動都提前完成，那么整個工程將會提前完成D 某些關鍵活動若提前完成，那么整個工程將會提前完【解答】B【分析】AOE網中的關鍵路徑可能不止一條，如果某一個關鍵活動提前完成，還不能提前整個工程，而必須同時提高在幾條關鍵路徑上的關鍵活動。3. 判斷題 一個有向圖的鄰接表和逆鄰接表中的結點個數一定相等。【解答】對。鄰接表和逆鄰接表的區別僅在于出邊和入邊，邊表中的結點個數都等于有向圖中邊的個數。 用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數有關，而與圖的邊數無關。【解答】對。鄰接矩陣的空間復雜度為(n2)，與邊的個數無關。 圖G的生成樹是該圖的一個極小連通子圖【解答】錯。必須包含全部頂點。 無向

9、圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的【解答】錯。有向圖的鄰接矩陣不一定對稱，例如有向完全圖的鄰接矩陣就是對稱的。 對任意一個圖，從某頂點出發進行一次深度優先或廣度優先遍歷，可訪問圖的所有頂點。【解答】錯。只有連通圖從某頂點出發進行一次遍歷，可訪問圖的所有頂點。 在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧。【解答】錯。只能說明從頂點a到頂點b有一條路徑。 若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲序列必定存在。【解答】對。參見第11題的證明。 在AOE網中一定只有一條關鍵路徑?br />【解答】錯。AOE網中可能有不止一條關鍵路徑，

10、他們的路徑長度相同。4n個頂點的無向圖，采用鄰接表存儲，回答下列問題?br /> 圖中有多少條邊？ 任意兩個頂點i和j是否有邊相連？ 任意一個頂點的度是多少?br />【解答】 邊表中的結點個數之和除以2。 第i個邊表中是否含有結點j。 該頂點所對應的邊表中所含結點個數。5n個頂點的無向圖，采用鄰接矩陣存儲，回答下列問題： 圖中有多少條邊？ 任意兩個頂點i和j是否有邊相連？ 任意一個頂點的度是多少？【解答】 鄰接矩陣中非零元素個數的總和除以2。 當鄰接矩陣A中Aij=1（或Aji=1）時，表示兩頂點之間有邊相連。 計算鄰接矩陣上該頂點對應的行上非零元素的個數。6證明：生成樹中最長路

11、徑的起點和終點的度均為。【解答】用反證法證明。設v1, v2, , vk是生成樹的一條最長路徑，其中，v1為起點，vk為終點。若vk的度為2，取vk的另一個鄰接點v，由于生成樹中無回路，所以，v在最長路徑上，顯然v1, v2, , vk , v的路徑最長，與假設矛盾。所以生成樹中最長路徑的終點的度為1。同理可證起點v1的度不能大于1，只能為1。7已知一個連通圖如圖6-6所示，試給出圖的鄰接矩陣和鄰接表存儲示意圖，若從頂點v1出發對該圖進行遍歷，分別給出一個按深度優先遍歷和廣度優先遍歷的頂點序列。 【解答】鄰接矩陣表示如下： 深度優先遍歷序列為：v1 v2 v3 v5 v4 v6廣度優先遍歷序列

12、為：v1 v2 v4 v6 v3 v5鄰接表表示如下：8圖6-7所示是一個無向帶權圖，請分別按Prim算法和Kruskal算法求最小生成樹。 【解答】按Prim算法求最小生成樹的過程如下：按Kruskal算法求最小生成樹的過程如下：9對于圖6-8所示的帶權有向圖，求從源點v1到其他各頂點的最短路徑。 【解答】從源點v1到其他各頂點的最短路徑如下表所示。源點 終點 最短路徑 最短路徑長度v1 v7 v1 v7 7v1 v5 v1 v5 11v1 v4 v1 v7 v4 13v1 v6 v1 v7 v4 v6 16v1 v2 v1 v7 v2 22v1 v3 v1 v7 v4 v6 v3 2510

13、如圖6-9所示的有向網圖，利用Dijkstra算法求從頂點v1到其他各頂點的最短路徑。 【解答】從源點v1到其他各頂點的最短路徑如下表所示。源點 終點 最短路徑 最短路徑長度v1 v3 v1 v3 15v1 v5 v1 v5 15v1 v2 v1 v3 v2 25v1 v6 v1 v3 v2 v6 40v1 v4 v1 v3 v2 v4 4511證明：只要適當地排列頂點的次序，就能使有向無環圖的鄰接矩陣中主對角線以下的元素全部為0。【解答】任意n個結點的有向無環圖都可以得到一個拓撲序列。設拓撲序列為v0v1v2vn-1，我們來證明此時的鄰接矩陣A為上三角矩陣。證明采用反證法。假設此時的鄰接矩陣

14、不是上三角矩陣，那么，存在下標i和j（i>j），使得Aij不等于零，即圖中存在從vi到vj的一條有向邊。由拓撲序列的定義可知，在任意拓撲序列中，vi的位置一定在vj之前，而在上述拓撲序列v0v1v2vn-1中，由于i>j，即vi的位置在vj之后，導致矛盾。因此命題正確。12. 算法設計 設計算法，將一個無向圖的鄰接矩陣轉換為鄰接表。【解答】先設置一個空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對應單鏈表中插入相應的邊表結點。鄰接矩陣存儲結構定義如下：const int MaxSize=10;template struct AdjMatrix T vertexMa

15、xSize; /存放圖中頂點的數組int arcMaxSizeMaxSize; /存放圖中邊的數組int vertexNum, arcNum; /圖的頂點數和邊數;鄰接表存儲結構定義如下：const int MaxSize=10;struct ArcNode /定義邊表結點int adjvex; /鄰接點域ArcNode *next;template struct VertexNode /定義頂點表結點T vertex;ArcNode *firstedge;struct AdjListVertexNode adjlistMaxSize;int vertexNum, arcNum; /圖的頂點數

16、和邊數;具體算法如下： 設計算法，將一個無向圖的鄰接表轉換成鄰接矩陣。【解答】在鄰接表上順序地取每個邊表中的結點，將鄰接矩陣中對應單元的值置為1。鄰接矩陣和鄰接表的存儲結構定義與上題相同。具體算法如下： 設計算法，計算圖中出度為零的頂點個數。【解答】在有向圖的鄰接矩陣中，一行對應一個頂點，每行的非零元素的個數等于對應頂點的出度。因此，當某行非零元素的個數為零時，則對應頂點的出度為零。據此，從第一行開始，查找每行的非零元素個數是否為零，若是則計數器加1。具體算法如下： 以鄰接表作存儲結構，設計按深度優先遍歷圖的非遞歸算法。【解答】參見6.2.1。 已知一個有向圖的鄰接表，編寫算法建立其逆鄰接表。

17、【解答】在有向圖中，若鄰接表中頂點vi有鄰接點vj，在逆鄰接表中vj一定有鄰接點vi，由此得到本題算法思路：首先將逆鄰接表的表頭結點firstedge域置空，然后逐行將表頭結點的鄰接點進行轉化。 分別基于深度優先搜索和廣度優先搜索編寫算法，判斷以鄰接表存儲的有向圖中是否存在由頂點vi到頂點vj的路徑（ij）。【解答】 基于深度優先遍歷： 基于廣度優先遍歷：學習自測及答案 1某無向圖的鄰接矩陣A=，可以看出，該圖共有（ ）個頂點。A 3 B 6 C 9 D 以上答案均不正確【解答】A2無向圖的鄰接矩陣是一個（ ），有向圖的鄰接矩陣是一個（ ）A 上三角矩陣 B 下三角矩陣 C 對稱矩陣 D 無規

18、律【解答】C，D3下列命題正確的是（ ）。A 一個圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一B 一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一C 一個圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一D 一個圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一【解答】B4十字鏈表適合存儲（ ），鄰接多重表適合存儲（ ）。【解答】有向圖，無向圖5. 在一個具有n 個頂點的有向完全圖中包含有（ ）條邊：A n(n-1)/2 B n(n-1) C n(n+1)/2 D n2【解答】B6n個頂點的連通圖用鄰接矩陣表示時，該矩陣至少有（ ）個非零元素。【解答】2(n-1)7表示一個有100個頂點，1000條邊的有向圖的鄰接矩陣有（ ）個非零矩陣元素。【解答】10008一個具有n個頂點k條邊的無向圖是一個森林（n>k），則該森林中必有（ ）棵樹。A k B n C n - k D 1【解答】C9用深度優先遍歷方法遍歷一個有向無環圖，并在深度優先遍歷算法中按退棧次序打印出相應的頂點，則輸出的頂點序列是（ ）。A 逆拓撲有序 B 拓撲有序 C 無序 D 深度優先遍歷序列【解答】A10. 關鍵路徑是AOE網中（ ）。A