數(shù)據(jù)結構第7章 圖習題

1、習題7 圖7.1 單項選擇題1在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_倍。A. 1/2 B. 1 C. 2 D. 4 2任何一個無向連通圖的最小生成樹 。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的_倍。A. 1/2 B. 1 C. 2 D. 44一個有n個頂點的無向圖最多有_條邊。A. n B. n(n-1) C. n(n-1)/2 D. 2n5具有4個頂點的無向完全圖有_條邊。A. 6 B. 12 C. 16 D. 206具有6個頂點的無向圖至少應有_條邊才能確保是一個連通圖。A. 5 B. 6 C. 7 D.

2、87在一個具有n個頂點的無向圖中，要連通全部頂點至少需要_條邊。A. n B. n+1 C. n-1 D. n/28對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是_。A. n B. (n-1)2 C. n-1 D. n29對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為_；所有鄰接表中的接點總數(shù)是_。 A. n B. n+1 C. n-1 D. n+e A. e/2 B. e C.2e D. n+e 10已知一個圖如圖7.1所示，若從頂點a出發(fā)按深度搜索法進行遍歷，則可能得到的一種頂點序列為_；按寬度搜索法進行遍歷，則可能得到的一種頂點序列為_。

3、A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,bbaecdf圖 7.1 一個無向圖11已知一有向圖的鄰接表存儲結構如圖7.2所示。12345324524圖7.2 一個有向圖的鄰接表存儲結構 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是_。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 根據(jù)有向圖

4、的寬度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是_。A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v212采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷13采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的_。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷14判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用_。A. 求關鍵路徑的方法 B. 求最短路徑的Dijkstra方法C. 寬度優(yōu)先遍歷算法 D.

5、 深度優(yōu)先遍歷算法15關鍵路徑是事件結點網(wǎng)絡中 。A.從源點到匯點的最長路徑 B.從源點到匯點的最短路徑C.最長的回路 D.最短的回路16下面不正確的說法是 。 （1）在AOE網(wǎng)中，減小一個關鍵活動上的權值后，整個工期也就相應減?。?（2）AOE網(wǎng)工程工期為關鍵活動上的權之和； （3）在關鍵路徑上的活動都是關鍵活動，而關鍵活動也必在關鍵路徑上。A.（1）B.（2）C.（3）D.（1）、（2）17用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印出相應的頂點，則輸出的頂點序列是 。A.逆拓樸有序的B.拓樸有序的C.無序的18在圖7.3所示的拓樸排列的結果序列為 。A.125634B.516

6、234C.123456D.521634圖7.3有向圖19一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù)為 。A.0B.1C.nD.n+120對于一個有向圖，若一個頂點的入度為k1,、出度為k2，則對應鄰接表中該頂點單鏈表中的結點數(shù)為 。A.k1B.k2C.k1-k2D.k1+k221對于一個有向圖，若一個頂點的入度為k1,、出度為k2，則對應逆鄰接表中該頂點單鏈表中的結點數(shù)為 。A.k1B.k2C.k1-k2D.k1+k27.2 填空題（將正確的答案填在相應餓空中）1n個頂點的連通圖至少_條邊。2在無權圖G的鄰接矩陣A中，若(vi,vj)或vi,vj屬于圖G的邊集合，則對應元素Aij等于_

7、，否則等于_。3在無向圖G的鄰接矩陣A中，若Aij等于1，則Aji 等于_。4已知圖G的鄰接表如圖7.4所示，其從頂點v1出發(fā)的深度有限搜索序列為_，其從頂點v1出發(fā)的寬度優(yōu)先搜索序列為_。v1v3v2v4v5v6v2v5v4v3v5v6v4v6v3 圖7.4 圖G的鄰接表5已知一個有向圖的鄰接矩陣表示，計算第i個結點的入度的方法是_。6已知一個圖的鄰接矩陣表示，刪除所有從第i個結點出發(fā)的邊的方法是_。7如果含n個頂點的圖形成一個環(huán)，則它有 棵生成樹。8一個非連通無向圖，共有28條邊，則該圖至少有 個頂點。9遍歷圖的過程實質上是 。BFS遍歷圖的時間復雜度為 ，DFS遍歷圖的時間復雜度為 ，兩

8、者不同之處在于 ，反映在數(shù)據(jù)結構上的差別是 。10一個圖的 表示法是唯一的，而 表示法是不唯一的。11有向圖中的結點前驅后繼關系的特征是 。12若無向圖G的頂點度數(shù)最小值大于等于 時，G至少有一條回路。13根據(jù)圖的存儲結構進行某種次序的遍歷，得到的頂點序列是 的。7.3 綜合題1562431已知如圖7.5所示的有向圖，請給出該圖的:（1）每個頂點的入/出度；（2）鄰接距陣；（3）鄰接表；（4）逆鄰接表；（5）強連通分量。圖7。5一個有向圖badcef161115151516131412212請用克魯斯卡爾和普里姆兩種算法分別為圖7.6、圖7.7構造最小生成樹： （1） 圖7.661213212

9、4952015161036154372（2） 圖7.73試列出圖7.8中全部的拓撲排序序列。123456圖7.84請用圖示說明圖7.9從頂點a到其余各頂點之間的最短路徑。543223356abdfce圖7.95已知AOE網(wǎng)有9個結點：V1，V2，V3，V4，V5，V6，V7，V8，V9，其鄰接矩陣如下：(1)請畫出該AOE圖。(2)計算完成整個計劃需要的時間。(3)求出該AOE網(wǎng)的關鍵路徑。645112974247.4 判斷題 1求最小生成樹的Prim算法在邊較少、結點較多時效率較高。（ ） 2圖的最小生成樹的形狀可能不唯一。（ ） 3用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用

10、的存儲空間大小只與圖中結點個數(shù)有關，而與圖的邊數(shù)無關。( )4 鄰接表法只用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。( )5 任何有向網(wǎng)絡（AOV-網(wǎng)絡）拓撲排序的結果是唯一的。( )6 有回路的圖不能進行拓撲排序。( )7 存儲無向圖的鄰接矩陣是對稱的，故只存儲鄰接矩陣的下(或上)三角部分即可。( ) 8. 用鄰接矩陣A表示圖，判定任意兩個結點Vi和Vj之間是否有長度為m的路徑相連，則只要檢查Am的第i行第j列的元素是否為0即可。( )9. 在AOE網(wǎng)中一定只有一條關鍵路徑。( )10. 縮短關鍵路徑上活動的工期一定能夠縮短整個工程的工期。( )11. 連通分量是無向圖中的極

11、小連通子圖。( )12. 強連通分量是有向圖中的極大強連通子圖。( )7.5 算法設計題 1試以鄰接矩陣為存儲結構實現(xiàn)圖的基本操作：InsertVex (G,v)、InsertArc (G,v,w)、DeleteVex (G,v)和DeleteArc (G,v,w)。2 試以鄰接表為存儲結構實現(xiàn)算法設計題1中所列圖的基本操作。3試以十字鏈表為存儲結構實現(xiàn)算法設計題1中所列圖的基本操作。4試以鄰接多重表為存儲結構實現(xiàn)算法設計題1中所列圖的基本操作。5試寫一算法由圖的鄰接鏈表存儲得到圖的十字鏈表存儲。 6寫一算法，由依次輸入圖的頂點數(shù)目、邊的數(shù)目、各頂點的信息和各條邊的信息建立無向圖的鄰接多重表。

12、 7試寫一個算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點vi到頂點vj的路徑（ij）。假設分別基于下述策略：（1） 圖的深度優(yōu)先搜索;（2） 圖的寬度優(yōu)先搜索。 8試修改Prim算法，使之能在鄰接表存儲結構上實現(xiàn)求圖的最小生成森林，并分析其時間復雜度（森林的存儲結構為孩子兄弟鏈表）。 9以鄰接表作存儲結構實現(xiàn)求從源點到其余各頂點的最短路徑的Dijkstra算法。 10給定n個村莊之間的交通圖，若村莊i和村莊j之間有道路，則將頂點i和頂點j用邊連結，邊上的權Wij表示這條道路的長度。現(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應建在那個村莊，才能使離醫(yī)院最近的村莊到醫(yī)院的路程最短

13、？試設計一個解答上述問題的算法，并應用該算法解答如圖所示的實例。2 12 15 6 24 9 4 6 10 4 7 3 3 6 2 景點不少于10個。以圖中頂點表示校內各景點。.假設采用鄰接表存儲，設計一個算法，判斷無向圖是否連通。若連通則返回；否則返回0。. 假設采用鄰接表存儲，設計一個算法，判斷無向圖中頂點i到頂點j是否有路徑，若有則返回，否則返回0。7.6 上機實習題目設計一個校園導游程序，為來訪的客人提供各種信息查詢服務?；疽螅?（1）設計你所在學校的校園平面圖，所含場所不少于10個。以圖中頂點表示校內各場所，存放場所名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。 （2）為來訪客人提供圖中任意場所相關信息的查詢。 （3）為來訪客人提供圖中任意場所的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。選作：（1） 提供圖中任意場所得問路查詢，即求任意兩個場所之間的所有路徑。（2） 校園導游圖的場所與道路的修改與擴充功能。習題答案 7.1 1. C2.B3.B4. C5. A6. A7.C8.D9. AC10.DB 11. CB12. A13. D 14.D15.A16.A17.A18.B19.B20.B21.A 7.2 1.n-1 2. 1;0 3. 1 4.v1,v2,v3,v6,v5, v4；v1,v2,v5,