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

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

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

3、規(guī)劃法C、貪心法D、回溯法13.備忘錄方法是那種算法的變形。 B A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法14哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為B 。A、On2nB、OnlognC、O2nD、On15分支限界法解最大團(tuán)問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是B 。A、最小堆B、最大堆 C、棧D、數(shù)組16最長(zhǎng)公共子序列算法利用的算法是B 。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法17實(shí)現(xiàn)棋盤覆蓋算法利用的算法是A 。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法18.下面是貪心算法的根本要素的是C 。A、重疊子問(wèn)題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最優(yōu)解19.回溯法的效率不依賴于以下哪些因素

4、 D A.滿足顯約束的值的個(gè)數(shù) B. 計(jì)算約束函數(shù)的時(shí)間 C. 計(jì)算限界函數(shù)的時(shí)間 D. 確定解空間的時(shí)間20.下面哪種函數(shù)是回溯法中為防止無(wú)效搜索采取的策略B A遞歸函數(shù)B.剪枝函數(shù) C。隨機(jī)數(shù)函數(shù)D.搜索函數(shù)21、下面關(guān)于NP問(wèn)題說(shuō)法正確的選項(xiàng)是B A NP問(wèn)題都是不可能解決的問(wèn)題B P類問(wèn)題包含在NP類問(wèn)題中C NP完全問(wèn)題是P類問(wèn)題的子集D NP類問(wèn)題包含在P類問(wèn)題中22、蒙特卡羅算法是B 的一種。A、分支界限算法 B、概率算法 C、貪心算法 D、回溯算法23.以下哪一種算法不是隨機(jī)化算法C A. 蒙特卡羅算法B. 拉斯維加斯算法C.動(dòng)態(tài)規(guī)劃算法D.舍伍德算法24. D 是貪心算法與動(dòng)

5、態(tài)規(guī)劃算法的共同點(diǎn)。A、重疊子問(wèn)題B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、最優(yōu)子結(jié)構(gòu)性質(zhì)25. 矩陣連乘問(wèn)題的算法可由B設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法 B、動(dòng)態(tài)規(guī)劃算法 C、貪心算法 D、回溯算法26. 分支限界法解旅行售貨員問(wèn)題時(shí)，活結(jié)點(diǎn)表的組織形式是A 。A、最小堆B、最大堆 C、棧D、數(shù)組27、Strassen矩陣乘法是利用A 實(shí)現(xiàn)的算法。A、分治策略 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法29、使用分治法求解不需要滿足的條件是A 。A 子問(wèn)題必須是一樣的B 子問(wèn)題不能夠重復(fù)C 子問(wèn)題的解可以合并D 原問(wèn)題和子問(wèn)題使用相同的方法解30、下面問(wèn)題B 不能使用貪心法解決。A 單源最短路徑問(wèn)題 B N皇

6、后問(wèn)題 C 最小花費(fèi)生成樹問(wèn)題 D 背包問(wèn)題31、以下算法中不能解決0/1背包問(wèn)題的是A A 貪心法 B 動(dòng)態(tài)規(guī)劃 C 回溯法 D 分支限界法32、回溯法搜索狀態(tài)空間樹是按照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 。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法35以下是動(dòng)態(tài)規(guī)劃算法根本要素的是D 。A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子問(wèn)題重疊性質(zhì)36以下算法中通常以自底向下的方式求解最優(yōu)解

7、的是B 。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法37采用廣度優(yōu)先策略搜索的算法是A 。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法38、合并排序算法是利用A 實(shí)現(xiàn)的算法。A、分治策略 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法39、在以下算法中得到的解未必正確的選項(xiàng)是B 。A、蒙特卡羅算法 B、拉斯維加斯算法 C、舍伍德算法 D、數(shù)值概率算法40、背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為B A、On2n B、Onlogn C、O2n D、On41實(shí)現(xiàn)大整數(shù)的乘法是利用的算法C 。A、貪心法B、動(dòng)態(tài)規(guī)劃法C、分治策略D、回溯法420-1背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為A A、On2nB、Onl

8、ognC、O2nD、On43采用最大效益優(yōu)先搜索方式的算法是A 。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法44貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是B 。A、最優(yōu)子結(jié)構(gòu)B、貪心選擇性質(zhì)C、構(gòu)造最優(yōu)解D、定義最優(yōu)解45. 實(shí)現(xiàn)最大子段和利用的算法是B 。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法46.優(yōu)先隊(duì)列式分支限界法選取擴(kuò)展結(jié)點(diǎn)的原那么是C 。A、先進(jìn)先出B、后進(jìn)先出C、結(jié)點(diǎn)的優(yōu)先級(jí)D、隨機(jī)47.背包問(wèn)題的貪心算法所需的計(jì)算時(shí)間為B 。A、On2nB、OnlognC、O2nD、On48、廣度優(yōu)先是A 的一搜索方式。A、分支界限法 B、動(dòng)態(tài)規(guī)劃法 C、貪心法 D、回溯法49、舍伍德算法

9、是B 的一種。A、分支界限算法 B、概率算法 C、貪心算法 D、回溯算法50、在以下算法中有時(shí)找不到問(wèn)題解的是B 。A、蒙特卡羅算法 B、拉斯維加斯算法 C、舍伍德算法 D、數(shù)值概率算法51以下哪一種算法是隨機(jī)化算法D A. 貪心算法B. 回溯法C.動(dòng)態(tài)規(guī)劃算法D.舍伍德算法52. 一個(gè)問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問(wèn)題的B 。A、重疊子問(wèn)題B、最優(yōu)子結(jié)構(gòu)性質(zhì)C、貪心選擇性質(zhì)D、定義最優(yōu)解53采用貪心算法的最優(yōu)裝載問(wèn)題的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法的時(shí)間復(fù)雜度為 ( B ) 。A、On2nB、OnlognC、O2nD、On54. 以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題

10、解的算法稱為 ( D ) 。A、分支界限算法 B、概率算法 C、貪心算法 D、回溯算法55. 實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是B 。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法56、算法是由假設(shè)干條指令組成的有窮序列，而且滿足以下性質(zhì) D （1） 輸入：有0個(gè)或多個(gè)輸入（2） 輸出：至少有一個(gè)輸出（3） 確定性：指令清晰，無(wú)歧義（4） 有限性：指令執(zhí)行次數(shù)有限，而且執(zhí)行時(shí)間有限 A (1)(2)(3) B(1)(2)(4) C(1)(3)(4) D (1) (2)(3)(4)57、函數(shù)32n+10nlogn的漸進(jìn)表達(dá)式是( B ).A. 2n B. 32n C. nlogn D. 10nlog

11、n58、大整數(shù)乘法算法是( A ).算法A.分治 B.貪心C.動(dòng)態(tài)規(guī)劃 D.窮舉59、用動(dòng)態(tài)規(guī)劃算法解決最大字段和問(wèn)題，其時(shí)間復(fù)雜性為( B ).A.logn B.n C.n2 D.nlogn60、解決活動(dòng)安排問(wèn)題，最好用B 算法A.分治 B.貪心C.動(dòng)態(tài)規(guī)劃 D.窮舉61、設(shè)f(N),g(N)是定義在正數(shù)集上的正函數(shù),如果存在正的常數(shù)C和自然數(shù)N0,使得當(dāng)NN0時(shí)有f(N)Cg(N),那么稱函數(shù)f(N)當(dāng)N充分大時(shí)有下界g(N),記作f(N)(g(N),即f(N)的階( A )g(N)的階.A.不高于 B.不低于C.等價(jià)于 D.逼近62、回溯法在解空間樹T上的搜索方式是( A ).A.深度優(yōu)

12、先 B.廣度優(yōu)先 C.最小消耗優(yōu)先 D.活結(jié)點(diǎn)優(yōu)先63、回溯算法和分支限界法的問(wèn)題的解空間樹不會(huì)是(D ).A.有序樹 B.子集樹C.排列樹 D.無(wú)序樹64、在對(duì)問(wèn)題的解空間樹進(jìn)行搜索的方法中,一個(gè)活結(jié)點(diǎn)最多有一次時(shí)機(jī)成為活結(jié)點(diǎn)的是( B ).A.回溯法 B.分支限界法C.回溯法和分支限界法 D.回溯法求解子集樹問(wèn)題65、從活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)的不同方式將導(dǎo)致不同的分支限界法,以下除( C )之外都是最常見的方式.A.隊(duì)列式分支限界法 B.優(yōu)先隊(duì)列式分支限界法C.棧式分支限界法 D.FIFO分支限界法二、 填空題 1.算法的復(fù)雜性有 時(shí)間 復(fù)雜性和 空間 復(fù)雜性之分。2、程序是 算法用

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

14、算法是_數(shù)值概率算法，運(yùn)行時(shí)以一定的概率得到正確解的隨機(jī)算法是_蒙特卡羅算法_。14、解決0/1背包問(wèn)題可以使用動(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皇后問(wèn)題和0/1背包問(wèn)題正好是兩種不同的類型，其中同時(shí)使用約束條件和目標(biāo)函數(shù)的界進(jìn)行裁剪的是 0/1背包問(wèn)題 ，只使用約束條件進(jìn)行裁剪的是 N皇后問(wèn)題 。16、 貪心選擇性質(zhì) 是貪心算法可行的第一個(gè)根本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。17、矩陣連乘問(wèn)題的算法可由 動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。18、拉斯

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

16、的一種排序算法。28.動(dòng)態(tài)規(guī)劃算法的兩個(gè)根本要素是. 最優(yōu)子結(jié)構(gòu) 性質(zhì)和 重疊子問(wèn)題 性質(zhì) 。 30.回溯法是一種既帶有 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 31.分支限界法主要有 隊(duì)列式FIFO 分支限界法和 優(yōu)先隊(duì)列式 分支限界法。32分支限界法是一種既帶有 系統(tǒng)性 又帶有 跳躍性 的搜索算法。33回溯法搜索解空間樹時(shí)，常用的兩種剪枝函數(shù)為 約束函數(shù) 和 限界函數(shù) 。34.任何可用計(jì)算機(jī)求解的問(wèn)題所需的時(shí)間都與其 規(guī)模 有關(guān)。35.快速排序算法的性能取決于 劃分的對(duì)稱性 。36. Prim算法利用 貪心 策略求解 最小生成樹 問(wèn)題，其時(shí)間復(fù)雜度是 O(n2) 。37. 圖的m著色問(wèn)題可用

17、 回溯 法求解，其解空間樹中葉子結(jié)點(diǎn)個(gè)數(shù)是 mn ，解空間樹中每個(gè)內(nèi)結(jié)點(diǎn)的孩子數(shù)是 m 。三、算法填空1.背包問(wèn)題的貪心算法void Knapsack(int 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(int n, int a) int sum=0, b=0； /sum存儲(chǔ)當(dāng)前最大的bj, b存儲(chǔ)bj fo

18、r(int j=1； j0) b+= aj ； else b=ai; ； /一旦某個(gè)區(qū)段和為負(fù)，那么從下一個(gè)位置累和 if(bsum) sum=b; return sum； 3.快速排序templatevoid QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); /對(duì)左半段排序 QuickSort (a,q+1,r); /對(duì)右半段排序 4.排列問(wèn)題Template void perm(Type list, int k, int m ) /產(chǎn)生listk:m的所有排列 if(k

19、=m) /只剩下一個(gè)元素 for (int i=0;i=m;i+) coutlisti; coutendl; else /還有多個(gè)元素待排列，遞歸產(chǎn)生排列 for (int i=k; i=m; i+) swap(listk，listi); perm(list,k+1;m); swap(listk,listi); 5.給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。 據(jù)此容易設(shè)計(jì)出二分搜索算法：template int BinarySearch(Type a, const Type& x, int l, int r) while (l=r ) int m = (l+

20、r)/2); if (x = am) return m; if (x am) r = m-1; else l = m+1; return -1; 6、合并排序描述如下：templatevoid Mergesort(Type a , int left, int right)if (left0) y=y*x; (return y);四、問(wèn)答題1.用計(jì)算機(jī)求解問(wèn)題的步驟：1、問(wèn)題分析2、數(shù)學(xué)模型建立3、算法設(shè)計(jì)與選擇4、算法指標(biāo)5、算法分析6、算法實(shí)現(xiàn)7、程序調(diào)試8、結(jié)果整理文檔編制2. 算法定義：算法是指在解決問(wèn)題時(shí)，按照某種機(jī)械步驟一定可以得到問(wèn)題結(jié)果的處理過(guò)程3.算法的三要素1、操作2、控制結(jié)

21、構(gòu)3、數(shù)據(jù)結(jié)構(gòu)4. 算法具有以下5個(gè)屬性：有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。確定性：算法中每一條指令必須有確切的含義。不存在二義性。只有一個(gè)入口和一個(gè)出口可行性：一個(gè)算法是可行的就是算法描述的操作是可以通過(guò)已經(jīng)實(shí)現(xiàn)的根本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定對(duì)象的集合。輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出同輸入有著某些特定關(guān)系的量。5. 算法設(shè)計(jì)的質(zhì)量指標(biāo)：正確性：算法應(yīng)滿足具體問(wèn)題的需求；可讀性：算法應(yīng)該好讀，以有利于讀者對(duì)程序的理解；健壯性：算法應(yīng)具有容錯(cuò)處理，當(dāng)輸入為非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反響，而不是

22、產(chǎn)生莫名其妙的輸出結(jié)果。效率與存儲(chǔ)量需求：效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。一般這兩者與問(wèn)題的規(guī)模有關(guān)。經(jīng)常采用的算法主要有迭代法、分治法、貪婪法、動(dòng)態(tài)規(guī)劃法、回溯法、分支限界法6. 迭代法: 也稱“輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推出新值的解決問(wèn)題的方法。7.利用迭代算法解決問(wèn)題，需要做好以下三個(gè)方面的工作：1)、確定迭代模型。在可以用迭代算法解決的問(wèn)題中，至少存在一個(gè)直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。2)、建立迭代關(guān)系式。所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式或關(guān)系。迭代關(guān)系式的建立是解決迭代問(wèn)題的關(guān)鍵

23、，通?？梢允褂眠f推或倒推的方法來(lái)完成。3)、對(duì)迭代過(guò)程進(jìn)行控制。在什么時(shí)候結(jié)束迭代過(guò)程？這是編寫迭代程序必須考慮的問(wèn)題。不能讓迭代過(guò)程無(wú)休止地重復(fù)執(zhí)行下去。迭代過(guò)程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來(lái)；另一種是所需的迭代次數(shù)無(wú)法確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來(lái)實(shí)現(xiàn)對(duì)迭代過(guò)程的控制；對(duì)于后一種情況，需要進(jìn)一步分析出用來(lái)結(jié)束迭代過(guò)程的條件。8.分治法的根本思想是：將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同。遞歸地解這些子問(wèn)題，然后將各個(gè)子問(wèn)題的解合并得到原問(wèn)題的解。9.分治法所能解決的問(wèn)題一般具有以下幾個(gè)特

24、征： 1該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決； 2該問(wèn)題可以分解為假設(shè)干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； 3利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解； 4該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子子問(wèn)題。 10、分治法的根本步驟 分治法在每一層遞歸上都有三個(gè)步驟： 1分解：將原問(wèn)題分解為假設(shè)干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題； 2解決：假設(shè)子問(wèn)題規(guī)模較小而容易被解決那么直接解，否那么遞歸地解各個(gè)子問(wèn)題； 3合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。11. 動(dòng)態(tài)規(guī)劃的根本思想前文主要介紹了動(dòng)態(tài)規(guī)劃的一些理論依據(jù)，我們將前文所說(shuō)

25、的具有明顯的階段劃分和狀態(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ī)劃是在研究多階段決策問(wèn)題時(shí)推導(dǎo)出來(lái)的，具有嚴(yán)格的數(shù)學(xué)形式，適合用于理論上的分析。在實(shí)際應(yīng)用中，許多問(wèn)題的階段劃分并不明顯，這時(shí)如果刻意地劃分階段法反而麻煩。一般來(lái)說(shuō)，只要該問(wèn)題可以劃分成規(guī)模更小的子問(wèn)題，并且原問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解即滿足最優(yōu)子化原理，那么可以考慮用動(dòng)態(tài)規(guī)劃解決。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問(wèn)題實(shí)例分解為更小的、相似的子問(wèn)題，并存儲(chǔ)子問(wèn)題的解而防止計(jì)算重復(fù)的子問(wèn)題，以解決最優(yōu)化問(wèn)題的算法策略。由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問(wèn)題實(shí)例歸納為更小

26、的、相似的子問(wèn)題，并通過(guò)求解子問(wèn)題產(chǎn)生一個(gè)全局最優(yōu)解。貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問(wèn)題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個(gè)子問(wèn)題是獨(dú)立的即不包含公共的子問(wèn)題，因此一旦遞歸地求出各子問(wèn)題的解后，便可自下而上地將子問(wèn)題的解合并成問(wèn)題的解。缺乏之處：如果當(dāng)前選擇可能要依賴子問(wèn)題的解時(shí)，那么難以通過(guò)局部的貪心策略到達(dá)全局最優(yōu)解；如果各子問(wèn)題是不獨(dú)立的，那么分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題。解決上述問(wèn)題的方法是利用動(dòng)態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問(wèn)題，這類問(wèn)題會(huì)有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最

27、優(yōu)最大或最小值的解。假設(shè)存在假設(shè)干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過(guò)程中，該方法也是通過(guò)求解局部子問(wèn)題的解到達(dá)全局最優(yōu)解，但與分治法和貪心法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問(wèn)題不獨(dú)立，亦即各子問(wèn)題可包含公共的子問(wèn)題也允許其通過(guò)自身子問(wèn)題的解作出選擇，該方法對(duì)每一個(gè)子問(wèn)題只解一次，并將結(jié)果保存起來(lái)，防止每次碰到時(shí)都要重復(fù)計(jì)算。因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問(wèn)題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問(wèn)題樹中的子問(wèn)題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到時(shí)加以求解，并把答案保存起來(lái)，讓以后再遇到時(shí)直接引用，不必重新求解。12、動(dòng)態(tài)規(guī)劃算法的根本步驟設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)

28、規(guī)劃算法，通常可按以下幾個(gè)步驟進(jìn)行：1劃分階段：按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為假設(shè)干個(gè)階段。注意這假設(shè)干個(gè)階段一定要是有序的或者是可排序的即無(wú)后向性，否那么問(wèn)題就無(wú)法用動(dòng)態(tài)規(guī)劃求解。 2選擇狀態(tài)：將問(wèn)題開展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿足無(wú)后效性。 3確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來(lái)了。但事實(shí)上，我們常常是反過(guò)來(lái)做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來(lái)確定決策。 4寫出規(guī)劃方程包括邊界條件：

29、動(dòng)態(tài)規(guī)劃的根本方程是規(guī)劃方程的通用形式化表達(dá)式。一般說(shuō)來(lái)，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比擬簡(jiǎn)單的。動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)局部就會(huì)非常簡(jiǎ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)行：1分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 2遞歸地定義最優(yōu)值。 3以自底向上的方式或自頂向下的記憶化方法備忘錄法計(jì)算出最優(yōu)值。 4根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。 步驟13是動(dòng)態(tài)規(guī)劃算法的根本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略，假設(shè)需要求出問(wèn)

30、題的一個(gè)最優(yōu)解，那么必須執(zhí)行步驟4。此時(shí)，在步驟3中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟4中，根據(jù)所記錄的信息，快速地構(gòu)造出一個(gè)最優(yōu)解?？偨Y(jié)：動(dòng)態(tài)規(guī)劃實(shí)際上就是最優(yōu)化的問(wèn)題，是指將原問(wèn)題的大實(shí)例等價(jià)于同一最優(yōu)化問(wèn)題的較小實(shí)例，自底向上的求解最小實(shí)例，并將所求解存放起來(lái)，存放的結(jié)果就是為了準(zhǔn)備數(shù)據(jù)。與遞歸相比，遞歸是不斷的調(diào)用子程序求解，是自頂向下的調(diào)用和求解。13. 分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)是：將待求解的問(wèn)題分解成假設(shè)干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。兩者的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。而用分治法求解的問(wèn)題

31、，經(jīng)分解得到的子問(wèn)題往往是互相獨(dú)立的。14. 回溯法 回溯法也稱為試探法，該方法首先暫時(shí)放棄關(guān)于問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)，就選擇下一個(gè)候選解；倘假設(shè)當(dāng)前候選解除了還不滿足問(wèn)題規(guī)模要求外，滿足所有其他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問(wèn)題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問(wèn)題的一個(gè)解。在回溯法中，放棄當(dāng)前候選解，尋找下一個(gè)候選解的過(guò)程稱為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過(guò)程稱為向前試探。15. 分支限界法：這是一種用于求解組合優(yōu)化問(wèn)題的排除非解的搜索算法。類似于回溯法，分枝定界法在搜索解空

32、間時(shí)，也經(jīng)常使用樹形結(jié)構(gòu)來(lái)組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小消耗方法來(lái)搜索這些樹。因此，可以很容易比擬回溯法與分枝定界法的異同。相對(duì)而言，分枝定界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。 算法思想：分枝限界branch and bound是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對(duì)E-節(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次時(shí)機(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)表

33、，然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充過(guò)程才結(jié)束。 有兩種常用的方法可用來(lái)選擇下一個(gè)E-節(jié)點(diǎn)雖然也可能存在其他的方法： 1) 先進(jìn)先出F I F O 即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的順序與參加節(jié)點(diǎn)的順序相同，因此活 節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。 2) 優(yōu)先隊(duì)列最小消耗或最大收益法在這種模式中，每個(gè)節(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的消耗或收益。如果查找 一個(gè)具有最小消耗的解，那么活節(jié)點(diǎn)表可用最小堆來(lái)建立，下一個(gè)E-節(jié)點(diǎn)就是具有最小消耗 的活節(jié)點(diǎn)；如果希望搜索一個(gè)具有最大收益的解，那么可用最大堆來(lái)構(gòu)造活節(jié)點(diǎn)表，下一個(gè) E-節(jié)點(diǎn)是具有最大收益的活節(jié)點(diǎn)16

34、. 分支限界法與回溯法的相同點(diǎn)是：都是一種在問(wèn)題的解空間樹T中搜索問(wèn)題解的算法。不同點(diǎn)：1求解目標(biāo)不同； 2搜索方式不同； 3對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同； 4存儲(chǔ)空間的要求不同。17. 分治法所能解決的問(wèn)題一般具有的幾個(gè)特征是：1該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決； 2該問(wèn)題可以分解為假設(shè)干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì); 3利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解； 4原問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。18. 用分支限界法設(shè)計(jì)算法的步驟是：(1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間對(duì)解進(jìn)行編碼； (2)確定易于搜索的解空間結(jié)構(gòu)

35、按樹或圖組織解 ； (3)以廣度優(yōu)先或以最小消耗最大收益優(yōu)先的方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)防止無(wú)效搜索。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)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。20. 回溯法中常見的兩類典型的解空間樹是子集樹和排列樹。當(dāng)所給的問(wèn)題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹。這類子集樹通常有2n個(gè)葉結(jié)點(diǎn)，遍歷子集樹需O(2n)計(jì)算時(shí)間 。當(dāng)所給的問(wèn)題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空

36、間樹稱為排列樹。這類排列樹通常有n!個(gè)葉結(jié)點(diǎn)。遍歷排列樹需要O(n!)計(jì)算時(shí)間。21. 分支限界法的搜索策略是： 在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)分支，然后再?gòu)漠?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. 請(qǐng)表達(dá)動(dòng)態(tài)規(guī)劃算法與貪心算法的異同。共同點(diǎn)：都需要最優(yōu)子結(jié)構(gòu)性質(zhì)，都用來(lái)求有優(yōu)化問(wèn)題。不同點(diǎn)：動(dòng)態(tài)規(guī)劃：每一步作一個(gè)選擇依賴于子問(wèn)題的解。 貪心方法：每一步作一個(gè)選擇不依賴于子問(wèn)題的

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

38、在小根堆中，將元素x插入到堆的末尾，然后將元素x的關(guān)鍵字與其雙親的關(guān)鍵字比擬，假設(shè)元素x的關(guān)鍵字小于其雙親的關(guān)鍵字，那么將元素x與其雙親交換，然后再將元素x與其新雙親的關(guān)鍵字相比，直到元素x的關(guān)鍵字大于雙親的關(guān)鍵字，或元素x到根為止。3O( log n) 25. 衡量算法時(shí)間效率的方法有哪兩種？請(qǐng)表達(dá)。答：有事前分析法和事后分析法兩種。事后分析法：先將算法用程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)，然后度量程序的運(yùn)行時(shí)間。事前分析法：算法的時(shí)間效率是問(wèn)題規(guī)模的函數(shù)，假設(shè)，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和函數(shù)f(n)的增長(zhǎng)率相同，那么可記作： T(n)=(f(n)稱T(n)為算法的漸進(jìn)時(shí)間復(fù)雜度。簡(jiǎn)稱時(shí)間復(fù)

39、雜度。26. 在算法復(fù)雜性分析中，O、這三個(gè)記號(hào)的意義是什么？在忽略常數(shù)因子的情況 下，O、分別提供了算法運(yùn)行時(shí)間的什么界？答：如果存在兩個(gè)正常數(shù)c和N0,對(duì)于所有的NN0，有|f(N)|C|g(N)|，那么記作：f(N)= O(g(N)。這時(shí)我們說(shuō)f(N)的階不高于g(N)的階。假設(shè)存在兩個(gè)正常數(shù)C和自然數(shù)N0，使得當(dāng)N N0時(shí)有|f(N)|C|g(N)|，記為f(N)=(g(N)。這時(shí)我們說(shuō)f(N)的階不低于g(N)的階。如果存在正常數(shù)c1，c2和n0，對(duì)于所有的nn0，有c1|g(N)| |f(N)| c2|g(N)| 那么記作 f(N)= (g,(N)O、分別提供了算法運(yùn)行時(shí)間的上界、

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

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

42、拉斯維加斯算法不會(huì)得到不正確的解，一旦用拉斯維加斯算法找到一個(gè)解，那么這個(gè)解肯定是正確的。但是有時(shí)候用拉斯維加斯算法可能找不到解。與蒙特卡羅算法類似。拉斯維加斯算法得到正確解的概率隨著它用的計(jì)算時(shí)間的增加而提高。對(duì)于所求解問(wèn)題的任一實(shí)例，用同一拉斯維加斯算法反復(fù)對(duì)該實(shí)例求解足夠?qū)掖危墒骨蠼馐У母怕嗜我庑　?33.舍伍德算法總能求得問(wèn)題的一個(gè)解，且所求得的解總是正確的。當(dāng)一個(gè)確定性算法在最壞情況下的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有較大差異時(shí)，可以在這個(gè)確定算法中引入隨機(jī)性將它改造成一個(gè)舍伍德算法，消除或減少問(wèn)題的好壞實(shí)例間的這種差異。舍伍德算法精髓不是防止算法的最壞情況行為，而是設(shè)法

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

44、1 2 20 1 1 2 2 最長(zhǎng)公共子序列：2對(duì)以下各組函數(shù)f (n) 和g (n)，確定f (n) = O (g (n) 或f (n) =(g (n)或f(n) =(g(n)，并簡(jiǎn)要說(shuō)明理由。(1) f(n)=2n； g(n)=n! (2) f(n)=； g (n)=log n2 (3) f(n)=100； g(n)=log100 (4) f(n)=n3； g(n)= 3n(5) f(n)=3n； g(n)=2n答： (1) f(n) = O(g(n) 因?yàn)間(n)的階比f(wàn)(n)的階高。(2) f(n) = (g(n) 因?yàn)間(n)的階比f(wàn)(n)的階低。(3) f(n) = (g(n) 因?yàn)間(n)與f(n)同階。(4) f(n) = O(g(n) 因?yàn)間(n)的階比f(wàn)(n)的階高。(5) f(n) = (g(n) 因?yàn)間(n)的階比f(wàn)(n)的階低。3對(duì)以下圖所示的連通網(wǎng)絡(luò)G，用克魯斯卡爾(Kruskal)算法求G的最小生成樹T,請(qǐng)寫出在算法執(zhí)行過(guò)程中，依次參加T的邊集TE中的邊。說(shuō)明該算法的貪心策略和