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

-----WORD格式--可編輯--專業(yè)資料-------完整版學習資料分享----一．填空題（每空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)選擇。9．PQ式的分支限界法中，對于活結點表中的結點，其下界函數(shù)值越小，優(yōu)先級越。10．選擇排序、插入排序和歸并排序算法中，算法是分治算法。11．隨機算法的一個基本特征是對于同一組輸入，不同的運行可能得到的結果。12.對于下面的確定性快速排序算法，只要在步驟3前加入隨機化步驟，就可得到一個隨機化快速排序算法，該隨機化步驟的功能是。算法QUICKSORT輸入：n個元素的數(shù)組A[1..n]。輸出：按非降序排列的數(shù)組A中的元素?？忌畔冢撸撸撸撸撸邔W院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學號＿＿＿＿＿裝訂線1.quicksort(1,n)endQUICKSORT過程quicksort(A,low,high)//對A[low..high]中的元素按非降序排序。2.iflow<highthen3.w=SPLIT(A,low,high)//算法SPLIT以A[low]為主元將A[low..high]劃分成兩部//分，返回主元的新位置。4.quicksort(A,low,w-1)5.quicksort(A,w+1,high)6．endifendquicksort13．下面算法的基本運算是運算，該算法的時間復雜性階為()。算法SPLIT輸入：正整數(shù)n，數(shù)組A[1..n]。輸出：…。i=1x=A[1]forj=2tonifA[j]<=xtheni=i+1ifijthenA[i]A[j]endifendforA[i]A[1]w=ireturnw,AendSPLIT二．計算題和簡答題（每小題7分，共21分）1．用O、、表示函數(shù)f與g之間階的關系，并分別指出下列函數(shù)中階最低和最高的函數(shù)：(1)f(n)=100g(n)=(2)f(n)=6n+ng(n)=3n(3)f(n)=n/logn-1g(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)endEX1過程ex1(n)ifn=1thenpro1(n)else考生信息欄＿＿＿＿＿＿學院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學號＿＿＿＿＿裝訂線pro2(n)ex1(n/2)endifreturnendex13．用Floyd算法求下圖每一對頂點之間的最短路徑長度，計算矩陣D0，D1，D2和D3，其中Dk[i,j]表示從頂點i到頂點j的不經(jīng)過編號大于k的頂點的最短路徑長度。三．算法填空題（共34分）1．（10分）設n個不同的整數(shù)按升序存于數(shù)組A[1..n]中，求使得A[i]=i的下標i。下面是求解該問題的分治算法。算法SEARCH輸入：正整數(shù)n，存儲n個按升序排列的不同整數(shù)的數(shù)組A[1..n]。輸出：A[1..n]中使得A[i]=i的一個下標i，若不存在，則輸出nosolution。i=find((1))ifi>0thenoutputielseoutput“nosolution”endSEARCH過程find(low,high)//求A[low..high]中使得A[i]=i的一個下標并返回，若不存在，//則返回0。if(2)thenreturn0elsemid=if(3)thenreturnmidelseifA[mid]<midthenreturnfind((4))elsereturn(5)endifendifendifendfind2．(10分)下面是求解矩陣鏈乘問題的動態(tài)規(guī)劃算法。矩陣鏈乘問題：給出n個矩陣M1,M2,…,Mn,Mi為riri+1階矩陣，i=1,2,…,n，求計算M1M2…Mn所需的最少數(shù)量乘法次數(shù)。記Mi,j=MiMi+1…Mj,i<=j。設C[i,j],1<=i<=j<=n,表示計算Mi,j的所需的最少數(shù)量乘法次數(shù)，則算法MATCHAIN輸入：矩陣鏈長度n,n個矩陣的階r[1..n+1],其中r[1..n]為n個矩陣的行數(shù)，r[n+1]為第n個矩陣的列數(shù)。輸出：n個矩陣鏈乘所需的數(shù)量乘法的最少次數(shù)?？忌畔冢撸撸撸撸撸邔W院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學號＿＿＿＿＿裝訂線fori=1tonC[i,i]=（1）ford=1ton-1fori=1ton-dj=(2)C[i,j]=∞fork=i+1tojx=(3)ifx<C[i,j]then(4)=xendifendforendforendforreturn(5)endMATCHAIN3．(14分)下面是用回溯法求解馬的周游問題的算法。馬的周游問題：給出一個nxn棋盤，已知一個中國象棋馬在棋盤上的某個起點位置（x0,y0），求一條訪問每個棋盤格點恰好一次，最后回到起點的周游路線。（設馬走日字。）算法HORSETRAVEL輸入：正整數(shù)n，馬的起點位置(x0,y0)，1<=x0,y0<=n。輸出：一條從起點始訪問nxn棋盤每個格點恰好一次，最后回到起點的周游路線；若問題無解，則輸出nosolution。tag[1..n,1..n]=0dx[1..8]={2,1,-1,-2,-2,-1,1,2}dy[1..8]={1,2,2,1,-1,-2,-2,-1}flag=falsex=x0;y=y0;tag[x,y]=1m=n*ni=1;k[i]=0while(1)andnotflagwhilek[i]<8andnotflagk[i]=(2)x1=x+dx[k[i]];y1=y+dy[k[i]]if((x1,y1)無越界andtag[x1,y1]=0)or((x1,y1)=(x0,y0)andi=m)thenx=x1;y=y1tag[x,y]=(3)ifi=mthenflag=trueelsei=(4)(5)endifendifendwhilei=i-1(6)(7)endwhileifflagthenoutputroute(k)//輸出路徑elseoutput“nosolution”endHORSETRAVEL考生信息欄＿＿＿＿＿＿學院＿＿＿＿＿＿系＿＿＿＿＿＿專業(yè)＿＿＿＿＿＿年級姓名＿＿＿＿＿＿學號＿＿＿＿＿裝訂線四．算法設計題（15分）1.一個旅行者要駕車從A地到B地，A、B兩地間距離為s。A、B兩地之間有n個加油站，已知第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.v=random(low,high);交換A[low]和A[v]的值隨機選主元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,n(2)low>high(3)A[mid]=mid(4)mid+1,high(5)find(low,mid-1)2.(1)0(2)i+d(3)C[i,k-1]+C[k,j]+r[i]*r[k]*r[j+1](4)C[i,j](5)C[1,n]3.(1)i>=1(2)k[i]+1(3)1(4)i+1(5)k[i]=0(6)tag[x,y]=0(7)x=x-dx[k[i]];y=y-dy[k[i]]算法設計題：1.貪心選擇策略：從起點的加油站起每次加滿