算法復(fù)習(xí)題(精煉版)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上填空題動態(tài)規(guī)劃算法的基本要素為：最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)1) 算法分析中，記號O表示漸進上界，記號表示漸進下界， 記號表示緊漸進界。2) 回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。3) 分支限界法在問題的解空間樹中，按廣度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。所謂貪心選擇性質(zhì)是指（所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到）。所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指（問題的最優(yōu)解包含了其子問題的最優(yōu)解）?；厮莘ㄊ腔厮莘ㄊ侵福ň哂邢藿绾瘮?shù)的深度優(yōu)先生成法）。回溯法的算法框架按照問題的解空間一般分為（子集樹）算法框架與（排列樹）算法框架

2、。4) 二分搜索算法是利用分治策略實現(xiàn)的算法。5) 衡量一個算法好壞的標(biāo)準(zhǔn)是時間復(fù)雜度低6) 最長公共子序列算法利用的算法是動態(tài)規(guī)劃法7) Strassen矩陣乘法是利用分治策略實現(xiàn)的算法8) 回溯法搜索狀態(tài)空間樹是按照深度優(yōu)先遍歷的順序。9) 算法中通常以自底向下的方式求解最優(yōu)解的是動態(tài)規(guī)劃法10) 背包問題的貪心算法所需的計算時間為O（nlogn）11) 0-1背包問題的回溯算法所需的計算時間為O（n2n）12) 用動態(tài)規(guī)劃算法解決最大字段和問題，其時間復(fù)雜性為n13) 一個算法就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類型問題的一系列運算，此外，算法還應(yīng)具有以下五個重要特性:_

3、有窮性，確定性，可行性，輸入，輸出。1.算法的復(fù)雜性有 時間 復(fù)雜性和 空間 復(fù)雜性之分。2、程序是 算法用某種程序設(shè)計語言的具體實現(xiàn)。3、算法的“確定性”指的是組成算法的每條 指令 是清晰的，無歧義的。4.矩陣連乘問題的算法可由 動態(tài)規(guī)劃 設(shè)計實現(xiàn)。6、算法是指解決問題的 一種方法 或 一個過程 。7、從分治法的一般設(shè)計模式可以看出，用它設(shè)計出的程序一般是 遞歸算法 。8、問題的 最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。9、以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 回溯法 。10、數(shù)值概率算法常用于 數(shù)值問題 的求解。15、使用回溯法進行狀態(tài)空間樹裁剪分支時一般有兩個

4、標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標(biāo)函數(shù)的界進行裁剪的是 0/1背包問題 ，只使用約束條件進行裁剪的是 N皇后問題 。16、 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。17、矩陣連乘問題的算法可由 動態(tài)規(guī)劃 設(shè)計實現(xiàn)。19.貪心算法的基本要素是 貪心選擇 質(zhì)和 最優(yōu)子結(jié)構(gòu) 性質(zhì) 。21. 動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干 子問題 ，先求解 子問題 ，然后從這些 子問題 的解得到原問題的解。23、大整數(shù)乘積算法是用 分治法 來設(shè)計的。26、 貪心選擇性質(zhì) 是貪心算法可行的第

5、一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。27.快速排序算法是基于 分治策略 的一種排序算法。30.回溯法是一種既帶有 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 33回溯法搜索解空間樹時，常用的兩種剪枝函數(shù)為 約束函數(shù) 和 限界函數(shù) 。34.任何可用計算機求解的問題所需的時間都與其 規(guī)模 有關(guān)。35.快速排序算法的性能取決于 劃分的對稱性 。37. 圖的m著色問題可用 回溯 法求解，其解空間樹中葉子結(jié)點個數(shù)是 mn ，解空間樹中每個內(nèi)結(jié)點的孩子數(shù)是 m 。簡答題1.用計算機求解問題的步驟：1、問題分析2、數(shù)學(xué)模型建立3、算法設(shè)計與選擇4、算法指標(biāo)5、算法分析6、算法實現(xiàn)7、程序調(diào)試8、結(jié)

6、果整理文檔編制2.最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法void binarysearchtree(int a,int b,int n,int *m,int *s,int *w) int i,j,k,t,l; for(i=1;i=n+1;i+) wii-1=ai-1; mii-1=0; for(l=0;l=n-1;l+)/-l是下標(biāo)j-i的差for(i=1;i=n-l;i+) j=i+l;wij=wij-1+aj+bj;mij=mii-1+mi+1j+wij;sij=i;for(k=i+1;k=j;k+) t=mik-1+mk+1j+wij;if(t1時）。寫成遞歸函數(shù)有：int fib(int n

7、) if (n=0) return 0;if (n=1) return 1;if (n1) return fib(n-1)+fib(n-2);2. 算法定義：算法是指在解決問題時，按照某種機械步驟一定可以得到問題結(jié)果的處理過程3.算法的三要素1、操作2、控制結(jié)構(gòu)3、數(shù)據(jù)結(jié)構(gòu)4. 算法具有以下5個屬性：有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。確定性：算法中每一條指令必須有確切的含義。不存在二義性。只有一個入口和一個出口可行性：一個算法是可行的就是算法描述的操作是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定對

8、象的集合。輸出：一個算法有一個或多個輸出，這些輸出同輸入有著某些特定關(guān)系的量。經(jīng)常采用的算法主要有迭代法、分治法、貪婪法、動態(tài)規(guī)劃法、回溯法、分支限界法8.分治法的基本思想是：將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。9.分治法所能解決的問題一般具有以下幾個特征： （1）該問題的規(guī)?？s小到一定的程度就可以容易地解決； （2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； （3）利用該問題分解出的子問題的解可以合并為該問題的解； （4）該問題所分解出的各個子問題是相互獨立的

9、，即子問題之間不包含公共的子子問題。 10、分治法的基本步驟 分治法在每一層遞歸上都有三個步驟： （1）分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題； （2）解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題； （3）合并：將各個子問題的解合并為原問題的解。11. 動態(tài)規(guī)劃的基本思想動態(tài)規(guī)劃的實質(zhì)是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。13. 分治法與動態(tài)規(guī)劃法的相同點是：將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原

10、問題的解。兩者的不同點是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨立的。14. 回溯法 回溯法也稱為試探法，該方法首先暫時放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時，就選擇下一個候選解；倘若當(dāng)前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當(dāng)前候選解，尋找下一個候選解的過程稱為回溯。擴大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過程稱為向

11、前試探。20. 回溯法中常見的兩類典型的解空間樹是子集樹和排列樹。當(dāng)所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應(yīng)的解空間樹稱為子集樹。這類子集樹通常有2n個葉結(jié)點，遍歷子集樹需O(2n)計算時間 。當(dāng)所給的問題是確定n個元素滿足某種性質(zhì)的排列時，相應(yīng)的解空間樹稱為排列樹。這類排列樹通常有n!個葉結(jié)點。遍歷排列樹需要O(n!)計算時間。22. 請敘述動態(tài)規(guī)劃算法與貪心算法的異同。共同點：都需要最優(yōu)子結(jié)構(gòu)性質(zhì)，都用來求有優(yōu)化問題。不同點：動態(tài)規(guī)劃：每一步作一個選擇依賴于子問題的解。 貪心方法：每一步作一個選擇不依賴于子問題的解。動態(tài)規(guī)劃方法的條件：子問題的重疊性質(zhì)。 可用貪心方法

12、的條件：最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心選擇性質(zhì)。動態(tài)規(guī)劃：自底向上求解； 貪心方法： 自頂向下求解?？捎秘澬姆〞r，動態(tài)規(guī)劃方法可能不適用； 可用動態(tài)規(guī)劃方法時，貪心法可能不適用。23. 請說明動態(tài)規(guī)劃方法為什么需要最優(yōu)子結(jié)構(gòu)性質(zhì)。答：最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問題的最優(yōu)解包含子問題的最優(yōu)解。動態(tài)規(guī)劃方法是自底向上計算各個子問題的最優(yōu)解，即先計算子問題的最優(yōu)解，然后再利用子問題的最優(yōu)解構(gòu)造大問題的最優(yōu)解，因此需要最優(yōu)子結(jié)構(gòu).26. 在算法復(fù)雜性分析中，O、這三個記號的意義是什么？在忽略常數(shù)因子的情況 下，O、分別提供了算法運行時間的什么界？答：如果存在兩個正常數(shù)c和N0,對于所有的NN0，有|f(N)|C|g(

13、N)|，則記作：f(N)= O(g(N)。這時我們說f(N)的階不高于g(N)的階。若存在兩個正常數(shù)C和自然數(shù)N0，使得當(dāng)N N0時有|f(N)|C|g(N)|，記為f(N)=(g(N)。這時我們說f(N)的階不低于g(N)的階。如果存在正常數(shù)c1，c2和n0，對于所有的nn0，有c1|g(N)| |f(N)| c2|g(N)| 則記作 f(N)= (g,(N)O、分別提供了算法運行時間的上界、下界、平均1用動態(tài)規(guī)劃策略求解最長公共子序列問題： （1）給出計算最優(yōu)值的遞歸方程。 （2）給定兩個序列X=B,C,D,A，Y=A,B,C,B，請采用動態(tài)規(guī)劃策略求出其最長公共子序列，要求給出過程。答：

14、(1) (2)0 0 0 00 0 1 1 10 0 1 2 20 0 1 2 20 1 1 2 2 最長公共子序列：2對下列各組函數(shù)f (n) 和g (n)，確定f (n) = O (g (n) 或f (n) =(g (n)或f(n) =(g(n)，并簡要說明理由。(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) 因為g(n)的階比f(n)的階高。(2) f(n) = (g(n)

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

16、最小的邊?；舅枷耄菏紫葘D中所有頂點都放到生成樹中，然后每次都在連接兩個不同連通分量的邊中選權(quán)值最小的邊，將其放入生成樹中，直到生成樹中有n-1條邊。時間復(fù)雜度為：O(eloge) 4. 請用分治策略設(shè)計遞歸的歸并排序算法，并分析其時間復(fù)雜性（要求：分別給出divide、conquer、combine這三個階段所花的時間，并在此基礎(chǔ)上列出遞歸方程，最后用套用公式法求出其解的漸進階）。答 ： Template void MergeSort (Type a , int left, int right) if (left2）；T(2)=1。因為 n=2 k（k 為正整數(shù)），所以，T(n)= T(2

17、 k)= 2T(2 k-1)+2= 22T(2 k-2)+ 22+2= 2k-1T(2)+ 2k-2+23+22+2= 2k-1+23+22+2。因此，T(n)=Q(n)。8. 考慮使用動態(tài)規(guī)劃方法求解下列問題：01背包數(shù)據(jù)如下表，求：能夠放入背包的最有價值的物品集合。物品i重量 wi價值 vi承重量 W1w1=2v1=12W=52w2=1v2=103w3=3v3=204w4=2v4=15如設(shè)： V(i, j) 前 i 個物品中能夠裝入承重量 j 的背包中的最大總價值。請將如下遞推式填寫完整：V(0, j) = 0（0個物品），V(i, 0) = 0（承重量0） V(i, j) = V(i-1, j) 第 i 個物品不能裝入， j wi （不超重） i在最優(yōu)子集中 i不在最優(yōu)子集中自底向上：按行或列填寫下表。Vj=012345i=000000010203040Vj=012345i=000000010203040答：V(0, j) = 0（0個物品），V(i, 0) = 0（承重量0）V(i, j) = V(i-1, j) 第 i 個物品不能裝入， j wi （不超重） i在最優(yōu)子集中 i不在最優(yōu)子集中Vj=012345i=000000010203040Vj=012345