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

1、1.一個算法就是一個有窮規(guī)那么的集合,其中之規(guī)那么規(guī)定了解決某一特殊類型問題的一系列運(yùn)算,止匕外,算法還應(yīng)具有以下五個重要特性:_有窮性_,_確定性_,_可行性_,_(0個或多個)輸入_,_(1個或多個)_輸出_.2 .算法的復(fù)雜性有時間復(fù)雜性和空間復(fù)雜性之分,衡量一個算法好壞的標(biāo)準(zhǔn)是時間復(fù)雜度上下.3 .某一問題可用動態(tài)規(guī)劃算法求解的顯著特征是_該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì).4 .假設(shè)序列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 .用回溯法解問題時,應(yīng)明確定義問題的解空間,問題

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

3、方式計(jì)算出最優(yōu)值；(4)根據(jù)計(jì)算最優(yōu)值時得到的信息,構(gòu)造最優(yōu)解.問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達(dá)式;最優(yōu)值的算法描述；構(gòu)造最優(yōu)解2,流水作業(yè)調(diào)度問題的johnson算法的思想.2、解：令N=i|ai<b,N2=i|ai>=b;將N中作業(yè)按a的非減序排序得到N',將N2中作業(yè)按bi的非增序排序得到N'N'中作業(yè)接N2'中作業(yè)就構(gòu)成了滿足Johnson法那么的最優(yōu)調(diào)度.3,假設(shè)n=4,在機(jī)器M1和M2上加工作業(yè)i所需的時間分別為a和bi,且(ai,a2,a3,a4)=(4,5,12,10),(b1,b2,b3,b4)=(8,2,15,9)

4、求4個作業(yè)的最優(yōu)調(diào)度方案,并計(jì)算最優(yōu)值.3、解：步驟為：N1=1,3,N2=2,4;N'=1,3,N2,=4,2;最優(yōu)值為：384 .使用回溯法解0/1背包問題：n=33種物品,C=9背包的容量為9),V=6,10,3(3種物品的價(jià)值分別為6,10,3),W=3,4,43種物品的重量分別為3,4,4,其解空間有長度為3的0-1向量組成,要求用一棵完全二叉樹表示其解空間從根出發(fā),左并畫出其解空間樹,計(jì)算其最優(yōu)值及最優(yōu)解.4、解：其解空間為：0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,(1,1,0),(1,1,1)解空間樹為:該問題的最優(yōu)值為:1

5、6=6+10最優(yōu)解為:(1,1,0)5 .設(shè)S=X,為,一,X是嚴(yán)格遞增的有序集,利用二叉樹的結(jié)點(diǎn)來存儲S中的元素,在表示S的二叉搜索樹中搜索一個元素X,返回的結(jié)果有兩種情形,1在二叉搜索樹的內(nèi)結(jié)點(diǎn)中找到X=X,其概率為b.2在二叉搜索樹的葉結(jié)點(diǎn)中確定X6X,X+1,其概率為ai.在表示S的二叉搜索樹T中,設(shè)存儲元素X的結(jié)點(diǎn)深度為C;葉結(jié)點(diǎn)X,X+1的結(jié)點(diǎn)深度為di,那么二叉搜索樹T的平均路長p為多少假設(shè)二叉搜索樹Tij=X,X+1,X最優(yōu)值為mij,Wij=ai-i+bi+b+a,那么mij1<=i<=j<=n遞歸關(guān)系表達(dá)式為什么nn5、解：二叉樹T的平均路長P=£

6、;bi*(1+Ci)+£aj*dji1j=0mij=Wij+minmik+mk+1j(1<=i<=j<=n,mii-1=0)mij=0(i>j)6 .描述0-1背包問題.6、解：一個背包的容量為C,有n件物品,物品i的重量為W,價(jià)彳1為V,求應(yīng)如何選擇裝入背包中的物品,使得裝入背包中物品的總價(jià)值最大.三、簡做題30分1 .流水作業(yè)調(diào)度中,有n個作業(yè),機(jī)器M1和M2上加工作業(yè)i所需的時間分別為a和bi,請寫出流水作業(yè)調(diào)度問題的johnson法那么中對ai和bi的排序算法.函數(shù)名可寫為sorts,n2 .最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法設(shè)函數(shù)名binarysear

7、chtree答案：一、填空1 .確定性有窮性可行性0個或多個輸入一個或多個輸出2 .時間復(fù)雜性空間復(fù)雜性時間復(fù)雜度上下3 .該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)4 .BABCD威CABCD或CADCD5 .一個(最優(yōu))解6 .子問題子問題子問題7 .回溯法8 .o(n*2n)o(minnc,2n)9 .最優(yōu)子結(jié)構(gòu)重疊子問題10 .動態(tài)規(guī)劃法二、綜合題1 .問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達(dá)式；最優(yōu)值的算法描述；構(gòu)造最優(yōu)解；2 .令N=i|ai<bi,N2=i|ai>=b;將N中作業(yè)按a的非減序排序得到N',將N中作業(yè)按bi的非增序排序得到N'N'中作業(yè)接N

8、'中作業(yè)就構(gòu)成了滿足Johnson法那么的最優(yōu)調(diào)度.3 .步驟為：N1=1,3,N2=2,4;N'=1,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)nn5 .二叉樹T的平均路長P=Zbi*(1+Ci)+£aj*dji1j=0mij=Wij+minmik+mk+1j(1<=i<=j<=n,mii-1=0)mij=0(i>j)6 .一個背包的容量為C,有n件

9、物品,物品i的重量為W,價(jià)值為V,求應(yīng)如何選擇裝入背包中的物品,使得裝入背包中物品的總價(jià)值最大.三、簡做題1.voidsort(flowjopes,intn)for(i=1;i<=n-1;i+)/選擇排序(k=i;while(k<=n&&sk.tag!=0)k+;if(k>n)break;/沒有ai,跳出else(for(j=k+1;j<=n;j+)if(sj.tag=0)if(sk.a>sj.a)k=j;swap(si.index,sk.index);swap(si.tag,sk.tag);l=i;/-記下當(dāng)前第一個bi的下標(biāo)for(i=l;i&

10、lt;=n-1;i+)(k=i;for(j=k+1;j<=n;j+)只移動index和tagif(sk.b<sj.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是下標(biāo)j-i的差for(i=1;i<=n-l;i+)j=i+1;wij=wij-1+aj+bj;m

11、ij=mii-1+mi+1j+wij;sij=i;for(k=i+1;k<=j;k+)t=mik-1+mk+1j+wij;if(t<mij)mij=t;sij=k;)一、填空題(此題15分,每題1分)1、 算法就是一組有窮的程序規(guī)那么,它們規(guī)定了解決某一特定類型問題的一方法和過程一系列運(yùn)算.2、 在進(jìn)行問題的計(jì)算復(fù)雜性分析之前,首先必須建立求解問題所用的計(jì)算模型.3個根本計(jì)算模型是順序結(jié)構(gòu)隨機(jī)存取機(jī)RAM、循環(huán)結(jié)構(gòu)隨機(jī)存取存儲程序機(jī)RASP、條件結(jié)構(gòu)圖靈機(jī)TM.3、 算法的復(fù)雜性是邛寸間資源和空間資源算法效率的度量,是評價(jià)算法優(yōu)劣的重要裱據(jù).4、 計(jì)算機(jī)的資源最重要的是時間和空間資

12、源.因而,算法的復(fù)雜性有時間復(fù)雜性和空間復(fù)雜性之分.5、 f(n)=6安+n2,f(n)的漸進(jìn)性態(tài)f(n)=O(_2n_)6、 貪心算法總是做出在當(dāng)前看來最優(yōu)的選擇.也就是說貪心算法并不從整體最優(yōu)考慮,它所做出山選擇只是在某種意義上的局部最優(yōu)選擇_.7、 許多可以用貪心算法求解的問題一般具有2個重要的性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì).二、簡做題(此題25分,每題5分)1、 簡單描述分治法的根本思想.1、答：分治法的根本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題,這些子問題相互獨(dú)立且與原問題相同.遞歸地解這些子問題,然后將個子問題的解合并得到原問題的解.2、 簡述動態(tài)規(guī)劃方法所運(yùn)用的

13、最優(yōu)化原理.2、答：在動態(tài)規(guī)劃中,不管子問題以后是否被用到,只要它被計(jì)算過,就將其結(jié)果填入表中.3、 何謂最優(yōu)子結(jié)構(gòu)性質(zhì)3、答：當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時,稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì).問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征.4、 簡單描述回溯法根本思想4、答：回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法,用其解決問題時,應(yīng)明確定義問題的解空間.確定解空間的組織結(jié)構(gòu)后,回溯法從開始結(jié)點(diǎn)(根結(jié)點(diǎn))出發(fā),以深度優(yōu)先方式搜索整個解空間.這個開始結(jié)點(diǎn)成為活結(jié)點(diǎn),同時也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn).在當(dāng)前擴(kuò)展結(jié)點(diǎn)處,搜索向縱深方向移至一個新結(jié)點(diǎn).這個新結(jié)點(diǎn)成為新的活結(jié)點(diǎn)

14、,并成為當(dāng)前的擴(kuò)展結(jié)點(diǎn).如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能在向縱深方向移動,那么當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn).此時,應(yīng)往回移動(回溯)至最近的活結(jié)點(diǎn)處,并使這個活結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn).回溯法以這種工作方式遞歸地在解空間中搜索,直至找到所要求的解或解空間中已無活結(jié)點(diǎn)為止.5、 何謂P、NRNPQ、可題5、答：P(Polynomial問題)：也即是多項(xiàng)式復(fù)雜程度的問題.NP就是Non-deterministicPolynomial的問題,也即是多項(xiàng)式復(fù)雜程度的非確定性問題.NPC(NP：omplete)問題,這種問題只有把解域里面的所有可能都窮舉了之后才能得出答案,這樣的問題是NP里面最難的問題,這種問題就是N

15、PC、可題.三、算法填空(此題20分,每題5分)1、n后問題回溯算法(1)用二維數(shù)組ANN存儲皇后位置,假設(shè)第i行第j列放有皇后,那么Aij為非0值,否那么值為0.(2)分別用一維數(shù)組MN、L2*N-1、R2*N-1表示豎列、左斜線、右斜線是否放有棋子,有那么值為1,否那么值為0.for(j=0;j<N;j+)if(1)/*平安檢查*/Aij=i+1;/*放皇后*/if(i=N-1)輸出結(jié)果；else3;/*試探下一行*/4;/*去皇后*/2、數(shù)塔問題.有形如下列圖所示的數(shù)塔,從頂部出發(fā),在每一結(jié)點(diǎn)可以選擇向左走或是向右走,一起走到底層,要求找出一條路徑,使路徑上的值最大.for(r=n

16、-2;r>=0;r-)/自底向上遞歸計(jì)算for(c=0;1;c+)if(tr+1c>tr+1c+1)2else_33、Hanoi算法Hanoi(n,a,b,c)if(n=1)/elseHanoi(n-1,b,a,c);)4、Dijkstra算法求單源最短路徑du:s到u的距離pu:記錄前一節(jié)點(diǎn)信息Init-single-source(G,s)foreachvertexvVGdodv=00;1ds=0Relax(u,v,w)ifdv>du+w(u,v)thendv=du+wu,v;dijkstra(G,w,s)1. Init-single-source(G,s)2. S=3.

17、Q=VG4. whileQ<>dou=min(Q)S=SUuforeachvertex3V,獲得中間解的結(jié)點(diǎn)用單圓圈.框起,do4四、算法理解題(此題10分)根據(jù)優(yōu)先隊(duì)列式分支限界法,求下列圖中從v1點(diǎn)到v9點(diǎn)的單源最短路徑,請畫出求得最優(yōu)解的解空間樹.要求中間被舍棄的結(jié)點(diǎn)用X標(biāo)記,最優(yōu)解用雙圓圈框起.五、算法理解題(此題5分)設(shè)有n=2k個運(yùn)發(fā)動要進(jìn)行循環(huán)賽,現(xiàn)設(shè)計(jì)一個滿足以下要求的比賽日程表:每個選手必須與其他n-1名選手比賽各一次;每個選手一天至多只能賽一次；循環(huán)賽要在最短時間內(nèi)完成.1如果n=2k,循環(huán)賽最少需要進(jìn)行幾天；2當(dāng)n=23=8時,請畫出循環(huán)賽日程表.六、算法設(shè)計(jì)

18、題此題15分分別用貪心算法、動態(tài)規(guī)劃法、回溯法設(shè)計(jì)0-1背包問題.要求：說明所使用的算法策略；寫出算法實(shí)現(xiàn)的主要步驟；分析算法的時間.七、算法設(shè)計(jì)題此題10分通過鍵盤輸入一個高精度的正整數(shù)nn的有效位數(shù)w240,去掉其中任意s個數(shù)字后,剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù).編程對給定的n和s,尋找一種方案,使得剩下的數(shù)字組成的新數(shù)最小.【樣例輸入】178543S=4【樣例輸出】13答案:一、填空題(此題15分,每題1分)1 .規(guī)那么一系列運(yùn)算2 .隨機(jī)存取機(jī)RAM(RandomAccessMachine);隨機(jī)存取存儲程序機(jī)RASP(RandomAccessStoredProgramMa

19、chine)圖靈機(jī)(TuringMachine)3 .算法效率4 .時間、空間、時間復(fù)雜度、空間復(fù)雜度5 .2n6 .最好局部最優(yōu)選擇7 .貪心選擇最優(yōu)子結(jié)構(gòu)二、簡做題(此題25分,每題5分)6、分治法的根本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題,這些子問題互相獨(dú)立且與原問題相同；對這k個子問題分別求解.如果子問題的規(guī)模仍然不夠小,那么再劃分為k個子問題,如此遞歸的進(jìn)行下去,直到問題規(guī)模足夠小,很容易求出其解為止；將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解,自底向上逐步求出原來問題的解.7、最優(yōu)化原理用數(shù)學(xué)化的語言來描述：假設(shè)為了解決某一優(yōu)化問題,需要依次彳出n個決策D

20、1,D2,Dn,如假設(shè)這個決策序列是最優(yōu)的,對于任何一個整數(shù)k,1<k<n,不管前面k個決策是怎樣的,以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài),即以后的決策Dk+1,Dk+2,Dn也是最優(yōu)的.8、某個問題的最優(yōu)解包含著其子問題的最優(yōu)解.這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì).9、回溯法的根本思想是在一棵含有問題全部可能解的狀態(tài)空間樹上進(jìn)行深度優(yōu)先搜索,解為葉子結(jié)點(diǎn).搜索過程中,每到達(dá)一個結(jié)點(diǎn)時,那么判斷該結(jié)點(diǎn)為根的子樹是否含有問題的解,如果可以確定該子樹中不含有問題的解,那么放棄對該子樹的搜索,退回到上層父結(jié)點(diǎn),繼續(xù)下一步深度優(yōu)先搜索過程.在回溯法中,并不是先構(gòu)造出整棵狀態(tài)空間樹,再進(jìn)

21、行搜索,而是在搜索過程,逐步構(gòu)造出狀態(tài)空間樹,即邊搜索,邊構(gòu)造.10、 P(Polynomial問題)：也即是多項(xiàng)式復(fù)雜程度的問題.NP就是Non-deterministicPolynomial的問題,也即是多項(xiàng)式復(fù)雜程度的非確定性問題.NPC(NPComplete)問題,這種問題只有把解域里面的所有可能都窮舉了之后才能得出答案,這樣的問題是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)Ai

22、j=0(5)Mj=Li+j=Ri-j+N=02、數(shù)塔問題.(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)1234214334124321567865877856876556786587785687651234214334124321四、算法理解題(此題10分)五、(1)8天(2分)；(2)當(dāng)n=23=8時,循環(huán)賽日程表(3分)六、算法設(shè)計(jì)題(此題15分)(1)貪心算法

23、O(nlog(n)首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi,然后,依貪心選擇策略,將盡可能多的單位重量價(jià)值最高的物品裝入背包.假設(shè)將這種物品全部裝入背包后,背包內(nèi)的物品總重量未超過C,那么選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包.依此策略一直地進(jìn)行下去,直到背包裝滿為止.具體算法可描述如下：voidKnapsack(intn,floatM,floatv,floatw,floatx)Sort(n,v,w);inti;for(i=1;i<=n;i+)xi=0;floatc=M;for(i=1;i<=n;i+)if(wi>c)break;xi=1;c-=wi;if(i<=n)xi=c/wi;(2)動態(tài)規(guī)劃法O(nc)m(i,j)是背包容量為j,可選擇物品為i,i+1,n時0-1背包問題的最優(yōu)值.由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì),可以建立計(jì)算m(i,j)的遞歸式如下.m(i,j)=«maxm(i1,j),m(i1,jm(i1,j)-wi)mj-wi0三j:wim(n,j)=,vn0j-wn0Mj:二wnvoidKnapSack(intv,intw,intc,intn,intm11)intjMax=min(wn-1,c);for(j=0;j<=jMax;j+)/*m(n,j)=00=<j<wn*/mnj=0;for(