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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上填空題動(dòng)態(tài)規(guī)劃算法的基本要素為：最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問(wèn)題性質(zhì)1) 算法分析中，記號(hào)O表示漸進(jìn)上界，記號(hào)表示漸進(jìn)下界， 記號(hào)表示緊漸進(jìn)界。2) 回溯法在問(wèn)題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。3) 分支限界法在問(wèn)題的解空間樹中，按廣度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。所謂貪心選擇性質(zhì)是指（所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到）。所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指（問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解）。回溯法是回溯法是指（具有限界函數(shù)的深度優(yōu)先生成法）?；厮莘ǖ乃惴蚣馨凑諉?wèn)題的解空間一般分為（子集樹）算法框架與（排列樹）算法框架

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

3、有窮性，確定性，可行性，輸入，輸出。1.算法的復(fù)雜性有 時(shí)間 復(fù)雜性和 空間 復(fù)雜性之分。2、程序是 算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。3、算法的“確定性”指的是組成算法的每條 指令 是清晰的，無(wú)歧義的。4.矩陣連乘問(wèn)題的算法可由 動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。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)題 的求解。15、使用回溯法進(jìn)行狀態(tài)空間樹裁剪分支時(shí)一般有兩個(gè)

4、標(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)。19.貪心算法的基本要素是 貪心選擇 質(zhì)和 最優(yōu)子結(jié)構(gòu) 性質(zhì) 。21. 動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干 子問(wèn)題 ，先求解 子問(wèn)題 ，然后從這些 子問(wèn)題 的解得到原問(wèn)題的解。23、大整數(shù)乘積算法是用 分治法 來(lái)設(shè)計(jì)的。26、 貪心選擇性質(zhì) 是貪心算法可行的第

5、一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。27.快速排序算法是基于 分治策略 的一種排序算法。30.回溯法是一種既帶有 系統(tǒng)性 又帶有 跳躍性 的搜索算法。 33回溯法搜索解空間樹時(shí)，常用的兩種剪枝函數(shù)為 約束函數(shù) 和 限界函數(shù) 。34.任何可用計(jì)算機(jī)求解的問(wèn)題所需的時(shí)間都與其 規(guī)模 有關(guān)。35.快速排序算法的性能取決于 劃分的對(duì)稱性 。37. 圖的m著色問(wèn)題可用 回溯 法求解，其解空間樹中葉子結(jié)點(diǎn)個(gè)數(shù)是 mn ，解空間樹中每個(gè)內(nèi)結(jié)點(diǎn)的孩子數(shù)是 m 。簡(jiǎ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é)

6、果整理文檔編制2.最優(yōu)二叉搜索樹問(wèn)題的動(dòng)態(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í)）。寫成遞歸函數(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. 算法定義：算法是指在解決問(wèn)題時(shí)，按照某種機(jī)械步驟一定可以得到問(wèn)題結(jié)果的處理過(guò)程3.算法的三要素1、操作2、控制結(jié)構(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ì)

8、象的集合。輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出同輸入有著某些特定關(guān)系的量。經(jīng)常采用的算法主要有迭代法、分治法、貪婪法、動(dòng)態(tài)規(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è)特征： （1）該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決； （2）該問(wèn)題可以分解為若干個(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ú)立的

9、，即子問(wèn)題之間不包含公共的子子問(wèn)題。 10、分治法的基本步驟 分治法在每一層遞歸上都有三個(gè)步驟： （1）分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題； （2）解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題； （3）合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。11. 動(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)題的算法策略。13. 分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)是：將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原

10、問(wèn)題的解。兩者的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。而用分治法求解的問(wèn)題，經(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è)候選解；倘若當(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ò)程稱為向

11、前試探。20. 回溯法中常見(jiàn)的兩類典型的解空間樹是子集樹和排列樹。當(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)的解空間樹稱為排列樹。這類排列樹通常有n!個(gè)葉結(jié)點(diǎn)。遍歷排列樹需要O(n!)計(jì)算時(shí)間。22. 請(qǐng)敘述動(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)題的解。動(dòng)態(tài)規(guī)劃方法的條件：子問(wèn)題的重疊性質(zhì)。 可用貪心方法

12、的條件：最優(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. 請(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).26. 在算法復(fù)雜性分析中，O、這三個(gè)記號(hào)的意義是什么？在忽略常數(shù)因子的情況 下，O、分別提供了算法運(yùn)行時(shí)間的什么界？答：如果存在兩個(gè)正常數(shù)c和N0,對(duì)于所有的NN0，有|f(N)|C|g(

13、N)|，則記作：f(N)= O(g(N)。這時(shí)我們說(shuō)f(N)的階不高于g(N)的階。若存在兩個(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í)間的上界、下界、平均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ò)程。答：

14、(1) (2)0 0 0 00 0 1 1 10 0 1 2 20 0 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)

15、 因?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ō)明該算法的貪心策略和算法的基本思想，并簡(jiǎn)要分析算法的時(shí)間復(fù)雜度。12345618111715192126679答：TE=(3,4), (2,3),(1,5),（4,6）（4,5） 貪心策略是每次都在連接兩個(gè)不同連通分量的邊中選權(quán)值

16、最小的邊。基本思想：首先將圖中所有頂點(diǎn)都放到生成樹中，然后每次都在連接兩個(gè)不同連通分量的邊中選權(quán)值最小的邊，將其放入生成樹中，直到生成樹中有n-1條邊。時(shí)間復(fù)雜度為：O(eloge) 4. 請(qǐng)用分治策略設(shè)計(jì)遞歸的歸并排序算法，并分析其時(shí)間復(fù)雜性（要求：分別給出divide、conquer、combine這三個(gè)階段所花的時(shí)間，并在此基礎(chǔ)上列出遞歸方程，最后用套用公式法求出其解的漸進(jìn)階）。答 ： Template void MergeSort (Type a , int left, int right) if (left2）；T(2)=1。因?yàn)?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. 考慮使用動(dòng)態(tài)規(guī)劃方法求解下列問(wèn)題：01背包數(shù)據(jù)如下表，求：能夠放入背包的最有價(jià)值的物品集合。物品i重量 wi價(jià)值 vi承重量 W1w1=2v1=12W=52w2=1v2=103w3=3v3=204w4=2v4=15如設(shè)： V(i, j) 前 i 個(gè)物品中能夠裝入承重量 j 的背包中的最大總價(jià)值。請(qǐng)將如下遞推式填寫完整：V(0, j) = 0（0個(gè)物品），V(i, 0) = 0（承重量0） V(i, j) = V(i-1, j) 第 i 個(gè)物品不能裝入， j wi （不超重） i在最優(yōu)子集中 i不在最優(yōu)子集中自底向上：按行或列填寫下表。Vj=012345i=000000010203040Vj=012345i=000000010203040答：V(0, j) = 0（0個(gè)物品），V(i, 0) = 0（承重量0）V(i, j) = V(i-1, j) 第 i 個(gè)物品不能裝入， j wi （不超重） i在最優(yōu)子集中 i不在最優(yōu)子集中Vj=012345i=000000010203040Vj=012345