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

1、一、填空題（20分）1 .一個算法確實是一個有窮規(guī)那么的集合，其中之規(guī)那么規(guī)定了解決某一特殊類型問題的一系列運算，另外，算法還應(yīng)具有以下五個重耍特性:,。2 .算法的復(fù)雜性有和之分，衡量一個算法好壞的標(biāo)準(zhǔn)是o3 .某一問題可用動態(tài)計劃算法求解的顯著特點是4 .假設(shè)序列X=B,C,A,D,B,C,D,Y=A,C,B,A,B,D,C,D,請給出序列X和Y的一個最長公共子序列o5 .用回溯法解問題時，應(yīng)明肯概念問題的解空間，問題的解空間至少應(yīng)包括O6 .動態(tài)計劃算法的大體思想是將待求解問題分解成假設(shè)干，先求解,然后從這些的解取得原問題的解。7 .以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為o背包問題的回溯

2、算法所需的計算時刻為，用動態(tài)計劃算法所需的計算時刻為O9 .動態(tài)計劃算法的兩個大體要素是和。10 .二分搜索算法是利用實現(xiàn)的算法。二、綜合題（50分）1 .寫出設(shè)計動態(tài)計劃算法的要緊步驟。2 .流水作業(yè)調(diào)度問題的johnson算法的思想。3 .假設(shè)n=4,在機械Ml和M2上加工作業(yè)i所需的時刻別離為a：和*且(ai,a2,a3,a,)=(4,5,12,10),(bbb2,b3,b,)=(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、間(從根動身，左1右0),并畫出其解空間樹，計算其最優(yōu)值及最優(yōu)解。5 .設(shè)S=X1，X2,XJ是嚴(yán)格遞增的有序集，利用二叉樹的結(jié)點來存儲S中的元素，在表示S的二叉搜索樹中搜索一個元素X,返回的結(jié)果有兩種情形，(1)在二叉搜索樹的內(nèi)結(jié)點中找到X二X：,其概率為b1O(2)在二叉搜索樹的葉結(jié)點中確信Xe(X,X-),其概率為a10在表示S的二叉搜索樹T中，設(shè)存儲元素&的結(jié)點深度為C；葉結(jié)點(無，X.)的結(jié)點深度為&,那么二叉搜索樹T的平均路長p為多少?假設(shè)二叉搜索樹,XJ最優(yōu)值為Wij=ai-i+bi+bj+aj,那么mij(l=i=j=n)遞歸關(guān)系表達(dá)式什么緣故？6 .描述0-1背包問題。三、簡

4、答題(30分)1 .流水作業(yè)調(diào)度中，已知有n個作業(yè)，機械Ml和M2上加工作業(yè)i所需的時刻別離為a和h,請寫出流水作業(yè)調(diào)度問題的johnson法那么中對電和瓦的排序算法。(函數(shù)名可寫為sort(s,n)2 .最優(yōu)二叉搜索樹問題的動態(tài)計劃算法(設(shè)函數(shù)名binarysearchtree)答案：一、填空L確信性有窮性可行性0個或多個輸入一個或多個輸出3 .時刻復(fù)雜性空間復(fù)雜性時刻復(fù)雜度高低4 .該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)5 .BABCD或CABCD或CADCD6 .一個(最優(yōu))解7 .子問題子問題子問題8 .回溯法9 .o(n*2n)o(minnc,2n)10 最優(yōu)子結(jié)構(gòu)重疊子問題11 .動態(tài)計劃法二、

5、綜合題1 .問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達(dá)式；最優(yōu)值的算法描述；構(gòu)造最優(yōu)解；2 .令N尸i|abj,N2=ia=bj；將NI中作業(yè)按區(qū)的非減序排序取得工，將N?中作業(yè)按b,的非增序排序取得帥；NJ中作業(yè)接NJ中作業(yè)就組成了知足Johnson法那么的最優(yōu)調(diào)度。3 .步驟為：N1=1,3,N2=2,4；NJ=1,3,NJ=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),(1,1,l)o解空間樹為:最優(yōu)解為:0)(1, 1,16該問題的最優(yōu)值為:5 .二叉樹T的平均路長P=fbi*(

6、l+Ci)+aj*djr-1y=Omij=Wij+minmik+mk+lj(l=i=jj)6 .已知一個背包的容量為C,有n件物品，物品i的重量為肌，價值為匕，求應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大。三、簡答j1.voidsort(flowjopes,intn)inti,k,jj;for(i=1;in)break;ag=O)if(sk.asj.a)k=j;swap(si.index,sk.index);swap(si.tag,sk.tag);)l=i;sj.b)k=j;swap(si.index,sk.index);ag,sk.tag);)voidbinarysearch

7、tree(inta,intb,intnjnt*m,int*w)(intfor(i=l;i=n+l;i+)fOr(l=0J=n-1*l+)HanoiHanoiInit-single-2. S二中3. Q二VQO中dou=min(Q)S=SUuforeachvertexdo4四、算法明白得題（此題10分）根據(jù)優(yōu)先隊列式分支限界法，求以下圖中從V1點到V9點的單源最短途徑，請畫出求得最優(yōu)解的解空間樹。要求中間被舍棄的結(jié)點用X標(biāo)記，取得中間解的結(jié)點用單圓圈O框起，最優(yōu)解用雙圓圈框起。五、算法明白得題（此題5分）設(shè)有1】=2卜個運動員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計一個知足以下要求的競賽日程表：每一個選手必需與其他

8、n-1名選手競賽各一次:每一個選手一天最多只能賽一次；循環(huán)賽要在最短時刻內(nèi)完成。（1）若是n=2,循環(huán)賽最少需要進(jìn)行幾天:（2）當(dāng)n=23=8時，請畫出循環(huán)賽日程表。六、算法設(shè)計題（此題15分）別離用貪婪算法、動態(tài)計劃法、回溯法設(shè)計0-1背包問題.要求：說明所利用的算法策略：寫出算法實現(xiàn)的要緊步驟：分析算法的時刻。七、算法設(shè)計題（此題10分）通過鍵盤輸入一個高精度的正整數(shù)n（n的有效位數(shù)W240）,去掉其中任意s個數(shù)字后，剩下的數(shù)字按原左右順序?qū)⒔M成一個新的正整數(shù)。編程對給定的n和s,尋覓一種方案，使得剩下的數(shù)字組成的新數(shù)最小，【樣例輸入】178543S=4【樣例輸出】13一、填空題（此題15

9、分，每題1分）1 .規(guī)那么一系列運算2 .隨機存取機RAM（RandomAccessMachine）；隨機存取存儲程序機RASP（RandomAccessStoredProgramMachine）：圖靈機（TuringMachine）3 .算法效率4 .時刻、空間、時刻復(fù)雜度、空間復(fù)雜度5 .2n6 .最好局部最優(yōu)選擇7 .貪婪選擇最優(yōu)子結(jié)構(gòu)二、簡答題(此題25分，每題5分)1、分治法的大體思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題相互獨立且與原問題相同：對這k個子問題別離求解。若是子問題的規(guī)模仍然不夠小，那么再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很

10、容易求出其解為止：將求出的小規(guī)模的問題的解歸并為一個更大規(guī)模的問題的解，自底向上慢慢求出原先問題的解。2、“最優(yōu)化原理”用數(shù)學(xué)化的語言來描述：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個決策DI,D2,.Dn,如假設(shè)那個決策序列是最優(yōu)的，關(guān)于任何一個整數(shù)k,lkn,不論前面k個決策是如何的，以后的最優(yōu)決策只取決于由前面決策所確信的當(dāng)前狀態(tài),即以后的決策Dk+1,Dk+2,，Dn也是最優(yōu)的。3、某個問題的最優(yōu)解包括著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)、4、回溯法的大體思想是在一棵含有問題全數(shù)可能解的狀態(tài)空間樹上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點。搜索進(jìn)程中，每抵達(dá)一個結(jié)點時，那么判定該結(jié)點為

11、根的子樹是不是含有問題的解，若是能夠確信該子樹中不含有問題的解，那么舍棄對該子樹的搜索，退回到上層父結(jié)點，繼續(xù)下一步深度優(yōu)先搜索進(jìn)程。在回溯法中，并非是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而是在搜索進(jìn)程，慢慢構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。5、P(Polynomial問題)：也即是多項式復(fù)雜程度的問題。NP確實是Non-deterministicPolynomial的問題，也即是多項式復(fù)雜程度的非確信性問題。NPC(NPComplete)問題，這種問題只有把解域里面的所有可能都窮舉了以后才能得出答案，如此的問題是NP里面最難的問題，這種問題確實是NPC問題。三、算法填空(此題20分，每題5

12、分)一、n后問題回溯算法(1) !Mj&!Li+j&!Ri-j+N(2) Mj=Li+j=Ri-j+N=l;(3) try(i+l,M,L,R,A)(4) Aij=O(5) Mj=Li+j=Ri-j+N=O二、數(shù)塔問題。(1) c=r(2)trc+=tr+lc(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) vGadju(4) Relax(u,v,w)四、算法明白得題(此題10分)五、（1）8天（2分）：（2）當(dāng)n=23=8時,循環(huán)賽日程表（3分）。六、算法

13、設(shè)計題（此題15分）（1）貪婪算法O（nlog（n）1234567 82 14365 8734 127 8 5 6432 187655 67 8123465 872 1437 85 634 12876543 2 1第一計算每種物品單位重量的價值Vi/Wi,然后，依貪婪選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。假設(shè)將這種物品全數(shù)裝入背包后，背包內(nèi)的物品總重量未超過C,那么選擇單位重量價值次高的物品并盡可能多地裝入背包，依此策略一直地進(jìn)行下去，直到背包裝滿為止。具體算法可描述如下：voidKnapsack(intn.floatM,floatv(,floatw(.floatx)Sort(

14、iLV,w);inti;for(i=l;i=n;i+)xi=0;floatc=M;for(i=l;ic)break;xi=l；c-=wi;)if(i=n)xi=c/wi;)(2)動態(tài)計劃法O(nc)m(i,j)是背包容量為j,可選擇物品為i,i+1,，n時0-1背包問題的最優(yōu)值。由0背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，能夠成立計算m(i,j)的遞歸式如下。max+L/),(，+1Jwf)+匕”嗎7。，/)=4m(i+1,/)0jwzynJno0jwnvoidKnapSack(intv4ntwJntc,intn,intmll)intjMax=min(wn-l,c);for(j=O;j=jMax;j+)/*

15、m(nJ)=00=jwn*/for(j=wn;j=wn*/mnj=vn;for(i=n-l;il;i-jintjMax=min(wi-1x);for(j=O;j=jMax;j+)/*m(ij)=m(i+lj)0=jwi*/for(j=wi;j=wn*/mi|j=inax(mi+lj,mi+lj-wi+vi);)mlc=m2c;if(c=wl)mlc=max(mlc,m|2c-wl+vl);)(3)回溯法0(2)cw:當(dāng)前重量cp:當(dāng)前價值bestp：當(dāng)前最優(yōu)值voidbacktrack(inti)回溯法i初值1if(in)抵達(dá)葉結(jié)點bestp=cp;return:if(cw+wibestp)搜索右子樹backtrack(i+l);七、算