算法設(shè)計與分析考試題及答案

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

2、為9.動態(tài)規(guī)劃算法的兩個基本要素是10.二分搜索算法是利用實現(xiàn)的算法。二、綜合題（50 分）1. 寫出設(shè)計動態(tài)規(guī)劃算法的主要步驟。2.流水作業(yè)調(diào)度問題的johnson算法的思想。3.若n=4,在機(jī)器M1和 M2上加工作業(yè)i所需的時間分別為a和b,且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8215,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向量組成，要求用一棵完全二叉樹表示其 解空間（從根出發(fā)，左1右0），并畫出其解空間樹，計算其最

3、優(yōu)值 及最優(yōu)解。5.設(shè)S=X, & ，X是嚴(yán)格遞增的有序集，利用二叉樹的結(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)值為 mijWij= ai-1 +bi+ +b+a，則mij(1<=i<=j<=n)遞歸關(guān)系表達(dá) 式為什么?6.描述0-1背

4、包問題。三、簡答題（30 分）1.流水作業(yè)調(diào)度中，已知有n個作業(yè)，機(jī)器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或CADCD 5. 一個（最優(yōu)）解6.子問題 子問題 子問題7.回溯法8. o(n*2 n) o(minnc,2n) 9.最優(yōu)子結(jié)構(gòu)重疊

5、子問題 10.動態(tài)規(guī)劃法二、綜合題1.問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達(dá)式;最優(yōu)值的算法描述；構(gòu)造最優(yōu)解;2.令Nl=i|a i<bi , NFi|a i>=b;將N中作業(yè)按a的非減序排序得到NI'將Nk中作業(yè)按bi的非增序排序得到Nk'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,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),

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

7、n&&sk.tag!=0)k+;if(k>n)break;/沒有 ai,跳出elsefor(j=k+1;j< 二n ;j+)if(sj.tag=O)if(sk.a>sj.a) k=j;swa p( si.i ndex,sk.i ndex);swa p(si.tag,sk.tag); l=i;/-記下當(dāng)前第一個bi的下標(biāo)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); / 只移動 index 禾口 tagswap (si.t

8、ag,sk.tag);(巨二 EVW二 蘭 E+D蘭曰 E 上(+iyd 土艾)£汗巨二SJm二 M+SD +二 E+L二曰 EHS曰 ENq+se+Dm 一亭巨二M(+土 uhvxl 上)£刑S 工晅$嚥-I!=(+= luhv=oh-)04XL二瓷 L二 S(+=l+uhvxlp)£3r 二U 一(M* 4urs* Miu* gu 4U二q ju二e 4£)4LPesAjeu一q p一0>1、2、3、4、5、6、7、填空題(本題15分，每小題1分)算法就是一組有窮的，它們規(guī)定了解決某一特定類型問題的。在進(jìn)行問題的計算復(fù)雜性分析之前，首先必須建立

9、求解問題所用的計算模型。3個基本計算模型是 、。算法的復(fù)雜性是 的度量，是評價算法優(yōu)劣的重要依據(jù)。計算機(jī)的資源最重要的是 和資源。因而，算法的復(fù)雜性有和之分。f(n)= 6 次+n2, f(n)的漸進(jìn)性態(tài) f(n)= 0()貪心算法總是做出在當(dāng)前看來的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上 的。許多可以用貪心算法求解的問題一般具有2個重要的性質(zhì)：性質(zhì)和性質(zhì)。24/* 去皇后*/1、2、3、4、5、if( 1) /*安全檢查*/ Aij=i+1;/*放皇后*/if(i=N-1)輸出結(jié)果;二、簡答題(本題25分，每小題5分)簡單描述分治法的基本思想。簡述動態(tài)規(guī)劃方

10、法所運用的最優(yōu)化原理。何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？ 簡單描述回溯法基本思想。何謂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。else 3;；/*試探下一行*/for(j=0;j<N;j+)2、數(shù)塔問題。有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點可 以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使 路徑上的值最大。自底向上遞歸計算for(r

11、= n-2;r>=0;r-) / for(c=0; 1;c+)if( t葉 1c>t 葉 1c+1)2else_33、Hanoi 算法Hano i( n, a,b,c)if(n=1)1else J2Hanoi(n-1,b, a, c);4、Dijkstra算法求單源最短路徑du:s到u的距離pu:記錄前一節(jié)點信息In it-s in gle-source(G,s)for each vertex v VGdo dv= X; 1ds=0Relax(u,v,w)if dv>du+w(u,v)then dv=du+wu,v;dijkstra(G,w,s)1. In it-s in g

12、le-source(G,s)2. S=3. Q=VG4.while Q<>do u=mi n(Q)S=S U ufor each vertex 3do 4四、算法理解題（本題10分） 根據(jù)優(yōu)先隊列式分支限界法，求下圖中從v1點到v9點的單源最短路徑，請畫出求得最優(yōu)解的解空間樹。要求中間被舍棄的結(jié)點用X標(biāo)記,獲得中間解的結(jié)點用單圓圈O框起,最優(yōu)解用雙圓圈框起。五、算法理解題（本題5分）設(shè)有n=2k個運動員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計一個滿足以下要求的比賽日程表: 每個選手必須與其他n-1名選手比賽各一次; 每個選手一天至多只能賽一次; 循環(huán)賽要在最短時間內(nèi)完成。（1）如果n=2k，循環(huán)賽最少

13、需要進(jìn)行幾天;（2）當(dāng)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ù)字按原左右次序?qū)⒔M成一個新的正整 數(shù)。編程對給定的n和S,尋找一種方案，使得剩下的數(shù)字組成的新 數(shù)最小?！緲永斎搿?78543S=4【樣例輸出】13答案:、填空題(本題15分，每小題1分)1. 規(guī)則一系列運算2. 隨機(jī)存取機(jī) RAM(Random Access Ma

14、chine);隨機(jī)存取存儲程序機(jī) RASP(Random Access Stored Program Machine)圖靈機(jī)(Turing Machine)3. 算法效率4. 時間、空間、時間復(fù)雜度、空間復(fù)雜度5. 2n6. 最好局部最優(yōu)選擇7. 貪心選擇最優(yōu)子結(jié)構(gòu)二、簡答題(本題25分，每小題5分)分治法的基本思想 是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題， 這些子問題互相獨立且與原問題相同；對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī)模的問題的解 合并為一個更大規(guī)模的問題的解，自底

15、向上逐步求出原來問題的解。最優(yōu)化原理”用數(shù)學(xué)化的語言來描述：假設(shè)為了解決某一優(yōu)化問題，需要 依次作出n個決策D1, D2,，Dn,如若這個決策序列是最優(yōu)的，對于任 何一個整數(shù)k，1 <k<n ，不論前面k個決策是怎樣的，以后的最優(yōu)決策 只取決于由前面決策所確定的當(dāng)前狀態(tài)，即以后的決策Dk+1， Dk+2,，Dn也是最優(yōu)的。某個問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)?；厮莘ǖ幕舅枷胧窃谝豢煤袉栴}全部可能解的狀態(tài)空間樹上進(jìn)行深度 優(yōu)先搜索，解為葉子結(jié)點。搜索過程中，每到達(dá)一個結(jié)點時，貝U判斷該結(jié) 點為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的

16、解，則放棄對該子樹的搜索，退回到上層父結(jié)點，繼續(xù)下一步深度優(yōu)先搜索過 程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而是在 搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。P(Polynomial問題)：也即是多項式復(fù)雜程度的問題。NP就是Non-deterministic Polynomial的問題，也即是多項式復(fù)雜程度的 非確定性問題。NPC(NP Comp lete)問題，這種問題只有把解域里面的所有可能都窮舉了之 后才能得出答案，這樣的問題是 NP里面最難的問題，這種問題就是 NPC'可 題。三、算法填空(本題20分，每小題5分)1、n后問題回溯算法(1) !Mj

17、&&!Li+j&&!Ri-j+N(2) Mj=Li+j=Ri-j+N=1;6、7、8、9、10、 try(i+1,M,L,R,A) Aij=O(5) Mj=Li+j=Ri-j+N=O2、數(shù)塔問題。(1) c<=r trc+=tr+1c(3)trc+=tr+1c+13、Hanoi 算法(1) move(a,c)(2) Hanoi(n-1, a, c , b)(3) Move(a,c)4、( 1)pv=NIL(2) pv=u(3) v adju(4) Relax(u,v,w)四、算法理解題(本題10 分)V|+21D1 2 3 45 6 7 82 1 4 36

18、 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 1然后，依貪心選擇策略，將盡 若將這種物品全部裝入背包五、(1) 8天(2分);(3 分)。(2)當(dāng)n=23=8時，循環(huán)賽日程表六、算法設(shè)計題(本題15分)(1)貪心算法 0 (nlog (n) 首先計算每種物品單位重量的價值 Vi/Wi , 可能多的單位重量價值最高的物品裝入背包。后，背包內(nèi)的物品總重量未超過 C,則選擇單位重量價值次高的物品并盡 可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。具體算法可

19、描述如下：void Knap sack( 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)動態(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)的遞歸式如下。rmaxm(i +1, j),m

20、(i +1,j-Wi)+« j >Wim(i,j)= Im(i +1, j)0 < J < WiVnj >Wnm(n ,j)=J；.l00 蘭 j CWnvoid Kna pSack(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 nj=0;for (j=w n;jv=c;j+)m nj=v n;for (i=n-1;i>1;i-) int jMax=mi n(wi-1,c);for (j=0;j<=jMax;j+)mij=mi+1j;/*m( n,j)=OO=vjvw n*/*m( n,j)=v nj>=w n*/*m(i,j)=m(i+1,j)0=<j<wi*/for (j=wi;j<=c;j+)/* m(n