算法設計與分析試題答案

1、算法設計與分析試題（三合一）答案算法分析與設計模擬試題一答案一、填空題答案 （每小題 4 分，共計 40 分）1. 最壞、最好、平均、最壞2. O（n2）、O（log n）3. 常數(shù)因子4. 直接或間接地調用自身、用函數(shù)自身給出定義5. 最好、局部最優(yōu)選擇6. 貪心選擇性質、最優(yōu)子結構性質7. 貪心算法、動態(tài)規(guī)劃算法8. 較小、互相獨立、相同、合并9. 最優(yōu)子結構（性質） 、子問題重疊（性質）10. 動態(tài)規(guī)劃算法、貪心算法。二、簡答題答案 （每小題 10 分，共計 40 分）1. 如果只需要求解問題的最優(yōu)值，動態(tài)規(guī)劃算法步驟如下：（1）找出最優(yōu)解的性質，并刻畫其結構特征；（2）遞歸地定義最優(yōu)值

2、；（3）以自底向上的方式計算出最優(yōu)值；如果需要構造最優(yōu)解，則還需要加上如下步驟：（ 4）根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。2. 所謂貪心選擇性質是指，所求問題的全局最優(yōu)解可以通過一系列局部最優(yōu)選擇，即貪心選擇來達到。3. 如果G的子圖G'是一棵包含 G的所有頂點的樹，則稱 G'為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費。在 G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。4. 動態(tài)規(guī)劃算法需要知道所有子問題的解，而貪心算法不需要知道所有子問題的解，它只是在每一步迭代中選擇看起來最好的解，并不從整體進行最優(yōu)考慮，因此效率較高。三、算法分析和設計題答案 （每小

3、題 10 分，共計 20 分）1. 漢諾塔問題的遞歸算法如下 :public static void Hanoi（int n, int a, int b, int c）if（ n>0 ）Hanoi（ n-1, a,c,b ）;Move（ a, b ）;Hanoi（ n-1, c,b,a ）；2. 算法如下：輸入：正整數(shù)n和存儲n個元素的數(shù)組a1.n,被搜索的元素x輸岀：若x在數(shù)組中則返回其下標否則返回0i=binarysearch(1,n,a,x);return I;end BINARYSEARCH1過程 binarysearch(low,high,a,x)/在數(shù)組a的下標為low到hi

4、gh范圍內尋找x,/若找到x則返回其下標否則返回0if low>high thenreturn 0;elsemid= (low high)/2 ;if amid=x thenreturn mid;else if amid<x thenreturn binarysearch(low,mid-1,a,x);else return binarysearch(mid+1,high,a,x);end ifend if算法分析與設計模擬試題二答案一、 填空題答案(每小題4分，共計40分)1. 程序設計語言、有限性2. 最壞3. 遞歸算法、遞歸函數(shù)4. 貪心算法、動態(tài)規(guī)劃算法5. 。(n?)、o

5、(C)6. log n、20n、5n2、n37. 分治策略、已排好序、O(log n)、O(n)8. 最優(yōu)子結構(性質)、子問題重疊(性質)9. 自頂向下、自底向上10. 貪心算法、動態(tài)規(guī)劃算法。二、 簡答題答案(每小題10分，共計40分)1. 分治算法的一般步驟：分解-直接或遞歸求解子問題-組合遞歸方程分治算法的時間復雜性 C(n)往往滿足如下的遞歸方程：C(n) d, n n0C(n) aC(n c) g(n) , n n°其中， n: 問題的規(guī)模。n0: 可直接解的問題規(guī)模的閾值。a: 分解出的需要求解的子問題的個數(shù)。n/c: 分解出的子問題的規(guī)模。g(n): 分解規(guī)模為 n

6、的問題以及組合相應子問題的解 所需的時間。d: 直接解規(guī)模為 n0 的問題所需的時間。2. 0-1 背包問題的形式化描述是：給定 C 0,wi 0,vi 0,1 i n,要求找出 n元0 1 向量(xx2,.,xn), x 0,1,nn使得wixiC,而且vx達到最大。i 1i 13. 貪心算法的簡要求解步驟如下： 將優(yōu)化問題轉化成這樣的一個問題，即先做出選擇，再解決剩下的一個子問題。 證明原問題總是有一個最優(yōu)解是做貪心選擇得到的，從而說明貪心選擇的安全性。 說明在做出貪心選擇后，剩余的子問題具有這樣的一個性質，即如果將子問題的最優(yōu)解和我們所 做的貪心選擇聯(lián)合起來，可以得出原問題的一個最優(yōu)解。

7、4. 歸并排序的基本思想是：將待排序的序列分成長度大致相等的兩個子序列， 分別對 2 個子序列進行排序， 最終將 2個已排好序的 子序列合并為有序的完整序列。三、算法分析和設計題答案 (每小題 10 分，共計 20 分)1. Fibonacci 數(shù)列的遞歸定義式是：1當 n 0,1F(n)F(n 1) F(n 2)當n 1第 n 個 Fibonacci 數(shù)可以遞歸計算如下 :public static int Fibonacci(int n)if( n<=1 ) return 1;return Fibonacci(n-1) + Fibonacci(n-2) ;2. 二分搜索算法的 jav

8、a 語言描述如下：public static int BinarySearch(int a, int x, int n)int left=0; int right=n-1;while(left<=right) int middle = (left+right)/2; if(x=amiddle) return middle;if(x>amiddle)left = middle+1;Else right = middle-1;return -1;算法分析與設計模擬試題三答案一、填空題答案(每小題4分，共計40分)1. 輸入、輸岀、確定性、有限性2. 時間、空間(即存儲器)、時間復雜性、

9、空間復雜性3. 將待求解問題分解為若干個子問題、子問題、互相獨立4. 類名、數(shù)據(jù)成員、方法、訪問修飾5. ADT、數(shù)據(jù)模型、運算6. O(f+g)、O(fg)7. 較小、分而治之8. 子問題9. 貪心選擇性質10. 完全二叉樹。二、簡答題答案(每小題10分，共計40分)1. 對于部分背包問題，依照貪心選擇策略，可以得到最優(yōu)解。而0-1背包問題，貪心選擇之所以不能得到最優(yōu)解，是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間 的價值降低了。因而我們選擇的判斷標準岀現(xiàn)了誤差。2. 相應的矩陣鏈相乘的最優(yōu)完全加括號方式為(A1(A2A3)(A4(A5A6)3. 哈夫曼樹哈夫曼編碼:字母abcdef頻率仟次)4513121695哈夫曼編碼0101100111110111004. 可以按以下步驟來設計動態(tài)規(guī)劃算法：（1）找岀最優(yōu)解的性質，并刻畫其結構特征；（2）遞歸地定義最優(yōu)值；（3）以自底向上的方式計算出最優(yōu)值；（4）根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。三、算法分析和設計題答案（每小題10分，共計20分）1.階乘n!的遞歸定義式是：1n0n!n(n1)! n0n!可以遞