數(shù)據(jù)結(jié)構(gòu)習(xí)題集 圖

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

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

3、、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e11. 在有向圖的鄰接表存儲結(jié)構(gòu)中，頂點(diǎn)v在表結(jié)點(diǎn)中出現(xiàn)的次數(shù)是（ ）。A、頂點(diǎn)v 的度 B、頂點(diǎn)v 的出度 C、頂點(diǎn)v 的入度 D、依附于頂點(diǎn)v 的邊數(shù)12. 已知一個圖，若從頂點(diǎn)a出發(fā)進(jìn)行深度和廣度優(yōu)先搜索遍歷，則可能得到的頂點(diǎn)序列分別為（ ）和（ ）（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. 已知一有向圖的鄰接表存儲結(jié)構(gòu)如下圖所示，分別根據(jù)圖的深度和廣度優(yōu)先搜索遍歷算法，從頂點(diǎn)v1出發(fā)，得到的頂點(diǎn)序列分別為（ ）和（ ）。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個頂點(diǎn)為A，B，C，D，E，F(xiàn)，G，H的無向圖，其鄰接矩陣存儲結(jié)構(gòu)如下，由此結(jié)構(gòu)，從A點(diǎn)開始深度遍歷，得到的頂點(diǎn)序列為（ ）。A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDCE、ABEHFGDC F、ABEHGFCD16. 已知一個圖如下，在該圖的最

5、小生成樹中各邊上權(quán)值之和為（ ），在該圖的最小生成樹中，從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. 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中的（ ）。A、從源點(diǎn)到匯點(diǎn)的最長路徑 B、從源點(diǎn)到匯點(diǎn)的最短路徑 C、最長的回路 D、最短的回路18. 正確的AOE網(wǎng)必須是（ ），AOE網(wǎng)中某邊權(quán)值應(yīng)當(dāng)是（ ）。（1）A、完全圖 B、哈密爾頓圖 C、無環(huán)圖 D、強(qiáng)連通圖（2）A、實(shí)數(shù) B、正整數(shù) C、正數(shù) D、非負(fù)數(shù)19. 已知一個圖如下，則由該圖得到的一種拓?fù)湫蛄袨椋?）。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. 下面結(jié)論中正確的是（ ）。A、在無向圖中，邊的條數(shù)是頂點(diǎn)度數(shù)之和。 B、在圖結(jié)構(gòu)中，頂點(diǎn)可以沒有任何前驅(qū)和后繼。 C、在n 個頂點(diǎn)的無向圖中，若邊數(shù)大于n-1，則該圖必定是連通圖 D、圖的鄰接矩陣必定是對稱矩陣。21. 下面結(jié)論中正確的是（ ）。A、若有向圖的鄰接矩陣中對角線以下元素均為0，則該圖的拓?fù)渑判蛐蛄斜囟ù嬖凇?B、網(wǎng)絡(luò)的最小代價生成樹是唯一的。 C、在拓?fù)渑判蛐蛄兄?，任意兩個相繼頂點(diǎn)vi 和vj 都存在從vi 到vj 的路徑。 D、在

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

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

9、任何一個帶權(quán)的無向連通圖的最小生成樹（ ）。A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在29. 以下說法正確的是（ ）。A、連通圖的生成樹，是該連通圖的一個極小連通子圖。B、無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣一定是不對稱的。C、任何一個有向圖，其全部頂點(diǎn)可以排成一個拓?fù)湫蛄?。D、有回路的圖不能進(jìn)行拓?fù)渑判颉?0. 以下說法錯誤的是（ ）。A、用鄰接矩陣法存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點(diǎn)個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。B、鄰接表法只能用于有向圖的存儲，而鄰接矩陣法對于有向圖和無向圖的存儲都適用。C、存儲無向圖的鄰接矩陣是對稱的，因此也

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

11、個頂點(diǎn)出發(fā)，進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個頂點(diǎn)。3. 任何有向網(wǎng)拓?fù)渑判虻慕Y(jié)果是唯一的。4. 有回路的圖不能進(jìn)行拓?fù)渑判颉?. 存儲有向圖的鄰接矩陣是對稱的。6. 一個有向圖G中若有弧<vi,vj>、<vj,vk>和<vi,vk>, 則在圖G的拓?fù)湫蛄兄校旤c(diǎn)vi,vj 和vk 的相對位置為vi,vj,vk。7. 在AOE網(wǎng)中一定有一條關(guān)鍵路徑。8. 含有10個頂點(diǎn)的無向連通圖其生成樹含有9 條邊。9. 十字鏈表是圖的一種順序表示法。三、 填空題1. 對具有n個頂點(diǎn)的圖，其生成樹有且僅有（ ）條邊，即生成樹是圖的邊數(shù)（ ）的連通圖。2. 一

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

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

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

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

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

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

18、設(shè)有一無向圖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) 按上述順序輸入后，畫出其相應(yīng)的鄰接表；2) 在該鄰接表上，從頂點(diǎn)4開始，寫出DFS序列和BFS序列。6. 已知連通網(wǎng)的鄰接矩陣如圖7.8所示，頂點(diǎn)集合為v1,v2,v3,v4,v5，試畫出它所表示的從頂點(diǎn)v1開始利用Prim 算法得到的最小生成樹。7. 拓?fù)渑判虻慕Y(jié)果不是唯一的，對圖7.9進(jìn)行拓?fù)渑判颍瑢懗鋈坎煌耐負(fù)渑判蛐蛄小?. 已知圖G的鄰接表如圖7.10所示，頂點(diǎn)V1為出發(fā)點(diǎn)，完成要求：（1） 深度優(yōu)先搜索的頂點(diǎn)序列；（2） 廣度優(yōu)先搜索的頂點(diǎn)序列；（3） 由深度優(yōu)先搜索得到的一棵生成樹；（4） 由廣度