計(jì)算機(jī)算法設(shè)計(jì)與分析期末復(fù)習(xí)資料

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一 填空題（20x1=20分）1. 當(dāng)設(shè)定的問題有多種算法去解決時(shí)，其選擇算法的主要原則是選擇其中復(fù)雜性最低者。2. 用函數(shù)自身給出定義的函數(shù)是一種遞歸函數(shù)。3. 動(dòng)態(tài)規(guī)劃算法適用于解最優(yōu)化問題。4. 貪心算法的兩個(gè)基本要素是最優(yōu)子結(jié)構(gòu)性質(zhì)、貪心選擇性質(zhì)。5. 回溯法在搜索解空間樹的時(shí)候，為了避免無效搜索，通常使用深度優(yōu)先手段來提高搜索效率。6. 依據(jù)求解目標(biāo)的不同，分支界限法和回溯法分別用廣度優(yōu)先遍歷或者最小耗費(fèi)優(yōu)先、深度優(yōu)先的方式搜索解空間樹。7. 分支界限法和回溯法主要區(qū)別在于求解目標(biāo)和搜索方式不同。8. 在分支界限法實(shí)現(xiàn)的時(shí)候，通常采用 方式來實(shí)現(xiàn)最大優(yōu)先隊(duì)列

2、。9. 依據(jù)求解所花費(fèi)的時(shí)間和所得到的結(jié)果不同，隨機(jī)化算法大致分為數(shù)值隨機(jī)化算法、蒙特卡羅算法、拉斯維加斯算法和舍伍德算法四類。10. 產(chǎn)生偽隨機(jī)數(shù)最常用的方法是線性同余法。11. 線性規(guī)劃算法中轉(zhuǎn)軸變化的目的是將入基變量與離基變量互調(diào)位置。12. 最大網(wǎng)絡(luò)流問題中可增廣路是殘留網(wǎng)絡(luò)中一條容量大于0的路。13. 待解決問題適用于動(dòng)態(tài)規(guī)劃法的兩個(gè)基本要素是 。14. 算法必須滿足的四個(gè)特征是輸入、輸出、確定性、有限性。15. 算法復(fù)雜性依賴于 、 、 三個(gè)方面的復(fù)雜因素。16. 實(shí)現(xiàn)遞歸調(diào)用的關(guān)鍵是 17. 動(dòng)態(tài)規(guī)劃算法求解問題的重要線索是問題的 性質(zhì)。18. 最優(yōu)子結(jié)構(gòu)性質(zhì)是貪心算法求解問題的

3、關(guān)鍵特征。19. 分支界限法的求解目標(biāo)是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。20. 問題的解空間樹常見的有子集樹、排列樹兩種類型。21. 分支界限算法依據(jù)其從和節(jié)點(diǎn)表中選擇獲得下一擴(kuò)展節(jié)點(diǎn)的不同方式被分為22. 對(duì)于任何約束標(biāo)準(zhǔn)型線性規(guī)劃問題，只要將所用分基本變量都設(shè)置為0，就可以獲得一個(gè) 解。二 判斷題（20x1=20分）1. 算法的描述方式有自然語言、程序語言，或者兩者相結(jié)合的形式。（ ）2. 算法滿足的特性有哪些，程序有什么特征，而這有什么關(guān)系。3. 算法復(fù)雜度越高或者越低與占用計(jì)算機(jī)資源的關(guān)系是什么。4. 算法復(fù)雜性上界的階，越高或者越低與結(jié)果的

4、準(zhǔn)確性和實(shí)際價(jià)值關(guān)系。5. 遞歸算法和非遞歸算法兩者之間的效率如何。6. 動(dòng)態(tài)規(guī)劃算法帶求解的問題是否可以用分支界限法、分治法、線性規(guī)劃法、回溯法等其他的算法求解。7. 動(dòng)態(tài)規(guī)劃算法帶求解的問題，經(jīng)分解得到的子問題，是獨(dú)立的還是不獨(dú)立的。8. 如果問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，請(qǐng)問這個(gè)問題使用動(dòng)態(tài)規(guī)劃法和貪心算法那個(gè)更好。9. 貪心算法在一般情況下，是否能夠得到整體最優(yōu)解，還是最優(yōu)解的近似值。10. 動(dòng)態(tài)規(guī)劃法和貪心算法，在求解問題的時(shí)候都是自頂向下的嗎？11. 請(qǐng)問對(duì)于待解決的問題，有“通用解題法”之稱的是什么算法？ 回溯法12. 回溯法是通過遍歷搜索樹找到問題的最優(yōu)解的嗎？13. 在分支界限法和

5、回溯法中，每個(gè)節(jié)點(diǎn)都有機(jī)會(huì)成為擴(kuò)展節(jié)點(diǎn)嗎？14. 對(duì)于待解決的同一個(gè)問題，隨機(jī)化算法與非隨機(jī)化算法，誰的復(fù)雜度高？誰的復(fù)雜度低？15. 數(shù)值化隨機(jī)算法用于求解問題的準(zhǔn)確解嗎？16. 蒙特卡羅算法是用于球問題的準(zhǔn)確解還是近似解，并且得到的解，一定是可靠的嗎？17. 舍伍德算法能夠得到問題的準(zhǔn)確解嗎？18. 二分搜索算法是那種算法的一種典型實(shí)例？ 分治法19. 矩陣連乘問題，最實(shí)用的算法是什么？20. 程序必須滿足算法的所有屬性嗎？21. 算法復(fù)雜性與計(jì)算機(jī)的本身資源有關(guān)嗎？22. 算法描述的方式除了自然語言、程序語言23. 算法復(fù)雜性的階越高越好嗎？24. 動(dòng)態(tài)規(guī)劃法和分治法一定要把求解的問題分

6、解成為若干個(gè)子問題嗎？25. 如果問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，貪心算法比其他的算法都要好嗎？三 概念題（6x2=12分）1. 算法復(fù)雜性：是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(fù)雜性，需要空間資源的量稱為空間復(fù)雜性。2. 遞歸算法：直接或間接地調(diào)用自身的算法稱為遞歸算法。3. 貪心算法：在對(duì)問題求解時(shí)，總是做出當(dāng)前看來是最好的選擇。也就是說，貪心算法并不從整體最優(yōu)考慮，他所做出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。4. 子集樹：當(dāng)所給問題是從n個(gè)元素的集合s中找出滿足某

7、種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹。5. 隊(duì)列式（FIFO）分支限界法：將活結(jié)點(diǎn)表組織成一個(gè)隊(duì)列，并按隊(duì)列的先進(jìn)先出原則選取下一個(gè)結(jié)點(diǎn)為當(dāng)前擴(kuò)展結(jié)點(diǎn)。6. 分治法：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。7. 算法：由若干條指令組成的有窮序列。8. 最優(yōu)子結(jié)構(gòu)：當(dāng)一個(gè)問題的最優(yōu)解包含了其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。9. 回溯法：以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。10. 排列樹：當(dāng)所給的問題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹稱為排列樹。11. 網(wǎng)絡(luò)流：是定義在網(wǎng)絡(luò)的邊集合E上的一個(gè)非負(fù)函數(shù)flow =

8、flow(v,w)，并稱flow(v,w)為邊（v,w）上的流量。四 簡(jiǎn)答題（3x4=12分）1. 在一個(gè)算法中調(diào)用另一個(gè)算法時(shí)，系統(tǒng)需在運(yùn)行被調(diào)用算法之前完成哪些工作？同時(shí)從被調(diào)用算法返回調(diào)用算法需完成哪些工作？答：在一個(gè)算法中調(diào)用另一算法時(shí)，系統(tǒng)需在運(yùn)行被調(diào)用算法之前先完成三件事：（1） 將所有實(shí)參指針、返回地址等信息傳遞給被調(diào)用算法；（2） 為被調(diào)用算法的局部變量分配存儲(chǔ)區(qū)；（3） 將控制轉(zhuǎn)移到被調(diào)用算法的入口。在從被調(diào)用算法返回調(diào)用算法時(shí)需完成三件事：（1） 保存被調(diào)用算法的計(jì)算結(jié)果；（2） 釋放分配給被調(diào)用算法的數(shù)據(jù)區(qū)；（3） 依照被調(diào)用算法保存的返回地址將控制轉(zhuǎn)移到調(diào)用算法。2.

9、動(dòng)態(tài)規(guī)劃算法求解問題的步驟？答：動(dòng)態(tài)規(guī)劃法適用于解最優(yōu)化問題。通?？梢园匆韵?個(gè)步驟設(shè)計(jì)：（1） 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；（2） 遞歸地定義最優(yōu)值；（3） 以自底向上的方式計(jì)算最優(yōu)值；（4） 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造最優(yōu)解。3. 線性規(guī)劃法中單純形算法的基本步驟？答：步驟一 選入基變量。步驟二 選離基變量。步驟三 做轉(zhuǎn)軸變換。步驟四 轉(zhuǎn)步驟一。4. 分治法的基本思想和原理是什么？答：分治法的基本思想是將一個(gè)規(guī)模為的問題分解為個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。5. 利用回溯法解決問題包含哪些步驟？答：

10、利用回溯法解題常包含以下3步驟：（1） 針對(duì)所給問題，定義問題的解空間；（2） 確定易于搜索的解空間結(jié)構(gòu)；（3） 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。五 分析題（36分）1求下列函數(shù)的漸進(jìn)表達(dá)式：3n2+10n; n2/10+2n; 21+1/n; logn3; 10log3n分析與解答：3n2+10n=O(n2); n2/10+2n=O(2n); 21+1/n=O(1); logn3=O(logn); 10log3n=O(n)2討論O(1)和O(2)的區(qū)別。分析與解答：根據(jù)符號(hào)O的定義易知O(1)=O(2)。用O(1)或O(2)表示同一個(gè)函數(shù)時(shí)，差別僅在于其中的常

11、數(shù)因子。3按漸近階排列表達(dá)式按照漸近階從低到高的順序排列以下表達(dá)式：4n2，logn，3n，20n，2，n2/3。又n!應(yīng)該排在哪一位？分析與解答：按漸近階從低到高，函數(shù)排列順序如下：2，logn，n2/3，20n，4n2，3n，n！。4.算法效率(1)假設(shè)某算法在輸入規(guī)模為n時(shí)計(jì)算時(shí)間為T(n)=3*2n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t秒?，F(xiàn)有另一臺(tái)計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題？(2)若上述算法的計(jì)算時(shí)間改進(jìn)為T(n)=n2，其余條件不變，則在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模為多大的問題？(3)若上述算法的計(jì)算時(shí)間進(jìn)

12、一步改進(jìn)為T(n)=8，其余條件不變，那么在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模為多大的問題？分析解答：(1)設(shè)新機(jī)器用同一算法在t秒內(nèi)能解輸入規(guī)模為n1的問題。因此有：t=3*22=3*2n1/64，解得你n1=n+6。(2)n12=64n2n1=8n。(3)由于T(n)=常數(shù)，因此算法可解任意規(guī)模的問題。5階乘函數(shù) 階乘函數(shù)可遞歸地定義為：int factorial(int n)if(n = = 0) return 1;return n * factorial(n-1);6Fibonacci數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為

13、：請(qǐng)對(duì)這個(gè)無窮數(shù)列設(shè)計(jì)一個(gè)算法，并進(jìn)行描述（自然語言描述和VC+描述）.第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：int fibonacci(int n) if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2); 7循環(huán)賽日程表設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行兵乓球循環(huán)賽。現(xiàn)在要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法解決以上問題，并進(jìn)行描述（自然語言和C+語言）按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就

14、可以通過為n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。8有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。分析回答以下兩個(gè)問題：(1)分析以上最優(yōu)裝載問題具有貪心選擇性質(zhì)(2)用C+程序進(jìn)行正確的算法描述分析與解答：(1) 設(shè)集裝箱已依其重量從小到大排序，(x1,x2,xn)是最有裝載問題的一個(gè)最優(yōu)解。又設(shè)k=mini|xi=1。易知，如果給定的最有裝載問題有解，則1kn。 當(dāng)k=1時(shí)，(x1,x2,xn)是滿足貪心選擇性質(zhì)的最優(yōu)解。當(dāng)k>1時(shí)，取y1=1;yk=0;yi=xi,1<in,ik,則因此，()是所給最有裝載問題的可行解。另一方面，由知，()是滿足貪心選擇性質(zhì)的最優(yōu)解。所以，最優(yōu)裝載問題具有貪心選擇性質(zhì)。 (2)最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描