算法設(shè)計(jì)與分析復(fù)習(xí)題目及答案

1、。選擇題1、二分搜索算法是利用（）實(shí)現(xiàn)的算法。2、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（找出最優(yōu)解的性質(zhì)B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、定義最A(yù)、備忘錄法B動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法優(yōu)解3、最大效益優(yōu)先是（。的一搜索方式。4、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法在下列算法中有時(shí)找不到問題解的是（蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法5.回溯法解旅行售貨員問題時(shí)的解空間樹是（子集樹C、深度優(yōu)先生成樹D廣度優(yōu)先生成樹6.下列算法中通常以自底向上的方式求解最優(yōu)解的是（備忘錄法B動(dòng)態(tài)規(guī)劃法C、貪心法回溯法7、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是

2、（C ）。A運(yùn)行速度快B占用空間少C時(shí)間復(fù)雜度低D代碼短 8、以下不可以使用分治法求解的是（D ）。A棋盤覆蓋問題B選擇問題C歸并排序D 0/1背包問題9.實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（）。A分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法回溯法10、下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是（C ）A數(shù)值概率算法B舍伍德算法C拉斯維加斯算法D蒙特卡羅算法11.下面不是分支界限法搜索方式的是（A廣度優(yōu)先B最小耗費(fèi)優(yōu)先C、最大效益優(yōu)先D深度優(yōu)先12 .下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是13. 備忘錄方法是那種算法的變形。（B ）A分治法B動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法14. 哈弗曼編碼的貪心算法所需

3、的計(jì)算時(shí)間為（A O( n2n)B O(nlogn )C O (2n)0(n)15. 分支限界法解最大團(tuán)問題時(shí)，活結(jié)點(diǎn)表的組織形式是A、最小堆B、最大堆16.最長公共子序列算法利用的算法是（）。A分支界限法B動(dòng)態(tài)規(guī)劃法C貪心法回溯法17.實(shí)現(xiàn)棋盤覆蓋算法利用的算法是A分治法B動(dòng)態(tài)規(guī)劃法貪心法回溯法18. 下面是貪心算法的基本要素的是（A重疊子問題B構(gòu)造最優(yōu)解貪心選擇性質(zhì)D定義最優(yōu)解19. 回溯法的效率不依賴于下列哪些因素（A.滿足顯約束的值的個(gè)數(shù)B.計(jì)算約束函數(shù)的時(shí)間C. 計(jì)算限界函數(shù)的時(shí)間D. 確定解空間的時(shí)間20. 下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（A.遞歸函數(shù)B.剪枝函數(shù)C

4、o隨機(jī)數(shù)函數(shù)D.搜索函數(shù)21、下面關(guān)于NP問題說法正確的是（A NP問題都是不可能解決的問題B P類問題包含在NP類問題中C NP完全問題是P類問題的子集D NP類問題包含在P類問題中22、蒙特卡羅算法是（）的一種。A分支界限算法B、概率算法C、貪心算法D、回溯算法23.下列哪一種算法不是隨機(jī)化算法（A.蒙特卡羅算法B.拉斯維加斯算法C.動(dòng)態(tài)規(guī)劃算法D.舍伍德算法24.(）是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。A重疊子問題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D最優(yōu)子結(jié)構(gòu)性質(zhì)25.矩陣連乘問題的算法可由（B）設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法B、動(dòng)態(tài)規(guī)劃算法C、貪心算法36.下列算法中通常以自底向下的方式求解最優(yōu)

5、解的是（B）。A分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法回溯算法26.分支限界法解旅行售貨員問題時(shí),活結(jié)點(diǎn)表的組織形式是A、最小堆C、棧D數(shù)組27、Strassen矩陣乘法是利用（。實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法29、使用分治法求解不需要滿足的條件是（A ）。A子問題必須是一樣的B子冋題不能夠重復(fù)C子問題的解可以合并D原問題和子問題使用相同的方法解30、下面問題（B。不能使用貪心法解決。A單源最短路徑問題B N皇后問題C最小花費(fèi)生成樹問題D背包問題31、下列算法中不能解決0/1背包問題的是（A ）A貪心法B動(dòng)態(tài)規(guī)劃C回溯法D分支限界法32、回溯法搜索狀態(tài)空間樹是按照（

6、C。的順序。A中序遍歷B廣度優(yōu)先遍歷C深度優(yōu)先遍歷D層次優(yōu)先遍歷33、下列隨機(jī)算法中運(yùn)行時(shí)有時(shí)候成功有時(shí)候失敗的是（C ）A數(shù)值概率算法B舍伍德算法C拉斯維加斯算法D蒙特卡羅算法34.實(shí)現(xiàn)合并排序利用的算法是（A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法35下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子冋題重疊性質(zhì)37.采用廣度優(yōu)先策略搜索的算法是（A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法38、合并排序算法是利用（）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法39、在下列算法中得到的解未必正確的是（）。B、拉斯維加斯算法C、舍伍德算法D、數(shù)

7、值概率算法40、背包問題的貪心算法所需的計(jì)算時(shí)間為（A、O（ n2n）B、O (nlogn )C、O (2n)O(n)41.實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（A、貪心法B、動(dòng)態(tài)規(guī)劃法分治策略回溯法42. 0-1背包問題的回溯算法所需的計(jì)算時(shí)間為（A、O (n2n)B、O(nlogn)O( 2n)O(n)43采用最大效益優(yōu)先搜索方式的算法是）。A分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法回溯法44.貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是A最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)構(gòu)造最優(yōu)解D、定義最優(yōu)解45.實(shí)現(xiàn)最大子段和利用的算法是（）。A分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法回溯法46.優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原則是（

8、A、先進(jìn)先出B、后進(jìn)先出C、結(jié)點(diǎn)的優(yōu)先級隨機(jī)47.背包問題的貪心算法所需的計(jì)算時(shí)間為（A、O (n2n)B、O(nlogn)C O(2n)O(n)48、廣度優(yōu)先是（）的一搜索方式。A分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法49、舍伍德算法是）的一種。算法50、在下列算法中有時(shí)找不到問題解的是（A分支界限算法B、概率算法C、貪心算法D、回溯A、蒙特卡羅算法B、拉斯維加斯算法C、舍伍德算法D、數(shù)值概率算法51下列哪一種算法是隨機(jī)化算法（A.貪心算法B.回溯法C.動(dòng)態(tài)規(guī)劃算法D.舍伍德算法 52. 一個(gè)問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的）。A、重疊子問題B最優(yōu)子結(jié)構(gòu)性質(zhì)C貪心選

9、擇性質(zhì)D定義最優(yōu)解53 采用貪心算法的最優(yōu)裝載問題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為（BA、O（ n2n）B、O(nlogn)O (2n)D O (n)54. 以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為A分支界限算法B、概率算法C、貪心算法D、回溯算法55. 實(shí)現(xiàn)最長公共子序列利用的算法是（A分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D回溯法56、算法是由若干條指令組成的有窮序列，而且滿足以下性質(zhì)（(1)輸入：有0個(gè)或多個(gè)輸入輸出：至少有一個(gè)輸出 確定性：指令清晰，無歧義 有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時(shí)間有限A (1)(2)(3)B(1)(2 ”4)C(1) (3)D

10、(1)57、函數(shù)32n+10nlogn的漸進(jìn)表達(dá)式是（B ）.A. 2n B. 32nC. nlognD. 10 nlogn58、大整數(shù)乘法算法是（A ）.算法A.分治B.貪心C.動(dòng)態(tài)規(guī)劃D.窮舉).59、用動(dòng)態(tài)規(guī)劃算法解決最大字段和問題，其時(shí)間復(fù)雜性為（BD. niog n2A.log nB.n C.n 60、解決活動(dòng)安排問題，最好用（B ）算法A.分治B.貪心C.動(dòng)態(tài)規(guī)劃D.窮舉61、設(shè)f(N),g(N)是定義在正數(shù)集上的正函數(shù)，如果存在正的常數(shù) C和自然數(shù)No,得當(dāng)NNo時(shí)有f(N) Cg(N則稱函數(shù)f(N)當(dāng)N充分大時(shí)有下界g(N),記作 f(N) O (g(N),即 f(N)的階(A

11、 )g(N)的階.A.不高于B.不低于C.等價(jià)于D.逼近62、回溯法在解空間樹T上的搜索方式是(A ).A.深度優(yōu)先B.廣度優(yōu)先C.最小耗費(fèi)優(yōu)先 D.活結(jié)點(diǎn)優(yōu)先63、回溯算法和分支限界法的問題的解空間樹不會是(D ).A.有序樹B.子集樹C.排列樹D.無序樹 64、在對問題的解空間樹進(jìn)行搜索的方法中，一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會成為活結(jié)點(diǎn)的是(B ).A.回溯法B.分支限界法C.回溯法和分支限界法 D.回溯法求解子集樹問題65、從活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的不同方式將導(dǎo)致不同的分支限界法，以下除(C )之外都是最常見的方式.A.隊(duì)列式分支限界法 B.優(yōu)先隊(duì)列式分支限界法C.棧式分支限界法 D.F

12、IFO分支限界法填空題1.算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。2、程序是 算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。3、算法的“確定性”指的是組成算法的每條指令 是清晰的，無歧義的。4.矩陣連乘問題的算法可由動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。5、拉斯維加斯算法找到的解一定是正確解。6、算法是指解決問題的一種方法或 一個(gè)過程遞歸算法7、從分治法的一般設(shè)計(jì)模式可以看出，用它設(shè)計(jì)出的程序一般是8、問題的最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的 關(guān)鍵特征。9、以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。10、數(shù)值概率算法常用于 數(shù)值問題的求解。11、計(jì)算一個(gè)算法時(shí)間復(fù)雜度通?？梢杂?jì)算循環(huán)次數(shù)、基本操

13、作的頻率或計(jì)算步。12、利用概率的性質(zhì)計(jì)算近似值的隨機(jī)算法是數(shù)值概率算法,運(yùn)行時(shí)以一定的概率得到正確解的隨機(jī)算法是蒙特卡羅算法14、解決0/1背包問題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是 動(dòng)態(tài)規(guī)劃，需要排序的是回溯法 ，分支限界法15、使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時(shí)一般有兩個(gè)標(biāo)準(zhǔn)：約束條件和目標(biāo)函 數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是0/1 背包問題，只使用約束條件進(jìn)行16、裁剪的是 N皇后問題貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài) 規(guī)劃算法的主要區(qū)別。17、矩陣連乘問題的算法可由

14、動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。18、拉斯維加斯算法找到的解一定是正確解。19.貪心算法的基本要素是貪心選擇質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。21. 動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干子問題先求解子問題，然后從這些子問題的解得到原問題的解。22. 算法是由若干條指令組成的有窮序列，且要滿足輸入、輸出確定性和有限性四條性質(zhì)。23、大整數(shù)乘積算法是用分治法 來設(shè)計(jì)的。24、以廣度優(yōu)先或以最小耗費(fèi)方式搜索問題解的算法稱為分支限界法25、舍伍德算法總能求得問題的一個(gè)解26、貪心選擇性質(zhì)是貪心算法可行的第一個(gè)基本要素,也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。27.快速排序算法是基于分治策略的一種排序算法。重疊子問題性質(zhì)。

15、30.回溯法是一種既帶有系統(tǒng)性又帶有跳躍性的搜索算法。31.分支限界法主要有隊(duì)列式（FIFO）分支限界法和分支限界法。32.分支限界法是一種既帶有系統(tǒng)性又帶有跳躍性 的搜索算法。33.回溯法搜索解空間樹時(shí)，常用的兩種剪枝函數(shù)為約束函數(shù)和 限界函數(shù)34.任何可用計(jì)算機(jī)求解的問題所需的時(shí)間都與其規(guī)模有關(guān)。35.快速排序算法的性能取決于 劃分的對稱性36. Prim算法利用貪心 策略求解最小生成樹冋題，其時(shí)間復(fù)雜度 是 OCn2)37.圖的m著色問題可用回溯法求解，其解空間樹中葉子結(jié)點(diǎn)個(gè)數(shù)是mn_,解空間樹中每個(gè)內(nèi)結(jié)點(diǎn)的孩子數(shù)是三、算法填空1. 背包問題的貪心算法 void Knap sack(i

16、nt n,float M,float v,float w,float x)Sort( n,v,w);int i;for (i=1;i=n ;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c - =wi;if (i=n) xi=c/wi;2. 最大子段和：動(dòng)態(tài)規(guī)劃算法int MaxSum(i nt n, i nt a)int sum=O, b=0/sum存儲當(dāng)前最大的bj, b 存儲bjfor(i nt j=1；j0) b+= ajelse b=ai;/ 一旦某個(gè)區(qū)段和為負(fù)，則從下一個(gè)位置累if(bsum) sum=b;return sum3. 快速排序t

17、empi atevciass Typevoid Quicksort (Type a, int p, int r)if (pvr) int q=P artiti on(a,p,r);Quicksort (a, p,q-1); /對左半段排序Quicksort (a,q+1,r); /對右半段排序4. 排列問題Tempi ate vclass Type void p erm(T ype list, int k, int m ) /產(chǎn)生listk:m的所有排列if(k=m) /只剩下一個(gè)元素for (i nt i=0;iv=m;i+) coutlisti;coutvve ndl;else /還有多個(gè)

18、元素待排列，遞歸產(chǎn)生排列for (int i=k; i=m; i+)sk,listi);p erm(list,k+1;m);sk,listi);5. 給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元據(jù)此容易設(shè)計(jì)出二分搜索算法:tempi ateclass Type int Bin arySearch(T ype a, const Type& x, int l, i nt r)while (l=r )int m = (l+r)/2);if (x = am) return m;if (x am ) r = m-1; else l = m+1;return -1;6、合并排序

19、描述如下:tempi ate0)y=y*x;(return y );四、問答題1. 用計(jì)算機(jī)求解問題的步驟:1、問題分析2、數(shù)學(xué)模型建立3、算法設(shè)計(jì)與選擇4、算法指標(biāo)5、算法分析6算法實(shí)現(xiàn)7、程序調(diào)試8、結(jié)果整理文檔編制2. 算法定義:算法是指在解決問題時(shí)，按照某種機(jī)械步驟一定可以得到問題結(jié)果的處理過3. 算法的三要素1、操作2、控制結(jié)構(gòu)3、數(shù)據(jù)結(jié)構(gòu)4. 算法具有以下5個(gè)屬性:有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束， 且每一步都在有窮時(shí)間 內(nèi)完成。確定性：算法中每一條指令必須有確切的含義。 不存在二義性。只有一個(gè)入 口和一個(gè)出口可行性：一個(gè)算法是可行的就是算法描述的操作是可以通過已經(jīng)實(shí)現(xiàn)

20、的基本 運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定對象的集合。輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出同輸入有著某些特定關(guān)系的量。5. 算法設(shè)計(jì)的質(zhì)量指標(biāo):正確性：算法應(yīng)滿足具體問題的需求;可讀性：算法應(yīng)該好讀，以有利于讀者對程序的理解;健壯性：算法應(yīng)具有容錯(cuò)處理，當(dāng)輸入為非法數(shù)據(jù)時(shí)，算法應(yīng)對其作出反應(yīng), 而不是產(chǎn)生莫名其妙的輸出結(jié)果。效率與存儲量需求：效率指的是算法執(zhí)行的時(shí)間；存儲量需求指算法執(zhí)行過 程中所需要的最大存儲空間。一般這兩者與問題的規(guī)模有關(guān)。經(jīng)常采用的算法主要有迭代法、分治法、貪婪法、動(dòng)態(tài)規(guī)劃法、回溯法、分支 限界法6.迭代法:也稱“輾轉(zhuǎn)法”，

21、是一種不斷用變量的舊值遞推出新值的解決問題的方法。7.利用迭代算法解決問題，需要做好以下三個(gè)方面的工作:1）、確定迭代模型。在可以用迭代算法解決的問題中， 至少存在一個(gè)直接或 間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。2）、建立迭代關(guān)系式。所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢?使用遞推或倒推的方法來完成。3) 、對迭代過程進(jìn)行控制。在什么時(shí)候結(jié)束迭代過程？這是編寫迭代程序必 須考慮的問題。不能讓迭代過程無休止地重復(fù)執(zhí)行下去。 迭代過程的控制通常可 分為兩種情況：一種是所需的迭代次數(shù)是個(gè)確定的值， 可以

22、計(jì)算出來；另一種是 所需的迭代次數(shù)無法確定。對于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來實(shí) 現(xiàn)對迭代過程的控制；對于后一種情況，需要進(jìn)一步分析出用來結(jié)束迭代過程的 條件。8. 分治法的基本思想是:將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立 且與原問題相同。遞歸地解這些子問題，然后將各個(gè)子問題的解合并得到原問題 的解。9. 分治法所能解決的問題一般具有以下幾個(gè)特征:(1) 該問題的規(guī)模縮小到一定的程度就可以容易地解決;(2) 該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；(3 )禾1用該問題分解出的子問題的解可以合并為該問題的解;(4 )該問題所分

23、解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不 包含公共的子子問題。10、分治法的基本步驟分治法在每一層遞歸上都有三個(gè)步驟:(1) 分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題 形式相同的子問題；(2) 解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地 解各個(gè)子問題；(3)合并：將各個(gè)子問題的解合并為原問題的解。11. 動(dòng)態(tài)規(guī)劃的基本思想前文主要介紹了動(dòng)態(tài)規(guī)劃的一些理論依據(jù)， 我們將前文所說的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動(dòng)態(tài)規(guī)劃稱為標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃，這種標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃是在研 究多階段決策問題時(shí)推導(dǎo)出來的，具有嚴(yán)格的數(shù)學(xué)形式，適合用于理論上的分析。 在實(shí)際應(yīng)用中，許多問題的階段劃分

24、并不明顯，這時(shí)如果刻意地劃分階段法反而 麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題， 并且原問題的最優(yōu) 解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動(dòng)態(tài)規(guī)劃解 決。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是 分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問題實(shí)例 分解為更小的、相似的子問題，并存儲子問題的解而避免計(jì)算重復(fù)的子問題, 解決最優(yōu)化冋題的算法策略。由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實(shí)例歸納為 更小的、相似的子問題，并通過求解子問題產(chǎn)生一個(gè)全局最優(yōu)解。貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出 的選擇和子問題。因此貪心法自頂向下，一步一步地作出

25、貪心選擇;而分治法中的各個(gè)子問題是獨(dú)立的（即不包含公共的子問題），因此一旦遞歸地 求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。不足之處：如果當(dāng)前選擇可能要依賴子問題的解時(shí)，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工 作，重復(fù)地解公共的子問題。解決上述問題的辦法是利用動(dòng)態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類 問題會有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)（最大或 最小）值的解。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過 程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解，但與分治法和貪心 法不同的

26、是，動(dòng)態(tài)規(guī)劃允許這些子問題不獨(dú)立， （亦即各子問題可包含公共的子 問題）也允許其通過自身子問題的解作出選擇，該方法對每一個(gè)子問題只解一次, 并將結(jié)果保存起來，避免每次碰到時(shí)都要重復(fù)計(jì)算。因此，動(dòng)態(tài)規(guī)劃法所針對的問題有一個(gè)顯著的特征，即它所對應(yīng)的子問題樹 中的子問題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對于重復(fù)出現(xiàn)的子問題， 只在第一次遇到時(shí)加以求解，并把答案保存起來，讓以后再遇到時(shí)直接引用，不 必重新求解。12、動(dòng)態(tài)規(guī)劃算法的基本步驟設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通?？砂匆韵聨讉€(gè)步驟進(jìn)行:（1）戈扮階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。注意這若干個(gè)階段一定要是有序的或者是可排序

27、的（即無后向性），否則問題就無法用 動(dòng)態(tài)規(guī)劃求解。（2）選擇狀態(tài)：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。（3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策和 狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階 段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但事實(shí)上, 我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策。（4）寫出規(guī)劃方程（包括邊界條件）：動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡單的。動(dòng)態(tài)

28、規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會非常簡單。 根據(jù)動(dòng)態(tài)規(guī)劃的基本方程可以直接遞歸計(jì)算最優(yōu)值，但是一般將其改為遞推計(jì)算。實(shí)際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃，而是按以下幾個(gè)步 驟進(jìn)行:分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計(jì)算出最優(yōu)值。(4)步驟根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。（1）（3）是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省略，若需要求出問題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟（4）。此時(shí),在步驟（3）中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟（4）中，

29、根 據(jù)所記錄的信息，快速地構(gòu)造出一個(gè)最優(yōu)解。總結(jié)：動(dòng)態(tài)規(guī)劃實(shí)際上就是最優(yōu)化的問題，是指將原問題的大實(shí)例等價(jià)于同最優(yōu)化問題的較小實(shí)例，自底向上的求解最小實(shí)例，并將所求解存放起來，存 放的結(jié)果就是為了準(zhǔn)備數(shù)據(jù)。與遞歸相比，遞歸是不斷的調(diào)用子程序求解，是自頂向下的調(diào)用和求解。13. 分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)是:將待求解的問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的 解得到原問題的解。兩者的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往 往不是互相獨(dú)立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨(dú) 立的。14.回溯法回溯法也稱為試探法，該方法首先暫時(shí)放棄關(guān)于問題規(guī)

30、模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)，就 選擇下一個(gè)候選解；倘若當(dāng)前候選解除了還不滿足問題規(guī)模要求外， 滿足所有其 他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括放棄當(dāng)以繼續(xù)問題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問題的一個(gè)解。在回溯法中, 前候選解，尋找下一個(gè)候選解的過程稱為回溯。 擴(kuò)大當(dāng)前候選解的規(guī)模, 試探的過程稱為向前試探。15.分支限界法:這是一種用于求解組合優(yōu)化問題的排除非解的搜索算法。類似于回溯法, 枝定界法在搜索解空間時(shí)，也經(jīng)常使用樹形結(jié)構(gòu)來組織解空間。 然而與回溯法不 同的是，回溯算法使用深度優(yōu)先方法搜索樹

31、結(jié)構(gòu)， 而分枝定界一般用寬度優(yōu)先或 最小耗費(fèi)方法來搜索這些樹。因此，可以很容易比較回溯法與分枝定界法的異同。相對而言，分枝定界算法的解空間比回溯法大得多， 因此當(dāng)內(nèi)存容量有限時(shí)，回 溯法成功的可能性更大。算法思想：分枝限界（branch and bound是另一種系統(tǒng)地搜索解空間的方法,它與回溯法的主要區(qū)別在于對 E-節(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次機(jī)會變成E-節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)镋-節(jié)點(diǎn)時(shí)，則生成從該節(jié)點(diǎn)移動(dòng)一步即可到達(dá) 的所有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn),其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)

32、行擴(kuò)充， 直到找到解或活動(dòng)表為空，擴(kuò)充過程才結(jié)束。有兩種常用的方法可用來選擇下一個(gè) E-節(jié)點(diǎn)（雖然也可能存在其他的方法）： 1）先進(jìn)先出（F IF O）即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的順序與加入節(jié)點(diǎn)的順序相同, 因此活 節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。2）（優(yōu)先隊(duì)列）最小耗費(fèi)或最大收益法在這種模式中，每個(gè)節(jié)點(diǎn)都有一個(gè)對應(yīng) 的耗費(fèi)或收益。如果查找一個(gè)具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小堆來建如果希望搜索一個(gè)具有最大收E-節(jié)點(diǎn)是具有最大收益的活節(jié)立，下一個(gè)E-節(jié)點(diǎn)就是具有最小耗費(fèi) 的活節(jié)點(diǎn);益的解，則可用最大堆來構(gòu)造活節(jié)點(diǎn)表，下一個(gè)16.分支限界法與回溯法的相同點(diǎn)是：都是種在問題的解空間樹T中搜索問題解的算法。不

33、同點(diǎn)：（1）求解目標(biāo)不同;(2)(3)搜索方式不同；對擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同;（4）存儲空間的要求不同。17. 分治法所能解決的問題一般具有的幾個(gè)特征是:(1)該問題的規(guī)?？s小到一定的程度就可以容易地解決;該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)(3)禾用該問題分解出的子問題的解可以合并為該問題的解；（4）原問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共 的子問題。18. 用分支限界法設(shè)計(jì)算法的步驟是:（1）針對所給問題，定義問題的解空間（對解進(jìn)行編碼）（2）確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）（3）以廣度優(yōu)先或以最小耗費(fèi)（最大收益）優(yōu)先的方式搜

34、索解空間，并在搜索 過程中用剪枝函數(shù)避免無效搜索。19. 常見的兩種分支限界法的算法框架:(1)隊(duì)列式(FIFO)分支限界法：按照隊(duì)列先進(jìn)先出(FIFO)原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。(2)優(yōu)先隊(duì)列式分支限界法：按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。20. 回溯法中常見的兩類典型的解空間樹是子集樹和排列樹。當(dāng)所給的問題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹。這類子集樹通常有2n個(gè)葉結(jié)點(diǎn)，遍歷子集樹需 0(2n)計(jì)算時(shí)間。當(dāng)所給的問題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹稱為排列樹。這類排列樹通常有n!個(gè)葉結(jié)點(diǎn)。遍歷排列樹需

35、要 0( n!)計(jì)算時(shí)間。21. 分支限界法的搜索策略是:在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)(分支)，然后再從當(dāng)前的活結(jié)點(diǎn) 表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，加速搜索的進(jìn)程，在 每一個(gè)活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值(限界)，并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中 選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間上有最優(yōu)解的分支推 進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。22. 請敘述動(dòng)態(tài)規(guī)劃算法與貪心算法的異同。共同點(diǎn): 都需要最優(yōu)子結(jié)構(gòu)性質(zhì), 都用來求有優(yōu)化問題。不同點(diǎn): 動(dòng)態(tài)規(guī)劃：每一步作一個(gè)選擇一依賴于子問題的解。貪心方法：每一步作一個(gè)選擇一不依賴于子問題的解 動(dòng)態(tài)規(guī)劃方法的條件：子問題的

36、重疊性質(zhì)?？捎秘澬姆椒ǖ臈l件：最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。動(dòng)態(tài)規(guī)劃：自底向上求解;貪心方法：自頂向下求解?？捎秘澬姆〞r(shí)，動(dòng)態(tài)規(guī)劃方法可能不適用;可用動(dòng)態(tài)規(guī)劃方法時(shí)，貪心法可能不適用。23. 請說明動(dòng)態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。答:最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問題的最優(yōu)解包含子問題的最優(yōu)解。動(dòng)態(tài)規(guī)劃方法是自底向上計(jì)算各個(gè)子問題的最優(yōu)解，即先計(jì)算子問題的最優(yōu)解，然后再利用子問題的最優(yōu)解構(gòu)造大問題的最優(yōu)解，因此需要最優(yōu)子結(jié)構(gòu).24.請說明:(1) 優(yōu)先隊(duì)列可用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)?(2) 優(yōu)先隊(duì)列插入算法基本思想？(3) 優(yōu)先隊(duì)列插入算法時(shí)間復(fù)雜度?答：(1)堆。(2)在小根堆中，將元素x插入到堆的末

37、尾，若兀素然后將元素x的關(guān)鍵字與其雙親的關(guān)鍵字比較, x的關(guān)鍵字小于其雙親的關(guān)鍵字，則將元素x與其雙親交換，然后再將元素x與其新雙親的關(guān)鍵字相比, 直到元素x的關(guān)鍵字大于雙親的關(guān)鍵字，或元素 x到根為止。(3) 0( log n)25.衡量算法時(shí)間效率的方法有哪兩種？請敘述。答：有事前分析法和事后分析法兩種。事后分析法：先將算法用程序設(shè)計(jì)語言實(shí)現(xiàn)，然后度量程序的運(yùn)行時(shí)間。 事前分析法：算法的時(shí)間效率是問題規(guī)模的函數(shù)，假如，隨著問題規(guī)模n的增長, 算法執(zhí)行時(shí)間的增長率和函數(shù)f(n)的增長率相同，貝冋記作:T( n)=O (f(n)稱T(n)為算法的漸進(jìn)時(shí)間復(fù)雜度。簡稱時(shí)間復(fù)雜度。26.在算法復(fù)雜

38、性分析中，0、Q、這三個(gè)記號的意義是什么？在忽略常數(shù)因子的情況下，0、Q、分別提供了算法運(yùn)行時(shí)間的什么界?答: 如果存在兩個(gè)正常數(shù)c和NO,對于所有的NNO,有f(N)|wC|g(N)|,則記作：f(N)=O(g(N)。這時(shí)我們說f(N)的階不高于g(N)的階。若存在兩個(gè)正常數(shù)C和自然數(shù)NO，使得當(dāng)N NO時(shí)有|f(N)|C|g(N)|,記為 f(N)=?(g(N)。這時(shí)我們說f(N)的階不低于g(N)的階。如果存在正常數(shù)c1,c2和nO,對于所有的nnO,有c1|g(N)| |f(N)| c2|g(N)|則記作 f(N)=(g,(N)O、Q、分別提供了算法運(yùn)行時(shí)間的上界、下界、平均27.概率

39、算法很多算法的每一個(gè)計(jì)算步驟都是固定的，而概率算法允許算法在執(zhí)行 的過程中隨機(jī)選擇下一個(gè)計(jì)算步驟。許多情況下，當(dāng)算法在執(zhí)行過程中面 臨一個(gè)選擇時(shí)，隨機(jī)性選擇常比最優(yōu)選擇省時(shí)。因此概率算法可在很大程 度上降低算法的復(fù)雜度。28.概率算法的一個(gè)基本特征是對所求解問題的同一實(shí)例用同一概率算法求解兩次可能得到完全不 同的效果。這兩次求解問題所需的時(shí)間甚至所得到的結(jié)果可能會有相當(dāng)大 的差別。29 .概率算法大致分為四類：數(shù)值概率算法，蒙特卡羅(Monte Carlo )算法，拉斯維加斯(Las Vegas) 算法和舍伍德(Sherwood)算法。30. 數(shù)值概率算法常用于數(shù)值問題的求解。這類算法所得到的

40、往往是近似解。而且近似 解的精度隨計(jì)算時(shí)間的增加不斷提高。在許多情況下，要計(jì)算出問題的精 確解是不可能或沒有必要的，因此用數(shù)值概率算法可得到相當(dāng)滿意的解。31. 蒙特卡羅算法用于求問題的準(zhǔn)確解。對于許多問題來說，近似解毫無意義。例如，一 個(gè)判定問題其解為“是”或“否”，二者必居其一，不存在任何近似解答。 又如，我們要求一個(gè)整數(shù)的因子時(shí)所給出的解答必須是準(zhǔn)確的，一個(gè)整數(shù) 的近似因子沒有任何意義。用蒙特卡羅算法能求得問題的一個(gè)解，但這個(gè) 解未必是正確的。求得正確解的概率依賴于算法所用的時(shí)間。算法所用的 時(shí)間越多，得到正確解的概率就越高。蒙特卡羅算法的主要缺點(diǎn)就在于此。 一般情況下，無法有效判斷得到

41、的解是否肯定正確。32. 拉斯維加斯算法不會得到不正確的解，一旦用拉斯維加斯算法找到一個(gè)解，那么這個(gè)解 肯定是正確的。但是有時(shí)候用拉斯維加斯算法可能找不到解。與蒙特卡羅 算法類似。拉斯維加斯算法得到正確解的概率隨著它用的計(jì)算時(shí)間的增加 而提高。對于所求解問題的任一實(shí)例，用同一拉斯維加斯算法反復(fù)對該實(shí) 例求解足夠多次，可使求解失效的概率任意小。33. 舍伍德算法總能求得問題的一個(gè)解，且所求得的解總是正確的。當(dāng)一個(gè)確定性算法 在最壞情況下的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有較大差別 時(shí)，可以在這個(gè)確定算法中引入隨機(jī)性將它改造成一個(gè)舍伍德算法，消除 或減少問題的好壞實(shí)例間的這種差別。舍伍德算法

42、精髓不是避免算法的最 壞情況行為，而是設(shè)法消除這種最壞行為與特定實(shí)例之間的關(guān)聯(lián)性。舍伍德算法 Sherwood algorithm舍伍德算法 一類概率算法的代稱。此類算法總能給出所求問題的正確的解。 當(dāng)解決某一問題的確定性算法的平均情形復(fù)雜性比最壞情形復(fù)雜性低得多時(shí)， 過引入隨機(jī)性來試圖減少甚至消除“好”、“壞”實(shí)體之間這種時(shí)間上的差別, 以期望較小的運(yùn)行時(shí)間。例五、算法設(shè)計(jì)與分析題1.用動(dòng)態(tài)規(guī)劃策略求解最長公共子序列問題:給出計(jì)算最優(yōu)值的遞歸方程。給定兩個(gè)序列X=B,C,D,A，Y=A,B,C,B，請采用動(dòng)態(tài)規(guī)劃策略求出 其最長公共子序列，要求給出過程。答:2.0當(dāng)i0或j0時(shí),jci 1,

43、j11當(dāng)i, j0且X imax(ci,j 1, ci 1,j)當(dāng) i, j0且X(2)Y A BC BX0.00 0B0011 1C001巧2D0012 l2A0112 2最長公共子序列：對下列各組函數(shù)f (n)和 g (n),確定 f (n) = O (g (n)或 f (n)0 (g(n)，并簡要說明理由。(1) f(n )=2n ；g( n)=n! f(n)= Jn ;2g (n)=log n f(n)=100;g(n )=log100 f(n )=n3;g(n)= 3n f(n)=3 n ；g(n )=2n答：(1) f(n) = O(g(n)因?yàn)間(n)的階比f(n)的階高。 f(

44、n) = Q (g(n)因?yàn)間(n)的階比f(n)的階低。 f(n) = 0 (g(n)因?yàn)間(n)與f(n)同階。 f(n) = O(g(n)因?yàn)間(n)的階比f(n)的階高。(5) f(n) = Q (g(n)因?yàn)間(n)的階比f(n)的階低。ciBC=Q (g (n)或 f(n)=G,用克魯斯卡爾(Kruskal)算法求G的最小生成樹T,請寫出在算法執(zhí)行過程中，依次加入T的邊集TE中的邊。說明該算法的貪心3.對下圖所示的連通網(wǎng)絡(luò)策略和算法的基本思想，并簡要分析算法的時(shí)間復(fù)雜度。答:TE=(3,4), (2,3),(1,5),(4,6 ) (4,5 ) 貪心策略是每次都在連接兩個(gè)不同連通分

45、量的邊中選權(quán)值最小的邊。基本思想：首先將圖中所有頂點(diǎn)都放到生成樹中，然后每次都在連接兩個(gè)不同連通分量的邊中選權(quán)值最小的邊， 將其放入生成樹中，直到生成樹中有n-1條邊。時(shí)間復(fù)雜度為：O(eloge)4.請用分治策略設(shè)計(jì)遞歸的歸并排序算法，并分析其時(shí)間復(fù)雜性(要求：分別給出divide、conquer、combine這三個(gè)階段所花的時(shí)間，并在此基礎(chǔ)上列出遞歸方程，最后用套用公式法求出其解的漸進(jìn)階) 答 : Temp late class Typevoid MergeSort (Type a , i nt left, i nt right) if (leftright) int i= ( left+right)/2;MergeSort( a, left, i);MergeSort( a, i+1, right);Merge(a, b, left, right);Cop y(a, b, left, right);Divide階段的時(shí)間復(fù)雜性:O(1)Con quer階段的時(shí)間復(fù)雜性:2T( n)Combi ne階段的時(shí)間復(fù)雜性: (n)T(n) 2T(n/2)0 (n)用套用公式法：a=2, b=2, nog ba = n , f(n)=n,因?yàn)?f(n)與 nog ba 同階, T(n) = (niogn)5、設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個(gè)