計算機軟考：軟件設(shè)計師練習試題及答案解析(5)

　　81. 利用逐點插入建立序列(52,43,73,88,76,18,38,61,45,39)對應(yīng)的二叉排序樹之后，查找元素61要進行 (86) 次元素間的比較。

　　(86) A.3

　　B.4

　　C.6

　　D.8

　　參考答案：(86)A。

　　解析：利用逐點插入建立二叉排序樹是從空樹開始，通過查找將每個節(jié)點作為一個葉子插入。建立序列(50,72,43,85,75,20,35,45,65,30)的二叉排序樹如圖8所示。

　　根據(jù)圖8所示的二叉排序樹可知，查找元素61要進行3次元素間的比較。

　　82. 為了在狀態(tài)空間樹中 (87) ，可以利用LC-檢索(Least Cost Search)快速找到一個答案節(jié)點。

　　(87) A.進行遍歷

　　B.找出最優(yōu)的答案節(jié)點

　　C.找出任一個答案節(jié)點

　　D.找出所有的答案節(jié)點

　　參考答案：(87)B。

　　解析：在狀態(tài)空間樹中，定義 為節(jié)點的成本函數(shù)，g(X)為從節(jié)點向X到達一個答案節(jié)點所需做的附加工作的估計函數(shù)，h(X)為從根節(jié)點到節(jié)點X的成本，則用成本估計函數(shù) 選擇下一個E-節(jié)點的檢索策略總是選取 值最小的活節(jié)點作為下一個E-節(jié)點，因此這種檢索策略稱為最小成本檢索，簡稱LC-檢索(Least Cost Search)。

　　在狀態(tài)空間樹中找出最優(yōu)的答案節(jié)點，就可以利用LC-檢索快速找到一個答案節(jié)點。根據(jù)定義在進行LC-檢索時，為避免算法過分偏向于做縱深檢查，應(yīng)該在成本估計函數(shù) 中考慮根節(jié)點到當前節(jié)點的成本(距離)。

　　83. 圖9中不存在 (88) 。

　　圖9

　　(88) A.歐拉路徑

　　B.歐拉回路

　　C.歐密爾頓路徑

　　D.哈密爾頓回路

　　參考答案：(88)B。

　　解析：通過連通圖G中每條邊一次且僅一次，遍歷圖中所有節(jié)點的回路稱為歐拉回路。

　　通過連通圖G中每條邊一次且僅一次，遍歷圖中所有節(jié)點的開路稱為歐拉開路(歐拉路徑)。

　　若G是連通圖，則存在歐拉回路的充要條件是所有節(jié)點的度數(shù)均為偶數(shù)度;存在歐拉開路的充要條件是當且僅當G中有且只有兩個節(jié)點的度數(shù)為奇數(shù)度。

　　由于圖3-6中有兩個節(jié)點的度數(shù)是奇數(shù)度，因此圖3-6中只存在歐拉路徑，但不符合歐拉回路的充要條件，即不存在歐拉回路。

　　通過連通圖G中每個節(jié)點一次且僅一次的回路稱為歐密爾頓回路。

　　通過連通圖G中每個節(jié)點一次且僅一次的開路稱為歐密爾頓開路(哈密爾頓路徑)。

　　84. 在最好和最壞情況下的時間復雜度均為O(nlogn)，但不穩(wěn)定的排序算法是 (89) 。

　　(89) A.堆排序

　　B.快速排序

　　C.歸并排序

　　D.基數(shù)排序

　　參考答案：(89)A。

　　解析：堆排序在最好和最壞情況下的時間復雜度均為O(nlogn)但不穩(wěn)定。

　　快速排序最好和最壞情況下的時間復雜度分別為O(n2)和O(nlogn)且不穩(wěn)定。

　　歸并排序是在最好和最壞情況下的時間復雜度均為O(nlogn)且穩(wěn)定的排序方法。

　　基數(shù)排序在最好和最壞情況下的時間復雜度均為O(d(n+rd))。