1方篮、對下圖進(jìn)行拓?fù)渑判蛴欣拢傻貌煌負(fù)湫蛄械膫€數(shù)是（）象踊。
- A：4
- B：3
- C：2
- D：1
解析
可以得到3種不同的拓?fù)湫蛄校碼bced棚壁，abecd和aebcd杯矩。
答案：B
2、下列關(guān)于最小生成樹的敘述中袖外，正確的是（）菊碟。
Ⅰ、最小生成樹的代價唯一
Ⅱ在刺、所有權(quán)值最小的邊一定會出現(xiàn)在所有的最小生成樹中
Ⅲ逆害、使用Prim算法從不同頂點(diǎn)開始得到的最小生成樹一定相同
Ⅳ、使用Prim算法和Kruskal算法得到的最小生成樹總不相同
- A：僅Ⅰ
- B：僅Ⅱ
- C：僅Ⅰ蚣驼、Ⅲ
- D：僅Ⅱ魄幕、Ⅳ
解析
最小生成樹的樹形可能不唯一（因?yàn)榭赡艽嬖跈?quán)值相同的邊），但代價一定是唯一的颖杏，Ⅰ正確纯陨。
若權(quán)值最小的邊有多條并且構(gòu)成環(huán)狀，則總有權(quán)值最小的邊將不出現(xiàn)在某棵最小生成樹中留储，Ⅱ錯誤翼抠。
設(shè)N各結(jié)點(diǎn)構(gòu)成環(huán)，N-1條邊權(quán)值相等获讳，另一條邊權(quán)值較小阴颖，則從不同的頂點(diǎn)開始Prim算法會得到N-1種不同的最小生成樹，Ⅲ錯誤丐膝。
當(dāng)最小生成樹唯一時（各邊的權(quán)值不同）量愧，Prim算法和Kruskal算法得到的最小生成樹相同，Ⅳ錯誤帅矗。
答案：A
3偎肃、對下圖所示的有向帶權(quán)圖，若采用Dijkstra算法求從源點(diǎn)a到其他各頂點(diǎn)的最短路徑浑此，則得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b累颂，第二條最短路徑的目標(biāo)頂點(diǎn)是c，后續(xù)得到的其余各最短路徑的目標(biāo)頂點(diǎn)依次是（）凛俱。
- A：d,e,f
- B：e,d,f
- C：f,d,e
- D：f,e,d
解析
從a到各頂點(diǎn)的最短路徑的求解過程如下：
后續(xù)目標(biāo)頂點(diǎn)依次為f,d,e紊馏。
答案：C
4料饥、下列AOE網(wǎng)表示一項(xiàng)包含8個活動的工程，通過同時加快若干活動的進(jìn)度可以縮短整個工程的工期瘦棋。下列選項(xiàng)中，加快其進(jìn)度就可以縮短工程工期的是（）暖哨。
- A：c和e
- B：d和c
- C：f和d
- D：f和h
解析
找出AOE網(wǎng)的全部關(guān)鍵路徑為bdcg赌朋、bdeh和bfh。根據(jù)定義篇裁，只有關(guān)鍵路徑上的活動時間同時減少時沛慢，才能縮短工期。選項(xiàng)A达布、B和D并不包括在所有的關(guān)鍵路徑中团甲，只有C包含，因此只有加快f和d的進(jìn)度才能縮短工期黍聂。
答案：C
5躺苦、對下圖所示的有向圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)湫蛄锌赡苁牵ǎ?/h3>
![]()
在這里插入圖片描述
- A：3,1,2,4,5,6
- B：3,1,2,4,6,5
- C：3,1,4,2,5,6
- D：3,1,4,2,6,5
解析
按照拓?fù)渑判虻乃惴ú梗看味歼x擇入度為0的結(jié)點(diǎn)從圖中刪除匹厘，此圖中一開始只有結(jié)點(diǎn)3的入度為0；刪除結(jié)點(diǎn)3后脐区，只有結(jié)點(diǎn)1的入度為0愈诚；刪除結(jié)點(diǎn)1后，只有結(jié)點(diǎn)4的入度為0牛隅；刪除結(jié)點(diǎn)4后炕柔，結(jié)點(diǎn)2和結(jié)點(diǎn)6的入度都為0，此時選擇刪除不同的結(jié)點(diǎn)媒佣，會得出不同的拓?fù)湫蛄胸袄郏謩e處理完畢后可知可能的拓?fù)湫蛄袨?,1,4,2,6,5和3,1,4,6,2,5，選D默伍。
答案：D
6哩罪、若對n個頂點(diǎn)、e條弧的有向圖采用鄰接表存儲巡验，則拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度是（）际插。
- A：O(n)
- B：O(n+e)
- C：O(
)
- D：O(ne)
解析
采用鄰接表作為AOV網(wǎng)的存儲結(jié)構(gòu)進(jìn)行拓?fù)渑判颍枰獙個頂點(diǎn)做進(jìn)棧显设、出棧框弛、輸出各一次，在處理e條邊時捕捂，需要檢測這n個頂點(diǎn)的邊鏈表的e個邊結(jié)點(diǎn)瑟枫，共需要的時間代價為O(n+e)斗搞。若采用鄰接矩陣作為AOV網(wǎng)的存儲結(jié)構(gòu)進(jìn)行拓?fù)渑判颍谔幚韊條邊時需對每個頂點(diǎn)檢測相應(yīng)矩陣中的某一行慷妙，尋找與它相關(guān)聯(lián)的邊僻焚，以便對這些邊的入度減1，需要的時間代價為O()膝擂。
答案：B
7虑啤、使用Dijkstra算法求下圖中從頂點(diǎn)1到其余各頂點(diǎn)的最短路徑，將當(dāng)前找到的從頂點(diǎn)1到頂點(diǎn)2架馋，3狞山，4，5的最短路徑長度保存在數(shù)組dist中叉寂，求出第二條最短路徑后萍启，dist中的內(nèi)容更新為（）。
- A：26屏鳍，3勘纯，14，6
- B：25钓瞭，3屡律，14，6
- C：21降淮，3超埋，14，6
- D：15佳鳖，3霍殴，14，6
解析
在執(zhí)行Dijkstra算法時系吩，首先初始化dist[]来庭，若頂點(diǎn)1到頂點(diǎn)i（i=2，3穿挨，4月弛，5）有邊，就初始化為邊的權(quán)值：若無邊科盛，就初始化為∞帽衙；初始化頂點(diǎn)集S只含頂點(diǎn)1.Dijkstra算法每次選擇一個到頂點(diǎn)1距離最近的頂點(diǎn)j加入頂點(diǎn)集S，并判斷由頂點(diǎn)1繞行頂點(diǎn)j后到任一頂點(diǎn)k是否距離更短贞绵，若距離更短（即dist[j] + arcs[j][k] < dist[k]）厉萝，則將dist[x]更新為dist[j]+arcs[j][k]；重復(fù)該過程，直至所有頂點(diǎn)都加入頂點(diǎn)集S谴垫。數(shù)組dist的變化過程如下圖所示章母，可知將第二個頂點(diǎn)5加入頂點(diǎn)集S后，數(shù)組dist更新為21翩剪，3乳怎，14，6前弯，故選C蚪缀。
答案：C
8、評價算法的標(biāo)準(zhǔn)包括如下幾方面：正確性博杖、____椿胯、健壯性筷登、高效率及低存儲量剃根。
- A： 可靠性
- B：可行性
- C：可讀性
- D：可能性
解析
算法設(shè)計的要求：
- 正確性
- 可讀性
- 健壯性
- 效率與低存儲量
答案：C
9、一個有n個結(jié)點(diǎn)的圖前方，最少有____個連通分量狈醉。
- A：0
- B：1
- C：n-1
- D：n
解析
最少是1個，這種情況下惠险，它本身就是一個連通圖苗傅；
最多是n個，這種情況下班巩，它由n個分散的點(diǎn)組成的一個圖渣慕。
答案：B
10、對{05抱慌，46逊桦，13，55抑进，94强经，17，42}進(jìn)行基數(shù)排序寺渗，一趟排序的結(jié)果是____匿情。
- A：05，46信殊，13炬称，55，94涡拘，17转砖，42
- B：05，13，17府蔗，42晋控，46，55姓赤，94
- C：42赡译，13，94不铆，05蝌焚，55，46誓斥，17
- D：05只洒，13，46劳坑，55毕谴，17，42距芬，94
解析
按照基數(shù)排序：
- （1）先按個位數(shù)數(shù)字涝开，一次放入對應(yīng)的桶，取出的結(jié)果為：42框仔，13舀武，94，05离斩，55银舱，46，17
- （2）再按十位數(shù)字跛梗，依次放入對應(yīng)的桶寻馏，取出的結(jié)果為：05，13茄袖，17操软，42，46宪祥，55聂薪，94
但題目中問的是一趟排序后的結(jié)果，所以選C蝗羊。
