判斷題

1.Prim's algorithm is to maintain a forest and to merge two trees into one at each stage.

T

F

描述指的是kruskal。

2.Kruskal's algorithm is to maintain a forest and to merge two trees into one at each stage.

T

F

3.Kruskal's algorithm is to grow the minimum spanning tree by adding one edge, and thus an associated vertex, to the tree in each stage.

T

F

描述指的是prim

4.Prim's algorithm is to grow the minimum spanning tree by adding one edge, and thus an associated vertex, to the tree in each stage.

T

F

5.If graph G is a connected graph, the spanning tree of G is a maximal connected subgraph containing all n vertices of G.

T

F

最小生成樹是最小聯(lián)通子圖，減去任何一條邊都會(huì)導(dǎo)致結(jié)點(diǎn)減少，最大聯(lián)通子圖是指不能再大，沒有新的邊可以加入。

選擇題

1.給定有權(quán)無向圖的鄰接矩陣如下，其最小生成樹的總權(quán)重是：

A.8
B.15
C.20
D.22

比如采用kruskal，直接找最短邊就好了，3-1，3-2，3-4，3-5，3-6，計(jì)算這些邊的權(quán)重總和

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

A.24
B.23
C.18
D.17

采用kruskal，依次連接3-4，1-4，4-5，1-6，3-2，計(jì)算權(quán)重之和。

3.給定有權(quán)無向圖如下。關(guān)于其最小生成樹，下列哪句是對的？

A.邊(B, A)一定在樹中，樹的總權(quán)重為23
B.邊(D, C)一定在樹中，樹的總權(quán)重為20
C.最小生成樹不唯一，其總權(quán)重為23
D.最小生成樹唯一，其總權(quán)重為20

觀察邊是否一定在最小生成樹中，可以看有多少邊和它權(quán)重相同，如果有，那么最小生成樹可能是不唯一的，但總權(quán)重一定是固定的。

4.任何一個(gè)無向連通圖的最小生成樹（）。

A.一定有多棵
B.可能不存在
C.有一棵或多棵
D.只有一棵

5.無向連通圖的最小生成樹（ ）

A.一定唯一
B.有一個(gè)或多個(gè)
C.一定有多個(gè)
D.可能不存在

6.對于下列的網(wǎng) ，使用Prim算法由頂點(diǎn)A出發(fā)，求最小生成樹，吸取的第三條邊是。

A.（A,D）
B.（D,E）
C.（C,E）
D.（B,C）

Prim算法，是一顆向外生長的樹，算法每一步在連接集合和集合外的結(jié)點(diǎn)的所有邊中，選一條最輕量的邊加入樹中。

這道題目中，第一次選A-D加入，第二次選D-E加入，第三次選E-C。

7.下列說法中正確的是

A.若一個(gè)無向圖的最小生成樹唯一，則該無向圖中沒有權(quán)值相同的邊
B.若一個(gè)無向完全圖有 N 個(gè)頂點(diǎn)，且各邊權(quán)值均相同，則該圖有 N! 種最小生成樹
C.若一個(gè)無向連通圖沒有權(quán)值相同的邊，則該無向圖的最小生成樹唯一
D.一個(gè)無向圖的最小生成樹是該圖的極大連通子圖

如果一個(gè)無向圖的極小連通子圖恰好是構(gòu)成這個(gè)圖的所有邊，那么因?yàn)檫厸]有任何選擇，所以無向圖中的邊無所謂權(quán)值是否一樣；

拿N等于3來舉例，當(dāng)各邊權(quán)值相同，有3種最小生成樹，顯然不符合N!這個(gè)規(guī)律；

最小生成樹是極小連通子圖。

8.在求最小生成樹時(shí)，Prim算法更適合于____。

A.有向圖
B.無向圖
C.稀疏圖
D.稠密圖

9.在求最小生成樹時(shí)，Kruskal算法更適合于____。

A.有向圖
B.無向圖
C.稀疏圖
D.稠密圖

10.以下哪個(gè)不是給定無向帶權(quán)圖的最小生成樹？

A.
B.
C.
D.

計(jì)算一下權(quán)重和，D過大

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法（周测6-最小生成树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。