算法設計與分析考試題及

1.一個算法就是一個有窮規(guī)則的會合，此中之規(guī)則規(guī)定認識決某一特殊種類問題的一系列運算，其余，算法還應擁有以下五個重要特性:________,_______,_______,_________,___。___2._______________________

算法的復雜性有

和_

之_

分，權衡一個算法好壞的標準是___________________。__某一問題可用動向規(guī)劃算法求解的明顯特點是若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，請給出序列X和Y的一個最長公共子序列___________________________。___用回溯法解問題時，應明確立義問題的解空間，問題的解空間最少應包括_________。_6.動向規(guī)劃算法的基本思想是將待求解問題分解成若干_，_先求解___________，_此后從這些__的_解獲取原問題的解。7.________________________________________________以深度優(yōu)先方式系統(tǒng)找尋問題解的算法稱為________________________。_背包問題的回溯算法所需的計算時間為_______________用_,動向規(guī)劃算法所需的計算時間為__________。_9.動向規(guī)劃算法的兩個基本因素是__________和_______。_二分找尋算法是利用_____________實_現(xiàn)的算法。二、綜合題（50分）寫出設計動向規(guī)劃算法的主要步驟。流水作業(yè)調動問題的johnson算法的思想。3.若n=4，在機器M1和M2上加工作業(yè)i所需的時間分別為ai和bi，且(ai,a2,a3,a4)=(4,5,12,10),(bi,b2,b3,b4)=(8,2,15,9)求4個作業(yè)的最優(yōu)調動方案，并計算最優(yōu)值。4.使用回溯法解0/1背包問題：n=3,C=9,V={6,10,3},W二{3,4,4},其解空間有長度為3的0-1向量構成，要求用一棵完滿二叉樹表示其解空間(從根出發(fā)，左1右0)，并畫出其解空間樹，計算其最優(yōu)值及最優(yōu)解。設S={Xi,X2,?Xn}是嚴格遞加的有序集，利用二叉樹的結點來儲蓄S中的元素，在表示S的二叉找尋樹中找尋一個元素X，返回的結果有兩種情況，(1)在二叉找尋樹的內結點中找到X=Xi，其概率為bi。(2)在二叉找尋樹的葉結點中確立X?(Xi,Xi+1),其概率為ai。在表示S的二叉找尋樹T中，設儲蓄元素Xi的結點深度為Ci；葉結點(Xi,Xi+1)的結點深度為di，則二叉找尋樹T的均勻路長p為多少假定二叉找尋樹T[i][j]={X,Xi+iX}最優(yōu)值為m[i][j],ijW[i][j]=ai-i+bi++bj+aj,則m[i][j](1＜二i＜二jv二n)遞歸關系表達式為何描繪0-1背包問題。三、簡答題(30分)流水作業(yè)調動中,已知有n個作業(yè),機器M1和M2上加工作業(yè)i所需的時間分別為a和b，請寫出流水作業(yè)調動問題的johnson法例中對aiii和bi的排序算法。(函數(shù)名可寫為sort(s,n))2.最優(yōu)二叉找尋樹問題的動向規(guī)劃算法(設函數(shù)名binarysearchtree))答案：一、填空1．確立性有窮性可行性0個或多個輸入一個或多個輸出時間復雜性空間復雜性時間復雜度高低該問題擁有最優(yōu)子結構性質{BABCD}或{CABCD}或{CADCD}一個(最優(yōu))解6.子問題子問題子問題回溯法o(n*2n)o(min{nc,2n})9.最優(yōu)子結構重疊子問題動向規(guī)劃法二、綜合題1?①問題擁有最優(yōu)子結構性質；②結構最優(yōu)值的遞歸關系表達式；③最優(yōu)值的算法描繪；④結構最優(yōu)解；2.①令Ni二{i|ai<bi}，N2={i|a>=bi};②將Ni中作業(yè)按ai的非減序排序獲取Ni'將N2中作業(yè)按bi的非增序排序獲取N2'③Ni'中作業(yè)接N2'中作業(yè)就構成了知足Johnson法例的最優(yōu)調動。3.步驟為：Ni={i，3}，N2={2，4}；Ni'={i，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),(1,1,1)}解空間樹為:該問題的最優(yōu)值為：16最優(yōu)解為：(1,1,0)n5.二叉樹T的均勻路長P=i1

nbi*(1Ci)+aj*djj0m[i][j]=W[i][j]+min{m[i][k]+m[k+1][j]}(1<=i<=j<=n,m[i][i-1]=0)m[i][j]=0(i>j)6.已知一個背包的容量為C,有n件物件，物件i的重量為Wi,價值為Vi，求應如何選擇裝入背包中的物件，使得裝入背包中物件的總價值最大。三、簡答題voidsort(flowjopes[],intn)inti,k,j,l;for(i=1;i<=n-1;i++)ag!=0)k++;if(k>n)break;ag==0)if(s[k].a>s[j].a)k=j;swap(s[i].index,s[k].index);swap(s[i].tag,s[k].tag);}}l=i;<s[j].b)k=j;swap(s[i].index,s[k].index);ag,s[k].tag);}}2.voidbinarysearchtree(inta[],intb[],intn,intm,intw)s,int{inti,j,k,t,l;for(i=1;i<=n+1;i++){w[i][i-1]=a[i-1];m[i][i-1]=0;}for(l=0;l<=n-1;l++)Init-single-source(G,s)S=①Q=V[G]Q<>①dou=min(Q)S=SU{u}foreachvertex3do4____________四、算法理解題（此題10分）依據(jù)優(yōu)先行列式分支限界法，求以下列圖中從v1點到v9點的單源最短路徑，請畫出求得最優(yōu)解的解空間樹。要求中間被舍棄的結點用X標志，獲取中間解的結點用單圓圈O框起，最優(yōu)解用雙圓圈◎框起。五、算法理解題（此題5分）設有n=2k個運動員要進行循環(huán)賽，現(xiàn)設計一個知足以下要求的競賽日程表：①每個選手必然與其余n-1名選手競賽各一次；②每個選手一天至多只好賽一次；③循環(huán)賽要在最短時間內達成。1）若是n=2k，循環(huán)賽最少需要進行幾日；2）當n=23=8時，請畫出循環(huán)賽日程表。六、算法設計題（此題15分）分別用貪婪算法、動向規(guī)劃法、回溯法設計0-1背包問題。要求:說明所使用的算法策略；寫出算法實現(xiàn)的主要步驟；分析算法的時間。七、算法設計題（此題10分）經(jīng)過鍵盤輸入一個高精度的正整數(shù)n（n的有效位數(shù)w240），去掉此中隨意s個數(shù)字后，剩下的數(shù)字按原左右序次將構成一個新的正整數(shù)。編程對給定的n和s,找尋一種方案，使得剩下的數(shù)字構成的新數(shù)最小。【樣例輸入】178543S=4【樣例輸出】13答案：一、填空題(此題15分，每題1分)1．規(guī)則一系列運算2.隨機存取機RAM(RandomAccessMachine)；隨機存取儲蓄程序機RASP(RandomAccessStoredProgramMachine)；圖靈機(TuringMachine)算法效率時間、空間、時間復雜度、空間復雜度5．2n6．最好局部最精選擇7.貪婪選擇最優(yōu)子結構二、簡答題(此題25分，每題5分)1、分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題相互獨立且與原問題同樣；對這k個子問題分別求解。若是子問題的規(guī)模仍舊不夠小，則再區(qū)分為k個子問題，這樣遞歸的進行下去，直到問題規(guī)模足夠小，很簡單求出其解為止；將求出的小規(guī)模的問題的解歸并為一個更大規(guī)模的問題的解，自底向上逐漸求出本來問題的解。2

、“最優(yōu)化原理”用數(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)的。3、某個問題的最優(yōu)解包括著其子問題的最優(yōu)解。這類性質稱為質。

最優(yōu)子結構性4、回溯法的基本思想是在一棵含有問題所有可能解的狀態(tài)空間樹進步行深度優(yōu)先找尋，解為葉子結點。找尋過程中，每抵達一個結點時，則判斷該結點為根的子樹能否含有問題的解，若是能夠確立該子樹中不含有問題的解，則放棄對該子樹的找尋，退回到上層父結點，連續(xù)下一步深度優(yōu)先找尋過程。在回溯法中，其實不是先結構出整棵狀態(tài)空間樹，再進行找尋，而是在找尋過程，逐漸構造出狀態(tài)空間樹，即邊找尋，邊結構。5、

NP

P(Polynomial問題)：也即是多項式復雜程度的問題。就是Non-deterministicPolynomial的問題，也即是多項式復雜程度

的非確定性問題。NPC(NPComplete)問題，這類問題只有把解域里面的所有可能都窮舉了才能得出答案，這樣的問題是NP里面最難的問題，這類問題就是題。三、算法填空(此題20分，每題5分)

此后NPC問1、n后問題回溯算法!M[j]&&!L[i+j]&&!R[i-j+N]M[j]=L[i+j]=R[i-j+N]=1;try(i+1,M,L,R,A)A[i][j]=0M[j]=L[i+j]=R[i-j+N]=02、數(shù)塔問題。(1)c<=rt[r][c]+=t[r+1][c]t[r][c]+=t[r+1][c+1]3、Hanoi算法move(a,c)Hanoi(n-1,a,c,b)Move(a,c)4、(1)p[v]=NILp[v]=uv?adj[u]Relax(u,v,w)四、算法理解題(此題10分)123456782143658五、(1)8天(2分)；7(2)當n=23=8時，循環(huán)賽日程表(3分)六、算法設計題(此題15分)(1)貪婪算法0(nlog(n))第一計算每種物件單位重量的價值Vi/Wi，此后，依貪婪選擇策略，將盡可能多的單位重量價值最高的物件裝入背包。若將這類物件所有裝入背包可能多地裝入背包。依此策略向來地進行下去，直到背包裝滿為止詳細算法可描繪以下：voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}(2)動向規(guī)劃法0(nc)m(i,j)是背包括量為j,可選擇物件為i,i+1,，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結構性質，能夠成立計算m(i,j)的遞歸式以下。max{m(i1,j),m(i1,jwjv}jw：m(i,j)0jWim(i1,j)m(n,j)Vnjwn00jwnvoidKnapSack(intv[],intw[],intc,intn,intm[][11]){intjMax=min(w[n]-1,c);for(j=0;j<=jMax;j++)/*m(n,j)=00=<j<w[n]*/m[n][j]=0;for(j=w[n];j<=c;j++)/*m(n,j)=v[n]j>=w[n]*/m[n][j]=v[n];for(i=n-1;i>1;i--){intjMax=min(w[i]-1,c);for(j=0;j<=jMax;j++)/*m(i,j)=m(i+1,j)0=<j<w[i]*/m[i][j]=m[i+1][j];for(j=w[i];j<=c;j++)/*m(n,j)=v[n]j>=w[n]*/m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}(3)回溯法O(2n)cw:目前重量cp:目前價值bestp：目前最優(yōu)值voidbacktrack(inti)回溯法i初值1{if(i>n)//抵達葉結點{bestp=cp;return;if(cw+w[i]<=c)//找尋左子樹{cw+=w[i];cp+=p[i];backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)>bestp)找尋右子樹backtrack(i+1);}七、算法設計題(此題10分)為了盡可能地迫近目標，我們采納的貪婪策略為：每一步老是選擇一個