中南大學(xué)現(xiàn)代遠(yuǎn)程教育課程考試復(fù)習(xí)試題及參考答案.doc

中南大學(xué)現(xiàn)代遠(yuǎn)程教育課程考試復(fù)習(xí)試題及參考答案算法分析與設(shè)計(jì)一 簡(jiǎn)答題 1. 算法的復(fù)雜性分析主要是分析算法的什么耗費(fèi)情況？ 2. 算法的重要特性是什么？3. 算法的時(shí)間復(fù)雜度用什么計(jì)量？4. 用比較樹模型描述三個(gè)數(shù)排序的過程。5. 分治法的基本思想。6. 二分檢索算法為什么可以提高查找的效率？7. 簡(jiǎn)述順序選擇select算法的基本流程。8. 簡(jiǎn)述順序選擇select2算法的改進(jìn)思路。9. 簡(jiǎn)述快速排序的基本思想。10. 快速排序算法的最壞時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性函數(shù)。11. 快速排序算法怎樣抽取分割元素？12. partition怎樣將數(shù)組劃分成3段？13. 分治合并排序的是怎樣分治的？14. 分治合并排序的二分歸并過程在最壞情況下花費(fèi)多少時(shí)間？15. 分治合并排序的二分歸并過程在最好情況下花費(fèi)多少時(shí)間？16. MaxMin算法是怎樣分治的？17. 貪心法的基本思路是什么？18. 用貪心法求解的問題有什么特點(diǎn)？19. 背包問題的目標(biāo)函數(shù)是什么，最優(yōu)量度是什么？20. 帶限期的作業(yè)調(diào)度的貪心策略是什么？約束條件是什么？21. 說明n皇后問題的解（x1,x2,.,xn）的含義。22. 簡(jiǎn)述n皇后算法的place函數(shù)的功能。23. 簡(jiǎn)述動(dòng)態(tài)規(guī)劃方法所運(yùn)用最優(yōu)化原理。24. 用多段圖說明最優(yōu)化原理。二 解釋下列動(dòng)態(tài)規(guī)劃優(yōu)解的一般遞歸形式。1） 0/1背包2） 貨郎擔(dān)問題3） 流水作業(yè)調(diào)度 三 算法分析。1 分析漢諾塔算法的時(shí)間復(fù)雜性。2 計(jì)算冒泡排序算法時(shí)間復(fù)雜性的階。3 分析maxmin算法的時(shí)間復(fù)雜性。4 分析分治合并排序算法的時(shí)間復(fù)雜性。5 分析二分檢索的時(shí)間復(fù)雜性。6 背包問題貪心算法的時(shí)間復(fù)雜性。7 快速排序的partition過程中，進(jìn)行了多少次元素之間的比較。8 多段圖算法的時(shí)間復(fù)雜性。四 算法段填空。 1 MaxMin 算法Maxmin(i,j,max,min)if then 對(duì)兩元素進(jìn)行比較;return;else maxmin(i,m,max1,min1); /其中max1和min1為解子問題1的解 2 Hanoi算法Hanoi(n,a,b,c)If n=1 then Else ;Hanoi(n-1,b, a, c);3 二分檢索BINSRCH(A,n,x,j)low1;highn;while lowhigh do _ mid(low+high)/2;case ：x=Amid ：jmid; return;：x Amid：_lowmid+1;endcasej0;end4 快速排序Quicksort(p,q)if pq then_ call partition(p,j);call _call _end 5 貪心方法的抽象化控制 procedure GREEDY(A，n) /A(1：n)包含n個(gè)輸入/ solutions ； for i1 to do xSELECT(A) if FEASIBLE(solution，x) then solutions ； endif return(solution)end GREEDY6 背包問題貪心算法procedure GREEDY-KNAPSACK(P，W，M，X，n) X0 ； cuM ； for i1 to n do if then exit endif X(i) _ ； cu ； if i n then X(i) ； endif end GREEDY-KNAPSACK7 分治合并排序算法procedure MERGESORT(low,high) if low M,i=1,2,3，n。最優(yōu)解是貨船能夠裝載最多的集裝箱。設(shè)計(jì)貪心算法。4 有n 個(gè)程序和長(zhǎng)度為L(zhǎng)的磁帶，程序i的長(zhǎng)度為ai，已知，求最優(yōu)解(xi，x2 ，.，xi， xn)，1, xi =1，表示程序i存入磁帶，xi =0，表示程序i不存入磁帶，滿足，且存放的程序數(shù)目最多。參考答案一、 簡(jiǎn)答題1. 算法的復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的耗費(fèi)量，需要的時(shí)間資源的耗費(fèi)量稱作時(shí)間復(fù)雜性。2. 有5個(gè)基本特性是：確定性、能行性、輸入給定、產(chǎn)生輸出、有窮性。3. 算法復(fù)雜性用算法的基本運(yùn)算步驟計(jì)量，運(yùn)算步驟與算法要解的問題的規(guī)模、算法的輸入有關(guān)。4. 比較樹模型5. 分治的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。找出各部分的解，然后把各部分的解組合成整個(gè)問題的解。6. 分治算法時(shí)間是這樣確定的：解決子問題所需的工作總量由子問題的個(gè)數(shù)、解決每個(gè)子問題的工作量、合并所有子問題所需的工作量所決定。折半查找最壞情況下，也只需要在原問題一半大小的子問題中查找，而且不需要合并子問題。7. 首先對(duì)于數(shù)組ap：q進(jìn)行劃分，以元素v為基準(zhǔn)元素將a劃分為三段ap：j-1，aj和aj+1：q，使得ap：j-1中任何一個(gè)元素都小于v，aj+1：q中任何一個(gè)元素大于等于v，下標(biāo)j在劃分中確定。如果 k = j ，則返回v；如果 k j ，則在aj+1：q中選擇；8. select算法的最壞情況下的時(shí)間復(fù)雜性的階為O(n2)，其原因是ap：j-1和aj+1：q的大小不是均衡的。Select2算法的基本思路就是改隨即抽取v為經(jīng)過經(jīng)處理產(chǎn)生，保證在最壞情況下ap：j-1和aj+1：q的元素個(gè)數(shù)不會(huì)小于原規(guī)模的1/4。9. 快速排序是基于分治策略的一個(gè)排序算法。基本思路：a) 分解(Divide) 以元素v為基準(zhǔn)元素將a劃分為三段ap：j-1，aj和aj+1：q，使得ap：j-1中任何一個(gè)元素都小于v，aj+1：q中任何一個(gè)元素大于等于v，下標(biāo)j在劃分中確定。b) 遞歸求解，通過遞歸調(diào)用快速排序算法分別對(duì)ap:j-1 和aj+1:q進(jìn)行排序。不必進(jìn)行任何合并操作。10. 快速排序算法的最壞情況下的時(shí)間復(fù)雜性的階為O(n2)，其原因是ap：j-1和aj+1：q的大小不是均衡的?？焖倥判蛩惴ǖ钠骄鶗r(shí)間復(fù)雜性的階為O(n log n)。11. 采用隨機(jī)抽取。對(duì)于數(shù)組ap：q，用v= ap作為分割元素。12. 使v= ap，q=q+1while (pq) do do p+; while (ap v);if (pq) 交換ap和aq；13. if 問題不可分 then 求解else m = (p+q)/2; 對(duì)ap,m排序； 對(duì)am+1，q排序； 將ap,m和am+1，q合并； 14. 分治合并排序的二分歸并過程在最壞情況下需比較n-1次，花費(fèi)可用cn表示。15. 最好情況下需比較n/2次。16. Maxmin(p,q,max,min)if 問題不可分：n=2then 對(duì)兩元素進(jìn)行比較產(chǎn)生max,min;return;elsem = (p+q)/2;Maxmin(p,m,max1,min1);maxmin(m+1,q,max2,min2);max=maxnum(max1,max2);min=minnum(min1,min2);17. 貪心算法的基本思路：從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。18. 具備最優(yōu)子結(jié)構(gòu)。19. 目標(biāo)函數(shù)：pi最大，最優(yōu)量度是選擇有最大利潤(rùn)/重量的物品。20. pi最大 ，i屬于可完工子集。21. xi表示第i行上的皇后所在的列。22. place函數(shù)的功能是判斷第k行皇后的位置和前k-1個(gè)皇后是否相容。23. 最優(yōu)化原理：無論過程的初始狀態(tài)是什么，其余的決策都必須相對(duì)于初始決策所產(chǎn)生的狀態(tài)是最優(yōu)的。通俗地講，每一步最優(yōu)都是上一步最優(yōu)加上本段的最優(yōu)。即當(dāng)前最優(yōu)只與上一步有關(guān)。24. 向前決策到第i段時(shí)，第i段的節(jié)點(diǎn)j的最優(yōu)可以用第i-1段的最優(yōu)值加上本段的長(zhǎng)度：cost(i,j)=mincost(i-1,l)+c(j,l) l是i-1段的節(jié)點(diǎn)j的后繼節(jié)點(diǎn)。二、 動(dòng)態(tài)規(guī)劃遞歸式1. fi(X)= maxfi-1(X-wi)+pi ，fi-1(X), （0=X1 執(zhí)行, T(n)=2 T(n-1)+1。用遞推式求T(n)。T(n)=2T(n-1)+1=22T(n-2)+1+1=22T(n-2)+2+1=222T(n-3) +2+1=23T(n-3)+ 22+2+1=232T(n-4)+ 1+22+2+1=24T(n-4)+ 23+22+2+1=2n-1T(1)+ 2n-2 +22+2+1=2n-12. 計(jì)算冒泡排序算法時(shí)間復(fù)雜度冒泡排序的主要步驟：for i=1 to n-1 do for j=1 to n-i do if aj aj+1 then 交換aj，aj+1；用比較次數(shù)作為算法的計(jì)量，比較一次所花的時(shí)間為常數(shù)，用O(1)表示，內(nèi)循環(huán)所花時(shí)間O(1)=O(n-i) ，外循環(huán)所花時(shí)間：O(n-i)=O(n(n-1)/2)= O(n2)3. 分析MaxMin的比較次數(shù)：當(dāng)n=2，T(2)=1當(dāng)n2時(shí)，比較次數(shù)T(n)=2T(n/2)+2設(shè)n是2的k次冪， n=2kT(n)=2T(2k-1)+2=22T(2k-1)+2+2=22T(2k-2)+22+2=2k-1T(2)+ 2k-1+22+2=2k-1+ 2k-1+22+2=2k-1+2k-2=3*2k-1-2=3n/2-2T(n)= 3n/2-24. 分治合并排序算法的時(shí)間復(fù)雜性設(shè)n個(gè)元素排序的mergesort算法的比較次數(shù)為T(n)，當(dāng)n=1，T(1)=a當(dāng)n1時(shí)：1）分別兩次調(diào)用mergesort對(duì)n/2的元素進(jìn)行排序，比較次數(shù)為2T(n/2)；2）合并兩個(gè)子問題的解所花時(shí)間為n-1T(n)= 2T(n/2)+n-1 設(shè)n是2的k次冪， n=2kT(n)=2T(2k-1)+cn=22T(2k-2)+ 2k-1 +n-1= 22T(2k-2)+ 2cn=23T(2k-3)+ 3cn=2kT(1)+kcn=an+c n log n如果2k n2k+1 ，T(n) T(2k+1)T(n)=O(n log n)5. 分析二分檢索的時(shí)間復(fù)雜性當(dāng)n=1，T(1)=1當(dāng)n1時(shí)：比較1次后，調(diào)用原過程在n/2的元素中查找，過程可用一棵二叉樹表示?？紤]最壞情況：比較到最后，x不在其間，比較次數(shù)就是二叉樹的深度。所以T(n)= log n+16. 背包問題貪心算法的時(shí)間復(fù)雜性如果不考慮排序的時(shí)間，背包問題貪心算法的時(shí)間就是循環(huán)語句：for i=1 to n do 執(zhí)行的時(shí)間，循環(huán)體語句可以用常數(shù)c表示，算法的時(shí)間復(fù)雜性為：T(n)=cn。7. 快速排序的partition的比較次數(shù)partition的主要步驟：while (pq) do do p+; while (ap v);if (pcu 1 cu-w(i) cu/ w(i)16 分治合并排序算法(low+high)/2; call MERGESORT(low,mid); MERGESORT(mid+1, high)17 多段圖動(dòng)態(tài)規(guī)劃算法COST(n) 0 jn-1 c(j，r)+COST(r) D(j)r j2 to k-118 n后問題遞歸算法n print(X) call ENQUEENS(k+1) 五.設(shè)計(jì)算法1. 遞歸形式的二分檢索算法RBINSRCH(A, x, p, q)If p=q then x=Ap then return p else return 0Else mid(low+high)/2;case ：x=Amid ： return (mid) ;：x Amid：return(RBINSRCH(A, x, mid+1,q) );endcaseend2. 設(shè)計(jì)三分檢索算法RSRCH3(A, x, p, q)If p=q then x=Ap then return p else return 0Else i(p+q)/3; j(i+q)/2case ：x=Ai ： return (i) ;：x=Aj ： return (j) ;：x Ai and xAj：return(RBINSRCH(A, x, i+1,j-1) );else return(RBINSRCH(A, x