1、1.一個算法就是一個有窮規則的集合,其中之規則規定了解決某一特殊類型問題的一系列運算，止匕外，算法還應具有以下五個重要特性:_有窮性_,_確定性_,_可行性_,_(0個或多個)輸入_,_(1個或多個)_輸出_。2 .算法的復雜性有時間復雜性和空間復雜性之分，衡量一個算法好壞的標準是時間復雜度高低。3 .某一問題可用動態規劃算法求解的顯著特征是_該問題具有最優子結構性質。4 .若序列X=B,C,A,D,B,C,D,Y=A,C,B,A,B,D,C,D，請給出序列X和Y的一個最長公共子序列_A,B,C,D_。BABCD由CABCD或CADCD5 .用回溯法解問題時，應明確定義問題的解空間，問題的解空

2、間至少應包含_問題的一個(最優)解_。6 .動態規劃算法的基本思想是將待求解問題分解成若干_子問題_,先求解子問題，然后從這些子問題的解得到原問題的解。7 .以深度優先方式系統搜索問題解的算法稱為回溯法_。8 .0-1背包問題的回溯算法所需的計算時間為_O(n2n)_,用動態規劃算法所需的計算時間為_O(n)_oo(minnc,2n)9 .動態規劃算法的兩個基本要素是_最優子結構_和_重疊子問題10 .二分搜索算法是利用動態規劃法實現的算法二、綜合題(50分)1.寫出設計動態規劃算法的主要步驟。1、解：(1)找出最優解的性質，并刻畫其結構特征；(2)遞歸地定義最優值；(3)以自底向上的方式計算

3、出最優值；(4)根據計算最優值時得到的信息，構造最優解。問題具有最優子結構性質；構造最優值的遞歸關系表達式;最優值的算法描述；構造最優解2,流水作業調度問題的johnson算法的思想。2、解：令N=i|ai=b;將N中作業按a的非減序排序得到N,將N2中作業按bi的非增序排序得到N;N中作業接N2中作業就構成了滿足Johnson法則的最優調度。3,若n=4,在機器M1和M2上加工作業i所需的時間分別為a和bi,且(ai,a2,a3,a4)=(4,5,12,10),(b1,b2,b3,b4)=(8,2,15,9)求4個作業的最優調度方案，并計算最優值。3、解：步驟為：N1=1,3,N2=2,4;

4、N=1,3,N2,=4,2;最優值為：384 .使用回溯法解0/1背包問題：n=3（3種物品），C=9（背包的容量為9),V=6,10,3(3種物品的價值分別為6,10,3),W=3,4,4（3種物品的重量分別為3,4,4）,其解空間有長度為3的0-1向量組成，要求用一棵完全二叉樹表示其解空間（從根出發，左并畫出其解空間樹，計算其最優值及最優解。4、解：其解空間為：（0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,(1,1,0),(1,1,1)解空間樹為:該問題的最優值為:16=6+10最優解為:(1,1,0)5 .設S=X,為，一，X是嚴格遞增的有序集

5、，利用二叉樹的結點來存儲S中的元素，在表示S的二叉搜索樹中搜索一個元素X,返回的結果有兩種情形，（1）在二叉搜索樹的內結點中找到X=X,其概率為b。（2）在二叉搜索樹的葉結點中確定X6（X,X+1）,其概率為ai。在表示S的二叉搜索樹T中，設存儲元素X的結點深度為C;葉結點（X,X+1）的結點深度為di,則二叉搜索樹T的平均路長p為多少？假設二叉搜索樹Tij=X,X+1，X最優值為mij,Wij=ai-i+bi+b+a,則mij（1=i=j=n）遞歸關系表達式為什么？nn5、解：二叉樹T的平均路長P=bi*(1+Ci)+aj*dji1j=0mij=Wij+minmik+mk+1j(1=i=jj

6、)6 .描述0-1背包問題。6、解：已知一個背包的容量為C,有n件物品，物品i的重量為W,價彳1為V,求應如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大。三、簡答題（30分）1 .流水作業調度中，已知有n個作業，機器M1和M2上加工作業i所需的時間分別為a和bi,請寫出流水作業調度問題的johnson法則中對ai和bi的排序算法。（函數名可寫為sort（s,n）2 .最優二叉搜索樹問題的動態規劃算法（設函數名binarysearchtree）答案：一、填空1 .確定性有窮性可行性0個或多個輸入一個或多個輸出2 .時間復雜性空間復雜性時間復雜度高低3 .該問題具有最優子結構性質4 .B

7、ABCD威CABCD或CADCD5 .一個(最優)解6 .子問題子問題子問題7 .回溯法8 .o(n*2n)o(minnc,2n)9 .最優子結構重疊子問題10 .動態規劃法二、綜合題1 .問題具有最優子結構性質；構造最優值的遞歸關系表達式；最優值的算法描述；構造最優解；2 .令N=i|ai=b;將N中作業按a的非減序排序得到N,將N中作業按bi的非增序排序得到N;N中作業接N中作業就構成了滿足Johnson法則的最優調度。3 .步驟為：N1=1,3,N2=2,4;N=1,3,N2=4,2;最優值為：384.解空間為(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1)

8、,(1,0,1),(1,1,0),(1,1,1)解空間樹為：該問題的最優值為：16最優解為：(1,1,0)nn5 .二叉樹T的平均路長P=Zbi*(1+Ci)+aj*dji1j=0mij=Wij+minmik+mk+1j(1=i=jj)6 .已知一個背包的容量為C,有n件物品，物品i的重量為W,價值為V,求應如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大。三、簡答題1.voidsort(flowjopes,intn)for(i=1;i=n-1;i+)/選擇排序(k=i;while(kn)break;/沒有ai,跳出else(for(j=k+1;jsj.a)k=j;swap(si.in

9、dex,sk.index);swap(si.tag,sk.tag);l=i;/-記下當前第一個bi的下標for(i=l;i=n-1;i+)(k=i;for(j=k+1;j=n;j+)只移動index和tagif(sk.bsj.b)k=j;swap(si.index,sk.index);/swap(si.tag,sk.tag);2.voidbinarysearchtree(inta,intb,intn,int*m,int*s,int*w)(inti,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+)/-1是下標j-i的差fo

10、r(i=1;i=n-l;i+)j=i+1;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(tmij)mij=t;sij=k;)一、填空題(本題15分，每小題1分)1、 算法就是一組有窮的程序規則，它們規定了解決某一特定類型問題的一方法和過程一系列運算。2、 在進行問題的計算復雜性分析之前，首先必須建立求解問題所用的計算模型。3個基本計算模型是順序結構隨機存取機RAM、循環結構隨機存取存儲程序機RASP、條件結構圖靈機TM。3、 算法的復雜性是邛寸間資源和空間資源算法效率的度量,是評價

11、算法優劣的重要裱據。4、 計算機的資源最重要的是時間和空間資源。因而，算法的復雜性有時間復雜性和空間復雜性之分。5、 f(n)=6安+n2,f(n)的漸進性態f(n)=O(_2n_)6、 貪心算法總是做出在當前看來最優的選擇。也就是說貪心算法并不從整體最優考慮，它所做出山選擇只是在某種意義上的局部最優選擇_。7、 許多可以用貪心算法求解的問題一般具有2個重要的性質：最優子結構性質和貪心選擇性質。二、簡答題(本題25分，每小題5分)1、 簡單描述分治法的基本思想。1、答：分治法的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題相互獨立且與原問題相同。遞歸地解這些子問題，然后將

12、個子問題的解合并得到原問題的解。2、 簡述動態規劃方法所運用的最優化原理。2、答：在動態規劃中，不管子問題以后是否被用到，只要它被計算過，就將其結果填入表中。3、 何謂最優子結構性質？3、答：當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用動態規劃算法或貪心算法求解的關鍵特征。4、 簡單描述回溯法基本思想4、答：回溯法是一個既帶有系統性又帶有跳躍性的搜索算法，用其解決問題時，應明確定義問題的解空間。確定解空間的組織結構后，回溯法從開始結點(根結點)出發，以深度優先方式搜索整個解空間。這個開始結點成為活結點，同時也成為當前的擴展結點。在當前擴

13、展結點處，搜索向縱深方向移至一個新結點。這個新結點成為新的活結點，并成為當前的擴展結點。如果在當前擴展結點處不能在向縱深方向移動，則當前擴展結點就成為死結點。此時，應往回移動(回溯)至最近的活結點處，并使這個活結點成為當前擴展結點。回溯法以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結點為止。5、 何謂P、NRNPQ、可題5、答：P(Polynomial問題)：也即是多項式復雜程度的問題。NP就是Non-deterministicPolynomial的問題，也即是多項式復雜程度的非確定性問題。NPC(NP：omplete)問題，這種問題只有把解域里面的所有可能都窮舉了之

14、后才能得出答案，這樣的問題是NP里面最難的問題，這種問題就是NPC、可題。三、算法填空(本題20分，每小題5分)1、n后問題回溯算法(1)用二維數組ANN存儲皇后位置，若第i行第j列放有皇后，則Aij為非0值,否則值為0。(2)分別用一維數組MN、L2*N-1、R2*N-1表示豎列、左斜線、右斜線是否放有棋子，有則值為1,否則值為0。for(j=0;j=0;r-)/自底向上遞歸計算for(c=0;1;c+)if(tr+1ctr+1c+1)2else_33、Hanoi算法Hanoi(n,a,b,c)if(n=1)/elseHanoi(n-1,b,a,c);)4、Dijkstra算法求單源最短路徑

15、du:s到u的距離pu:記錄前一節點信息Init-single-source(G,s)foreachvertexvVGdodv=00;1ds=0Relax(u,v,w)ifdvdu+w(u,v)thendv=du+wu,v;dijkstra(G,w,s)1. Init-single-source(G,s)2. S=3. Q=VG4. whileQdou=min(Q)S=SUuforeachvertex3V，獲得中間解的結點用單圓圈。框起,do4四、算法理解題(本題10分)根據優先隊列式分支限界法，求下圖中從v1點到v9點的單源最短路徑，請畫出求得最優解的解空間樹。要求中間被舍棄的結點用X標記,

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

17、數。編程對給定的n和s,尋找一種方案，使得剩下的數字組成的新數最小。【樣例輸入】178543S=4【樣例輸出】13答案:一、填空題(本題15分，每小題1分)1 .規則一系列運算2 .隨機存取機RAM(RandomAccessMachine);隨機存取存儲程序機RASP(RandomAccessStoredProgramMachine)圖靈機(TuringMachine)3 .算法效率4 .時間、空間、時間復雜度、空間復雜度5 .2n6 .最好局部最優選擇7 .貪心選擇最優子結構二、簡答題(本題25分，每小題5分)6、分治法的基本思想是將一個規模為n的問題分解為k個規模較小的子問題，這些子問題互

18、相獨立且與原問題相同；對這k個子問題分別求解。如果子問題的規模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規模足夠小，很容易求出其解為止；將求出的小規模的問題的解合并為一個更大規模的問題的解，自底向上逐步求出原來問題的解。7、最優化原理”用數學化的語言來描述：假設為了解決某一優化問題，需要依次彳出n個決策D1,D2,，Dn,如若這個決策序列是最優的，對于任何一個整數k,1kn,不論前面k個決策是怎樣的，以后的最優決策只取決于由前面決策所確定的當前狀態，即以后的決策Dk+1,Dk+2,Dn也是最優的。8、某個問題的最優解包含著其子問題的最優解。這種性質稱為最優子結構性質。9、回

19、溯法的基本思想是在一棵含有問題全部可能解的狀態空間樹上進行深度優先搜索，解為葉子結點。搜索過程中，每到達一個結點時，則判斷該結點為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對該子樹的搜索，退回到上層父結點，繼續下一步深度優先搜索過程。在回溯法中，并不是先構造出整棵狀態空間樹，再進行搜索，而是在搜索過程，逐步構造出狀態空間樹，即邊搜索，邊構造。10、 P(Polynomial問題)：也即是多項式復雜程度的問題。NP就是Non-deterministicPolynomial的問題，也即是多項式復雜程度的非確定性問題。NPC(NPComplete)問題，這種問題只有把解域里

20、面的所有可能都窮舉了之后才能得出答案，這樣的問題是NP里面最難的問題，這種問題就是NPC可題。三、算法填空(本題20分，每小題5分)1、n后問題回溯算法(1)!Mj&!Li+j&!Ri-j+NMj=Li+j=Ri-j+N=1;try(i+1,M,L,R,A)Aij=0(5)Mj=Li+j=Ri-j+N=02、數塔問題。(1)c=r(2)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) vCadju(4) Relax(u,v,w)123421

21、4334124321567865877856876556786587785687651234214334124321四、算法理解題(本題10分)五、(1)8天(2分)；(2)當n=23=8時，循環賽日程表(3分)六、算法設計題(本題15分)(1)貪心算法O(nlog(n)首先計算每種物品單位重量的價值Vi/Wi,然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總重量未超過C,則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。具體算法可描述如下：voidKnapsack(intn,floatM,floatv,floatw,floatx)Sort(n,v,w);inti;for(i=1;i=n;i+)xi=0;floatc=M;for(i=1;ic)break;xi=1;c-=wi;if(i=n)xi=c/wi;(2)動態規劃法O(nc)m(i,j)是背包容量為j,可選擇物品為i,i+1,，n時0-1背包問題的最優值。由0-1背包問題的最優子結構性質，可以建立計算m(i,j)的遞歸式如下。m(