計(jì)算機(jī)軟考：軟件設(shè)計(jì)師練習(xí)試題及答案解析(6)

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

　　(86) A.3

　　B.4

　　C.6

　　D.8

　　參考答案：(86)A。

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

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

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

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

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

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

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

　　參考答案：(87)B。

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

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

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

　　圖9

　　(88) A.歐拉路徑

　　B.歐拉回路

　　C.歐密爾頓路徑

　　D.哈密爾頓回路

　　參考答案：(88)B。

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

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

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

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

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

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