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

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)第7章圖習(xí)題

第7章圖

一、單項(xiàng)選擇題

1．在一個(gè)無(wú)向圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的______倍。A．l/2C．2

B．1D．4

2．在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的______倍。A．l/2C．2

B．1D．4

3．一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖最多包含______條邊。A．nC．n-1

B．n＋1D．n(n-1)/2

4．一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖包含______條邊。A．n(n-l)C．n(n-l)/2

B．n(n+l)D．n(n-l)/2

5．一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含______條邊。A．n(n-1)C．n(n-l)/2

B．n(n+l)D．n(n+l)/2

6．對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為_(kāi)_____。A．nC．n-1

7．無(wú)向圖的鄰接矩陣是一個(gè)______。A．對(duì)稱(chēng)矩陣C．上三角矩陣

B．零矩陣D．對(duì)角矩陣B．n×nD．(n-l)×(n-l)

8．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)(有)向圖，若采用鄰接表表示，則表頭向量的大小為_(kāi)_____。

A．nC．2n

B．eD．2e

9．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)(有)向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為_(kāi)_____。

A．nC．2n

B．eD．2e

10．在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有______鄰接點(diǎn)。A．入邊

C．入邊和出邊

B．出邊

D．不是入邊也不是出邊

11．在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有______鄰接點(diǎn)。A．入邊

C．入邊和出邊

B．出邊

D．不是人邊也不是出邊

12．假使從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先探尋即可訪問(wèn)所有頂點(diǎn)，則該圖一定是______。

A．完全圖C．有回路

B．連通圖D．一棵樹(shù)

13．采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的______算法。A．先序遍歷

B．中序遍歷

C．后序遍歷D．按層遍歷

14．采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的______算法。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷

15．假使無(wú)向圖G必需進(jìn)行二次廣度優(yōu)先探尋才能訪問(wèn)其所有頂點(diǎn)，則以下說(shuō)

法中不正確的是______。A．G確定不是完全圖

B．G一定不是連通圖

C．G中一定有回路D．G有二個(gè)連通分量16．以下有關(guān)圖遍歷的說(shuō)法不正確的是______。A．連通圖的深度優(yōu)先探尋是一個(gè)遞歸過(guò)程

B．圖的廣度優(yōu)先探尋中鄰接點(diǎn)的尋覓具有“先進(jìn)先出〞的特征C．非連通圖不能用深度優(yōu)先探尋法D．圖的遍歷要求每一頂點(diǎn)僅被訪問(wèn)一次17．以下說(shuō)法中不正確的是______。

A．無(wú)向圖中的極大連通子圖稱(chēng)為連通分量

B．連通圖的廣度優(yōu)先探尋中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)C．圖的深度優(yōu)先探尋中一般要采用棧來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)D．有向圖的遍歷不可采用廣度優(yōu)先探尋方法

18．一個(gè)有向圖G的鄰接表存儲(chǔ)如下圖7-1所示，現(xiàn)按深度優(yōu)先探尋遍歷，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是______。

A．v1，v2，v3，v4，v5B．v1，v2，v3，v5，v4C．v1，v2，v4，v5，v3D．v1，v2，v5，v3，v4

v1v2v3v4∧v5235∧35∧4∧4∧圖7-1一個(gè)有向圖的鄰接表

19．對(duì)圖7-2所示的無(wú)向圖，從頂點(diǎn)1開(kāi)始進(jìn)行深度優(yōu)先遍歷，可得到頂點(diǎn)訪問(wèn)

序列______。

A．1，2，4，3，5，7，6B．1，2，4，3，5，6，7C．1，2，4，5，6，3，7D．1，2，3，4，5，7，6

1324657圖7-2一個(gè)無(wú)向圖

20．對(duì)圖7-2所示的無(wú)向圖，從頂點(diǎn)1開(kāi)始進(jìn)行廣度優(yōu)先遍歷，可得到頂點(diǎn)訪問(wèn)

序列______。

A．1，3，2，4，5，6，7

B．1，2，4，3，5，6，7

C．1，2，3，4，5，7，6D．2，5，1，4，7，3，621．一個(gè)無(wú)向連通圖的生成樹(shù)是含有該連通圖的全部頂點(diǎn)的______。

A．微小連通子圖C．極大連通子圖

B．微小子圖D．極大子圖

22．設(shè)無(wú)向圖G=(V,E)和G’=(V’,E’)，假使G’為G的生成樹(shù)，則以下說(shuō)法中

不正確的是______。

A．G’為G的連通分量B．G’為G的無(wú)環(huán)子圖

C．G’為G的子圖D．G’為G的微小連通子圖且V’＝V23.任意一個(gè)無(wú)向連通圖______最小生成樹(shù)。A．只有一棵C．一定有多棵

B．有一棵或多棵D．可能不存在

24．對(duì)于含有n個(gè)頂點(diǎn)的帶權(quán)連通圖，它的最小生成樹(shù)是指圖中任意一個(gè)

________。

A．由n-1條權(quán)值最小的邊構(gòu)成的子圖。B．由n-1條權(quán)值之和最小的邊構(gòu)成的子圖。C．由n-1條權(quán)值之和最小的邊構(gòu)成的連通子圖。D．由n個(gè)頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的生成樹(shù)。

25．若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄?，則可斷定該有向圖_______。A．是個(gè)有根有向圖B．是個(gè)強(qiáng)連通圖

C．含有多個(gè)入度為0的頂點(diǎn)D．含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量26．判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用____。

A．求關(guān)鍵路徑的方法B．求最短路徑的Dijkstra算法C．廣度優(yōu)先遍歷算法D．深度優(yōu)先遍歷算法27．求最短路徑的Dijkstra算法的時(shí)間繁雜度為_(kāi)_____。A．O(n)

B．O(n+e)

C．O(n2)D．O(ne)28．求最短路徑的Floyd算法的時(shí)間繁雜度為_(kāi)_____。A．O(n)C．O(n2)29．關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中______。A．從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑

B．O(ne)D．O(n3)

B．從源點(diǎn)到匯點(diǎn)的最短路徑

C．最長(zhǎng)的回路30．下面說(shuō)法不正確的是______。

D．最短的回路

A．在AOE網(wǎng)中，減少任一關(guān)鍵活動(dòng)的權(quán)值后，整個(gè)工期也就相應(yīng)減少B．AOE網(wǎng)工程工期為關(guān)鍵活動(dòng)的權(quán)值和

C．在關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)也必需在關(guān)鍵路徑上D．A和B

31．下面說(shuō)法不正確的是______。

A．關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B．任何一個(gè)關(guān)鍵活動(dòng)提前完成，將使整個(gè)工程提前完成C．所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程提前完成D．某些關(guān)鍵活動(dòng)若提前完成，將使整個(gè)工程提前完成

二、填空題

1．對(duì)于具有n個(gè)頂點(diǎn)的無(wú)向圖G最多有_________條邊。2．對(duì)于具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖G至少有_________條邊。3．對(duì)于具有n個(gè)頂點(diǎn)的有向圖，每個(gè)頂點(diǎn)的度最大可達(dá)___________。4．若無(wú)向圖G的頂點(diǎn)度數(shù)最小值大于___________時(shí)，G至少有一條回路。5．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為_(kāi)__________，所有鄰接表中的結(jié)點(diǎn)總數(shù)是__________。

6．已知一個(gè)有向圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的弧的方法是____________。

7．對(duì)于n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是__________，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相連的方法是__________，求任意一個(gè)頂點(diǎn)的度的方法是___________。

8．對(duì)于n個(gè)頂點(diǎn)的有向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是_________，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相連的方法是__________，求任意一個(gè)頂點(diǎn)的度的方法是__________。

9．無(wú)向圖的連通分量是指___________。

10．已知圖G的鄰接表如圖7-3所示，從頂點(diǎn)v1出發(fā)的深度優(yōu)先探尋序列為_(kāi)_______，從頂點(diǎn)1出發(fā)的廣度優(yōu)先探尋序列為_(kāi)____________。

v1v2v3v4∧v5v6∧236∧35∧4∧463∧圖7-3圖G的鄰接表

11．n個(gè)頂點(diǎn)連通圖的生成樹(shù)一定有__________條邊。12．一個(gè)連通圖的___________是一個(gè)微小連通子圖。

13．Prim算法適用于求_________的網(wǎng)的最小生成樹(shù)，Kruskal算法適用于求

________的網(wǎng)的最小生成樹(shù)。

14．在AOV圖中，頂點(diǎn)表示________,有向邊表示________。15．可以進(jìn)行拓?fù)渑判虻挠邢驁D一定是_________。

16．從源點(diǎn)到匯點(diǎn)長(zhǎng)度最長(zhǎng)的路徑稱(chēng)為關(guān)鍵路徑，該路徑上的活動(dòng)稱(chēng)為_(kāi)_______。17．Dijkstra算法從源點(diǎn)到其它各頂點(diǎn)的路徑長(zhǎng)度按________次序依次產(chǎn)生，該

算法在邊上的權(quán)出現(xiàn)_________狀況時(shí)，不能正確產(chǎn)生最短路徑。18．求從某源點(diǎn)到其余各項(xiàng)點(diǎn)的Dijkstra算法在圖的頂點(diǎn)數(shù)為10，用鄰接矩陣表

示圖時(shí)計(jì)算時(shí)間約為10ms，則在圖的頂點(diǎn)數(shù)為40時(shí)，計(jì)算時(shí)間約為_(kāi)________ms。

三、判斷題

1．具有n個(gè)頂點(diǎn)的無(wú)向圖至多有n（n-1）條邊。2．有向圖中各頂點(diǎn)的入度之和等于各頂點(diǎn)的出度之和。3．鄰接矩陣只儲(chǔ)存了邊的信息，沒(méi)有存儲(chǔ)頂點(diǎn)的信息。

4．對(duì)同一個(gè)有向圖，只保存出邊的鄰接表中結(jié)點(diǎn)的數(shù)目總是和只保存入邊的鄰接表中結(jié)點(diǎn)的數(shù)目一樣多。

5．假使表示圖的鄰接矩陣是對(duì)稱(chēng)矩陣，則該圖一定是無(wú)向圖。

6．假使表示有向圖的鄰接矩陣是對(duì)稱(chēng)矩陣，則該有向圖一定是有向完全圖。

7．假使表示某個(gè)圖的鄰接矩陣不是對(duì)稱(chēng)矩陣，則該圖一定是有向圖。8．連通分量是無(wú)向圖的微小連通子圖。9．強(qiáng)連通分量是有向圖的極大連通子圖。

10．對(duì)有向圖G，假使以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先探尋能訪問(wèn)

到每一個(gè)頂點(diǎn)，則該圖一定是完全圖。

11．連通圖的廣度優(yōu)先探尋中一般要采用隊(duì)列來(lái)暫時(shí)剛訪問(wèn)過(guò)的頂點(diǎn)。12．圖的深度優(yōu)先探尋中一般要采用棧來(lái)暫時(shí)剛訪問(wèn)過(guò)的頂點(diǎn)。13．有向圖的遍歷不可采用廣度優(yōu)先探尋方法。14．連通圖的生成樹(shù)包含了圖中所有頂點(diǎn)。

15．設(shè)G為具有n個(gè)頂點(diǎn)的連通圖，假使其中的某個(gè)子圖有n個(gè)頂點(diǎn)，n-1條邊，則該子圖一定是G的生成樹(shù)。16．最小生成樹(shù)是指邊數(shù)最小的生成樹(shù)。

17．從n個(gè)頂點(diǎn)的連通圖中選取n-1條權(quán)值最小的邊，即可構(gòu)成最小生成樹(shù)。18．只要無(wú)向網(wǎng)中沒(méi)有權(quán)值一致的邊，其最小生成樹(shù)就是惟一的。19．只要無(wú)向網(wǎng)中有權(quán)值一致的邊，其最小生成樹(shù)就可能不是惟一的。20．有環(huán)圖也能進(jìn)行拓?fù)渑判颉?/p>

21．拓?fù)渑判蛩惴▋H適用于有向無(wú)環(huán)圖。

22．任何有向無(wú)環(huán)圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，而且拓?fù)湫蛄胁晃┮弧?3．關(guān)鍵路徑是由權(quán)值最大的邊構(gòu)成的。

24．在AOE網(wǎng)中，減小任一關(guān)鍵活動(dòng)上的權(quán)值后，整個(gè)工期也就相應(yīng)減小。25．在AOE網(wǎng)中工程工期為關(guān)鍵活動(dòng)上權(quán)值之和。

26．在關(guān)鍵路徑的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)未必在關(guān)鍵路徑上。27．關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。28．所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程將提前完成。29．某些關(guān)鍵活動(dòng)若提前完成，將可能使整個(gè)工程提前完成。30．求單源最短路徑的狄克斯特拉算法不適用于有回路的有向網(wǎng)。

四、簡(jiǎn)答題

1．圖G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有多少個(gè)頂點(diǎn)？2．用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是

否有關(guān)？

3．對(duì)于稠密圖和稀疏圖，就存儲(chǔ)而言，采用鄰接矩陣和鄰接表哪個(gè)更好些？4．請(qǐng)回復(fù)以下關(guān)于圖的一些問(wèn)題：

（1）有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊？最少有多少條邊？（2）表示一個(gè)有1000個(gè)頂點(diǎn)，1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣

元素？是否為稀疏矩陣？

（3）對(duì)于一個(gè)有向圖，不用拓?fù)渑判?，如何判斷圖是否存在環(huán)？

5．對(duì)n個(gè)頂點(diǎn)的無(wú)向圖和有向圖，采用鄰接表表示時(shí)，如何判別以下有關(guān)問(wèn)題？（1）圖中有多少條邊？

（2）任意兩個(gè)頂點(diǎn)i和j是否有邊相連？（3）任意一個(gè)頂點(diǎn)的度是多少？

6．給出如圖7-4所示的無(wú)向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。并在給定的鄰接表基礎(chǔ)上，指出從頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。

41352圖7-4一個(gè)無(wú)向圖

7．對(duì)于圖7-5所示的有向圖，試給出：

（1）鄰接矩陣。（2）鄰接表（3）強(qiáng)連通分量（4）對(duì)照鄰接表，給出從頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷序列。（5）對(duì)照鄰接表，給出從頂點(diǎn)3出發(fā)的深度優(yōu)先遍歷序列。

154623圖7-5一個(gè)有向圖

8．什么樣的圖其最小生成樹(shù)是惟一的？

9．已知帶權(quán)連通圖G(V,E)鄰接表如圖7-6所示，請(qǐng)畫(huà)出該圖，并分別以深度優(yōu)

先和廣度優(yōu)先遍歷該圖，寫(xiě)出遍歷中結(jié)點(diǎn)的序列，并畫(huà)出該圖的一棵最小生成樹(shù)，其中表結(jié)點(diǎn)的3個(gè)域各為：1.2.34.5

v1v2v3v4v5頂點(diǎn)號(hào)邊上所帶的權(quán)316322234410∧指針418∧522∧44∧510∧212112116118222圖7-6連通圖的鄰接表

10．已知世界6大城市為：北京（B）紐約（N）巴黎（P）倫敦（L）東京（T）

墨西哥城（M）試用由表1給出的交通網(wǎng)確定最小生成樹(shù)，并說(shuō)明所使用的方法及其時(shí)間繁雜度。

BNB109N109P8258L8155T21108M12432PLTM82812112458551083239792395899795113928911311．對(duì)于圖7-7所示的帶權(quán)有向圖，采用狄克斯特拉算法求從頂點(diǎn)1到其它頂點(diǎn)

的最短路徑，要求給出求解過(guò)程。

128953213221157440131354346212123

圖7-7一個(gè)有向圖圖7-8一個(gè)有向圖

12．設(shè)圖7-8中的頂點(diǎn)表示村莊，有向邊代表交通路線，若要建立一家醫(yī)院，試

問(wèn)建在哪個(gè)村莊能使個(gè)村莊總體交通代價(jià)最小。

13．表2所示給出了某工程各工序之間的優(yōu)先關(guān)系和各工序所需的時(shí)間。

表2某工程各工序關(guān)系表

工序ABCDEFGHIJKLMN所需時(shí)間15105081540300151206015302040先驅(qū)工作--A,BBC,DBEG,IEIF,IH,J,KLG完成如下各小題：

（1）畫(huà)出相應(yīng)的AOE網(wǎng)

（2）列出事件的最早發(fā)生時(shí)間，最遲發(fā)生時(shí)間。（3）找出關(guān)鍵路徑并指明完成該工程所需的最短時(shí)間。14．如圖7-9所示的AOE網(wǎng)，求：

（1）每項(xiàng)活動(dòng)ai最早開(kāi)始時(shí)間e(ai)和最遲開(kāi)始時(shí)間l(ai)。（2）完成此工程最少需要多少天（設(shè)邊上權(quán)值為天數(shù)）。（3）哪些是關(guān)鍵活動(dòng)

（4）是否存在某項(xiàng)活動(dòng)，當(dāng)其提高速度后能使整個(gè)工程縮短工期？

a3=32a1=51a2=63a5=35a4=6a6=37a10=598a11=210

4a7=46a12=4a8=1a9=4a13=2圖7-9五、算法設(shè)計(jì)題

1．假設(shè)圖G采用鄰接表存儲(chǔ)，分別設(shè)計(jì)實(shí)現(xiàn)以下要求的算法：（1）求出圖G中每個(gè)頂點(diǎn)的入度。（2）求出圖G中每個(gè)頂點(diǎn)的出度

（3）求出圖G中出度最大的一個(gè)頂點(diǎn)，輸出該頂點(diǎn)的編號(hào)。（4）計(jì)算圖G中出度為0的頂點(diǎn)數(shù)。

（5）判斷圖G中是否存在邊。

2．假設(shè)圖G采用鄰接矩陣存儲(chǔ)，分別設(shè)計(jì)實(shí)現(xiàn)以下要求的算法：（1）求出圖G中每個(gè)頂點(diǎn)的入度。（2）求出圖G中每個(gè)頂點(diǎn)的出度

（3）求出圖G中出度最大的一個(gè)頂點(diǎn)，輸出該頂點(diǎn)的編號(hào)。（4）計(jì)算圖G中出度為0的頂點(diǎn)數(shù)。（5）判斷圖G中是否存在邊。3．設(shè)計(jì)一個(gè)將鄰接表轉(zhuǎn)換為鄰接矩陣的算法。

4．一個(gè)連通圖采用鄰接表作為存儲(chǔ)機(jī)構(gòu)，設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)從頂點(diǎn)v出發(fā)的深度優(yōu)先遍歷的非遞歸過(guò)程。

5．設(shè)計(jì)一個(gè)算法，求不帶權(quán)無(wú)向連通圖G中距離頂點(diǎn)v的最遠(yuǎn)頂點(diǎn)。

6．設(shè)計(jì)一個(gè)算法，判斷無(wú)向圖G是否是一棵樹(shù)，若是樹(shù)，返回1；否則返回0。7．假設(shè)圖采用鄰接表存儲(chǔ)，分別寫(xiě)出基于DFS和BPS遍歷的算法來(lái)判別頂點(diǎn)i和頂點(diǎn)j（i!=j）之間是否有路徑。

8．假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，判斷無(wú)向圖G是否連通，若連通則返回1；否則返回0。

9．假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)u到v的長(zhǎng)度為1的所有簡(jiǎn)單路徑。

10．假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)u到v的所有簡(jiǎn)單路徑。

11．假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，從如圖7-10所示的無(wú)向圖G中

找出滿(mǎn)足如下條件的一條路徑：（1）給定起點(diǎn)vi和終點(diǎn)vj。

（2）給定一組必經(jīng)點(diǎn){7,9}，即輸出的路徑必需包含這些頂點(diǎn)。（3）給定一組必避點(diǎn){1,6}，即輸出的路徑不能包含這些頂點(diǎn)。

15032698121410741113

圖7-10

12．假設(shè)圖G采用鄰接矩