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

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

2、) n 1.則該算法的時間復(fù)雜性是什么？解：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ī)劃算法進(jìn)行求解。第 1 頁 共 4 頁得分閱卷人得分閱卷人得分閱卷人題號12345678910總分得分閱卷人求解矩陣為：因此，最佳乘積序列為（A1A2）（A3A4）（A5A6），共執(zhí)行乘法 2010 次。四、（10 分）請問二分搜索算法、快速排序算法、線性時間選擇算法和

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

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

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