數據結構習題集 圖

1、第7章 圖一、 選擇題1. 一個有n 個頂點的無向圖最多有（ ）條邊。A、n B、n(n-1) C、n(n-1)/2 D、2n2. 具有6 個頂點的無向圖至少有（ ）條邊才能保證是一個連通圖。A、5 B、6 C、7 D、83. 具有n 個頂點且每一對不同的頂點之間都有一條邊的圖被稱為（ ）。A、線性圖 B、無向完全圖 C、無向圖 D、簡單圖4. 具有4個頂點的無向完全圖有（ ）條邊。A、6 B、12 C、16 D、205. G是一個非連通無向圖，共有28 條邊，則該圖至少有（ ）個頂點。A、6 B、7 C、8 D、96. 存儲稀疏圖的數據結構常用的是（ ）。A、鄰接矩陣 B、三元組 C、鄰接表

2、 D、十字鏈表7. 對一個具有n個頂點的圖，采用鄰接矩陣表示則該矩陣的大小為（ ）。A、n B、(n-1)2 C、(n+1)2 D、n28. 設連通圖G的頂點數為n，則G 的生成樹的邊數為（ ）。A、n-1 B、n C、2n D、2n-19. 對于一個具有N個頂點和E條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為（ （1） ）；所有鄰接表中的結點總數是（ （2） ）。（1）A、N B、N+1 C、N-1 D、N+E（2）A、E/2 B、E C、2E D、N+E10. 對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表向量的大小為（ ），所有頂點鄰接表的結點總數為（ ）。A、n B

3、、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e11. 在有向圖的鄰接表存儲結構中，頂點v在表結點中出現的次數是（ ）。A、頂點v 的度 B、頂點v 的出度 C、頂點v 的入度 D、依附于頂點v 的邊數12. 已知一個圖，若從頂點a出發(fā)進行深度和廣度優(yōu)先搜索遍歷，則可能得到的頂點序列分別為（ ）和（ ）（1） A、abecdf B、acfebd C、acebfd D、acfdeb（2） A、abcedf B、abcefd C、abedfc D、acfdeb13. 采用鄰接表存儲的圖的深度和廣度優(yōu)先搜索遍歷算法類似于二叉樹的（ ）和（ ）。A、中序遍歷 B、先序遍歷 C、

4、后序遍歷 D、層次遍歷14. 已知一有向圖的鄰接表存儲結構如下圖所示，分別根據圖的深度和廣度優(yōu)先搜索遍歷算法，從頂點v1出發(fā)，得到的頂點序列分別為（ ）和（ ）。A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v3,v4,v5,v2 D、v1,v4,v3,v5,v215. 已知有8個頂點為A，B，C，D，E，F，G，H的無向圖，其鄰接矩陣存儲結構如下，由此結構，從A點開始深度遍歷，得到的頂點序列為（ ）。A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDCE、ABEHFGDC F、ABEHGFCD16. 已知一個圖如下，在該圖的最

5、小生成樹中各邊上權值之和為（ ），在該圖的最小生成樹中，從v1到v6的路徑為（ ）。A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v617. 關鍵路徑是事件結點網絡中的（ ）。A、從源點到匯點的最長路徑 B、從源點到匯點的最短路徑 C、最長的回路 D、最短的回路18. 正確的AOE網必須是（ ），AOE網中某邊權值應當是（ ）。（1）A、完全圖 B、哈密爾頓圖 C、無環(huán)圖 D、強連通圖（2）A、實數 B、正整數 C、正數 D、非負數19. 已知一個圖如下，則由該圖得到的一種拓撲序列為（ ）。A、v1,v4,

6、v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v520. 下面結論中正確的是（ ）。A、在無向圖中，邊的條數是頂點度數之和。 B、在圖結構中，頂點可以沒有任何前驅和后繼。 C、在n 個頂點的無向圖中，若邊數大于n-1，則該圖必定是連通圖 D、圖的鄰接矩陣必定是對稱矩陣。21. 下面結論中正確的是（ ）。A、若有向圖的鄰接矩陣中對角線以下元素均為0，則該圖的拓撲排序序列必定存在。 B、網絡的最小代價生成樹是唯一的。 C、在拓撲排序序列中，任意兩個相繼頂點vi 和vj 都存在從vi 到vj 的路徑。 D、在

7、有向圖中，從一個頂點到另一個頂點的最短路徑是唯一的。22. 下面結論不正確的是（ ）。A、無向圖的連通分量是該圖的極大連通子圖。 B、有向圖用鄰接矩陣表示容易實現求頂點度數的操作。 C、無向圖用鄰接矩陣表示，圖中的邊數等于鄰接矩陣元素之和的一半。 D、有向圖的鄰接矩陣必定不是對稱矩陣。23. 下面結論中正確的是（ ）。A、按深度優(yōu)先搜索遍歷圖時，與始點相鄰的頂點先于不與始點相鄰的頂點訪問。 B、一個圖按深度優(yōu)先搜索遍歷的結果是唯一的。 C、若有向圖G中包含一個環(huán)，則G的頂點間不存在拓撲排序。 D、圖的拓撲排序序列是唯一的。24. 下面結論中不正確的是（ ）。A、按廣度優(yōu)先搜索遍歷圖時，與始點相

8、鄰的頂點先于不與始點相鄰的頂點訪問。 B、一個圖按廣度優(yōu)先搜索遍歷的結果是唯一的。 C、無向圖的鄰接表表示法中，表中結點的數目是圖中邊的條數的2倍。D、圖的多重鄰接表表示法中，表中結點數目是圖中邊的條數。25. 在一個圖中，所有頂點的度數之和等于所有邊數的（ ）倍。A、1/2 B、1 C、2 D、426. 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（ ）倍。A、1/2 B、1 C、2 D、427. 判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用（ ）。A、求關鍵路徑的方法 B、求最短路徑的DIJKSTRA 方法C、廣度優(yōu)先遍歷算法 D、深度優(yōu)先遍歷算法28.

9、任何一個帶權的無向連通圖的最小生成樹（ ）。A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在29. 以下說法正確的是（ ）。A、連通圖的生成樹，是該連通圖的一個極小連通子圖。B、無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣一定是不對稱的。C、任何一個有向圖，其全部頂點可以排成一個拓撲序列。D、有回路的圖不能進行拓撲排序。30. 以下說法錯誤的是（ ）。A、用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結點個數有關，而與圖的邊數無關。B、鄰接表法只能用于有向圖的存儲，而鄰接矩陣法對于有向圖和無向圖的存儲都適用。C、存儲無向圖的鄰接矩陣是對稱的，因此也

10、可以只要存儲鄰接矩陣的下（或上）三角部分。D、用鄰接矩陣A 表示圖，判定任意兩個結點Vi 和Vj 之間是否有長度為m 的路徑相連，則只要檢查Am的第i行第j列的元素是否為0 即可。31. 以下說法正確的是（ ）。A、連通分量是無向圖中的極小連通子圖。B、強連通分量是有向圖中的極大強連通子圖。C、在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧<a,b>。D、對有向圖G,如果從任意頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點，則該圖一定是完全圖。二、 判斷題1. 用鄰接矩陣法存儲一個圖時，所占用的存儲空間大小僅與圖中結點個數有關。2. 對任意一個圖，從它的某

11、個頂點出發(fā)，進行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個頂點。3. 任何有向網拓撲排序的結果是唯一的。4. 有回路的圖不能進行拓撲排序。5. 存儲有向圖的鄰接矩陣是對稱的。6. 一個有向圖G中若有弧<vi,vj>、<vj,vk>和<vi,vk>, 則在圖G的拓撲序列中，頂點vi,vj 和vk 的相對位置為vi,vj,vk。7. 在AOE網中一定有一條關鍵路徑。8. 含有10個頂點的無向連通圖其生成樹含有9 條邊。9. 十字鏈表是圖的一種順序表示法。三、 填空題1. 對具有n個頂點的圖，其生成樹有且僅有（ ）條邊，即生成樹是圖的邊數（ ）的連通圖。2. 一

12、個無向圖有n個頂點和e條邊，則所有頂點的度數之和為（ ），其鄰接矩陣是一個關于（ ）對稱的矩陣。3. 在圖形結構中，每個結點的前驅結點和后繼結點可以有（ ）。4. 設無向圖G的頂點數為n，圖G最少有（ ）邊，最多有（ ）條邊。若G為有向圖，有n個頂點，則圖G最少有（ ）條邊，最多有（ ）條邊。具有n個頂點的無向完全圖，邊的總數為（ ）條，而有n個頂點的有向完全圖，邊的總數為（ ）條。5. 在無權圖G的鄰接矩陣A中，若(vi,vj)或<vi,vj>屬于G的邊/弧的集合，則對應元素Aij等于（ ），否則等于（ ）。6. 在無向圖G的鄰接矩陣A中，若Aij=1，則Aji等于（ ）。7.

13、已知一個圖的鄰接矩陣表示，計算第I個頂點的入度方法為（ ）。8. 在一個圖G的鄰接表表示中，每個頂點的鄰接表中所含的結點數，對于有向圖而言等于該頂點的（ ），而對于無向圖而言等于該頂點的（ ）。9. 已知圖G的鄰接表如圖7.4所示，其從頂點V1出發(fā)的深度優(yōu)先搜索序列為（ ），其從頂點V1出發(fā)的廣度優(yōu)先搜索序列為（ ）。10. n個頂點的弱連通有向圖G最多有（ ）條弧，最少有（ ）條弧。11. 在n個頂點e條邊的連通圖中，連通分量個數為（ ）。12. 任何（ ）的有向圖，其所有結點都可以排在一個拓撲序列中，拓撲排序的方法是先從圖中選一個（ ）為0的結點且輸出，然后從圖中刪除該結點及其（ ），反復

14、執(zhí)行，直到所有結點都輸出為止。13. 一個連通圖的（ ）是一個極小連通子圖。14. 在AOE網中，從源點到匯點各活動時間總和最長的路徑為（ ）。15. 在有向圖的鄰接矩陣上，由第i行可得到第（ ）個結點的出度，而由第j列可得到第（ ）個結點的入度。16. 對無向圖，設有n個結點，e條邊，則其鄰接表表示中需要（ ）個表結點，對有向圖，設有n個頂點，e條弧，則其鄰接表表示需要（ ）個表結點。17. 在無權圖G的鄰接矩陣A中，若 (Vi,Vj)或<Vi,Vj>屬于圖G的邊集,則對應元素Ai,j等于（ ），否則等于（ ）。18. 已知一個有向圖的鄰接矩陣表示，計算第i個結點的入度的方法是（

15、 ）。刪除所有從第 i個結點出發(fā)的邊的方法是（ ）。19. 設無向圖G中頂點數為n，則圖G最少有（ ）條邊，最多有（ ）條邊。若G為有向圖，有n個頂點，則圖至少有（ ）條邊，最多有（ ）條邊。20. 某作業(yè)工程表示成網絡圖，如圖7.5所示。事件5的最早完成時間是（ ）。事件4的最遲開始時間是（ ）。事件5 的遲緩時間是（ ）。關鍵路徑是（ ）。21. 設 x,yV，若<x,y>E,則<x,y>表示有向圖G中從x到y(tǒng)的一條（ ），x稱為（ ）點，y稱為（ ）點。若（x,y）E，則在無向圖G中x和y間有一條（ ）。22. 在無向圖中，如果從頂點v到頂點v有路徑，則稱v和v是

16、（ ）的。如果對于圖中的任意兩個頂點vi,vjV，且vi和vj都是連通的，則稱G為（ ）。23. 連通分量是無向圖中的（ ）連通子圖。24. 對無向圖，若它有n個頂點e條邊，則其鄰接表中需要（ ）個結點。其中，（ ）個結點構成頭結點，（ ）個結點構成邊結點表。25. 對有向圖，若它有n頂點e條邊，則其鄰接表中需要（ ）個結點。其中，（ ）個結點構成頭結點，（ ）個結點構成邊結點表。26. 在鄰接表上，無向圖中頂點vi的度恰為（ ）。對有向圖，頂點vi的出度是（ ）。為了求入度，必須遍歷整個鄰接表，在所有單鏈表中，其鄰接點域的值為（ ）的結點的個數是頂點vi的入度。27. 遍歷圖的基本方法有（

17、）優(yōu)先搜索和（ ）優(yōu)先搜索兩種。四、 簡答題1. 對于一個具有n個頂點的連通無向圖，如果它有且只有一個簡單回路，此圖有幾條邊？一個具有n個頂點的弱連通圖至少有幾條邊？2. 已知某圖的鄰接表，如何建立該圖的鄰接矩陣？3. 簡述無向圖和有向圖有哪幾種存儲結構，并說明各種結構在圖的不同操作中有什么優(yōu)越性？什么是AOE網的關鍵路徑？五、 補充應用題1. 給出無向圖如圖7.6所示的G1的鄰接矩陣和鄰接表。圖 7.62. 分別給出圖7.6所示的G2的鄰接矩陣、鄰接表和逆鄰接表。3. 分別給出圖7.6所示的G3從v5出發(fā)按深度優(yōu)先搜索和廣度優(yōu)先搜索算法遍歷得到的頂點序列。4. 求出圖7.7的連通分量。5.

18、設有一無向圖G=(V,E),其中V=1,2,3,4,5,6,E=(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)。1) 按上述順序輸入后，畫出其相應的鄰接表；2) 在該鄰接表上，從頂點4開始，寫出DFS序列和BFS序列。6. 已知連通網的鄰接矩陣如圖7.8所示，頂點集合為v1,v2,v3,v4,v5，試畫出它所表示的從頂點v1開始利用Prim 算法得到的最小生成樹。7. 拓撲排序的結果不是唯一的，對圖7.9進行拓撲排序，寫出全部不同的拓撲排序序列。8. 已知圖G的鄰接表如圖7.10所示，頂點V1為出發(fā)點，完成要求：（1） 深度優(yōu)先搜索的頂點序列；（2） 廣度優(yōu)先搜索的頂點序列；（3） 由深度優(yōu)先搜索得到的一棵生成樹；（4） 由廣度