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

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

2、0分)1、當(dāng)(a1,a2,a3,a4,a5,a6) =(-2,11,-4,13,-5,-2)時(shí)，最大子段和為刀ak(2v=k<=4) (5 分)2、 由流水作業(yè)調(diào)度問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，T (N , 0) = (5 分)3、最大子段和問(wèn)題的簡(jiǎn)單算法(10分)int maxsum(i nt n ,i nt *a,i nt & bestj)in tsum=0;for (i nt i=1;i<=n ;i+)for (in t j=i;j<=n ;j+)int thissum=0;for(i nt k=i;k<=j;k+);if(thissum>sum)sum

3、=thissum; ?bestj=j;return sum;4、設(shè)計(jì)最優(yōu)二叉搜索樹問(wèn)題的動(dòng)態(tài)規(guī)劃算法OptimalBinarysearchTree?(15 分)* w)；Void OptimalB in arysearchTree(i nt a,i nt n ,i nt * * m, int *for(i nt i=0;i<=n;i+)wi+1i=ai; mi+1i=for(i nt r=0;r <n 丁+)for(i nt i=1;i<=n-r;i+)int j=i+r;wij=wij-1+aj+bj;mij= ；sij=i;for(int k=i+1;k<=j;k+

4、)int t=mik-1+mk+1j;if()mij=t; sij=k;mij=t; sij=k;5、設(shè) n=4, (a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15) 用兩 種方法求 4 個(gè)作業(yè)的最優(yōu)調(diào)度方案并計(jì)算其最優(yōu)值？( 15 分)三、簡(jiǎn)答題( 30 分)1、將所給定序列 a1:n 分為長(zhǎng)度相等的兩段 a1:n/2 和 an/2+1:n ， 分別求出這兩段的最大子段和，則 a1:n 的最大子段和有哪三種情 形？(10分)答：2、 由 01 背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以對(duì)m( i,j )建立怎樣 的遞歸式 ? (10 分 )3、 0 1

5、背包求最優(yōu)值的步驟分為哪幾步？(10 分)參考答案：填空題 ：確定性 分解成若干個(gè)子問(wèn)題最優(yōu)解的性質(zhì)遞歸地定義最優(yōu)值 以自底向上的方式計(jì)算出最優(yōu)值構(gòu)造最優(yōu)解 i|ai<bi ai 的非減序排序；將 N2 中作業(yè)依 bi 的 非增序排序minb 頑),ani+i) > minb 頑+i),ano 最小平均查找長(zhǎng)度綜合題： 20 minai+T(N-i,bi)(1=<i<=n)thissum+=ak besti=i 0 mi+1jt<mij法一： min(ai,bj)<=min(aj,bi)因?yàn)?min(a1,b2)<=min(a2,b1)所以1-2(先1

6、后2)由 min(a1,b3)<=min(a3,b1)得 1 - 3 (先 1 后 3)同理可得：最后為 1 -3-4-2法二： johnson 算法思想N1= 1 , 3, 4 N2 = 2N11= 1 , 3, 4N12= 2所以 N11 -N12得：1-3-4-2簡(jiǎn)答題：1 、 ( 1 )a1 :n 的最大子段和與 a1:n/2 的最大子段和相同。 ( 2) a1:n 的最大子段和與的最大子段 an/2+1:n 和相同。(3) a1:n的最大子段和為刀ak(i=vkv=J)，且 1<=i<=n/2,n/2+1<=J<=n 。(j>=wi)2、(1)m(

7、i,j)=maxm(i+1,j),m(i+1,j-wi)+ui或則 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+1 -qi+1,qi+1=pi+1(wi,vi)(3) 、Mij=pi+1 U qi+1Pi=Mij 其中的受控點(diǎn)=pi+1 U qi+1其中的受控(4) 、重復(fù)( 2) - (3)直到求出 P11. 在一個(gè)算法中調(diào)用另一個(gè)算法時(shí)，系統(tǒng)需在運(yùn)行被調(diào)用算法之前完成哪些工 作？同時(shí)從被調(diào)用算法返回調(diào)用算法需完成哪些工作？答：在

8、一個(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ī)劃算法求解問(wèn)題的步驟？答：動(dòng)態(tài)規(guī)劃法適用于解最優(yōu)化問(wèn)題。通?？梢园匆韵?4 個(gè)步驟設(shè)計(jì)：（ 1） 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；（ 2） 遞歸地定義最優(yōu)值；（ 3） 以自底向上的方式計(jì)算最優(yōu)值；（

9、4） 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造最優(yōu)解。3. 線性規(guī)劃法中單純形算法的基本步驟？答：步驟一選入基變量。步驟二選離基變量。步驟三做轉(zhuǎn)軸變換。步驟四轉(zhuǎn)步驟一。4. 分治法的基本思想和原理是什么？答：分治法的基本思想是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn) 題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同。遞歸地解這些子問(wèn)題，然后 將各子問(wèn)題的解合并得到原問(wèn)題的解。5. 利用回溯法解決問(wèn)題包含哪些步驟？答：利用回溯法解題常包含以下 3 步驟：（1）針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；3) 以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。五分析題( 36 分)

10、1求下列函數(shù)的漸進(jìn)表達(dá)式：3n2+10n; n2/10+2n; 21+1/n; logn 3; 10log3n分析與解答：3n2+10n=O(n 2);n2/10+2 n=O(2 n);21+1/n=O(1); logn3=O(logn);10log3 n=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á)式按照漸近階從低到高的順序排列以下表達(dá)式：4n2, logn , 3n, 20n , 2, n2/3。又n!應(yīng)該排在哪一位？分析與解答：按漸近階從低到高

11、，函數(shù)排列順序如下：2， logn， n2/3， 20n， 4n2， 3n， n！。4. 算法效率(1) 假設(shè)某算法在輸入規(guī)模為 n時(shí)計(jì)算時(shí)間為T(n)=3*2 n。在某臺(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ī)模為多大的問(wèn)題？(2) 若上述算法的計(jì)算時(shí)間改進(jìn)為 T(n)=n 2，其余條件不變，則在新機(jī)器上用 t 秒時(shí)間能解輸入規(guī)模為多 大的問(wèn)題？(3) 若上述算法的計(jì)算時(shí)間進(jìn)一步改進(jìn)為 T(n)=8 ，其余條件不變，那么在新機(jī)器上用 t 秒時(shí)間能解輸入 規(guī)模為多大的問(wèn)題？分析解答：(1)

12、 設(shè)新機(jī)器用同一算法在t秒內(nèi)能解輸入規(guī)模為n1的問(wèn)題。因此有：t=3*2 2=3*2n1/64，解得你n1= n+622(2) n1 2=64n2? n1=8n。(3) 由于 T(n)= 常數(shù)，因此算法可解任意規(guī)模的問(wèn)題。5. 階乘函數(shù)階乘函數(shù)可遞歸地定義為：int factorial(int n)if(n=0) return 1; return n* factorial(n-1);6 Fibonacci 數(shù)列無(wú)窮數(shù)列1, 1, 2, 3, 5, 8, 13, 21, 34, 55,，稱為 Fib on acci數(shù)列。它可以遞歸地定義為： 請(qǐng)對(duì)這個(gè)無(wú)窮數(shù)列設(shè)計(jì)一個(gè)算法，并進(jìn)行描述(自然語(yǔ)言描述

13、和VC+ 描述) .第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：intfibonacci (int n)if (n <= 1) return 1; 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è)算法解決以上問(wèn)題,并進(jìn)行描述(自然語(yǔ)言和C+ 語(yǔ)言)按分治策略, 將所有的選手分為兩半, n 個(gè)選手的比賽日程表就可以通過(guò)為 n/2 個(gè)選手設(shè)計(jì)的

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