




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、算法分析與設(shè)計(jì)期末復(fù)習(xí)題(一)一、 選擇題1 下列關(guān)于排序算法的敘述,不正確的是?( )A) 堆排序的最差情形運(yùn)行時(shí)間為(nlgn)B) 快速排序平均情形運(yùn)行時(shí)間為(nlgn)C) 任何排序算法的最差情形運(yùn)行時(shí)間都不可能比(nlgn)更小D) 插入排序在最好情形下的運(yùn)行時(shí)間為(n)2.Hanoi塔問題如下圖所示?,F(xiàn)要求將塔座A上的的所有圓盤移到塔座B上,并仍按同樣順序疊置。移動(dòng)圓盤時(shí)遵守Hanoi塔問題的移動(dòng)規(guī)則。由此設(shè)計(jì)出解Hanoi塔問題的遞歸算法正確的為:()A. void hanoi(int n, int A, int C, int B) if (n > 0) hanoi(n-1
2、,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); Hanoi塔B. void hanoi(int n, int A, int B, int C) if (n > 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); C. void hanoi(int n, int C, int B, int A) if (n > 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); D. void hanoi(int n, int C,
3、int A, int B) if (n > 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); 3. 動(dòng)態(tài)規(guī)劃算法的基本要素為()A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B重疊子問題性質(zhì)與貪心選擇性質(zhì)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D. 預(yù)排序與遞歸調(diào)用4. 算法分析中,記號(hào)O表示(B), 記號(hào)表示(A), 記號(hào)表示()。A.漸進(jìn)下界B.漸進(jìn)上界C.非緊上界D.緊漸進(jìn)界E.非緊下界 5. 以下關(guān)于漸進(jìn)記號(hào)的性質(zhì)是正確的有:(A)A.B. C. O(f(n)+O(g(n) = O(minf(n),g(n) D. 6. 能采用貪心算法
4、求最優(yōu)解的問題,一般具有的重要性質(zhì)為:()A 重疊子問題性質(zhì)與貪心選擇性質(zhì)B 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)C 最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D 預(yù)排序與遞歸調(diào)用7. 回溯法在問題的解空間樹中,按()策略,從根結(jié)點(diǎn)出發(fā)搜索解空間樹。E 廣度優(yōu)先 B. 活結(jié)點(diǎn)優(yōu)先 C. 深度優(yōu)先 D. 擴(kuò)展結(jié)點(diǎn)優(yōu)先8. 分支限界法在問題的解空間樹中,按()策略,從根結(jié)點(diǎn)出發(fā)搜索解空間樹。 A深度優(yōu)先B. 活結(jié)點(diǎn)優(yōu)先 C.擴(kuò)展結(jié)點(diǎn)優(yōu)先 D. 廣度優(yōu)先9. 程序塊()是回溯法中遍歷排列樹的算法框架程序。void backtrack (int t) if (t>n) output(x); else for (in
5、t i=t;i<=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); A.void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t+1); B. void backtrack (int t) if (t>n) output(x); else for (int i=0;i<=1;i+) xt=i; if (legal(t) backtrack(t-1)
6、; C.D.void backtrack (int t) if (t>n) output(x); else for (int i=t;i<=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); 10. 回溯法的效率不依賴于以下哪一個(gè)因素?( )A. 滿足約束函數(shù)和上界函數(shù)約束的所有xk的個(gè)數(shù);B. 問題的解空間的形式; C. 計(jì)算上界函數(shù)bound的時(shí)間;D. 計(jì)算約束函數(shù)constraint的時(shí)間;11. 常見的兩種分支限界法為()A. 隊(duì)列式(FIFO)分支限界法與優(yōu)先隊(duì)列式分支限界法;B. 隊(duì)列式(FIFO)分支限界法與堆棧式分支限
7、界法;C. 排列樹法與子集樹法;D. 廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法;12. 記號(hào)O的定義正確的是()。A. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有:0 cg(n) f(n) ;B. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有:0 f(n) cg(n) ;C. O(g(n) = f(n) | 對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所有nn0有:0 f(n)<cg(n) ;D. O(g(n) = f(n) | 對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所有nn0有:0 cg(n) <
8、; f(n) ;15. 記號(hào)的定義正確的是()。A. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有:0 f(n) cg(n) ;B. (g(n) = f(n) | 對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所有nn0有:0 f(n)<cg(n) ;C. O(g(n) = f(n) | 存在正常數(shù)c和n0使得對(duì)所有nn0有:0 cg(n) f(n) ;D. (g(n) = f(n) | 對(duì)于任何正常數(shù)c>0,存在正數(shù)和n0 >0使得對(duì)所有nn0有:0 cg(n) < f(n) ;16. 對(duì)于ELECT(課堂講解的線性時(shí)間內(nèi)找第i小
9、的元素的)算法,下列敘述中不正確的是?( )A) 算法第一步中可以按每五個(gè)元素一組找中位數(shù);B) 算法第一步中可以按每七個(gè)元素一組找中位數(shù);B) 算法第一步中不能按每三個(gè)元素一組找中位數(shù);D) 如果要求的n個(gè)元素的中位數(shù),則中位數(shù)一定是第一步中找到的中位數(shù)中的某一個(gè)。17下列哪些問題不能用貪心法求解?( )A) 0-1背包問題B) 單源最短路徑問題C) 霍夫曼編碼問題D) 最小生成樹問題18. 在快速排序算法中引入隨機(jī)過程的主要目的是什么?( )A) 保證算法總能在O(nlgn)時(shí)間內(nèi)結(jié)束B) 改善確定性算法的平均運(yùn)行時(shí)間C) 避免了算法最壞情況下的發(fā)生D) 改善了確定性算法最壞情形下的平均運(yùn)
10、行時(shí)間19. 下列是動(dòng)態(tài)規(guī)劃算法基本要素的是( )。A、定義最優(yōu)解 B、構(gòu)造最優(yōu)解C、子問題重疊性質(zhì) D、算出最優(yōu)解20. 算法分析中,記號(hào)表示( )。A、漸進(jìn)下界B、漸進(jìn)上界C、非緊上界D、緊漸進(jìn)界21. 回溯法解旅行售貨員問題時(shí)的解空間樹是( )。A、排列樹 B、子集樹C、深度優(yōu)先生成樹D、廣度優(yōu)先生成樹22. 下列算法中通常以自底向上的方式求解最優(yōu)解的是( )。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法23. 下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是( )。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法 D、回溯法24. 常見的兩種分支限界法為( )A、廣度優(yōu)先分支限界法與深度優(yōu)先分支限
11、界法;B、隊(duì)列式(FIFO)分支限界法與堆棧式分支限界法;C、排列樹法與子集樹法;D、隊(duì)列式(FIFO)分支限界法與優(yōu)先隊(duì)列式分支限界法;二、 填空題1. 下面程序段的所需要的計(jì)算時(shí)間為( )。int MaxSum(int n, int *a, int &besti, int &bestj)int sum=0;for(int i=1;i<=n;i+) int thissum=0;for(int j=i;j<=n;j+) thissum+=aj;if(thissum>sum)sum=thissum;besti=i;bestj=j;return sum;2. 有1
12、1個(gè)待安排的活動(dòng),它們具有下表所示的開始時(shí)間與結(jié)束時(shí)間,如果以貪心算法求解這些活動(dòng)的最優(yōu)安排(即為活動(dòng)安排問題:在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合),得到的最大相容活動(dòng)子集合為活動(dòng)( )。1413121110987654fi122886535031Si1110987654321i3. 所謂貪心選擇性質(zhì)是指( )。4. 所謂最優(yōu)子結(jié)構(gòu)性質(zhì)是指( )。5. 回溯法是回溯法是指( )。6. 用回溯法解題的一個(gè)顯著特征是在搜索過程中動(dòng)態(tài)產(chǎn)生問題的解空間。在任何時(shí)刻,算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹 中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h(n),則回溯法所需的計(jì)算空間通常為(
13、 )。7. 回溯法的算法框架按照問題的解空間一般分為( )算法框架與( )算法框架。8. 用回溯法解0/1背包問題時(shí),該問題的解空間結(jié)構(gòu)為( )結(jié)構(gòu)。9.用回溯法解TSP問題時(shí),該問題的解空間結(jié)構(gòu)為( )結(jié)構(gòu)。10.用回溯法解0/1背包問題時(shí),計(jì)算結(jié)點(diǎn)的上界的函數(shù)如下所示,請(qǐng)?jiān)诳崭裰刑钊牒线m的內(nèi)容:Typep Knap<Typew, Typep>:Bound(int i)/ 計(jì)算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 結(jié)點(diǎn)的上界 / 以物品單位重量價(jià)值遞減序裝入物品 while (i <= n && wi
14、 <= cleft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i <= n) (b += pi/wi * cleft); return b;11. 用回溯法解布線問題時(shí),求最優(yōu)解的主要程序段如下。如果布線區(qū)域劃分為的方格陣列,擴(kuò)展每個(gè)結(jié)點(diǎn)需O(1)的時(shí)間,L為最短布線路徑的長度,則算法共耗時(shí) ( ),構(gòu)造相應(yīng)的最短距離需要( )時(shí)間。for (int i = 0; i < NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if
15、(gridnbr.rownbr.col = 0) / 該方格未標(biāo)記 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) && (nbr.col = finish.col) break; / 完成布線 Q.Add(nbr); 12. 用回溯法解圖的m著色問題時(shí),使用下面的函數(shù)OK檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色的可用性,則需耗時(shí)(漸進(jìn)時(shí)間上限)為( )。Bool Color:OK(int k)/ for(int j=1;j<=n;j+)if(akj= =1)&&am
16、p;(xj= =xk) return false;return true;6.7.三、 解答題1. 已知非齊次遞歸方程: ,其中,b、c是常數(shù),g(n)是n的某一個(gè)函數(shù)。則f(n)的非遞歸表達(dá)式為:?,F(xiàn)有Hanoi塔問題的遞歸方程為: ,求h(n)的非遞歸表達(dá)式。2. 單源最短路徑的求解。問題的描述:給定帶權(quán)有向圖(如下圖所示)G =(V,E),其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外,還給定V中的一個(gè)頂點(diǎn),稱為源?,F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。解法:現(xiàn)采用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請(qǐng)將此過程填
17、入下表中。432110030maxint10-1初始dist5dist4dist3dist2uS迭代3. 請(qǐng)寫出用回溯法解裝載問題的函數(shù)。裝載問題:有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船,其中集裝箱i的重量為wi,且。裝載問題要求確定是否有一個(gè)合理的裝載方案可將這n個(gè)集裝箱裝上這2艘輪船。如果有,找出一種裝載方案。4. 用分支限界法解上述裝載問題時(shí),對(duì)算法進(jìn)行了一些改進(jìn),下面的程序段給出了改進(jìn)部分;試說明斜線部分完成什么功能,以及這樣做的原因,即采用這樣的方式,算法在執(zhí)行上有什么不同。/ 檢查左兒子結(jié)點(diǎn) Type wt = Ew + wi; / 左兒子結(jié)點(diǎn)的重量 if (wt
18、 <= c) / 可行結(jié)點(diǎn) if (wt > bestw) bestw = wt; / 加入活結(jié)點(diǎn)隊(duì)列 if (i < n) Q.Add(wt);/ 檢查右兒子結(jié)點(diǎn) if (Ew + r > bestw && i < n) Q.Add(Ew); / 可能含最優(yōu)解 Q.Delete(Ew); / 取下一擴(kuò)展結(jié)點(diǎn) 7. 最長公共子序列問題:給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn,找出X和Y的最長公共子序列。 由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列Xi和Yj的最長公共子序列的長度。其中, Xi=x
19、1,x2,xi;Yj=y1,y2,yj。當(dāng)i=0或j=0時(shí),空序列是Xi和Yj的最長公共子序列。故此時(shí)Cij=0。其它情況下,由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下:在程序中,bij記錄Cij的值是由哪一個(gè)子問題的解得到的。(1) 請(qǐng)?zhí)顚懗绦蛑械目崭瘢允购瘮?shù)LCSLength完成計(jì)算最優(yōu)值的功能。void LCSLength(int m,int n,char *x,char *y,int *c,int *b) int i,j; for (i = 1; i <= m; i+) ci0 = 0; for (i = 1; i <= n; i+) c0i = 0; for (i = 1; i
20、 <= m; i+) for (j = 1; j <= n; j+) if ( ;else if ) ; else ; (2) 函數(shù)LCS實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請(qǐng)?zhí)顚懗绦蛑械目崭?,以使函?shù)LCS完成構(gòu)造最長公共子序列的功能(請(qǐng)將bij的取值與(1)中您填寫的取值對(duì)應(yīng),否則視為錯(cuò)誤)。void LCS(int i,int j,char *x,int *b) if (i =0 | j=0) return; if ( LCS( ); cout<<xi; else if ( ) LCS( ); else LCS( );算法分析與設(shè)計(jì)期末復(fù)習(xí)題(二)一
21、、簡要回答下列問題 :1. 算法重要特性是什么? 2. 算法分析的目的是什么?3. 算法的時(shí)間復(fù)雜性與問題的什么因素相關(guān)?4. 算法的漸進(jìn)時(shí)間復(fù)雜性的含義?5. 最壞情況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性有什么不同?6. 簡述二分檢索(折半查找)算法的基本過程。7. 背包問題的目標(biāo)函數(shù)和貪心算法最優(yōu)化量度相同嗎?8. 采用回溯法求解的問題,其解如何表示?有什么規(guī)定?9. 回溯法的搜索特點(diǎn)是什么? 10. n皇后問題回溯算法的判別函數(shù)place的基本流程是什么?11. 為什么用分治法設(shè)計(jì)的算法一般有遞歸調(diào)用?12. 為什么要分析最壞情況下的算法時(shí)間復(fù)雜性? 13. 簡述漸進(jìn)時(shí)間復(fù)雜性上界的定義。14
22、. 二分檢索算法最多的比較次數(shù)?15. 快速排序算法最壞情況下需要多少次比較運(yùn)算?16. 貪心算法的基本思想?17. 回溯法的解(x1,x2,xn)的隱約束一般指什么?18. 闡述歸并排序的分治思路。19. 快速排序的基本思想是什么。 20. 什么是直接遞歸和間接遞歸?消除遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)?21. 什么是哈密頓環(huán)問題?22. 用回溯法求解哈密頓環(huán),如何定義判定函數(shù)?23. 請(qǐng)寫出prim算法的基本思想。參考答案:1. 確定性、可實(shí)現(xiàn)性、輸入、輸出、有窮性2. 分析算法占用計(jì)算機(jī)資源的情況,對(duì)算法做出比較和評(píng)價(jià),設(shè)計(jì)出額更好的算法。3. 算法的時(shí)間復(fù)雜性與問題的規(guī)模相關(guān),是問題大小n的
23、函數(shù)。4當(dāng)問題的規(guī)模n趨向無窮大時(shí),影響算法效率的重要因素是T(n)的數(shù)量級(jí),而其他因素僅是使時(shí)間復(fù)雜度相差常數(shù)倍,因此可以用T(n)的數(shù)量級(jí)(階)評(píng)價(jià)算法。時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱為漸進(jìn)時(shí)間復(fù)雜性。5. 最壞情況下的時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性考察的是n固定時(shí),不同輸入實(shí)例下的算法所耗時(shí)間。最壞情況下的時(shí)間復(fù)雜性取的輸入實(shí)例中最大的時(shí)間復(fù)雜度:W(n) = max T(n,I) , IDn平均時(shí)間復(fù)雜性是所有輸入實(shí)例的處理時(shí)間與各自概率的乘積和:A(n) =P(I)T(n,I) IDn6. 設(shè)輸入是一個(gè)按非降次序排列的元素表Ai:j 和x,選取A(i+j)/2與x比較,如果A(i+j
24、)/2=x,則返回(i+j)/2,如果A(i+j)/2<x,則Ai:(i+j)/2-1找x,否則在A (i+j)/2+1:j 找x。上述過程被反復(fù)遞歸調(diào)用?;厮莘ǖ乃阉魈攸c(diǎn)是什么7. 不相同。目標(biāo)函數(shù):獲得最大利潤。最優(yōu)量度:最大利潤/重量比。8. 問題的解可以表示為n元組:(x1,x2,xn),xiSi, Si為有窮集合,xiSi, (x1,x2,xn)具備完備性,即(x1,x2,xn)是合理的,則(x1,x2,xi)(i<n)一定合理。9. 在解空間樹上跳躍式地深度優(yōu)先搜索,即用判定函數(shù)考察xk的取值,如果xk是合理的就搜索xk為根節(jié)點(diǎn)的子樹,如果xk取完了所有的值,便回溯到x
25、k-1。10. 將第K行的皇后分別與前k-1行的皇后比較,看是否與它們相容,如果不相容就返回false,測(cè)試完畢則返回true。11 . 子問題的規(guī)模還很大時(shí),必須繼續(xù)使用分治法,反復(fù)分治,必然要用到遞歸。12 最壞情況下的時(shí)間復(fù)雜性決定算法的優(yōu)劣,并且最壞情況下的時(shí)間復(fù)雜性較平均時(shí)間復(fù)雜性游可操作性。 13 .T(n)是某算法的時(shí)間復(fù)雜性函數(shù),f(n)是一簡單函數(shù),存在正整數(shù)No和C,nNo,有T(n)<f(n),這種關(guān)系記作T(n)=O(f(n)。14 .二分檢索算法的最多的比較次數(shù)為 log n 。15.最壞情況下快速排序退化成冒泡排序,需要比較n2次。16. 是一種依據(jù)最優(yōu)化量度
26、依次選擇輸入的分級(jí)處理方法?;舅悸肥牵菏紫雀鶕?jù)題意,選取一種量度標(biāo)準(zhǔn);然后按這種量度標(biāo)準(zhǔn)對(duì)這n個(gè)輸入排序,依次選擇輸入量加入部分解中。如果當(dāng)前這個(gè)輸入量的加入,不滿足約束條件,則不把此輸入加到這部分解中。17回溯法的解(x1,x2,xn)的隱約束一般指個(gè)元素之間應(yīng)滿足的某種關(guān)系。 18. 講數(shù)組一分為二,分別對(duì)每個(gè)集合單獨(dú)排序,然后將已排序的兩個(gè)序列歸并成一個(gè)含n個(gè)元素的分好類的序列。如果分割后子問題還很大,則繼續(xù)分治,直到一個(gè)元素。19.快速排序的基本思想是在待排序的N個(gè)記錄中任意取一個(gè)記錄,把該記錄放在最終位置后,數(shù)據(jù)序列被此記錄分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的放在前一部分,所有
27、比它大的放置在后一部分,并把該記錄排在這兩部分的中間,這個(gè)過程稱作一次快速排序。之后重復(fù)上述過程,直到每一部分內(nèi)只有一個(gè)記錄為止。20.在定義一個(gè)過程或者函數(shù)的時(shí)候又出現(xiàn)了調(diào)用本過程或者函數(shù)的成分,既調(diào)用它自己本身,這稱為直接遞歸。如果過程或者函數(shù)P調(diào)用過程或者函數(shù)Q,Q又調(diào)用P,這個(gè)稱為間接遞歸。消除遞歸一般要用到棧這種數(shù)據(jù)結(jié)構(gòu)。21.哈密頓環(huán)是指一條沿著圖G的N條邊環(huán)行的路徑,它的訪問每個(gè)節(jié)點(diǎn)一次并且返回它的開始位置。22.當(dāng)前選擇的節(jié)點(diǎn)Xk是從未到過的節(jié)點(diǎn),即XkXi(i=1,2,k-1),且C(Xk-1, Xk),如果k=-1,則C(Xk, X1) 。23. 思路是:最初生成樹T為空,
28、依次向內(nèi)加入與樹有最小鄰接邊的n-1條邊。處理過程:首先加入最小代價(jià)的一條邊到T,根據(jù)各節(jié)點(diǎn)到T的鄰接邊排序,選擇最小邊加入,新邊加入后,修改由于新邊所改變的鄰接邊排序,再選擇下一條邊加入,直至加入n-1條邊。二、復(fù)雜性分析題(分析一下算法的復(fù)雜性)1、 MERGESORT(low,high) if low<high; then mid(low,high)/2; MERGESORT(low,mid); MERGESORT(mid+1,high); MERGE(low,mid,high); endif end MERGESORT答: 1、 遞歸方程 設(shè)n=2k解遞歸方程:2、 proced
29、ure S1(P,W,M,X,n) i1; a0 while i n do if W(i)>M then return endif aa+i ii+1 ; repeat end 解: i1 ;s0 時(shí)間為:O(1) while i n do 循環(huán)n次 循環(huán)體內(nèi)所用時(shí)間為 O(1) 所以 總時(shí)間為:T(n)=O(1)+ nO(1)= O(n)3.procedure PARTITION(m,p) Integer m,p,i;global A(m:p-1) vA(m);im looploop ii+1 until A(i) v repeatloop pp-1 until A(p) v repe
30、at if i<p then call INTERCHANGE(A(i),A(p) else exit endif repeat A(m) A(p);A(p) v End PARTITION參考答案:最多的查找次數(shù)是p-m+1次 4.procedure F1(n) if n<2 then return(1) else return(F2(2,n,1,1) endif end F1 procedure F2(i,n,x,y) if in then call F2(i+1,n,y,x+y) endif return(y) end F2解:F2(2,n,1,1)的時(shí)間復(fù)雜度為: T(n)
31、=O(n-2); 因?yàn)閕n時(shí)要遞歸調(diào)用F2,一共是n-2次 當(dāng)n1時(shí)F1(n)的時(shí)間為 O(1)當(dāng)n>1時(shí)F1(n)的時(shí)間復(fù)雜度與F2(2,n,1,1)的時(shí)間復(fù)雜度相同即為為 O(n) 5.procedure MAX(A,n,j) xmaxA(1);j1 for i2 to n do if A(i)>xmax then xmaxA(i); ji;endif repeatend MAX 解:xmaxA(1);j1 時(shí)間為:O(1) for i2 to n do 循環(huán)最多n-1次 所以 總時(shí)間為: T(n)=O(1)+ (n-1)O(1)= O(n)6.procedure BINSRC
32、H(A,n,x,j) integer low,high,mid,j,n; low1;highn while lowhigh do mid|_(low+high)/2_| case :x<A(mid):highmid-1:x>A(mid):lowmid+1:else:jmid; return endcase repeat j0 end BINSRCH參考答案: log2n+1三、算法理解1、寫出多段圖最短路經(jīng)動(dòng)態(tài)規(guī)劃算法求解下列實(shí)例的過程,并求出最優(yōu)值。52863174各邊的代價(jià)如下:C(1,2)=3, C(1,3)=5 ,C(1,4)=2 C(2,6)=8 ,C(2,7)=4 ,C
33、(3,5)=5 ,C(3,6)=4, C(4,5)=2,C(4,6)=1C(5,8)=4, C(6,8)=5 ,C(7,8)=6參考答案樣例 解:Cost(4,8)=0Cost(3,7)= C(7,8)+0=6 ,D5=8Cost(3,6)= C(6,8)+0=5, D6=8Cost(3,5)= C(5,8)+0=4 D7=8Cost(2,4)= minC(4,6)+ Cost(3,6), C(4,5)+ Cost(3,5) = min1+ 5, 2+4=6 D4=6Cost(2,3)= minC(3,6)+ Cost(3,6) = min4+5=9 D3=5Cost(2,2)= minC(2
34、,6)+ Cost(3,6), C(2,7)+ Cost(3,7) = min8+5, 4+6=10 D2=7Cost(1,1)= minC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4) = min3+10, 5+9,2+6= 8D1=414682、 寫出maxmin算法對(duì)下列實(shí)例中找最大數(shù)和最小數(shù)的過程。數(shù)組 A=(48,12,61,3,5,19,32,7) 3、 快速排序算法對(duì)下列實(shí)例排序,算法執(zhí)行過程中,寫出數(shù)組A第一次被分割的過程。 A=(65,70,75,80,85,55,50,2)參考答案樣例解:第一個(gè)分割元素為65(1
35、) (2) (3) (4) (5) (6) (7) (8) i p65 70 75 80 85 55 50 2 2 865 2 75 80 85 55 50 70 3 765 2 50 80 85 55 75 70 4 665 2 50 55 85 80 75 70 4 655 70 75 80 85 65 50 25、寫出歸并排序算法對(duì)下列實(shí)例排序的過程。(6,2,9,3,5,1,8,7)參考答案樣例 解:調(diào)用第一層次 6,2,9,3 5,1,8,7 分成兩個(gè)子問題 調(diào)用第二層次 6,2 9,3 5,1 8,7 分成四個(gè)子問題 調(diào)用第三層次 6 2 9 3 5 1 8 7 分成八個(gè)子問題 調(diào)
36、用第四層次 只有一個(gè)元素返回上一層第三層歸并 2 ,6 3, 9 1,5 7,8 返回上一層第二層歸并 2 ,3,6, 9 1,5,7,8 返回上一層第一層歸并 1, 2 ,3, 5 ,6, 7, 8,9 排序結(jié)束,返回主函數(shù)6、寫出用背包問題貪心算法解決下列實(shí)例的過程。 P=(18,12,4,1) W=(12,10,8,3) M=257、有一個(gè)有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當(dāng)使用二分查找值為82的結(jié)點(diǎn)時(shí),經(jīng)過多少次比較后查找成功并給出過程。解:有一個(gè)有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當(dāng)使用二分
37、查找值為82的結(jié)點(diǎn)時(shí),經(jīng)過多少次比較后查找成功并給出過程。一共要要執(zhí)行四次才能找到值為82的數(shù)。8、使用prim算法構(gòu)造出如下圖G的一棵最小生成樹。124356dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6四、設(shè)計(jì)算法 1、 設(shè)計(jì)一個(gè)算法在一個(gè)向量A中找出最大數(shù)和最小數(shù)的元素。2、 設(shè)有n項(xiàng)獨(dú)立的作業(yè)1,2, n,由m臺(tái)相同的機(jī)器加工處理。作業(yè)i所需要的處理時(shí)間為ti。約定:任何一項(xiàng)作業(yè)可在任何一臺(tái)機(jī)器
38、上處理,但未完工前不準(zhǔn)中斷處理;任何作業(yè)不能拆分更小的子作業(yè)。多機(jī)調(diào)度問題要求給出一種調(diào)度方案,使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器處理完。設(shè)計(jì)算法,并討論是否可獲最優(yōu)解。3. 有n個(gè)物品,已知n=7, 利潤為P=(10,5,15,7,6,18,3),重量W=(2,3,5,7,1,4,1),背包容積M=15,物品只能選擇全部裝入背包或不裝入背包,設(shè)計(jì)貪心算法,并討論是否可獲最優(yōu)解。4、對(duì)于下列各組函數(shù)f(n)和g(n),確定f(n)=O(g(n)或或,并簡述理由。(12分)(1) (2) (3) 5、試用分治法實(shí)現(xiàn)有重復(fù)元素的排列問題:設(shè)是要進(jìn)行排列的個(gè)元素,其中元素可能相同,試計(jì)算的
39、所有不同排列。(13分)6、試用分治法對(duì)一個(gè)有序表實(shí)現(xiàn)二分搜索算法。(12分)7、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)0-1閉包問題。(15分)8、試用貪心算法求解下列問題:將正整數(shù)n分解為若干個(gè)互不相同的自然數(shù)之和,使這些自然數(shù)的乘積最大。(15分)9、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最大子矩陣和問題:求矩陣A的一個(gè)子矩陣,使其各元素之各為最大。(15分)10、試用回溯法解決下列整數(shù)變換問題:關(guān)于整數(shù)的變換和定義如下:。對(duì)于給定的兩個(gè)整數(shù)和,要求用最少的變換和變換次數(shù)將變?yōu)?。?8分)一、 排序和查找是經(jīng)常遇到的問題。按照要求完成以下各題:(20分)(1) 對(duì)數(shù)組A=15,29,135,18,32,1,27,25,5,
40、用快速排序方法將其排成遞減序。(2) 請(qǐng)描述遞減數(shù)組進(jìn)行二分搜索的基本思想,并給出非遞歸算法。(3) 給出上述算法的遞歸算法。(4) 使用上述算法對(duì)(1)所得到的結(jié)果搜索如下元素,并給出搜索過程:18,31,135。參考答案樣例答案:(1)第一步:15 29 135 18 32 1 27 25 5 第二步:29 135 18 32 27 25 15 1 5 【1分】第三步:135 32 29 18 27 25 15 5 1 【1分】第四步:135 32 29 27 25 18 15 5 1 【1分】(2)基本思想:首先將待搜索元素v與數(shù)組的中間元素進(jìn)行比較,如果,則在前半部分元素中搜索v;若,
41、則搜索成功;否則在后半部分?jǐn)?shù)組中搜索v?!?分】非遞歸算法:輸入:遞減數(shù)組Aleft:right,待搜索元素v?!?分】輸出:v在A中的位置pos,或者不在A中的消息(-1)?!?分】步驟:【3分】int BinarySearch(int A,int left,int right,int v)int mid;while (left<=right)mid=int(left+right)/2);if (v=Amid) return mid;else if (v>Amid) right=mid-1;else left=mid+1;return -1;(3)遞歸算法:輸入:遞減數(shù)組Alef
42、t:right,待搜索元素v。【1分】輸出:v在A中的位置pos,或者不在A中的消息(-1)?!?分】步驟:【3分】int BinarySearch(int A,int left,int right,int v)int mid;if (left<=right)mid=int(left+right)/2);if (v=Amid) return mid;else if (v>Amid) return BinarySearch(A,left,mid-1,v);else return BinarySearch(A,mid+1,right,v);elsereturn -1;(4)搜索18:首
43、先與27比較,18<27,在后半部分搜索;再次與18比較,搜索到,返回5?!?分】 搜索31:首先與27比較,31>27,在前半部分搜索;再次32比較,31<32,在后半部分搜索,與29比較,31>29,此時(shí)只有一個(gè)元素,未找到,返回-1。【2分】 搜索135:首先與27比較,135>27,在前半部分搜索;再次32比較,135>32,在前半部分搜索;與135比較,相同,返回0。【2分】二、 對(duì)于下圖使用Dijkstra算法求由頂點(diǎn)a到頂點(diǎn)h的最短路徑。(20分)。參考答案樣例答案:用V1表示已經(jīng)找到最短路徑的頂點(diǎn),V2表示與V1中某個(gè)頂點(diǎn)相鄰接且不在V1中的
44、頂點(diǎn);E1表示加入到最短路徑中的邊,E2為與V1中的頂點(diǎn)相鄰接且距離最短的路徑。【1分】步驟 V1 V2 E1 E21. ab ab2. a,bd ab bd3. a,b,d c,f ab,bd dc,df4. a,b,d,c f ab,bd df5. a,b,c,d,f e ab,bd,dc,df fe6. a,b,c,d,e,fg ab,bd,dc,df,fe eg7. a,b,c,d,e,f,gh ab,bd,dc,df,fe,eggh8. a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 【以上每步2分】結(jié)果:從a到h的最短路徑為,權(quán)值為18?!?分】三、 假設(shè)
45、有7個(gè)物品,它們的重量和價(jià)值如下表所示。若這些物品均不能被分割,且背包容量M150,使用動(dòng)態(tài)規(guī)劃和回溯方法求解此背包問題。請(qǐng)寫出解矩陣(C矩陣與B矩陣)以及回溯方法的狀態(tài)空間搜索樹(30分)。物品ABCDEFG重量35306050401025價(jià)值10403050354030參考答案樣例:解: 按照單位效益從大到小依次排列這7個(gè)物品為:FBGDECA。將它們的序號(hào)分別記為17。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個(gè)節(jié)點(diǎn)處的限界函數(shù)值通過如下方式求得:【排序1分】【狀態(tài)空間搜索樹及其計(jì)算過程17分,每個(gè)節(jié)點(diǎn)1分】a b. c d. e. f. g. h. i.j. 在Q1處獲得該問題的最優(yōu)解為,背包效益為170。即在背包中裝入物品F、B、G、D、A時(shí)達(dá)到最大效益,為170,重量為150。【結(jié)論2分】四、 已知,k=1,2,3,4,5,6,r
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年Z世代消費(fèi)趨勢(shì)下新消費(fèi)品牌競爭策略報(bào)告
- 中藥材質(zhì)控體系建設(shè)
- 急性腹痛的常見病因分析2025
- DEEPSEEK在生產(chǎn)制造場景中的智能排產(chǎn)APS落地方案
- 《前赤壁賦》教案教學(xué)設(shè)計(jì)
- 細(xì)胞模擬生物試題及答案
- 2025年西藏自治區(qū)日喀則市昂仁縣中考一模歷史試題 (含答案)
- 2025農(nóng)業(yè)生產(chǎn)設(shè)備租賃合同格式
- 提升家電產(chǎn)品的用戶體驗(yàn)與客戶粘性
- 福建省季延中學(xué)08-09學(xué)年高二下學(xué)期期中考試(數(shù)學(xué)理)
- 藥品理化檢驗(yàn)培訓(xùn)
- 腹部帶蒂皮瓣護(hù)理
- 甘肅省2025年甘肅高三月考試卷(四4月)(甘肅二診)(物理試題+答案)
- 汽車維修工電子燃油噴射系統(tǒng)試題及答案
- 浙江首考2025年1月普通高等學(xué)校招生全國統(tǒng)一考試 地理 含答案
- 2019全國中學(xué)生生物學(xué)聯(lián)賽試題詳解
- 錨桿靜壓樁專項(xiàng)施工方案
- 火災(zāi)自動(dòng)報(bào)警系統(tǒng)設(shè)計(jì)規(guī)范完整版2025年
- 2025-2030年烘焙專用果醬項(xiàng)目商業(yè)計(jì)劃書
- 高血壓、2型糖尿病、高脂血癥、肥胖癥膳食運(yùn)動(dòng)指導(dǎo)要點(diǎn)基層醫(yī)務(wù)人員應(yīng)用實(shí)操手冊(cè)
- 超市水產(chǎn)海鮮
評(píng)論
0/150
提交評(píng)論