算法分析與設計期末試題答案2011-c

1、。裝。訂。線。2011 年2012 年第 一 學期算法分析與設計期末試卷C 卷時間共 120 分鐘一、（10 分）算法？算法有哪些基本特征？請算法同程序的相同點與不同點。解: 算法是解決問題的方法或過程，是滿足以下四個性質(zhì)的指令序列1）輸入：有0 個以上的輸入2）輸出：至少有 1 個輸出3）確定性：指令清晰、無歧義4）有限性：指令執(zhí)行次數(shù)有限，時間有限算法和程序的相同點：兩者都具有輸入、輸出和確定性的特征不同點：程序是算法用某種程序語言的具體實現(xiàn)，程序不滿足算法具有的有限性性質(zhì)二、（10 分）設某個算法的運行時間 T(n)滿足如下遞歸方程：n 1T (n) O(1)2T (n / 2) O(n

2、) n 1.則該算法的時間復雜性是什么？解：T(n)=O(nlogn).三、（10 分）已知 A (a(k ) )，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求kijri *ri1矩陣鏈積 A1A2A3A4A5A6 的最佳求積順序。（要求：給出計算步驟）解：使用動態(tài)規(guī)劃算法進行求解。第 1 頁 共 4 頁得分閱卷人得分閱卷人得分閱卷人題號12345678910總分得分閱卷人求解矩陣為：因此，最佳乘積序列為（A1A2）（A3A4）（A5A6），共執(zhí)行乘法 2010 次。四、（10 分）請問二分搜索算法、快速排序算法、線性時間選擇算法和

3、最近點對問題的時間復雜性各為多少？解:二分搜索算法：情況 O(logn)、快速排序算法:情況 O(n2)，最好情況和平均情況均為 O(nlogn)線性時間選擇算法:情況 O(n)最近點對問題:時間復雜性 O(nlogn)五、（15 分）分治算法和動態(tài)規(guī)劃算法都是通過對問題進行分解，通過對子問題的求解然后進行解重構，從而實現(xiàn)對原問題的求解。請這兩種算法在對問題進行分解時各自所遵循的原則。解：分治算法對問題進行分解時所遵循的原則是將待求解問題分解為若干個規(guī)模較小、相互獨立且與原問題相同的子問題（不包含公共的子問題）。動態(tài)規(guī)劃對問題進行分解時所遵循的原則是將待求解問題分解為若干個規(guī)模較小、相互關聯(lián)的

4、與原問題類似的子問題（包含公共的子問題），采用表的方法來保存所有已解決問題的，而在需要的時候再找出已求得的，避免大量的重復計算。第 2頁 共 4 頁得分閱卷人得分閱卷人1234561012242202222303444044505601234561015033040516552010六、（15 分）貪心算法的設計是什么，特點？如果一個問題用貪心算法可以獲得全局最優(yōu)解，那么該問題的求解應滿足哪些條件？解：貪心算法的設計是在對問題求解時，總是做出在當前看來是最好的選擇。它的特點是 1）不是從整體考慮得到的解可能不是全局最優(yōu) 2）簡單，直接，易理解，效率高。如使用貪心算法求解問題獲得全局最優(yōu)解，則問

5、題應滿足1）貪心選擇性質(zhì)（與動態(tài)規(guī)劃的主要區(qū)別）所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇（即貪心選擇）來達到2）最優(yōu)子結構性質(zhì)（動態(tài)規(guī)劃算法和貪心算法的共同點）一個問題的最優(yōu)解包含其子問題的最優(yōu)解時。七、（15 分）請簡要描述回溯法的實現(xiàn)過程。用回溯法求解 0/1 背包問題、TSP 問題、N 皇后問題時，其各自的解空間樹各是什么形式？解：實現(xiàn)過程：確定解空間的組織結構，然后從開始結點（根結點）出發(fā)，以深度優(yōu)先方式搜索整個解空間。這個開始結點成為活結點，同時也成為當前的擴展結點。在當前擴展結點處，搜索向縱深方向移至一個新結點。這個新結點成為新的活結點，并成為擴展結點。否則如果在當前擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。此時，應往回移動（回溯）到最近的活結點處，并使該結點成為當前的擴展結點?；厮莘ò瓷鲜龇绞竭f歸地在解空間中搜索，直到找到所要求的解或解空間中以無活結點為止。0/1 背包：n+1 層的子集樹TSP 問題：(n-1)!個葉節(jié)點的排列樹N 皇后問題：完全