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

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