算法設計與分析期末考試卷及答案a

1、一填空題（每空2分，共30分）1算法的時間復雜性指算法中 的執(zhí)行次數(shù)。2在忽略常數(shù)因子的情況下，O、和三個符號中， 提供了算法運行時間的一個上界。3設Dn表示大小為n的輸入集合，t(I)表示輸入為I時算法的運算時間, p(I)表示輸入I出現(xiàn)的概率，則算法的平均情況下時間復雜性A(n)= 。4分治算法的時間復雜性常常滿足如下形式的遞歸方程： 其中，g(n)表示 。5. 分治算法的基本步驟包括 。6回溯算法的基本思想是 。7動態(tài)規(guī)劃和分治法在分解子問題方面的不同點是 。8貪心算法中每次做出的貪心選擇都是 最優(yōu)選擇。9PQ式的分支限界法中，對于活結(jié)點表中的結(jié)點，其下界函數(shù)值越小，優(yōu)先級越 。10選擇

2、排序、插入排序和歸并排序算法中， 算法是分治算法。 11隨機算法的一個基本特征是對于同一組輸入， 不同的運行可能得到 的結(jié)果。 12.對于下面的確定性快速排序算法，只要在步驟3前加入隨機化步驟 ，就可得到一個隨機化快速排序算法，該隨機化步驟的功能是 。算法 QUICKSORT輸入：n個元素的數(shù)組A1.n。輸出：按非降序排列的數(shù)組A中的元素?？忌畔趯W院系 專業(yè) 年級姓名 學號裝 訂 線1. quicksort(1, n)end QUICKSORT過程 quicksort(A, low, high)/ 對Alow.high中的元素按非降序排序。 2. if low<high then3.

3、 w=SPLIT(A, low, high) /算法SPLIT以Alow為主元將Alow.high劃分成兩部 /分，返回主元的新位置。4. quicksort (A, low, w-1)5. quicksort (A, w+1, high)6 end ifend quicksort13下面算法的基本運算是 運算，該算法的時間復雜性階為( )。算法 SPLIT輸入：正整數(shù)n，數(shù)組A1.n。輸出：。 i=1 x=A1 for j=2 to n if Aj<=x then i=i+1 if ij then AiAj end if end for AiA1w =i return w, Aend

4、SPLIT二計算題和簡答題（每小題7分，共21分）1用O、表示函數(shù)f與g之間階的關系，并分別指出下列函數(shù)中階最低和最高的函數(shù)：(1)f (n)=100 g(n)= (2) f(n)=6n+n g(n)=3n(3) f(n)= n/logn-1 g(n)=(4) f(n)= g(n)=(5) f(n)= g(n)= 2下面是一個遞歸算法，其中，過程pro1和pro2的運算時間分別是1和。給出該算法的時間復雜性T(n)滿足的遞歸方程，并求解該遞歸方程，估計T(n)的階（用表示）。 算法 EX1 輸入：正整數(shù)n，n=2k。 輸出： ex1(n) end EX1過程 ex1(n) if n=1 the

5、n pro1(n)else 考生信息欄學院系 專業(yè) 年級姓名 學號裝 訂 線pro2(n)ex1(n/2)end ifreturnend ex13用Floyd算法求下圖每一對頂點之間的最短路徑長度，計算矩陣D0，D1，D2和D3，其中Dki, j表示從頂點i到頂點j的不經(jīng)過編號大于k的頂點的最短路徑長度。三算法填空題（共34分）1（10分）設n個不同的整數(shù)按升序存于數(shù)組A1.n中，求使得Ai=i的下標i 。下面是求解該問題的分治算法。 算法 SEARCH 輸入：正整數(shù)n，存儲n個按升序排列的不同整數(shù)的數(shù)組A1.n。 輸出：A1.n中使得Ai=i的一個下標i，若不存在，則輸出 no soluti

6、on。i=find ( (1) )if i>0 then output ielse output “no solution”end SEARCH過程 find (low, high) / 求Alow.high 中使得Ai=i的一個下標并返回，若不存在， /則返回0。 if (2) then return 0 else mid= if (3) then return mid else if Amid<mid then return find( (4) )elsereturn (5) end if end if end ifend find2(10分) 下面是求解矩陣鏈乘問題的動態(tài)規(guī)劃

7、算法。矩陣鏈乘問題：給出n個矩陣M1, M2, , Mn , Mi 為riri+1階矩陣，i=1, 2, , n，求計算M1M2Mn所需的最少數(shù)量乘法次數(shù)。記 Mi, j=MiMi+1Mj , i<=j。設Ci, j, 1<=i<=j<=n, 表示計算Mi, j的所需的最少數(shù)量乘法次數(shù)，則 算法 MATCHAIN輸入：矩陣鏈長度n, n個矩陣的階r1.n+1, 其中r1.n為n個矩陣的行數(shù)，rn+1為第n個矩陣的列數(shù)。輸出：n個矩陣鏈乘所需的數(shù)量乘法的最少次數(shù)。 考生信息欄學院系 專業(yè) 年級姓名 學號裝 訂 線for i=1 to n Ci, i= （1） for d=

8、1 to n-1 for i=1 to n-d j= (2) Ci, j= for k=i+1 to j x= (3) if x<Ci, j then (4) =x end if end for end for end for return (5) end MATCHAIN3(14分) 下面是用回溯法求解馬的周游問題的算法。馬的周游問題：給出一個nxn棋盤，已知一個中國象棋馬在棋盤上的某個起點位置（x0, y0），求一條訪問每個棋盤格點恰好一次，最后回到起點的周游路線。（設馬走日字。）算法 HORSETRAVEL 輸入：正整數(shù)n，馬的起點位置(x0, y0)，1<=x0, y0&l

9、t;=n 。輸出：一條從起點始訪問nxn棋盤每個格點恰好一次，最后回到起點的周游路線；若問題無解，則輸出no solution。tag1.n, 1.n=0 dx1.8=2, 1, -1, -2, -2, -1, 1, 2dy1.8=1, 2, 2, 1, -1, -2, -2, -1 flag=false x=x0; y=y0 ; tagx, y=1 m=n*n i=1; ki=0 while (1) and not flag while ki<8 and not flag ki= (2) x1= x+dxki; y1= y+dyki if (x1,y1)無越界and tagx1, y1

10、=0) or (x1,y1)=(x0,y0) and i=m) then x=x1; y=y1 tagx, y= (3) if i=m then flag=true elsei= (4) (5) end if end if end whilei=i-1 (6) (7) end while if flag then outputroute(k) /輸出路徑 else output “no solution”end HORSETRAVEL考生信息欄學院系 專業(yè) 年級姓名 學號裝 訂 線四算法設計題（15分）1. 一個旅行者要駕車從A地到B地，A、B兩地間距離為s。A、B兩地之間有n個加油站，已知第

11、i個加油站離起點A的距離為公里，0=，車加滿油后可行駛m公里，出發(fā)之前汽車油箱為空。應如何加油使得從A地到B地沿途加油次數(shù)最少？給出用貪心法求解該最優(yōu)化問題的貪心選擇策略，寫出求該最優(yōu)化問題的最優(yōu)值和最優(yōu)解的貪心算法，并分析算法的時間復雜性。算法設計與分析期考試卷(A)標準答案一. 填空題： 1. 元運算2. O3. 4. 將規(guī)模為n的問題分解為子問題以及組合相應的子問題的解所需的時間5. 分解，遞歸，組合6. 在問題的狀態(tài)空間樹上作帶剪枝的DFS搜索（或：DFS+剪枝）7. 前者分解出的子問題有重疊的，而后者分解出的子問題是相互獨立（不重疊）的8. 局部9. 高10. 歸并排序算法11. 不

12、同12. v=random (low, high); 交換Alow和Av的值 隨機選主元13. 比較 n二. 計算題和簡答題：1. 階的關系： (1) f(n)= O(g(n) (2) f(n)=(g(n) (3) f(n)=(g(n) (4) f(n)= O(g(n)(5) f(n)=(g(n)階最低的函數(shù)是：100階最高的函數(shù)是：2. 該遞歸算法的時間復雜性T(n)滿足下列遞歸方程： 將n=, a=1, c=2, g(n)=, d=1代入該類遞歸方程解的一般形式得：T(n)=1+=1+k-=1+ k-=+1所以，T(n)= +1=。3. 三. 算法填空題：1. (1) 1, n (2) l

13、ow>high (3) Amid=mid (4) mid+1, high (5) find(low, mid-1)2. (1) 0 (2) i+d (3) Ci, k-1+Ck, j+ri*rk*rj+1 (4) Ci, j (5) C1, n3. (1) i>=1 (2)ki+1 (3) 1 (4) i+1 (5) ki=0 (6) tagx, y=0 (7) x=x-dxki; y=y-dyki四. 算法設計題：1. 貪心選擇策略：從起點的加油站起每次加滿油后不加油行駛盡可能遠，直至油箱中的油耗盡前所能到達的最遠的油站為止，在該油站再加滿油。算法 MINSTOPS輸入：A、B兩地間的距離s，A、B兩地間的加油站數(shù)n，車加滿油后可行駛的公里數(shù)m，存儲各加油站離起點A的距離的數(shù)組d1.n。輸出：從A地到B地的最少加油次數(shù)k以及最優(yōu)解x1.k（xi表示第i次加油的加油站序號），若問題無解，則輸出no solution。 dn+1=s; /設置虛擬加油站第n+1站。 for i=1 to n if di+1-di>m then output “no solution”; return /無解，返回en