算法設(shè)計(jì)與分析考試題及

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

算法的復(fù)雜性有

和_

之_

分，權(quán)衡一個(gè)算法好壞的標(biāo)準(zhǔn)是___________________。__某一問(wèn)題可用動(dòng)向規(guī)劃算法求解的明顯特點(diǎn)是若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，請(qǐng)給出序列X和Y的一個(gè)最長(zhǎng)公共子序列___________________________。___用回溯法解問(wèn)題時(shí)，應(yīng)明確立義問(wèn)題的解空間，問(wèn)題的解空間最少應(yīng)包括_________。_6.動(dòng)向規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干_，_先求解___________，_此后從這些__的_解獲取原問(wèn)題的解。7.________________________________________________以深度優(yōu)先方式系統(tǒng)找尋問(wèn)題解的算法稱(chēng)為_(kāi)_______________________。_背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為_(kāi)______________用_,動(dòng)向規(guī)劃算法所需的計(jì)算時(shí)間為_(kāi)_________。_9.動(dòng)向規(guī)劃算法的兩個(gè)基本因素是__________和_______。_二分找尋算法是利用_____________實(shí)_現(xiàn)的算法。二、綜合題（50分）寫(xiě)出設(shè)計(jì)動(dòng)向規(guī)劃算法的主要步驟。流水作業(yè)調(diào)動(dòng)問(wèn)題的johnson算法的思想。3.若n=4，在機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間分別為ai和bi，且(ai,a2,a3,a4)=(4,5,12,10),(bi,b2,b3,b4)=(8,2,15,9)求4個(gè)作業(yè)的最優(yōu)調(diào)動(dòng)方案，并計(jì)算最優(yōu)值。4.使用回溯法解0/1背包問(wèn)題：n=3,C=9,V={6,10,3},W二{3,4,4},其解空間有長(zhǎng)度為3的0-1向量構(gòu)成，要求用一棵完滿(mǎn)二叉樹(shù)表示其解空間(從根出發(fā)，左1右0)，并畫(huà)出其解空間樹(shù)，計(jì)算其最優(yōu)值及最優(yōu)解。設(shè)S={Xi,X2,?Xn}是嚴(yán)格遞加的有序集，利用二叉樹(shù)的結(jié)點(diǎn)來(lái)儲(chǔ)蓄S中的元素，在表示S的二叉找尋樹(shù)中找尋一個(gè)元素X，返回的結(jié)果有兩種情況，(1)在二叉找尋樹(shù)的內(nèi)結(jié)點(diǎn)中找到X=Xi，其概率為bi。(2)在二叉找尋樹(shù)的葉結(jié)點(diǎn)中確立X?(Xi,Xi+1),其概率為ai。在表示S的二叉找尋樹(shù)T中，設(shè)儲(chǔ)蓄元素Xi的結(jié)點(diǎn)深度為Ci；葉結(jié)點(diǎn)(Xi,Xi+1)的結(jié)點(diǎn)深度為di，則二叉找尋樹(shù)T的均勻路長(zhǎng)p為多少假定二叉找尋樹(shù)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)遞歸關(guān)系表達(dá)式為何描繪0-1背包問(wèn)題。三、簡(jiǎn)答題(30分)流水作業(yè)調(diào)動(dòng)中,已知有n個(gè)作業(yè),機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間分別為a和b，請(qǐng)寫(xiě)出流水作業(yè)調(diào)動(dòng)問(wèn)題的johnson法例中對(duì)aiii和bi的排序算法。(函數(shù)名可寫(xiě)為sort(s,n))2.最優(yōu)二叉找尋樹(shù)問(wèn)題的動(dòng)向規(guī)劃算法(設(shè)函數(shù)名binarysearchtree))答案：一、填空1．確立性有窮性可行性0個(gè)或多個(gè)輸入一個(gè)或多個(gè)輸出時(shí)間復(fù)雜性空間復(fù)雜性時(shí)間復(fù)雜度高低該問(wèn)題擁有最優(yōu)子結(jié)構(gòu)性質(zhì){BABCD}或{CABCD}或{CADCD}一個(gè)(最優(yōu))解6.子問(wèn)題子問(wèn)題子問(wèn)題回溯法o(n*2n)o(min{nc,2n})9.最優(yōu)子結(jié)構(gòu)重疊子問(wèn)題動(dòng)向規(guī)劃法二、綜合題1?①問(wèn)題擁有最優(yōu)子結(jié)構(gòu)性質(zhì)；②結(jié)構(gòu)最優(yōu)值的遞歸關(guān)系表達(dá)式；③最優(yōu)值的算法描繪；④結(jié)構(gòu)最優(yōu)解；2.①令Ni二{i|ai<bi}，N2={i|a>=bi};②將Ni中作業(yè)按ai的非減序排序獲取Ni'將N2中作業(yè)按bi的非增序排序獲取N2'③Ni'中作業(yè)接N2'中作業(yè)就構(gòu)成了知足Johnson法例的最優(yōu)調(diào)動(dòng)。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)}解空間樹(shù)為:該問(wèn)題的最優(yōu)值為：16最優(yōu)解為：(1,1,0)n5.二叉樹(shù)T的均勻路長(zhǎng)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.已知一個(gè)背包的容量為C,有n件物件，物件i的重量為Wi,價(jià)值為Vi，求應(yīng)如何選擇裝入背包中的物件，使得裝入背包中物件的總價(jià)值最大。三、簡(jiǎn)答題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(mào)=V[G]Q<>①dou=min(Q)S=SU{u}foreachvertex3do4____________四、算法理解題（此題10分）依據(jù)優(yōu)先行列式分支限界法，求以下列圖中從v1點(diǎn)到v9點(diǎn)的單源最短路徑，請(qǐng)畫(huà)出求得最優(yōu)解的解空間樹(shù)。要求中間被舍棄的結(jié)點(diǎn)用X標(biāo)志，獲取中間解的結(jié)點(diǎn)用單圓圈O框起，最優(yōu)解用雙圓圈◎框起。五、算法理解題（此題5分）設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個(gè)知足以下要求的競(jìng)賽日程表：①每個(gè)選手必然與其余n-1名選手競(jìng)賽各一次；②每個(gè)選手一天至多只好賽一次；③循環(huán)賽要在最短時(shí)間內(nèi)達(dá)成。1）若是n=2k，循環(huán)賽最少需要進(jìn)行幾日；2）當(dāng)n=23=8時(shí)，請(qǐng)畫(huà)出循環(huán)賽日程表。六、算法設(shè)計(jì)題（此題15分）分別用貪婪算法、動(dòng)向規(guī)劃法、回溯法設(shè)計(jì)0-1背包問(wèn)題。要求:說(shuō)明所使用的算法策略；寫(xiě)出算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間。七、算法設(shè)計(jì)題（此題10分）經(jīng)過(guò)鍵盤(pán)輸入一個(gè)高精度的正整數(shù)n（n的有效位數(shù)w240），去掉此中隨意s個(gè)數(shù)字后，剩下的數(shù)字按原左右序次將構(gòu)成一個(gè)新的正整數(shù)。編程對(duì)給定的n和s,找尋一種方案，使得剩下的數(shù)字構(gòu)成的新數(shù)最小?！緲永斎搿?78543S=4【樣例輸出】13答案：一、填空題(此題15分，每題1分)1．規(guī)則一系列運(yùn)算2.隨機(jī)存取機(jī)RAM(RandomAccessMachine)；隨機(jī)存取儲(chǔ)蓄程序機(jī)RASP(RandomAccessStoredProgramMachine)；圖靈機(jī)(TuringMachine)算法效率時(shí)間、空間、時(shí)間復(fù)雜度、空間復(fù)雜度5．2n6．最好局部最精選擇7.貪婪選擇最優(yōu)子結(jié)構(gòu)二、簡(jiǎn)答題(此題25分，每題5分)1、分治法的基本思想是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題同樣；對(duì)這k個(gè)子問(wèn)題分別求解。若是子問(wèn)題的規(guī)模仍舊不夠小，則再區(qū)分為k個(gè)子問(wèn)題，這樣遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很簡(jiǎn)單求出其解為止；將求出的小規(guī)模的問(wèn)題的解歸并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐漸求出本來(lái)問(wèn)題的解。2

、“最優(yōu)化原理”用數(shù)學(xué)化的語(yǔ)言來(lái)描繪：假定為認(rèn)識(shí)決某一優(yōu)化問(wèn)題，需要挨次作出n個(gè)決議D1,D2，，Dn,如若這個(gè)決議序列是最優(yōu)的，關(guān)于任何一個(gè)整數(shù)k，1<k<n，無(wú)論前面k個(gè)決議是如何的，此后的最優(yōu)決議只取決于由前面決議所確立的目前狀態(tài)，即此后的決議Dk+1，Dk+2

，，

Dn

也是最優(yōu)的。3、某個(gè)問(wèn)題的最優(yōu)解包括著其子問(wèn)題的最優(yōu)解。這類(lèi)性質(zhì)稱(chēng)為質(zhì)。

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

NP

P(Polynomial問(wèn)題)：也即是多項(xiàng)式復(fù)雜程度的問(wèn)題。就是Non-deterministicPolynomial的問(wèn)題，也即是多項(xiàng)式復(fù)雜程度

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

此后NPC問(wèn)1、n后問(wè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ù)塔問(wèn)題。(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)當(dāng)n=23=8時(shí)，循環(huán)賽日程表(3分)六、算法設(shè)計(jì)題(此題15分)(1)貪婪算法0(nlog(n))第一計(jì)算每種物件單位重量的價(jià)值Vi/Wi，此后，依貪婪選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物件裝入背包。若將這類(lèi)物件所有裝入背包可能多地裝入背包。依此策略向來(lái)地進(jìn)行下去，直到背包裝滿(mǎn)為止詳細(xì)算法可描繪以下：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)動(dòng)向規(guī)劃法0(nc)m(i,j)是背包括量為j,可選擇物件為i,i+1,，n時(shí)0-1背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，能夠成立計(jì)算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:目前價(jià)值bestp：目前最優(yōu)值voidbacktrack(inti)回溯法i初值1{if(i>n)//抵達(dá)葉結(jié)點(diǎn){bestp=cp;return;if(cw+w[i]<=c)//找尋左子樹(shù){cw+=w[i];cp+=p[i];backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)>bestp)找尋右子樹(shù)backtrack(i+1);}七、算法設(shè)計(jì)題(此題10分)為了盡可能地迫近目標(biāo)，我們采納的貪婪策略為：每一步老是選擇一個(gè)