計算機算法試題含答案1

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

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

3、 sum;4、設(shè)計最優(yōu)二叉搜索樹問題的動態(tài)規(guī)劃算法OptimalBinarysearchTree?(15 分)Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w)for(int i=0;i<=n;i+)wi+1i=ai; mi+1i= ;for(int r=0;r<n;r+)for(int i=1;iv=n-r;i+)int j=i+r;wij=wij-1+aj+bj;mij= ;sij=i;for(int k=i+1;kv=j;k+)int t=mik-1+mk+1j;if( )mij=t; sij=k;mi

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

5、計算出最優(yōu)值構(gòu)造最優(yōu)解i|aivbi ai的非減序排序；將N2中作業(yè)依bi的非增序排序minb ni),ani+i)minb ni+i),anD 最小平均查找長度綜合題：20minai+T(N-i,bi)(仁<i<=n)thissum+=ak besti=i 0mi+1jt<mij法一：min(ai,bj)v=min(aj,bi) 因為 min(a1,b2)v=min(a2,b1)所以1 -2(先1后2)由 min(a1,b3)v=min(a3,b1)得 1-3 (先1后3)同理可得：最后為1 3 42法二：johnson算法思想N1= 1 , 3, 4 N2 = 2N11

6、= 1 , 3, 4 N 12= 2所以 N 11 N12得：1 3 4 2簡答題：1、(1) a1:n的最大子段和與a1:n/2的最大子段和相同(2) a1:n的最大子段和與的最大子段an/2+1:n和相同。(3 ) a1:n的最大子段和為刀ak(i=vkv=J),且1<=iv=n/2,n/2+lv=Jv=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

7、+1=(0,0)(2) 、由 pi+1- qi+1,qi+1=pi+1(wi,vi)(3) 、Mij=pi+1 U qi+1Pi=Mij 其中的受控點= pi+1 U qi+1其中的受控(4) 、重復(fù)(2) - ( 3)直到求出P11. 在一個算法中調(diào)用另一個算法時，系統(tǒng)需在運行被調(diào)用算法之前完成哪些工作？同時從被調(diào)用算法返回調(diào)用算法需完成哪些工作？答：在一個算法中調(diào)用另一算法時，系統(tǒng)需在運行被調(diào)用算法之前先完成三件事：(1) 將所有實參指針、返回地址等信息傳遞給被調(diào)用算法；(2) 為被調(diào)用算法的局部變量分配存儲區(qū)；(3) 將控制轉(zhuǎn)移到被調(diào)用算法的入口。在從被調(diào)用算法返回調(diào)用算法時需完成三件事

8、：(1) 保存被調(diào)用算法的計算結(jié)果；(2) 釋放分配給被調(diào)用算法的數(shù)據(jù)區(qū)；(3) 依照被調(diào)用算法保存的返回地址將控制轉(zhuǎn)移到調(diào)用算法。2. 動態(tài)規(guī)劃算法求解問題的步驟？答：動態(tài)規(guī)劃法適用于解最優(yōu)化問題。通?？梢园匆韵?個步驟設(shè)計：(1) 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；(2) 遞歸地定義最優(yōu)值；(3) 以自底向上的方式計算最優(yōu)值；(4) 根據(jù)計算最優(yōu)值時得到的信息構(gòu)造最優(yōu)解。3. 線性規(guī)劃法中單純形算法的基本步驟？答：步驟一選入基變量。步驟二選離基變量。步驟三做轉(zhuǎn)軸變換。步驟四轉(zhuǎn)步驟一。4. 分治法的基本思想和原理是什么？答：分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，

9、這些子 問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得 至噸問題的解。5. 利用回溯法解決問題包含哪些步驟？答：利用回溯法解題常包含以下3步驟：(1) 針對所給問題，定義問題的解空間；(2) 確定易于搜索的解空間結(jié)構(gòu)；(3) 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。五分析題(36分)1 求下列函數(shù)的漸進表達(dá)式：3n2+10n; n2/10+2n; 21+1/n; logn 3; 10log3n分析與解答：2 23n +10n=0(n );n2/10+2n=O(2n);21+1/n=0(1);3logn =O(log n);10log3n=O(

10、n)2 .討論0(1)和0(2)的區(qū)別。分析與解答： 根據(jù)符號0的定義易知 0(1)=0(2)。用0(1)或0(2)表示同一個函數(shù)時，差別僅在于其中的 常數(shù)因子。3按漸近階排列表達(dá)式按照漸近階從低到高的順序排列以下表達(dá)式：4n2，logn，3n，20n，2，n2/3。又n!應(yīng)該排在哪一位？分析與解答：按漸近階從低到高，函數(shù)排列順序如下：2，logn，n2/3，20n, 4n2，3n，n !。4.算法效率(1) 假設(shè)某算法在輸入規(guī)模為 n時計算時間為T(n)=3*2 n。在某臺計算機上實現(xiàn)并完成該算法 的時間為t秒?，F(xiàn)有另一臺計算機，其運行速度為第一臺的64倍，那么在這臺新機器上用同一算法在t秒

11、內(nèi)能解輸入規(guī)模為多大的問題？ 若上述算法的計算時間改進為T(n)=n 2,其余條件不變，則在新機器上用t秒時間能解輸入規(guī)模為多大的問題？(3)若上述算法的計算時間進一步改進為T(n)=8，其余條件不變，那么在新機器上用t秒時間能解輸入規(guī)模為多大的問題？分析解答：(1) 設(shè)新機器用同一算法在t秒內(nèi)能解輸入規(guī)模為 n1的問題。因此有：t=3*2 2=3*2n1/64，解得你n仁n+6。(2) n1 2=64 n2n 1=8n。(3) 由于T(n)=常數(shù)，因此算法可解任意規(guī)模的問題。5階乘函數(shù)階乘函數(shù)可遞歸地定義為:n! = *"n 1)!int factorial( int n)if(n

12、=0) return 1; return n* factorial( n-1);6. Fibonacci 數(shù)列無窮數(shù)列1, 1, 2, 3, 5, 8, 13, 21, 34, 55,，稱為 Fibonacci數(shù)列。它可以遞歸地 定義為：”1n=0F( n)=«1n=1F(n_ 1)+F(n _ 2)n=1請對這個無窮數(shù)列設(shè)計一個算法，并進行描述(自然語言描述和VC+描述)第n個Fibonacci數(shù)可遞歸地計算如下：int fibonacci (int n)if (n <= 1) return 1;returnfibonacci (n-1)+ fibonacci (n-2);7

13、. 循環(huán)賽日程表設(shè)有n=2k個運動員要進行兵乓球循環(huán)賽?，F(xiàn)在要設(shè)計一個滿足以下要求的比賽日程表：(1) 每個選手必須與其他 n-1個選手各賽一次；(2) 每個選手一天只能賽一次；(3) 循環(huán)賽一共進行n-1天。請設(shè)計一個算法解決以上問題，并進行描述(自然語言和C+語言)按分治策略，將所有的選手分為兩半，n個選手的比賽日程表就可以通過為 n/2個選手設(shè)計的比賽日程表來決定。遞歸地用對選手進行分割，直到只剩下2個選手時，比賽日程表的制 定就變得很簡單。這時只要讓這 2個選手進行比賽就可以了。&有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為 Wi。最優(yōu)裝載問題要求確定在裝載體積

14、不受限制的情況下，將盡可能多的集裝箱裝上輪船。分析回答以下兩個問題：(1) 分析以上最優(yōu)裝載問題具有貪心選擇性質(zhì)(2) 用C+程序進行正確的算法描述分析與解答：(1)設(shè)集裝箱已依其重量從小到大排序，(X1,X2,Xn)是最有裝載問題的一個最優(yōu)解。又設(shè)k=mini|x i=1。易知，如果給定的最有裝載問題有解，則K k< n。 當(dāng)k=1時，(x1,x2,兇)是滿足貪心選擇性質(zhì)的最優(yōu)解。當(dāng) k>1 時，取 y1=1;y k=0;y i=Xi ,1<i < n,i 豐 k,貝U因此，（）是所給最有裝載問題的可行解。另一方面，由知，（）是滿足貪心選擇性質(zhì)的最優(yōu)解。所以，最優(yōu)裝載問題具有貪心 選擇性質(zhì)。（2）最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu) 裝載問題的