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

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

2、 D、十字鏈表7. 對(duì)一個(gè)具有n個(gè)頂點(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. 對(duì)于一個(gè)具有N個(gè)頂點(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. 對(duì)于一個(gè)具有n個(gè)頂點(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. 在有向圖的鄰接表存儲(chǔ)結(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. 已知一個(gè)圖，若從頂點(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. 采用鄰接表存儲(chǔ)的圖的深度和廣度優(yōu)先搜索遍歷算法類似于二叉樹的（ ）和（ ）。A、中序遍歷 B、先序遍歷 C、

4、后序遍歷 D、層次遍歷14. 已知一有向圖的鄰接表存儲(chǔ)結(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個(gè)頂點(diǎn)為A，B，C，D，E，F(xiàn)，G，H的無向圖，其鄰接矩陣存儲(chǔ)結(jié)構(gòu)如下，由此結(jié)構(gòu)，從A點(diǎn)開始深度遍歷，得到的頂點(diǎn)序列為（ ）。A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDCE、ABEHFGDC F、ABEHGFCD16. 已知一個(gè)圖如下，在該圖的最

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. 已知一個(gè)圖如下，則由該圖得到的一種拓?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 個(gè)頂點(diǎn)的無向圖中，若邊數(shù)大于n-1，則該圖必定是連通圖 D、圖的鄰接矩陣必定是對(duì)稱矩陣。21. 下面結(jié)論中正確的是（ ）。A、若有向圖的鄰接矩陣中對(duì)角線以下元素均為0，則該圖的拓?fù)渑判蛐蛄斜囟ù嬖凇?B、網(wǎng)絡(luò)的最小代價(jià)生成樹是唯一的。 C、在拓?fù)渑判蛐蛄兄?，任意兩個(gè)相繼頂點(diǎn)vi 和vj 都存在從vi 到vj 的路徑。 D、在

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

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

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

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

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

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

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

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

15、 ）。刪除所有從第 i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是（ ）。19. 設(shè)無向圖G中頂點(diǎn)數(shù)為n，則圖G最少有（ ）條邊，最多有（ ）條邊。若G為有向圖，有n個(gè)頂點(diǎn)，則圖至少有（ ）條邊，最多有（ ）條邊。20. 某作業(yè)工程表示成網(wǎng)絡(luò)圖，如圖7.5所示。事件5的最早完成時(shí)間是（ ）。事件4的最遲開始時(shí)間是（ ）。事件5 的遲緩時(shí)間是（ ）。關(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、（ ）的。如果對(duì)于圖中的任意兩個(gè)頂點(diǎn)vi,vjV，且vi和vj都是連通的，則稱G為（ ）。23. 連通分量是無向圖中的（ ）連通子圖。24. 對(duì)無向圖，若它有n個(gè)頂點(diǎn)e條邊，則其鄰接表中需要（ ）個(gè)結(jié)點(diǎn)。其中，（ ）個(gè)結(jié)點(diǎn)構(gòu)成頭結(jié)點(diǎn)，（ ）個(gè)結(jié)點(diǎn)構(gòu)成邊結(jié)點(diǎn)表。25. 對(duì)有向圖，若它有n頂點(diǎn)e條邊，則其鄰接表中需要（ ）個(gè)結(jié)點(diǎn)。其中，（ ）個(gè)結(jié)點(diǎn)構(gòu)成頭結(jié)點(diǎn)，（ ）個(gè)結(jié)點(diǎn)構(gòu)成邊結(jié)點(diǎn)表。26. 在鄰接表上，無向圖中頂點(diǎn)vi的度恰為（ ）。對(duì)有向圖，頂點(diǎn)vi的出度是（ ）。為了求入度，必須遍歷整個(gè)鄰接表，在所有單鏈表中，其鄰接點(diǎn)域的值為（ ）的結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)vi的入度。27. 遍歷圖的基本方法有（

17、）優(yōu)先搜索和（ ）優(yōu)先搜索兩種。四、 簡答題1. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的連通無向圖，如果它有且只有一個(gè)簡單回路，此圖有幾條邊？一個(gè)具有n個(gè)頂點(diǎn)的弱連通圖至少有幾條邊？2. 已知某圖的鄰接表，如何建立該圖的鄰接矩陣？3. 簡述無向圖和有向圖有哪幾種存儲(chǔ)結(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é)果不是唯一的，對(duì)圖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） 由廣度