《計算機算法基礎》試題及答案「完整版」

《計算機算法基礎》試題及答案【完整版】

一、填空題（每空1分，共35分）

1、算法是指_解決問題的一種方法或一個過程_，更嚴格地講，算法是____由若干條指令組成的有窮序列__，且滿足下述4條性質：_輸入、
輸出、  確定性、 有限性 。

2、算法的時間復雜性是指______需要時間的量_____，它依賴于求解問題的  要解的問題的規(guī)模、 算法的輸入、  算法本身的函數(shù)_____。

4、選擇算法的一個重要準則是____復雜性最低____。

5、一個___直接或間接地調用身____的算法稱為遞歸算法，一個___使用函數(shù)自身定義___的函數(shù)稱為遞歸函數(shù)，每個遞歸函數(shù)都必須有____非遞歸定的___的初始值。

6、關于N個字符的哈夫曼算法的計算時間為_____O（nlog n）___。

7、回溯法解題時常遇到的兩類典型解空間樹是：a：____排列樹____、b：___子集樹_____，若問題有N個元素，其中樹通常有__a __ 2ⁿ __個葉結點，其結點總個數(shù)為____n！_2^(n +1)-1___，遍歷它的任何算法均需____Ω（n！）__  Ω（2ⁿ）__的計算時間。

8、一個問題能用動態(tài)規(guī)劃算法求解的兩個重要特征是_____最優(yōu)子結構______和_____計算重要性______。

9、回溯法是一個既帶有系統(tǒng)性又帶有_____跳躍性______的搜索算法。它按照____深度優(yōu)先用約束函數(shù)在擴展結點處剪去不滿足約束的子樹、用限界函數(shù)剪去不能得到最優(yōu)解的子樹_______優(yōu)先的策略對空間樹進行搜索，通常采用如下兩種策略來避免無效搜索，提高回溯法的搜索效，其一是_____剪枝函數(shù)______，其二是____遞歸回溯_______，這兩類函數(shù)統(tǒng)稱為______選代回溯_____。

10、分支限界法最常見的兩種方式分別是_____ 隊列式（FIFO）分支限界法______和_____優(yōu)先隊列式分支限界法______。

11、概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法，求解兩次可能得到___完全不同的效果___。

二、判斷題（下列各題，你認為正確的，請在題干的括號內打“√”、錯誤的打“×”，每題2分，共8分）

1、貪心算法的核心是排序（  ×  ）

2、貪心算法對所有問題都能得到整體最優(yōu)解（ √   ）

3、0/1背包問題和背包問題都可以用貪心法求解 （ ×   ）

4、概率算法在執(zhí)行過程中每一計算步驟都是確定的（ ×   ）

三、簡答題（每小題5分，共35分）

1、為什么分治法與遞歸像一對孿生兄弟，經常同時應用在算法設計中？

答：因為分治法對原問題分小之后的子問題與原問題在特性上保持一致，只是規(guī)�？s小，這正好符合遞歸函數(shù)的性質。5分

2、敘述回溯法解題通常的三個步驟。

① 針對所給問題，定義問題的解空間

② 確定易于搜索的解空間結構

③ 以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索3分

3、敘述回溯法與分支限界算法的異同之處。

都是在問題的狀態(tài)空間樹上搜索解，但求解目標不同；回溯法只通過約束條件，而分支限界法不僅通過約束條件，而且通過目標函數(shù)的限界來減少無效搜索，回溯法采用深度優(yōu)先策略，而分支限界法采用先廣后深的策略。

4、敘述分支限界算法的分支和限界的涵意。

分支：剪去不何能產生最優(yōu)答案結點

限界：包括上界函數(shù)U和下界函數(shù)C*(X

所有C*(X)>U的結點被殺死

5、解釋什么是活結點，擴展結點，死結點？

活結點：被激活后還未完全生成其兒子結點的結點

擴展結點：當前正在生成其兒子結點的結點

死結點：已生成完其兒子結點的結點

6、說出優(yōu)先隊列式分支限界法解題的具體步驟。

① 針對所給問題，定義問題的解空間

② 定義上界和下界

③ 以先廣后深的方式搜索狀態(tài)空間樹，并且在搜索過程中用剪枝函數(shù)避免無效搜索

7、說出教材中所介紹的五種主要算法，并對每一種算法舉出一個典型。求解的例子（不必寫出每種具體解法過程）。

分治法、動態(tài)規(guī)劃、貪心法、回溯法、分支限界法

四、計算題（每小題10分，共20分）

（1，1，0，0，1）、（1，0，1，1）、（0，0，1，0，0，1）

分別對應于：5+10+15=30    5+12+13=30    12+18=30

實際生成的狀態(tài)空間樹

2、某公司訂購4箱海鮮品，分配給下屬的Ⅰ，Ⅱ，Ⅲ三個門市部，各門市部獲得海鮮品后的盈利如表所示。試用動態(tài)規(guī)劃求解，如何分配海鮮品，才能獲得最大利潤？（要寫出詳細的步驟）。

【《計算機算法基礎》試題及答案「完整版」】相關文章：

《計算機導論》試題及答案完整版04-21

算法分析設計相關試題及答案04-02

微波技術基礎試題及答案04-02

最優(yōu)化理論與算法試題及參考答案04-02

程序設計基礎試題及答案04-02

java基礎面試題及答案04-05

《園林工程》試題及答案「完整版」04-21

大學《管理學基礎》試題及答案04-02

《管理學基礎》模擬試題及答案04-01