2015算法設(shè)計與分析報告復(fù)習試題及問題詳解

1、1. 一個算法就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類型問題的一系列運算，此外，算法還應(yīng)具有以下五個重要特性:,。2. 算法的復(fù)雜性有 和 分，衡量一個算法好壞的標準是。3. 某一問題可用動態(tài)規(guī)劃算法求解的顯著特征是4. 若序列 X二B,C,A,D,B,C,D，Y二A,C,B,A,B,D,C,D，請給出序列 X禾廿Y的一個最長公共子序列 。5. 用回溯法解問題時，應(yīng)明確定義問題的解空間，問題的解空間至少應(yīng)包含。6. 動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干，先求解然后從這些的 解得到原問題的解。7. 以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 。8.0-1背包問題的回溯算法所需

2、的計算時間為，用動態(tài)規(guī)劃算法所需的計算時間為。9. 動態(tài)規(guī)劃算法的兩個基本要素是 和。10. 二分搜索算法是利用 現(xiàn)的算法。二、綜合題（50分）1. 寫出設(shè)計動態(tài)規(guī)劃算法的主要步驟。2. 流水作業(yè)調(diào)度問題的johnson算法的思想。3. 若n=4,在機器M1和M2上加工作業(yè)i所需的時間分別為 日和bi,且（ai,a2,a3,a4）=（4,5,12,10），（bi,b2,b3,b4）=（8,2,15,9） 求 4 個作業(yè)的最優(yōu)調(diào)度方案，并計算最優(yōu)值。4. 使用回溯法解 0/1 背包問題：n=3, C=9, V二6,10,3，W二3,4,4, 其解空間有長度為3的0-1向量組成，要求用一棵完全二叉

3、樹表示其 解空間（從根出發(fā)，左1右0），并畫出其解空間樹，計算其最優(yōu)值 及最優(yōu)解。5. 設(shè)S=X, & ，是嚴格遞增的有序集，利用二叉樹的結(jié)點來存儲S中的元素，在表示S的二叉搜索樹中搜索一個元素 X,返回 的結(jié)果有兩種情形，（1）在二叉搜索樹的內(nèi)結(jié)點中找到 X=X，其概率 為bi。（2）在二叉搜索樹的葉結(jié)點中確定X（ X，X+1 ），其概率為ai。在表示S的二叉搜索樹T中，設(shè)存儲元素X的結(jié)點深度為C;葉 結(jié)點（X，X+1）的結(jié)點深度為di，則二叉搜索樹T的平均路長p為多 少？假設(shè)二叉搜索樹Tij=X，X+1，X最優(yōu)值為mij，Wij= a i-1 +bi+ +b+a，貝S mij（1&

4、lt;=i<=j<=n）遞歸關(guān)系表達式為什么？6. 描述0-1背包問題。三、簡答題（30分）1. 流水作業(yè)調(diào)度中，已知有n個作業(yè)，機器M1和M2上加工作業(yè)i所 需的時間分別為ai和bi，請寫出流水作業(yè)調(diào)度問題的johnson法則中 對ai和bi的排序算法。（函數(shù)名可寫為sort（s,n）2. 最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法（設(shè)函數(shù)名 bin arysearchtree) )答案：一、填空1確定性有窮性可行性0個或多個輸入一個或多個輸出2. 時間復(fù)雜性空間復(fù)雜性時間復(fù)雜度高低3該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)4. BABCD或CABCD或CADCD5. 一個(最優(yōu))解6. 子問題 子問題

5、子問題7. 回溯法8. o(n*2 n) o(minnc,2n)9. 最優(yōu)子結(jié)構(gòu)重疊子問題10. 動態(tài)規(guī)劃法二、綜合題1. 問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達式；最優(yōu)值的算法描述；構(gòu)造最優(yōu)解；2. 令N=i|a i<bi , N2=i|a i>=b；將N中作業(yè)按a的非減序排序得到NI'將N2中作業(yè)按b的非增序排序得到N2'N'中作業(yè) 接N '中作業(yè)就構(gòu)成了滿足Johnson法則的最優(yōu)調(diào)度。3. 步驟為：N1=1, 3 , N2=2, 4；N =1 , 3 , N2' =4 , 2；最優(yōu)值為：384. 解空間為(0,0,0),(0

6、,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1) 。解空間樹為：nn5. 二叉樹T的平均路長Pa bi*(1 Ci)+v aj*dji =1j=0mij=Wij+mi nmik+mk+1j (1<=i<=j<=n, mii-1=0)mij=0 (i>j)6. 已知一個背包的容量為C,有n件物品，物品i的重量為W,價值為V，求應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大。三、簡答題1.void sort(flowjope s,i nt n)int i,k,j,l;for(i=1;i<二n-1;i

7、+)選擇排序k=i;while(k<=n&&sk.tag!=O) k+;if(k>n) break;/沒有 ai，跳出elsefor(j=k+1;j< 二n ;j+)if(sj.tag=0)if(sk.a>sj.a) k=j;swap(si.i ndex,sk.i ndex);swap(si.tag,sk.tag); l=i;/-記下當前第一個bi的下標for(i=l;i< 二n-1;i+)k=i;for(j=k+1;j< 二n ;j+)if(sk.b<sj.b) k=j;swap(si.index,sk.index); /只移動 in

8、dex 禾口 tagswap(si.tag,sk.tag); 2.*m,i ntvoidbin arysearchtree(i nta,i ntb,i ntn ,i nt*s,i nt *w)int i,j,k,t,l;for(i=1;i< 二n+1;i+) wii-1=ai-1;mii-1=O;for(l=0;l<=n-1;l+)-1是下標 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(t

9、<mij) mij=t;sij=k;一、填空題(本題15分，每小題1分)1、算法就是一組有窮的 ，它們規(guī)定了解決某一特定類型問題的。2、在進行問題的計算復(fù)雜性分析之前，首先必須建立求解問題所用的計算模型。3個基本計算模型是 、。3、算法的復(fù)雜性是 的度量，是評價算法優(yōu)劣的重要依據(jù)。4、計算機的資源最重要的是和資源。因而，算法的復(fù)雜性有和之分。5、f(n)二 6 x 2n+n2, f(n)的漸進性態(tài) f(n)二 0( )6、貪心算法總是做出在當前看來 的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的。7、許多可以用貪心算法求解的問題一般具有2個重要的性質(zhì)：性質(zhì)和

10、性質(zhì)。二、簡答題(本題25分，每小題5分)1、簡單描述分治法的基本思想。2、簡述動態(tài)規(guī)劃方法所運用的最優(yōu)化原理。3、何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？4、簡單描述回溯法基本思想。5、何謂P、NR NPC、可題三、算法填空(本題20分，每小題5分)1、n后問題回溯算法(1) 用二維數(shù)組ANN存儲皇后位置，若第i行第j列放有皇后，則 Aij 為非0值,否則值為0。(2) 分別用一維數(shù)組 MN、L2*N-1、R2*N-1表示豎列、左斜線、 右斜線是否放有棋子，有則值為1,否則值為0。for(j=0;j<N;j+)if( 1 ) /*安全檢查*/ Aij=i+1;/*放皇后 */if(i=N-1)輸出結(jié)果;e

11、lse 3; ; /*試探下一行 */4;/* 去皇后*/2、數(shù)塔問題。有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點可 以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使 路徑上的值最大。自底向上遞歸計算8266141224for(r= n-2;r>=0;r-) / for(c=0;1;c+)if( tr+ 1c>t r+ 1c+1) else3Hano i( n, a,b,c)3、Hanoi 算法if(n=1)1elseHanoi(n-1,b, a, c); 4、Dijkstra算法求單源最短路徑du:s到u的距離pu:記錄前一節(jié)點信息In it-s in gle-sou

12、rce(G,s) for each vertex v VGdo dv= oo ; 1ds=0Relax(u,v,w)if dv>du+w(u,v)then dv=du+wu,v;2dijkstra(G,w,s)1. In it-s in gle-source(G,s)2. S=3. Q=VG4. while Q<>do u=min(Q)S=S U ufor each vertex 3獲得中間解的結(jié)點用單圓圈O框起,do 4四、算法理解題(本題10分)根據(jù)優(yōu)先隊列式分支限界 法，求下圖中從v1點到v9 點的單源最短路徑，請畫出 求得最優(yōu)解的解空間樹。要 求中間被舍棄的結(jié)點用x標

13、記, 最優(yōu)解用雙圓圈框起。五、算法理解題(本題5分)設(shè)有n=2k個運動員要進行循環(huán)賽，現(xiàn)設(shè)計一個滿足以下要求的比賽日程表: 每個選手必須與其他n-1名選手比賽各一次； 每個選手一天至多只能賽一次； 循環(huán)賽要在最短時間內(nèi)完成。（1）如果n=2循環(huán)賽最少需要進行幾天；（2）當n=23=8時，請畫出循環(huán)賽日程表。六、算法設(shè)計題（本題15分）分別用貪心算法、動態(tài)規(guī)劃法、回溯法設(shè)計 0-1背包問題。要求： 說明所使用的算法策略；寫出算法實現(xiàn)的主要步驟；分析算法的時間。七、算法設(shè)計題（本題10分）通過鍵盤輸入一個高精度的正整數(shù) n（n的有效位數(shù)w 240），去掉 其中任意s個數(shù)字后，剩下的數(shù)字按原左右次序

14、將組成一個新的正整 數(shù)。編程對給定的n和s,尋找一種方案，使得剩下的數(shù)字組成的新 數(shù)最小。【樣例輸入】178543S=4【樣例輸出】13答案：一、填空題(本題15分，每小題1分)1 規(guī)則 一系列運算2. 隨機存取機 RAM(Ra ndomAccess Mach ine)；隨機存取存儲程序機 RASP(Random Access Stored Program Machine);圖靈機(Turing Machine)3. 算法效率4.時間、空間、時間復(fù)雜度、空間復(fù)雜度5.2n6.最好局部最優(yōu)選擇7.貪心選擇最優(yōu)子結(jié)構(gòu)1、簡答題(本題25分，每小題5分)6分治法的基本思想是將一個規(guī)模為n的問題分解為

15、k個規(guī)模較小的子問題， 這些子問題互相獨立且與原問題相同；對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī)模的問題的解 合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。7、“最優(yōu)化原理”用數(shù)學(xué)化的語言來描述：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個決策D1, D2,，Dn,如若這個決策序列是最優(yōu)的，對于 任何一個整數(shù)k，1 < k < n ，不論前面k個決策是怎樣的，以后的最優(yōu)決 策只取決于由前面決策所確定的當前狀態(tài)，即以后的決策Dk+1, Dk+2,Dn也是最優(yōu)的。8、

16、某個問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為 最優(yōu)子結(jié)構(gòu)性 質(zhì)。9、回溯法的基本思想是在一棵含有問題全部可能解的狀態(tài)空間樹上進行深度優(yōu)先搜索，解為葉子結(jié)點。搜索過程中，每到達一個結(jié)點時，貝U判斷該結(jié) 點為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對該子樹的搜索，退回到上層父結(jié)點，繼續(xù)下一步深度優(yōu)先搜索過 程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進行搜索，而是在 搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。10、P(Polynomial問題)：也即是多項式復(fù)雜程度的問題。NP就是Non-determi ni sticPoly no mial的問題，

17、也即是多項式復(fù)雜程度的非確定性問題。NPC(NP Complete)問題，這種問題只有把解域里面的所有可能都窮舉了之 后才能得出答案，這樣的冋題是 NP里面最難的冋題，這種冋題就是 NPC可 題。三、算法填空（本題20分，每小題5分）1、n后冋題回溯算法!Mj&&!Li+j&&!Ri-j+N(2) Mj=Li+j=Ri-j+N=1; try(i+1,M,L,R,A) Aij=0(5) Mj=Li+j=Ri-j+N=02、數(shù)塔問題。(1) c<=r trc+=tr+1c(3) trc+=tr+1c+13、Hanoi 算法(1) move(a,c)(2) Ha

18、noi(n-1, a, c , b)(3) Move(a,c)4、( 1)pv=NIL(2) pv=u(3) v adju(4) Relax(u,v,w)1 2 3 45 6 7 82 1 4 36 5 8 73 4 1 27 8 5 64 3 2 18 7 6 55 6 7 81 2 3 46 5 8 72 1 4 37 8 5 63 4 1 28 7 6 54 3 2 1ViVi/Wi，然后，依貪心選擇策略，將盡四、算法理解題(本題10 分)五、（1） 8天（2分）;（2）當n=23=8時，循環(huán)賽日程表（3分）六、算法設(shè)計題（本題15分）（1）貪心算法 O （nlog （n）首先計算每種物

19、品單位重量的價值 可能多的單位重量價值最高的物品裝入背包。 若將這種物品全部裝入背包 后，背包內(nèi)的物品總重量未超過 C,則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。 具體算法可描述如下：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;i<=n ;i+)if (wi>c) break;xi=1;c-=wi;if (i<=n) xi=c/wi;(2)

20、動態(tài)規(guī)劃法0( nc)m(i , j)是背包容量為j，可選擇物品為i , i+1，n時0-1背包問題的最 優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i ,j)的遞歸式如下。'maxm(i+1, j),m(i+1, j wj+« j >Wim(i, J)=丿m(i +1, j)0 乞 j v wim(n, j)0j -Wn0 _ j ： Wnvoid KnapSack(int v,int w,int c,int n,int m11) int jMax=mi n(w n-1,c);for (j=0;j<=jMax;j+) /*m(n,j)=0 0=<j<wn*/m nj=0;for (j=wn;j<=c;j+)/*m(n,j)=vn j>=wn*/m nj=v n;for (i=n-1;i>1;i-) int jMax=mi n(wi-1,c);for (j=0;j<=jMax;j+) /*m(i,j)=m(i+1,j) 0=<j<wi*/ mij=mi+1j;for (j