




下載本文檔
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、算法設計與分析試卷一、填空題(20分,每空2分)1、 算法的性質包括輸入、輸出、有限性。2、 動態(tài)規(guī)劃算法的基本思想就將待求問題、先求解子問題,然后從這些子問題的解得到原問題的解。3、 設計動態(tài)規(guī)劃算法的4個步驟:(1) 找出,弁刻畫其結構特征。(2) 。(4) 根據計算最優(yōu)值得到的信息,。4、 流水作業(yè)調度問題的johnson算法:(1) 令N1=,N2=i|ai>=bj;(2) 將N1中作業(yè)依ai的。5、對于流水作業(yè)高度問題,必存在一個最優(yōu)調度兀,使得作業(yè)兀(i)和兀(i+1)滿足Johnson不等式。6、最優(yōu)二叉搜索樹即是的二叉搜索樹。二、綜合題(50分)1、當(a1,a2,a3,
2、a4,a5,a6)=(-2,11,-4,13,-5,-2)時,最大子段和為Eak(2<=k<=4)(5分)2、由流水作業(yè)調度問題的最優(yōu)子結構性質可知,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、設計最優(yōu)二叉搜索樹問題的動
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、設n=4,(a1,a2,a3,a4)=(3,4,8
4、,10),(b1,b2,b3,b4)=(6,2,9,15)用兩種方法求4個作業(yè)的最優(yōu)調度方案并計算其最優(yōu)值?(15分)三、簡答題(30分)1、將所給定序列a1:n分為長度相等的兩段a1:n/2和an/2+1:n,分別求出這兩段的最大子段和,則a1:n的最大子段和有哪三種情形?(10分)答:2、由01背包問題的最優(yōu)子結構性質,可以對m(i,j)建立怎樣的遞歸式?(10分)3、01背包求最優(yōu)值的步驟分為哪幾步?(10分)參考答案:填空題:確定性分解成若干個子問題最優(yōu)解的性質遞歸地定義最優(yōu)值以自底向上的方式計算出最優(yōu)值構造最優(yōu)解i|ai<biai的非減序排序;將N2中作業(yè)依bi的非增序排序mi
5、nb喇后項+i)>minb#1)總電)最小平均查找長度綜合題:20minai+T(N-i,bi)(1=<i<=n)thissum+=akbesti=i0mi+1jt<mij法一:min(ai,bj)<=min(aj,bi)因為min(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、受控點=pi+1Uqi+1其中的受控(4)、重復(2)-(3)直到求出P11 .在一個算法中調用另一個算法時,系統(tǒng)需在運行被調用算法之前完成哪些工作?同時從被調用算法返回調用算法需完成哪些工作?答:在一個算法中調用另一算法時,系統(tǒng)需在運行被調用算法之前先完成三件事:(1) 將所有實參指針、返回地址等信息傳遞給被調用算法;(2) 為被調用算法的局部變量分配存儲區(qū);(3) 將控制轉移到被調用算法的入口。在從被調用算法返回調用算法時需完成三件事:(1) 保存被調用算法的計算結果;(2) 釋放分配給被調用算法的數據區(qū);(3) 依照被調用算法保存的返回地址將控制轉移到調用算法。2 .動態(tài)規(guī)劃算法求解問題
8、的步驟?答:動態(tài)規(guī)劃法適用于解最優(yōu)化問題。通??梢园匆韵?個步驟設計:(1) 找出最優(yōu)解的性質,并刻畫其結構特征;(2) 遞歸地定義最優(yōu)值;(3) 以自底向上的方式計算最優(yōu)值;(4) 根據計算最優(yōu)值時得到的信息構造最優(yōu)解。3 .線性規(guī)劃法中單純形算法的基本步驟?答:步驟一選入基變量。步驟二選離基變量。步驟三做轉軸變換。步驟四轉步驟一。4 .分治法的基本思想和原理是什么?答:分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題,這些子問題互相獨立且與原問題相同。遞歸地解這些子問題,然后將各子問題的解合并得到原問題的解。5 .利用回溯法解決問題包含哪些步驟?答:利用回溯法解題常包含以下
9、3步驟:(1) 針對所給問題,定義問題的解空間;(2) 確定易于搜索的解空間結構;(3) 以深度優(yōu)先方式搜索解空間,并在搜索過程中用剪枝函數避免無效搜索。五分析題(36分)1 .求下列函數的漸進表達式: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ū)別。分析與解答:根據符號0的定義易知0(1)=0(2)。用0(1)或0(2)表示同一個函數時,差別僅在于其中的常數因子。3 .按漸近階排列表達式按
10、照漸近階從低到高的順序排列以下表達式:4n2,logn,3n,20n,2,n2/3。又n!應該排在哪一位?分析與解答:按漸近階從低到高,函數排列順序如下:2,logn,n2/3,20n,4n13n,n!。4 .算法效率(1)假設某算法在車入規(guī)模為n時計算時間為T(n)=3*2n。在某臺計算機上實現并完成該算法的時間為t秒。現有另一臺計算機,其運行速度為第一臺的64倍,那么在這臺新機器上用同一算法在t秒內能解輸入規(guī)模為多大的問題?(2)若上述算法的計算時間改進為T(n)=n2,其余條件不變,則在新機器上用t秒時間能解輸入規(guī)模為多大的問題?(3)若上述算法的計算時間進一步改進為T(n)=8,其余條
11、件不變,那么在新機器上用t秒時間能解輸入規(guī)模為多大的問題?分析解答:(1)設新機器用同一算法在t秒內能解輸入規(guī)模為n1的問題。因此有:t=3*22=3*2n1/64,解得你n1=n+6。(2)n12=64n2;n1=8n。(3)由于T(n)=常數,因此算法可解任意規(guī)模的問題。5 .階乘函數階乘函數可遞歸地定義為:'1n=0n!=*n(n-1)!n>0intfactorial(intn)if(n=0)return1;returnn*factorial(n-1);6 .Fibonacci數列無窮數列1,1,2,3,5,8,13,21,34,55,,稱為Fibonacci數列。它可以遞
12、歸地定義為:|1n=0F(n)=1n=1F(n_1)+F(n.2)n>1請對這個無窮數列設計一個算法,并進行描述(自然語言描述和VC+描述).第n個Fibonacci數可遞歸地計算如下:intfibonacci(intn)(if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);7 .循環(huán)賽日程表設有n=2k個運動員要進行兵乓球循環(huán)賽?,F在要設計一個滿足以下要求的比賽日程表:(1)每個選手必須與其他n-1個選手各賽一次;(2)每個選手一天只能賽一次;(3)循環(huán)賽一共進行n-1天。請設計一個算法解決以上問題,并進行描述(自然語言和C+語
13、言)按分治策略,將所有的選手分為兩半,n個選手的比賽日程表就可以通過為n/2個選手設計的比賽日程表來決定。遞歸地用對選手進行分割,直到只剩下2個選手時,比賽日程表的制定就變得很簡單。這時只要讓這2個選手進行比賽就可以了。8 .有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wio最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下,將盡可能多的集裝箱裝上輪船。分析回答以下兩個問題:(1)分析以上最優(yōu)裝載問題具有貪心選擇性質(2)用C+程序進行正確的算法描述分析與解答:(1) 設集裝箱已依其重量從小到大排序,(X1,X2,,Xn)是最有裝載問題的一個最優(yōu)解。又設k=mini|xi=1。易知,如果給定的最有裝載問題有解,則1wkwn。當k=1時,(x1,x2,,Xn)是滿足貪心選擇性質的最優(yōu)解。當k>1時,取y1=1;yk=0;yi=x,1<i<n,iwk,則因此,()是所給最有裝載問題的可行解。另一方面,由知,()是滿足貪心選擇性質的最優(yōu)解。所以,最優(yōu)裝載問題具有貪心選擇性質。(2)最優(yōu)裝載問題可用貪心
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 公司組織團日活動方案
- 公司熒光夜跑活動方案
- 公司疫情理發(fā)活動方案
- 公司溫情環(huán)節(jié)活動方案
- 公司激勵經銷商活動方案
- 公司新年娛樂活動方案
- 公司活動創(chuàng)新活動方案
- 公司線上中秋節(jié)活動方案
- 公司月主體研討活動方案
- 公司紀念畫冊策劃方案
- 醫(yī)學高級職稱評審答辯報告PPT模板
- 《緩解新入園幼兒焦慮策略的研究》課題結題材料(開題報告、中期報告、結題報告、調查問卷、課題論文)
- 健康生活方式基本的知識講座
- 消防管理檢查評分表
- 制造執(zhí)行系統(tǒng)SMT MES解決方案
- 高二區(qū)域地理 撒哈拉以南的非洲課件
- 數字化精密加工車間項目可行性研究報告建議書
- 2022年《內蒙古自治區(qū)建設工程費用定額》取費說明
- Q∕GDW 10799.6-2018 國家電網有限公司電力安全工作規(guī)程 第6部分:光伏電站部分
- 寧波市建設工程資料統(tǒng)一用表(2022版)1 通用分冊
- 危險化學品安全技術說明書MSDS—汽油
評論
0/150
提交評論