計(jì)算機(jī)算法試題含答案

1、算法設(shè)計(jì)與分析試卷一、填空題(20分，每空2分)1、 算法的性質(zhì)包括輸入、輸出、有限性。2、 動(dòng)態(tài)規(guī)劃算法的基本思想就將待求問題、先求解子問題，然后從這些子問題的解得到原問題的解。3、 設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的4個(gè)步驟：(1) 找出,弁刻畫其結(jié)構(gòu)特征。(2) 。(4) 根據(jù)計(jì)算最優(yōu)值得到的信息，。4、 流水作業(yè)調(diào)度問題的johnson算法：(1) 令N1=,N2=i|ai>=bj;(2) 將N1中作業(yè)依ai的。5、對(duì)于流水作業(yè)高度問題，必存在一個(gè)最優(yōu)調(diào)度兀，使得作業(yè)兀(i)和兀(i+1)滿足Johnson不等式。6、最優(yōu)二叉搜索樹即是的二叉搜索樹。二、綜合題(50分)1、當(dāng)(a1,a2,a3,

2、a4,a5,a6)=(-2,11,-4,13,-5,-2)時(shí),最大子段和為Eak(2<=k<=4)(5分)2、由流水作業(yè)調(diào)度問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，T(N,0)=(5分)3、最大子段和問題的簡單算法(10分)intmaxsum(intn,int*a,int&bestj)(intsum=0;for(inti=1;i<=n;i+)for(intj=i;j<=n;j+)intthissum=0;for(intk=i;k<=j;k+);if(thissum>sum)sum=thissum;；bestj=j;returnsum;4、設(shè)計(jì)最優(yōu)二叉搜索樹問題的動(dòng)

3、態(tài)規(guī)劃算法OptimalBinarysearchTree?(15分)VoidOptimalBinarysearchTree(inta,intn,int*m,int*w)for(inti=0;i<=n;i+)wi+1i=ai;mi+1i=;for(intr=0;r<n;r+)for(inti=1;i<=n-r;i+)intj=i+r;wij=wij-1+aj+bj;mij=;sij=i;for(intk=i+1;k<=j;k+)intt=mik-1+mk+1j;if()mij=t;sij=k;)mij=t;sij=k;5、設(shè)n=4,(a1,a2,a3,a4)=(3,4,8

4、,10),(b1,b2,b3,b4)=(6,2,9,15)用兩種方法求4個(gè)作業(yè)的最優(yōu)調(diào)度方案并計(jì)算其最優(yōu)值？(15分)三、簡答題(30分)1、將所給定序列a1:n分為長度相等的兩段a1:n/2和an/2+1:n,分別求出這兩段的最大子段和，則a1:n的最大子段和有哪三種情形？(10分)答：2、由01背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以對(duì)m(i,j)建立怎樣的遞歸式？(10分)3、01背包求最優(yōu)值的步驟分為哪幾步？(10分)參考答案：填空題：確定性分解成若干個(gè)子問題最優(yōu)解的性質(zhì)遞歸地定義最優(yōu)值以自底向上的方式計(jì)算出最優(yōu)值構(gòu)造最優(yōu)解i|ai<biai的非減序排序；將N2中作業(yè)依bi的非增序排序mi

5、nb喇后項(xiàng)+i)>minb#1)總電)最小平均查找長度綜合題：20minai+T(N-i,bi)(1=<i<=n)thissum+=akbesti=i0mi+1jt<mij法一：min(ai,bj)<=min(aj,bi)因?yàn)閙in(a1,b2)<=min(a2,b1)所以1-2(先1后2)由min(a1,b3)<=min(a3,b1)得1-3(先1后3)同理可得：最后為173f42法二：johnson算法思想N1=1,3,4N2=2N11=1,3,4N12=2所以N11fN12得：1342簡答題：1、(1)a1:n的最大子段和與a1:n/2的最大子段

6、和相同(2)a1:n的最大子段和與的最大子段an/2+1:n和相同。(3)a1:n的最大子段和為工；ak(i=<k<=J),且1<=i<=n/2,n/2+1<=J<=n。2、(1)m(i,j)=maxm(i+1,j),m(i+1,j-wi)+ui(j>=wi)或則m(i,j)=m(i+1,j)(0<=j<wi)(2) m(n,j)=unj>=wn或則m(n,j)=00<=j<wn3、(1)、pn+1=(0,0)(2)、由pi+1fqi+1,qi+1=pi+1(wi,vi)(3)、Mij=pi+1Uqi+1Pi=Mij其中的

7、受控點(diǎn)=pi+1Uqi+1其中的受控(4)、重復(fù)(2)-(3)直到求出P11 .在一個(gè)算法中調(diào)用另一個(gè)算法時(shí)，系統(tǒng)需在運(yùn)行被調(diào)用算法之前完成哪些工作？同時(shí)從被調(diào)用算法返回調(diào)用算法需完成哪些工作？答：在一個(gè)算法中調(diào)用另一算法時(shí)，系統(tǒng)需在運(yùn)行被調(diào)用算法之前先完成三件事：(1) 將所有實(shí)參指針、返回地址等信息傳遞給被調(diào)用算法；(2) 為被調(diào)用算法的局部變量分配存儲(chǔ)區(qū)；(3) 將控制轉(zhuǎn)移到被調(diào)用算法的入口。在從被調(diào)用算法返回調(diào)用算法時(shí)需完成三件事：(1) 保存被調(diào)用算法的計(jì)算結(jié)果；(2) 釋放分配給被調(diào)用算法的數(shù)據(jù)區(qū)；(3) 依照被調(diào)用算法保存的返回地址將控制轉(zhuǎn)移到調(diào)用算法。2 .動(dòng)態(tài)規(guī)劃算法求解問題

8、的步驟？答：動(dòng)態(tài)規(guī)劃法適用于解最優(yōu)化問題。通?？梢园匆韵?個(gè)步驟設(shè)計(jì)：(1) 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；(2) 遞歸地定義最優(yōu)值；(3) 以自底向上的方式計(jì)算最優(yōu)值；(4) 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造最優(yōu)解。3 .線性規(guī)劃法中單純形算法的基本步驟？答：步驟一選入基變量。步驟二選離基變量。步驟三做轉(zhuǎn)軸變換。步驟四轉(zhuǎn)步驟一。4 .分治法的基本思想和原理是什么？答：分治法的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。5 .利用回溯法解決問題包含哪些步驟？答：利用回溯法解題常包含以下

9、3步驟：(1) 針對(duì)所給問題，定義問題的解空間；(2) 確定易于搜索的解空間結(jié)構(gòu)；(3) 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。五分析題(36分)1 .求下列函數(shù)的漸進(jìn)表達(dá)式：3n2+10n;n2/10+2n;21+1/n;logn3;1010g3n分析與解答：3n2+10n=O(n2);n2/10+2n=O(2n);21+1/n=O(1);1ogn3=O(1ogn);101og3n=O(n)2 .討論0(1)和0(2)的區(qū)別。分析與解答：根據(jù)符號(hào)0的定義易知0(1)=0(2)。用0(1)或0(2)表示同一個(gè)函數(shù)時(shí)，差別僅在于其中的常數(shù)因子。3 .按漸近階排列表達(dá)式按

10、照漸近階從低到高的順序排列以下表達(dá)式：4n2,logn,3n,20n,2,n2/3。又n!應(yīng)該排在哪一位？分析與解答：按漸近階從低到高，函數(shù)排列順序如下：2,logn,n2/3,20n,4n13n,n!。4 .算法效率(1)假設(shè)某算法在車入規(guī)模為n時(shí)計(jì)算時(shí)間為T(n)=3*2n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t秒。現(xiàn)有另一臺(tái)計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題？(2)若上述算法的計(jì)算時(shí)間改進(jìn)為T(n)=n2,其余條件不變，則在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模為多大的問題？(3)若上述算法的計(jì)算時(shí)間進(jìn)一步改進(jìn)為T(n)=8,其余條

11、件不變，那么在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模為多大的問題？分析解答：(1)設(shè)新機(jī)器用同一算法在t秒內(nèi)能解輸入規(guī)模為n1的問題。因此有：t=3*22=3*2n1/64,解得你n1=n+6。(2)n12=64n2；n1=8n。(3)由于T(n)=常數(shù)，因此算法可解任意規(guī)模的問題。5 .階乘函數(shù)階乘函數(shù)可遞歸地定義為：'1n=0n!=*n(n-1)!n>0intfactorial(intn)if(n=0)return1;returnn*factorial(n-1);6 .Fibonacci數(shù)列無窮數(shù)列1,1,2,3,5,8,13,21,34,55,，稱為Fibonacci數(shù)列。它可以遞

12、歸地定義為：|1n=0F(n)=1n=1F(n_1)+F(n.2)n>1請(qǐng)對(duì)這個(gè)無窮數(shù)列設(shè)計(jì)一個(gè)算法，并進(jìn)行描述(自然語言描述和VC+描述).第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：intfibonacci(intn)(if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);7 .循環(huán)賽日程表設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行兵乓球循環(huán)賽?，F(xiàn)在要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法解決以上問題，并進(jìn)行描述(自然語言和C+語

13、言)按分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過為n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。8 .有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wio最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。分析回答以下兩個(gè)問題：(1)分析以上最優(yōu)裝載問題具有貪心選擇性質(zhì)(2)用C+程序進(jìn)行正確的算法描述分析與解答：(1) 設(shè)集裝箱已依其重量從小到大排序，(X1,X2，,Xn)是最有裝載問題的一個(gè)最優(yōu)解。又設(shè)k=mini|xi=1。易知，如果給定的最有裝載問題有解，則1wkwn。當(dāng)k=1時(shí)，(x1,x2，,Xn)是滿足貪心選擇性質(zhì)的最優(yōu)解。當(dāng)k>1時(shí)，取y1=1;yk=0;yi=x,1<i<n,iwk,則因此，()是所給最有裝載問題的可行解。另一方面，由知，()是滿足貪心選擇性質(zhì)的最優(yōu)解。所以，最優(yōu)裝載問題具有貪心選擇性質(zhì)。(2)最優(yōu)裝載問題可用貪心