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

2、算法所需的計算時刻為，用動態計劃算法所需的計算時刻為O9 .動態計劃算法的兩個大體要素是和。10 .二分搜索算法是利用實現的算法。二、綜合題（50分）1 .寫出設計動態計劃算法的要緊步驟。2 .流水作業調度問題的johnson算法的思想。3 .假設n=4,在機械Ml和M2上加工作業i所需的時刻別離為a：和*且(ai,a2,a3,a,)=(4,5,12,10),(bbb2,b3,b,)=(8,2,15,9)求4個作業的最優調度方案，并計算最優值。4 .利用回溯法解0/1背包問題：n=3,C=9,V=6,10,3,W=3,4,4),其解空間有長度為3的0-1向量組成，要求用一棵完全二叉樹表示其解空

3、間(從根動身，左1右0),并畫出其解空間樹，計算其最優值及最優解。5 .設S=X1，X2,XJ是嚴格遞增的有序集，利用二叉樹的結點來存儲S中的元素，在表示S的二叉搜索樹中搜索一個元素X,返回的結果有兩種情形，(1)在二叉搜索樹的內結點中找到X二X：,其概率為b1O(2)在二叉搜索樹的葉結點中確信Xe(X,X-),其概率為a10在表示S的二叉搜索樹T中，設存儲元素&的結點深度為C；葉結點(無，X.)的結點深度為&,那么二叉搜索樹T的平均路長p為多少?假設二叉搜索樹,XJ最優值為Wij=ai-i+bi+bj+aj,那么mij(l=i=j=n)遞歸關系表達式什么緣故？6 .描述0-1背包問題。三、簡

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

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

6、l+Ci)+aj*djr-1y=Omij=Wij+minmik+mk+lj(l=i=jj)6 .已知一個背包的容量為C,有n件物品，物品i的重量為肌，價值為匕，求應如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大。三、簡答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分）根據優先隊列式分支限界法，求以下圖中從V1點到V9點的單源最短途徑，請畫出求得最優解的解空間樹。要求中間被舍棄的結點用X標記，取得中間解的結點用單圓圈O框起，最優解用雙圓圈框起。五、算法明白得題（此題5分）設有1】=2卜個運動員要進行循環賽，現設計一個知足以下要求的競賽日程表：每一個選手必需與其他

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

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

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

11、根的子樹是不是含有問題的解，若是能夠確信該子樹中不含有問題的解，那么舍棄對該子樹的搜索，退回到上層父結點，繼續下一步深度優先搜索進程。在回溯法中，并非是先構造出整棵狀態空間樹，再進行搜索，而是在搜索進程，慢慢構造出狀態空間樹，即邊搜索，邊構造。5、P(Polynomial問題)：也即是多項式復雜程度的問題。NP確實是Non-deterministicPolynomial的問題，也即是多項式復雜程度的非確信性問題。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二、數塔問題。(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）當n=23=8時,循環賽日程表（3分）。六、算法

13、設計題（此題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,然后，依貪婪選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。假設將這種物品全數裝入背包后，背包內的物品總重量未超過C,那么選擇單位重量價值次高的物品并盡可能多地裝入背包，依此策略一直地進行下去，直到背包裝滿為止。具體算法可描述如下：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)動態計劃法O(nc)m(i,j)是背包容量為j,可選擇物品為i,i+1,，n時0-1背包問題的最優值。由0背包問題的最優子結構性質，能夠成立計算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:當前重量cp:當前價值bestp：當前最優值voidbacktrack(inti)回溯法i初值1if(in)抵達葉結點bestp=cp;return:if(cw+wibestp)搜索右子樹backtrack(i+l);七、算