高級(jí)中學(xué)信息技術(shù)填空題每日一練(2018.10.22)

來源：考試資料網(wǎng)

1.填空題用回溯法解問題時(shí)，應(yīng)明確定義問題的解空間，問題的解空間至少應(yīng)包含（）。

2.填空題用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h（n），則回溯法所需的計(jì)算空間通常為（）

參考答案：O(h(n))

3.填空題若序列X={B，C，A，D，B，C，D}，Y={A，C，B，A，B，D，C，D}，請(qǐng)給出序列X和Y的一個(gè)最長公共子序列：（）

參考答案：{B，A，B，C，D}或{C，A，B，C，D}或{C，A，D，C，D｝

4.填空題回溯法是指（）。

參考答案：具有限界函數(shù)的深度優(yōu)先生成法

5.填空題用回溯法解批處理作業(yè)調(diào)度問題時(shí)，該問題的解空間結(jié)構(gòu)為（）結(jié)構(gòu)。

參考答案：排列樹