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

1、一、填空題(20分)一個(gè)算法就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類(lèi)型問(wèn)題的一系列運(yùn)算，此 夕卜，算法還應(yīng)具有以下五個(gè)重要特性:確定性 有窮性 可行性0個(gè)或多個(gè)輸入 一個(gè)或多個(gè)輸 出算法的復(fù)雜性有時(shí)間復(fù)雜性空間復(fù)雜性之分，衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是時(shí)間復(fù)雜度高低某一問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征是該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)若序列X=B,C,A,D,B,C,D，Y=A,C,B,A,B,D,C,D，請(qǐng)給出序列X和Y的一個(gè)最長(zhǎng)公共子序列 BABCD或CABCD或CADCD用回溯法解問(wèn)題時(shí)，應(yīng)明確定義問(wèn)題的解空間，問(wèn)題的解空間至少應(yīng)包含一個(gè)(最優(yōu))解動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分

2、解成若干子問(wèn)題，先求解_子問(wèn)題，然后從這些子 問(wèn)題 的解得到原問(wèn)題的解。以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題解的算法稱(chēng)為回溯法8.0-1背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間為o(n*2n)，用動(dòng)態(tài)規(guī)劃算法所需的計(jì)算時(shí)間為o(minnc,2n)動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是最優(yōu)子結(jié)構(gòu)和重疊子問(wèn)題二分搜索算法是利用動(dòng)態(tài)規(guī)劃法實(shí)現(xiàn)的算法。二、綜合題(50分)寫(xiě)出設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟。問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；構(gòu)造最優(yōu)值的遞歸關(guān)系表達(dá)式；最優(yōu)值的算法描述；構(gòu)造最優(yōu)解；流水作業(yè)調(diào)度問(wèn)題的johnson算法的思想。令N = i|a=b；將N中作業(yè)按a的非減序排序得到N，將N中作業(yè)按b的 非增序排序相薊N2；N：申作業(yè)

3、接1中作業(yè)就肉成了滿(mǎn)足Johnson法則的最猊調(diào)度。若n=4,在機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間分別為a和b，且(a ,a ,a ,a ) = (4,5,12,10)，. - 、. -.i 一一 i 12 3 4(bb ,b3，b4)= (8,2,15,9)求4個(gè)作業(yè)的最優(yōu)調(diào)度方案，并計(jì)算最優(yōu)值。步驟為：3n1=1，3，N2=2, 4；N =1，3， N =4, 2；最優(yōu)值為：38 2使用回溯法解0/1背包問(wèn)題：n=3, C=9, V=6,10,3，W=3,4,4,其解空間有長(zhǎng)度為3的0-1 向量組成，要求用一棵完全二叉樹(shù)表示其解空間(從根出發(fā)，左1右0)，并畫(huà)出其解空間樹(shù)，計(jì) 算其最優(yōu)值

4、及最優(yōu)解。解空間為(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)該問(wèn)題的最優(yōu)值為：16最優(yōu)解為：(1，1，0)設(shè)S=X , X , , X 是嚴(yán)格遞增的有序集，利用二叉樹(shù)的結(jié)點(diǎn)來(lái)存儲(chǔ)S中的元素，在表示S 的二叉搜索樹(shù)中搜索一個(gè)元素X,返回的結(jié)果有兩種情形，(1)在二叉搜索樹(shù)的內(nèi)結(jié)點(diǎn)中找到X=X., 其概率為b。(2)在二叉搜索樹(shù)的葉結(jié)點(diǎn)中確定Xe(X,X )，其概率為a。在表示S的二叉搜索 樹(shù)T中，設(shè)存儲(chǔ)元素X的結(jié)點(diǎn)深度為C；葉結(jié)點(diǎn)(X,氏)的結(jié)點(diǎn)深度為d

5、，則二叉搜索樹(shù)丁的平 均路長(zhǎng)P為多少？假設(shè)二叉搜索樹(shù)Tij= X. X1+； , X最優(yōu)值為mij, Wij = TOC o 1-5 h z ._ _ ， i 一 . i+1 .ja. i+bi+ +bj+a則 mij(1=i=j=n)遞歸關(guān)系表達(dá)式為什么？.二叉樹(shù)T的平均路長(zhǎng)？= Y bi*(1 + Ci) +才aj*dji=1j=0mij=Wij+minmik+mk+1j (1=i=jj)描述0-1背包問(wèn)題。巳知一個(gè)背包的容量為C,有n件物品，物品i的重量為W,價(jià)值為V,求應(yīng)如何選擇裝入背包中 的物品，使得裝入背包中物品的總價(jià)值最大。ii三、簡(jiǎn)答題(30分)流水作業(yè)調(diào)度中，巳知有n個(gè)作業(yè)，

6、機(jī)器M1和M2上加工作業(yè)i所需的時(shí)間分別為*和七，請(qǐng)寫(xiě) 出流水作業(yè)調(diào)度問(wèn)題的johnson法則中對(duì)a.和七的排序算法。(函數(shù)名可寫(xiě)為sort(s,n) void sort(flowjope s,int n)(int i,k,j,l;for(i=1;i=n-1;i+)/選擇排序(k=i;while(kn) break;/沒(méi)有 a.，跳出else(for(j=k+1;jsj.a) k=j;swap(si.index,sk.index);swap(si.tag,sk.tag);l=i;/記下當(dāng)前第一個(gè)b.的下標(biāo)for(i=l;i=n-1;i+)(k=i;for(j=k+1;j=n;j+)if(sk.

7、bsj.b) k=j;swap(si.index,sk.index); /只移動(dòng) index 和 tagswap(si.tag,sk.tag);2、最優(yōu)二叉搜索樹(shù)問(wèn)題的動(dòng)態(tài)規(guī)劃算法(設(shè)函數(shù)名binarysearchtree)void binarysearchtree(int a,int b,int n,int *m,int *s,int *w)(int i,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+l;wij=wij-1+aj+bj;mij=m

8、ii-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、算法就是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類(lèi)型問(wèn)題的一系列運(yùn)算。2、在進(jìn)行問(wèn)題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問(wèn)題所用的計(jì)算模型。3個(gè)基本計(jì)算模型是隨機(jī)存取機(jī)RAM；隨機(jī)存取存儲(chǔ)程序機(jī)RASP；圖靈機(jī)(Turing Machine)3、算法的復(fù)雜性是算法效率的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。4、計(jì)算機(jī)的資源最重要的是時(shí)間和空間資源。因而算法的復(fù)雜性有時(shí)間復(fù)雜度和空間復(fù)雜度之分。5、f(n)=

9、 6X2n+n2，f(n)的漸進(jìn)性態(tài) f(n)= O(2n )6、貪心算法總是做出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所做出 的選擇只是在某種意義上的局部最優(yōu)選擇7、許多可以用貪心算法求解的問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇_性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。二、簡(jiǎn)答題(本題25分，每小題5分)1、簡(jiǎn)單描述分治法的基本思想。分治法的基本思想是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立 且與原問(wèn)題相同；對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子 問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止；將求出的小規(guī)模的問(wèn) 題

10、的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。2、簡(jiǎn)述動(dòng)態(tài)規(guī)劃方法所運(yùn)用的最優(yōu)化原理?！白顑?yōu)化原理”用數(shù)學(xué)化的語(yǔ)言來(lái)描述：假設(shè)為了解決某一優(yōu)化問(wèn)題，需要依次作出n個(gè)決策D1， D2,，Dn，如若這個(gè)決策序列是最優(yōu)的，對(duì)于任何一個(gè)整數(shù)k，1 k n，不論前面k個(gè)決策 是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即以后的決策Dk+1，Dk+2,， Dn也是最優(yōu)的。3、何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？某個(gè)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)。4、簡(jiǎn)單描述回溯法基本思想?；厮莘ǖ幕舅枷胧窃谝豢煤袉?wèn)題全部可能解的狀態(tài)空間樹(shù)上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)

11、 點(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ò)程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹(shù)，再進(jìn)行搜索，而是在搜索過(guò)程，逐步 構(gòu)造出狀態(tài)空間樹(shù)，即邊搜索，邊構(gòu)造。5、何謂P、NP、NPC問(wèn)題P(Polynomial問(wèn)題)：也即是多項(xiàng)式復(fù)雜程度的問(wèn)題。NP就是Non-deterministic Polynomial的問(wèn)題，也即是多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題。NPC(NP Complete)問(wèn)題，這種問(wèn)題只有把解域里面的所有可能都窮舉了之后才能得出答案，這樣的 問(wèn)題

12、是NP里面最難的問(wèn)題，這種問(wèn)題就是NPC問(wèn)題。三、算法填空(本題20分，每小題5分)1、n后問(wèn)題回溯算法用二維數(shù)組ANN存儲(chǔ)皇后位置，若第i行第j列放有皇后，則Aij為非0值,否則值為0。分別用一維數(shù)組MN、L2*N-1、R2*N-1表示豎列、左斜線、右斜線是否放有棋子，有則 值為1,否則值為0。for(j=0;j=0;r-) /自底向上遞歸計(jì)算for(c=0;1;c+)if( tr+1ctr+1c+1)2else 3 ；cdu+w(u,v)then ( dv=du+wu,v;2dijkstra(G,w,s)Init-single-source(G,s)S=OQ=VGwhile Q 中do u

13、=min(Q)S=S U ufor each vertexdo 4pv=NILpv=uvadjuRelax(u,v,w)_四、算法理解題(本題10分)根據(jù)優(yōu)先隊(duì)列式分支限界法，求下圖中從v1點(diǎn)到v9點(diǎn)的單源最短路徑，請(qǐng)畫(huà)出求得最優(yōu)解的解 空間樹(shù)。要求中間被舍棄的結(jié)點(diǎn)用X標(biāo)記，獲得中間解的結(jié)點(diǎn)用單圓圈?？蚱穑顑?yōu)解用雙圓圈 框起。五、算法理解題(本題5分)1 2 3 45 6 7 8設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個(gè)滿(mǎn)足以下要求的比賽日程表：2 1 4 36 5 8 7每個(gè)選手必須與其他n-1名選手比賽各一次；3 4 1 27 8 5 6每個(gè)選手一天至多只能賽一次；4 3 2 18 7

14、 6 5循環(huán)賽要在最短時(shí)間內(nèi)完成。5 6 7 81 2 3 4(1)如果n=2k，循環(huán)賽最少需要進(jìn)行幾天；6 5 8 72 1 4 3(2)當(dāng)n=23=8時(shí)，請(qǐng)畫(huà)出循環(huán)賽日程表。7 8 5 63 4 1 21) 8 天(2 分)；(2)當(dāng)n=23=8時(shí)，循環(huán)賽日程表(3分)。8 7 6 54 3 2 1六、算法設(shè)計(jì)題(本題15分)分別用貪心算法、動(dòng)態(tài)規(guī)劃法、回溯法設(shè)計(jì)0-1背包問(wèn)題。要求：說(shuō)明所使用的算法策略；寫(xiě) 出算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間。貪心算法 O (nlog (n)首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量 價(jià)值最高的物品裝入背包。若

15、將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C， 則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背 包裝滿(mǎn)為止。具體算法可描述如下：void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w);int i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;if (i=n) xi=c/wi;動(dòng)態(tài)規(guī)劃法O(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)性

16、質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下。j Z wi0 j wi_ | maxm(i +1, j), m(i +1, j - g) + 七 1mj Z wi0 j wm(n, j) = 1 人 c/ n0 0 j wnvoid KnapSack(int v,int w,int c,int n,int m11)int jMax=min(wn-1,c);for (j=0;j=jMax;j+)/*m(n,j)=00=jwn*/mnj=0;for (j=wn;j=wn*/mnj=vn;for (i=n-1;i1;i-) int jMax=min(wi-1,c);for (j=0;j=jMax;j+)/*m(i,j)=m(i+1,j)0=jwi*/mij=mi+1j;for (j=wi;j=wn*/mij=max(mi+1j,mi+1j-wi+vi);m1c=m2c;if(c=w1)m1c=max(m1c,m2c-w1+v1