目錄

一、判斷題

二、選擇題?

在開(kāi)始之前，先為大家推薦四篇介紹該章四個(gè)主要算法的的文章，供大家參考。

Dijkstra算法求最短路徑：Dijkstra算法原理_平凡的L同學(xué)的博客-CSDN博客_dijiesitela

Floyd算法求最短路徑：Floyd算法求最短路徑

Prim算法求最小生成樹(shù)：Prim算法求最小生成樹(shù)

Kruskal算法求最小上生成樹(shù)：Kruskal算法求最小上生成樹(shù)

一、判斷題

1、用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)。F

解析：用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)，空間代價(jià)為O（n*n）；用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)，有向圖為O（n+2e）,無(wú)向圖為O（n+e）。

2、無(wú)向連通圖所有頂點(diǎn)的度之和為偶數(shù)。T

解析：頂點(diǎn)的度為頂點(diǎn)所連接的邊的個(gè)數(shù)，無(wú)向連通圖中的頂點(diǎn)的度之和為邊數(shù)*2所以頂點(diǎn)的度之和為偶數(shù)。

3、無(wú)向圖的鄰接矩陣可用一維數(shù)組存儲(chǔ)。T

解析：習(xí)慣上無(wú)向圖的鄰接矩陣一般用二維數(shù)組存儲(chǔ)，這樣使用方便。當(dāng)然，任意二維數(shù)組都是可以用一維數(shù)組存儲(chǔ)的，只是用起來(lái)不方便。

4、若圖G有環(huán)，則G不存在拓?fù)渑判蛐蛄?。T

解析：拓?fù)渑判驅(qū)σ粋€(gè)有向無(wú)環(huán)圖(Directed Acyclic Graph簡(jiǎn)稱DAG)G進(jìn)行拓?fù)渑判?，存在拓?fù)渑判蚝蛨D是否有環(huán)是充分必要條件。

5、Prim 算法是通過(guò)每步添加一條邊及其相連的頂點(diǎn)到一棵樹(shù)，從而逐步生成最小生成樹(shù)。T

解析：prim算法是通過(guò)每步添加一條邊及其相連的頂點(diǎn)到一棵樹(shù)，從而逐步生成最小生成樹(shù)；

Kruskal 算法是維護(hù)一個(gè)森林，每一步把兩棵樹(shù)合并成一棵。

6、用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。T

解析：用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)，空間代價(jià)為O（n*n）。

7、在一個(gè)有向圖中，所有頂點(diǎn)的入度與出度之和等于所有邊之和的2倍。T

解析：有一條邊就會(huì)有兩個(gè)頂點(diǎn)分別增加一個(gè)入度和出度，所以所有頂點(diǎn)的入度與出度之和等于所有邊之和的2倍。

8、連通分量指的是有向圖中的極大連通子圖。F

解析：連通圖和連通分量都是針對(duì)無(wú)向圖而言的。在有向圖中，任意兩個(gè)頂點(diǎn)都有一條從1到2和一條從2到1的有向路徑，則稱該圖為強(qiáng)連通圖。有向圖中的極大連通子圖稱為該有向圖中的強(qiáng)連通分量。

9、在任一有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和。T

解析：在有向圖中，一條邊必然會(huì)對(duì)應(yīng)一個(gè)頂點(diǎn)的出和一個(gè)頂點(diǎn)的入，所以入度等于出度。

10、從n個(gè)頂點(diǎn)的連通圖中選取n-1條權(quán)值最小的邊即可構(gòu)成最小生成樹(shù)。F

解析：一個(gè)有N個(gè)頂點(diǎn)的連通圖的生成樹(shù)有N-1條邊，但是含N個(gè)頂點(diǎn)N-1條邊的圖不一定是生成樹(shù)。且最小生成樹(shù)的總權(quán)最小，不是其中的任意路徑最小。

11、對(duì)于帶權(quán)無(wú)向圖 G = (V, E)，M 是 G 的最小生成樹(shù)，則 M 中任意兩點(diǎn) V1 到 V2 的路徑一定是它們之間的最短路徑。F

解析：最小生成樹(shù)的總權(quán)最小，不是其中的任意路徑最小。

12、如果從有向圖?G?的每一點(diǎn)均能通過(guò)深度優(yōu)先搜索遍歷到所有其它頂點(diǎn)，那么該圖一定不存在拓?fù)湫蛄?。T

解析：如果從有向圖?G?的每一點(diǎn)均能通過(guò)深度優(yōu)先搜索遍歷到所有其它頂點(diǎn)，則該圖是一個(gè)有環(huán)圖；而拓?fù)渑判虻那疤崾怯邢驘o(wú)環(huán)圖。

二、選擇題?

1、數(shù)據(jù)結(jié)構(gòu)中Dijkstra算法用來(lái)解決哪個(gè)問(wèn)題？

A.字符串匹配

B.拓?fù)渑判?/p>

C.最短路徑

D.關(guān)鍵路徑

解析：

最短路徑算法：Dijkstra，F(xiàn)loyd

最小生成樹(shù)：Prim，Kruskal

字符串匹配：Kmp

拓?fù)渑判颍簩?duì)有向無(wú)環(huán)圖進(jìn)行

2、給定有權(quán)無(wú)向圖的鄰接矩陣如下，其最小生成樹(shù)的總權(quán)重是：

A.11

B.14

C.10

D.12

解析：

3、已知一個(gè)圖的鄰接矩陣如下，則從頂點(diǎn)V1出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，可能得到的一種頂點(diǎn)序列為：

A.V1,V2,V3,V5,V4,V6

B.V1,V3,V5,V6,V4,V2

C.V1,V3,V5,V2,V4,V6

D.V1,V2,V4,V5,V6,V3

解析：

4、對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向圖，要連通所有頂點(diǎn)至少需要多少條邊？

A.N

B.N/2

C.N?1

D.N+1

解析：連通是兩個(gè)頂點(diǎn)之間有路徑即連通，N-1條就夠了。

5、關(guān)于圖的鄰接矩陣，下列哪個(gè)結(jié)論是正確的？

A.有向圖的鄰接矩陣總是不對(duì)稱的

B.無(wú)向圖的鄰接矩陣可以是不對(duì)稱的，也可以是對(duì)稱

C.有向圖的鄰接矩陣可以是對(duì)稱的，也可以是不對(duì)稱的

D.無(wú)向圖的鄰接矩陣總是不對(duì)稱的

解析：有向圖的鄰接矩陣可以是不對(duì)稱的，也可以是對(duì)稱的；無(wú)向圖的鄰接矩陣一定是對(duì)稱的。?

6、在用鄰接表表示有N個(gè)結(jié)點(diǎn)E條邊的圖時(shí)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為：

A.O(N+E)

B.O(N2×E)

C.O(N2)

D.O(N)

解析：深度和廣度優(yōu)先優(yōu)先遍歷的時(shí)間復(fù)雜度一樣，采用鄰接表表示法，有向圖為O(n+2e)，無(wú)向圖為O(n+e)；鄰接矩陣法O(n*n)。

7、?給定一個(gè)有向圖的鄰接表如下圖，則該圖有__個(gè)強(qiáng)連通分量。

A.4 {{0, 1, 5}, {2}, {3}, {4}}

B.1 {0, 1, 2, 3, 4, 5}

C.1 {0, 5, 1, 3}

D.3 {{2}, {4}, {0, 1, 3, 5}}

解析：

8、對(duì)于有向圖，其鄰接矩陣表示比鄰接表表示更易于：

A.求一個(gè)頂點(diǎn)的出邊鄰接點(diǎn)

B.進(jìn)行圖的廣度優(yōu)先遍歷

C.進(jìn)行圖的深度優(yōu)先遍歷

D.求一個(gè)頂點(diǎn)的入度

解析：對(duì)于鄰接矩陣來(lái)說(shuō)，求一個(gè)結(jié)點(diǎn)的度，只需要訪問(wèn)鄰接矩陣的一行或一列就可以判斷次結(jié)點(diǎn)的度。

9、對(duì)下圖進(jìn)行拓?fù)渑判颍梢缘玫讲煌耐負(fù)湫蛄械膫€(gè)數(shù)是：

A.4

B.3

C.1

D.2

解析：個(gè)數(shù)是3，分別是abced,abecd,aebcd。先統(tǒng)計(jì)所有節(jié)點(diǎn)的入度，對(duì)于入度為0的節(jié)點(diǎn)就可以分離出來(lái)，然后把這個(gè)節(jié)點(diǎn)指向的節(jié)點(diǎn)的入度減一。一直做改操作，直到所有的節(jié)點(diǎn)都被分離出來(lái)。如果最后不存在入度為0的節(jié)點(diǎn)，那就說(shuō)明有環(huán)，不存在拓?fù)渑判?，也就是很多題目的無(wú)解的情況。

10、任何一個(gè)帶權(quán)無(wú)向連通圖的最小生成樹(shù)——

A.有可能不唯一

B.有可能不存在

C.是唯一的

D.是不唯一的

解析：最小生成樹(shù)不一定唯一，但如果邊的權(quán)值都不相等，則一定唯一。

11、下面給出的有向圖中，有__個(gè)強(qiáng)連通分量。

A.1 ({1,2,3,4})

B.2 ({1,2,3,4}, {0})

C.1 ({0,1,2,3,4})

D.5 ({0}, {1}, {2}, {3}, {4})?

解析：其實(shí)就是有幾個(gè)最大的環(huán)。

12、下面關(guān)于圖的存儲(chǔ)的敘述中，哪一個(gè)是正確的？

A.用相鄰矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)

B.用相鄰矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)

C.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)

D.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)

解析：鄰接矩陣只與結(jié)點(diǎn)個(gè)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān)；而鄰接表表示法與結(jié)點(diǎn)和邊的個(gè)數(shù)都有關(guān)系。?

上面的題目均是博主在期末考試前總結(jié)的重難點(diǎn)，歡迎各位大佬指正錯(cuò)誤或者給出更優(yōu)質(zhì)的解析。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-487635.html

到了這里，關(guān)于算法與數(shù)據(jù)結(jié)構(gòu) 第六章 圖（詳解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！