判斷題

1.AOE圖的關(guān)鍵路徑就是最長(zhǎng)的路徑

T

F

2.AOE圖的權(quán)值最大的邊（活動(dòng)）一定是關(guān)鍵活動(dòng)。

T

F

兩條邊相加可能比最大的邊還要大。

3.在AOE-網(wǎng)工程中，減少任一關(guān)鍵活動(dòng)上的權(quán)值后，整個(gè)工期也就會(huì)相應(yīng)的減小。

T

F

關(guān)鍵路徑有多條時(shí)不一定。

4.AOE-網(wǎng)工程工期為關(guān)鍵活動(dòng)上的權(quán)之和。

T

F

工期為起點(diǎn)到終點(diǎn)的最大路徑長(zhǎng)度。

5.在關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)，而關(guān)鍵活動(dòng)也必在關(guān)鍵路徑上。

T

F

6.若圖G有環(huán)，則G不存在拓?fù)渑判蛐蛄小?/p>

T

F

存在拓?fù)渑判蚝蛨D是否有環(huán)是充分必要條件。

7.若圖G為連通圖且不存在拓?fù)渑判蛐蛄校瑒t圖G必有環(huán)。

T

F

8.拓?fù)湫蛞欢ㄊ俏ㄒ坏摹?/p>

T

F

選擇題

1.在AOE網(wǎng)中，什么是關(guān)鍵路徑？

A.最短回路
B.最長(zhǎng)回路
C.從第一個(gè)事件到最后一個(gè)事件的最短路徑
D.從第一個(gè)事件到最后一個(gè)事件的最長(zhǎng)路徑

見定義。

2.如圖所示的AOE-網(wǎng)，求這個(gè)工程最早可能在什么時(shí)間結(jié)束。

A.33
B.18
C.43
D.26

關(guān)鍵路徑為1-3-2-5-6，把權(quán)值相加為43。

3.求如圖所示的AOE-網(wǎng)的關(guān)鍵路徑。

A.<1,2><2,4><4,6>
B.<1, 3><3, 2><2, 5><5, 6>
C.<1,3><3,5><5,6>
D.<1,2><2,5><5.6>

關(guān)鍵路徑為1-3-2-5-6。

4.如圖所示的AOE-網(wǎng) ，事件④的最遲發(fā)生時(shí)間是。

A.29
B.37
C.38
D.43

4的最遲發(fā)生時(shí)間為整個(gè)工程的時(shí)間減去6。

5.下圖所示的 AOE 網(wǎng)表示一項(xiàng)包含 8 個(gè)活動(dòng)的工程。活動(dòng) d 的最早開始時(shí)間和最遲開始時(shí)間分別是：

A.3 和 7
B.12 和 12
C.12 和 14
D.15 和 15

d的最早開始時(shí)間為2結(jié)束后，也就是8+4=12，最遲發(fā)生時(shí)間為工程總時(shí)間27減g和d的長(zhǎng)度。

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

A.4
B.3
C.2
D.1

abced,aebcd,abecd。

7.下圖為一個(gè)AOV網(wǎng)，其可能的拓?fù)溆行蛐蛄袨椋?br />

A.ACBDEF
B.ABCEFD
C.ABCDFE
D.ABCEDF

8.在拓?fù)渑判蛩惴ㄖ杏枚褩：陀藐?duì)列產(chǎn)生的結(jié)果會(huì)不同嗎？

A.是的肯定不同
B.肯定是相同的
C.有可能會(huì)不同
D.以上全不對(duì)

9.設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，采用鄰接表存儲(chǔ)，進(jìn)行拓?fù)渑判驎r(shí)，時(shí)間復(fù)雜度為（）。

A.O (nlog_?2e)
B.O ( elog_?2n)
C.O (e*n )
D.O (n+e)

算法每次找玩度為0的點(diǎn)，需要O(n)，有e條邊，所以頂點(diǎn)的入度減1一共花了O(e)，總共就是O(n+e)。

10.有拓?fù)渑判虻膱D一定是（）。

A.無(wú)向圖
B.有向無(wú)環(huán)圖
C.有環(huán)圖
D.強(qiáng)連通圖

11.判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以利用（）。

A.求最短路徑的Dijkstra
B.求生成樹的方法
C.深度優(yōu)先遍歷算法
D.寬度優(yōu)先遍歷算法

深度優(yōu)先搜索如果一個(gè)頂點(diǎn)被兩次遍歷就存在回路。

12.下列選項(xiàng)中，不是如下有向圖的拓?fù)湫蛄械氖牵?br />

A.1, 5, 2, 3, 6, 4
B.5, 1, 2, 6, 3, 4
C.5, 1, 2, 3, 6, 4
D.5, 2, 1, 6, 3, 4

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法（周测7-拓扑排序和AOV网络）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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