算法分析與設(shè)計期末考試模擬試題三

1、PAGE 第7頁 （共7頁）算法分析與設(shè)計期末考試模擬試題三課程名稱：_ 算法分析與設(shè)計 考試形式： 閉 卷 學(xué)習(xí)中心：_ 考試時間： 90分鐘 姓 名：_ 學(xué) 號： 填空題（每小題4分，共計40分）1. 算法是滿足 、 、 和 等四個性質(zhì)的指令序列。2. 算法復(fù)雜性的高低體現(xiàn)在運行該算法所需的計算機資源的多少上，計算機的資源最重要的是 和 ，因此算法的復(fù)雜性有 和 之分。3.與分治法類似，動態(tài)規(guī)劃算法的基本思想是_，先求解_，然后從這些解得到原問題的解。與分治法不同的是，適合用動態(tài)規(guī)劃算法求解的問題，經(jīng)分解得到的子問題往往不是_的。4. Java語言的類(class)體現(xiàn)了抽象數(shù)據(jù)類型(AD

2、T)的思想，一般由4個部分組成： 、 、 和 。5. 抽象數(shù)據(jù)類型的英文簡稱是 ，它是算法的一個 _連同定義在該模型上并作為算法構(gòu)件的一組_ 。6. O(f)+O(g)= _，O(f)O(g)= 。7. 分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模_的相同問題 , 以便各個擊破，_。8. 動態(tài)規(guī)劃算法的第一步通常是刻畫最優(yōu)解的結(jié)構(gòu)。當(dāng)問題的最優(yōu)解包含了其_的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。9. 動態(tài)規(guī)劃算法與貪心算法的主要區(qū)別是_性質(zhì)。10.表示最優(yōu)前綴碼的二叉樹總是一顆 ，即樹中任一個結(jié)點都有兩個兒子結(jié)點。二、簡答題（每小題10分，共計40分）1. 請簡述為什么部分背

3、包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。2. 請寫出如圖語法樹所對應(yīng)的矩陣鏈相乘的最優(yōu)完全加括號方式。3. 按照下表中的字母出現(xiàn)頻率，請畫出哈夫曼樹，并設(shè)計相應(yīng)的哈夫曼編碼。 字母abcdef頻率(千次)4513121695哈夫曼編碼4. 請簡述動態(tài)規(guī)劃算法求解最優(yōu)化問題的步驟。三、算法分析和設(shè)計題（每小題10分，共計20分）1. 請寫出階乘函數(shù)的遞歸定義式及其簡要遞歸算法。2. 給定圖G=(V,E)，其中，頂點集為V=1,2,3,4,5,6，邊集和每條邊的權(quán)如圖所示。用Prim算法求該圖的最小生成樹(畫圖說明算法的求解過程)。用Kruskal算法求最小生成樹(畫圖說明

4、算法的求解過程)。算法分析與設(shè)計模擬試題三答案一、填空題答案（每小題4分，共計40分）1. 輸入、輸出、確定性、有限性2. 時間、空間（即存儲器）、時間復(fù)雜性、空間復(fù)雜性3. 將待求解問題分解為若干個子問題、子問題、互相獨立4. 類名、數(shù)據(jù)成員、方法、訪問修飾5. ADT、數(shù)據(jù)模型、運算6. O(f+g)、O(fg)7. 較小、分而治之8. 子問題9. 貪心選擇性質(zhì)10. 完全二叉樹。二、簡答題答案（每小題10分，共計40分）1.對于部分背包問題，依照貪心選擇策略，可以得到最優(yōu)解。而0-1背包問題，貪心選擇之所以不能得到最優(yōu)解，是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間

5、使每公斤背包空間的價值降低了。因而我們選擇的判斷標準出現(xiàn)了誤差。2. 相應(yīng)的矩陣鏈相乘的最優(yōu)完全加括號方式為(A1(A2A3)(A4(A5A6)3. 哈夫曼樹哈夫曼編碼：字母abcdef頻率(千次)4513121695哈夫曼編碼0101100111110111004. 可以按以下步驟來設(shè)計動態(tài)規(guī)劃算法： （1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征； （2）遞歸地定義最優(yōu)值； （3）以自底向上的方式計算出最優(yōu)值； （4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。三、算法分析和設(shè)計題答案（每小題10分，共計20分）1. 階乘n!的遞歸定義式是： n!可以遞歸計算如下:public static int factorial(int n)if( n