計(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)找出_，并刻畫(huà)其結(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)二叉搜索樹(shù)即是_的二叉搜索樹(shù)。二、綜合題(50分)1、 當(dāng)(a1

2、,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;ksum)sum=thissum;-?bestj=j;return sum;4、設(shè)計(jì)最優(yōu)二叉搜索樹(shù)問(wèn)題的動(dòng)態(tài)規(guī)劃算法Optima

3、lB in arysearchTree (15分)Void OptimalB in arysearchTree(i nt a,i nt n ,i nt * * m, int* * w)for(i nt i=0;i=n;i+) wi+1i=ai; mi+1i=_;for(int r=0;rn;r+) for(int 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+)int t=mik-1+mk+1j;if(_) mij=t; sij=k;mij=t; sij=k;5、 設(shè)n=4, (a1,a2,a3,

4、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、01背包求最優(yōu)值的步驟分為哪幾步(10分)參考答案：填空題 ：確定性 分解成若干個(gè)子問(wèn)題 最優(yōu)解的性質(zhì) 遞歸地定義最優(yōu)值 以自底向上的方式計(jì)算出最優(yōu)值構(gòu)造最優(yōu)解i|aiminbn(i+i),an 最小平均查

5、找長(zhǎng)度綜 合 題 ：20minai+T(N-i,bi)(1=i=n)thissum+=ak besti=i 0mi+1jtmij法一：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)同理可得：最后為1-3-4-2法二：johnson算法思想N1=1,3,4 N2=2N1 1=1,3,4 N 1 2=2所以N 1 1N1 2得：1342簡(jiǎn)答題：1、 (1)a1 :n的最大子段和與a1:n/2的最大子 段和相同。(2)a 1 :n的最大子段和與的最大子段an/2+1:n和

6、相同。(3)a1:n的最大子段和為刀ak(i=vkv=J),且1=i=n/2,n/2+1=J=wi)或則m(i,j)= m(i+1,j)(0v=jvwi)(2)m(n,j)=un j=wn或則m(n,j)=0 0v=jvwn3、 (1)、pn+1 =(0,0)(2) 、由pi+1qi+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)用算法需完成哪些工作答：在一個(gè)算法中調(diào)用另

7、一算法時(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ì)，并刻畫(huà)其結(jié)構(gòu)特征；（2）遞歸地定義最優(yōu)值；（3）以自底向上的方式計(jì)算最優(yōu)值；（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造

8、最優(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 分)1求下列函數(shù)的漸進(jìn)表達(dá)式：3n2+10n;

9、n2/10+2n; 21+1/n; logn3; 10log3n分析與解答：2 .討論 0(1)和 0(2)的區(qū)別。分析與解答：根據(jù)符號(hào) 0 的定義易知 0(1)=0(2) 。用 0(1)或 0(2)表示同一個(gè)函數(shù)時(shí)，差別僅在于其中的常數(shù)因子。223n2+10n=O(n2);n2/10+2n=O(2n);21+1/n=O(1);3logn =O(logn);10log3n=O(n)3 按漸近階排列表達(dá)式按照漸近階從低到高的順序排列以下表達(dá)式：4n2, logn , 3n, 20n, 2, n2/3。又 n!應(yīng)該排在哪一位分析與解答：按漸近階從低到高，函數(shù)排列順序如下：2，logn，n2/3，2

10、0n, 4n2, 3： n !。4.算法效率(1)假設(shè)某算法在輸入規(guī)模為 n 時(shí)計(jì)算時(shí)間為 T(n)=3*2n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法 的時(shí)間為 t 秒?，F(xiàn)有另一臺(tái)計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的64 倍，那么在這臺(tái)新機(jī)器上用同一算法在 t 秒內(nèi)能解輸入規(guī)模為多大的問(wèn)題 若上述算法的計(jì)算時(shí)間改進(jìn)為T(mén)(n)=n2,其余條件不變，則在新機(jī)器上用 t 秒時(shí)間能解輸入規(guī)模為多大的問(wèn)題(3)若上述算法的計(jì)算時(shí)間進(jìn)一步改進(jìn)為T(mén)(n)=8，其余條件不變，那么在新機(jī)器上用t 秒時(shí)間能解輸入規(guī)模為多大的問(wèn)題分析解答：(1)設(shè)新機(jī)器用同一算法在t 秒內(nèi)能解輸入規(guī)模為 n1 的問(wèn)題。因此有：t=3*22=3*2

11、n1/64，解得你 n 仁 n+6。2 2n1 =64n n 仁 8n。(3)由于 T(n)=常數(shù)，因此算法可解任意規(guī)模的問(wèn)題。44 階乘函數(shù)階乘函數(shù)可遞歸地定義為:n!1n0n(n1)!n0int 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，.，稱為 Fibo nacci 數(shù)列。它可以遞歸地定義為：1n0F(n)1n1F(n1)F(n2)n1請(qǐng)對(duì)這個(gè)無(wú)窮數(shù)列設(shè)計(jì)一個(gè)算法，并進(jìn)行描述(自然語(yǔ)言描述和VC+苗述)第 n 個(gè)

12、 Fibonacci 數(shù)可遞歸地計(jì)算如下：int fibonacci (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)賽。現(xiàn)在要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他 n-1 個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行 n-1 天。if(n=0) return 1;請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法解決以上問(wèn)題，并進(jìn)行描述(自然語(yǔ)言和C+語(yǔ)言)按分治策略，將所有的選手分為兩半，n 個(gè)選手的比賽日程表就可以通過(guò)為 n/2 個(gè)選手設(shè)計(jì) 的比

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