1捷兰、已知帶權(quán)連通無向圖G=（V，E）皆的，其中V={
悲敷，
,
,
,
,
,
}究恤，E={(,)10,(,)2,(,)2,(,)11,(,)1,(,)4,(,)6,(,)7,(,)3}（注：頂點(diǎn)偶對(duì)括號(hào)外的數(shù)據(jù)表示邊上的權(quán)值）俭令，從源點(diǎn)到頂點(diǎn)的最短路徑上經(jīng)過的頂點(diǎn)序列是（）后德。
- A：
- B：
- C：
- D：
解析
題干內(nèi)容所述的圖G如上圖所示。A抄腔，B瓢湃，C，D對(duì)應(yīng)的路徑長度分別為18赫蛇，13绵患，15，24悟耘。應(yīng)用Dijkstra算法求出最短路徑為B所示路徑落蝙。
答案：B
2、下面的（）方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）暂幼。
Ⅰ筏勒、深度優(yōu)先遍歷
Ⅱ、拓?fù)渑判?br>
Ⅲ旺嬉、求最短路徑
Ⅳ管行、求關(guān)鍵路徑
- A：Ⅰ、Ⅱ邪媳、Ⅳ
- B：Ⅰ捐顷、Ⅲ、Ⅳ
- C：Ⅰ雨效、Ⅱ迅涮、Ⅲ
- D：全部可以
解析
使用深度優(yōu)先遍歷，若從有向圖上的某個(gè)頂點(diǎn)u出發(fā)徽龟，在DFS(u)結(jié)束之前出現(xiàn)一條從頂點(diǎn)v到u的邊叮姑，由于v在生成樹上是u的子孫，則圖中必定存在包含u和v的環(huán)顿肺，因此深度優(yōu)先遍歷可以檢測一個(gè)有向圖是否有環(huán)戏溺。
拓?fù)渑判驎r(shí)，當(dāng)某頂點(diǎn)不為任何邊的頭時(shí)才能加入序列屠尊，存在環(huán)時(shí)環(huán)中的頂點(diǎn)一直是某條邊的頭旷祸，不能加入拓?fù)湫蛄小Ｒ簿褪钦f讼昆，還存在無法找到下一個(gè)可以加入拓?fù)湫蛄械捻旤c(diǎn)托享，則說明此圖存在回路。
求最短路徑是允許圖有環(huán)的。
關(guān)鍵路徑能否判斷一個(gè)圖有環(huán)闰围，則存在一些爭議赃绊。關(guān)鍵路徑本身雖然不允許有環(huán)，但求關(guān)鍵路徑的算法本身無法判斷是否有環(huán)羡榴，判斷是否有環(huán)是求關(guān)鍵路徑的第一步——拓?fù)渑判颉?/p>
答案：A
3碧查、若一個(gè)有向圖的頂點(diǎn)不能排在一個(gè)拓?fù)湫蛄兄校瑒t可判定該有向圖（）校仑。
- A：是一個(gè)有根的有向圖
- B：是一個(gè)強(qiáng)連通圖
- C：含有多個(gè)入度為0的頂點(diǎn)
- D：含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量
解析
若不存在拓?fù)渑判蛑沂郏瑒t表示圖中必定存在回路，該回路構(gòu)成一個(gè)強(qiáng)連通分量（頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量中必然存在回路）迄沫。
答案：D
4稻扬、以下關(guān)于拓?fù)渑判虻恼f法中，錯(cuò)誤的是（）羊瘩。
Ⅰ泰佳、若某有向圖存在環(huán)路，則該有向圖一定不存在拓?fù)渑判?br>
Ⅱ尘吗、在拓?fù)渑判蛩惴ㄖ袨闀捍嫒攵葹榱愕捻旤c(diǎn)逝她，可以使用棧，也可以使用隊(duì)列
Ⅲ摇予、若有向圖的拓?fù)溆行蛐蛄形ㄒ黄睿瑒t圖中每個(gè)頂點(diǎn)的入度和出度最多為1
- A：Ⅰ、Ⅲ
- B：Ⅱ侧戴、Ⅲ
- C：Ⅱ
- D：Ⅲ
解析
Ⅰ中宁昭，對(duì)于一個(gè)存在環(huán)路的有向圖，使用拓?fù)渑判蛩惴ㄟ\(yùn)行后酗宋，肯定會(huì)出現(xiàn)有環(huán)的子圖积仗，在此環(huán)中無法再找到入度為0的結(jié)點(diǎn)，拓?fù)渑判蛞簿瓦M(jìn)行不下去蜕猫。
Ⅱ中寂曹，注意，若兩個(gè)結(jié)點(diǎn)之間不存在祖先或子孫關(guān)系回右，則它們?cè)谕負(fù)湫蛄兄械年P(guān)系是任意的（即前后關(guān)系任意）隆圆，因此使用棧和隊(duì)列都可以，因?yàn)檫M(jìn)椣杷福或隊(duì)列的都是入度為0的結(jié)點(diǎn)渺氧，此時(shí)入度為0的所有結(jié)點(diǎn)是沒有關(guān)系的。
Ⅲ中蹬屹，若拓?fù)溆行蛐蛄形ㄒ宦卤常瑒t很自然地讓人聯(lián)想到一個(gè)線性的有向圖（錯(cuò)誤）白华，下圖的拓?fù)湫蛄幸彩俏ㄒ坏模葏s不滿足條件贩耐。
答案：D
5弧腥、若一個(gè)有向圖的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄校瑒t判定該有向圖（）潮太。
- A：含有多個(gè)出度為0的頂點(diǎn)
- B：是個(gè)強(qiáng)連通圖
- C：含有多個(gè)入度為0的頂點(diǎn)
- D：含有頂點(diǎn)數(shù)大于1的強(qiáng)連通分量
解析
一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄泄芴拢砻髌渲写嬖谝粋€(gè)頂點(diǎn)數(shù)目大于1的回路，該回路構(gòu)成一個(gè)強(qiáng)連通分量消别，從而答案選D抛蚤。
答案：D
6、下圖所示有向圖的所有拓?fù)湫蛄泄灿校ǎ﹤€(gè)寻狂。
- A：4
- B：6
- C：5
- D：7
解析
本圖的拓?fù)渑判蛐蛄杏蠥BCFDEG，ABCDFEG朋沮，ABCDEFG蛇券，ABDCFEG和ABDCEFG。
答案：C
7樊拓、若一個(gè)人有向圖具有有序的拓?fù)渑判蛐蛄芯姥牵瑒t它的鄰接矩陣必定為（）。
- A：對(duì)稱
- B：稀疏
- C：三角
- D：一般
解析
對(duì)有向圖中的頂點(diǎn)適當(dāng)?shù)鼐幪?hào)筋夏，使其鄰接矩陣為三角矩陣且主對(duì)角元素全為零的充分必要條件是蒂胞，該有向圖可以進(jìn)行拓?fù)渑判颉?/p>
若一個(gè)有向圖的鄰接矩陣為三角矩陣（對(duì)角線上元素為0），則圖中必不存在環(huán)条篷，因此其拓?fù)湫蛄斜厝淮嬖凇?/p>
答案：C
8骗随、下列關(guān)于圖的說法中，正確的是（）赴叹。
Ⅰ鸿染、有向圖中頂點(diǎn)V的度等于其鄰接矩陣中第V行中1的個(gè)數(shù)
Ⅱ紊选、無向圖的鄰接矩陣一定是對(duì)稱矩陣庆寺，有向圖的鄰接矩陣一定是非對(duì)稱矩陣
Ⅲ、在圖G的最小生成樹中津坑，某條邊的權(quán)值可能會(huì)超過未選邊的權(quán)值
Ⅳ绽媒、若有向無環(huán)圖的拓?fù)湫蛄形ㄒ徊隙瑒t可以唯一確定該圖
- A：Ⅰ、Ⅱ和Ⅲ
- B：Ⅲ和 Ⅳ
- C：Ⅲ
- D：Ⅳ
解析
有向圖鄰接矩陣的第V行中1的個(gè)數(shù)是頂點(diǎn)V的出度是辕，而有向圖中頂點(diǎn)的度為入度與出度之和囤热，Ⅰ錯(cuò)。
無向圖的鄰接矩陣一定是對(duì)稱矩陣免糕，但當(dāng)有向圖中任意兩個(gè)頂點(diǎn)之間有邊相連赢乓，且是兩條方向相反的有向邊（無向圖也可視為有兩條方向相反的有向邊的特殊有向圖）時(shí)忧侧，有向圖的鄰接矩陣也是一個(gè)對(duì)稱矩陣，Ⅱ錯(cuò)牌芋。
最小生成樹中的n-1條邊并不能保證是圖中權(quán)值最小的n-1條邊蚓炬，因?yàn)闄?quán)值最小的n-1條邊并不一定能使圖連通。在下圖中躺屁，左圖的最小生成樹如右圖所示肯夏，權(quán)值為3的邊并不在其最小生成樹中。
有向無環(huán)圖的拓?fù)湫蛄形ㄒ徊⒉荒芪ㄒ淮_定該圖犀暑。在下圖所示的兩個(gè)有向無環(huán)圖中驯击，拓?fù)湫蛄卸紴?img class="math-inline" src="https://math.jianshu.com/math?formula=V_1" alt="V_1" mathimg="1">，
答案：C
9暇矫、若某帶權(quán)圖為G=（V，E）择吊，其中V={,,,,,,,
,
,
}李根，E={<,>5,<,>6,<,>3,<,>6,<,>3,<,>3,<,>1,<,>4,<,>4,<,>2,<,>4,<,>5,<,>2,<,
>2}（注：邊括號(hào)外的數(shù)據(jù)表示邊上的權(quán)值），則G的關(guān)鍵路徑的長度為（）几睛。
- A：19
- B：20
- C：21
- D：22
解析
畫出題目所表示的圖如下房轿，可得到關(guān)鍵路徑的長度為21.圖中所示的兩條路徑都是關(guān)鍵路徑。
答案：C
10所森、下面關(guān)于求關(guān)鍵路徑的說法中囱持，不正確的是（）。
- A：求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的
- B：一個(gè)事件的最早發(fā)生時(shí)間與以該事件為始的弧的活動(dòng)的最早開始時(shí)間相同
- C：一個(gè)事件的最遲發(fā)生時(shí)間是以該事件為尾的弧的活動(dòng)的最遲開始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差
- D：關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上
解析
一個(gè)事件的最遲發(fā)生時(shí)間等于Min{以該事件為尾的弧的活動(dòng)的最遲開始時(shí)間必峰，最遲結(jié)束時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差}洪唐。
