2010軟考軟件設計師考前練習試題及答案解析(1)

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

　　(86) A.3

　　B.4

　　C.6

　　D.8

　　參考答案：(86)A。

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

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

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

　　(87) A.進(jìn)行遍歷

　　B.找出最優(yōu)的答案節點(diǎn)

　　C.找出任一個(gè)答案節點(diǎn)

　　D.找出所有的答案節點(diǎn)

　　參考答案：(87)B。

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

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

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

　　圖9

　　(88) A.歐拉路徑

　　B.歐拉回路

　　C.歐密爾頓路徑

　　D.哈密爾頓回路

　　參考答案：(88)B。

　　解析：通過(guò)連通圖G中每條邊一次且僅一次，遍歷圖中所有節點(diǎn)的回路稱(chēng)為歐拉回路。

　　通過(guò)連通圖G中每條邊一次且僅一次，遍歷圖中所有節點(diǎn)的開(kāi)路稱(chēng)為歐拉開(kāi)路(歐拉路徑)。

　　若G是連通圖，則存在歐拉回路的充要條件是所有節點(diǎn)的度數均為偶數度;存在歐拉開(kāi)路的充要條件是當且僅當G中有且只有兩個(gè)節點(diǎn)的度數為奇數度。

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

　　通過(guò)連通圖G中每個(gè)節點(diǎn)一次且僅一次的回路稱(chēng)為歐密爾頓回路。

　　通過(guò)連通圖G中每個(gè)節點(diǎn)一次且僅一次的開(kāi)路稱(chēng)為歐密爾頓開(kāi)路(哈密爾頓路徑)。