(完整版)算法設(shè)計與分析期末考試卷及答案a.doc

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

2、其下界函數(shù)值越小，優(yōu)先級越O10.選擇排序、插入排序和歸并排序算法中，算法是分治算法。11.隨機算法的一個基本特征是對于同一組輸入，不同的運行可能得到的侖12.對于下面的確定性快速排序算法，只要在步驟3前加入隨機化步驟，就可得到 f 隨-機r化快部序算法,該隨機化步驟的功能是o算法QUEKSORT輸入：n個元素的數(shù)組Al.no輸出：按非降序排列的數(shù)組A中的元素。1.i.1i.i1.1.F1J.1.1:.,.學(xué).1.欄芬1.01.姓.:息.級1.01t.年線！1.信.10一i業(yè).B專訂生.Bi.B.一系i10.i.!考1.1.一裝.0tI.81.,1.:!.學(xué)一i1L1.quicksort。，n

3、)endQUEKSORT程quicksort(A,bw,high)/Abw.hjgh中的元素按非降序排序。2.3.4.5.6.ifbwhighthenw二SPLIT(A,bw,high)法SPLIT以Abw主元將Abw.high劃分成兩部憐,返回主元的新位置。quicksort(A,bw,w-1)quicksort(A,w+1,high)endifendquicksort下面算法的基本5E算是運算，算法的復(fù)性)o算法SPLIT入：正整數(shù)n,數(shù)ALn。出:。Fln,x=A1forj=2tonifAj=xthenifijthenA田Aj|endifendforelseADOAlww,AendSPL

4、IT二.計算題和簡答題(每小題 7 分，共 21 分)1.用0、表示函數(shù)f與g之的關(guān)系，并分指出下列函數(shù)中最低和最高的函數(shù):(1)f6)=100(2)f(h)=6n+nbgn(5)氏D二2.下面是一個算法，其中,prol和pro2的運算分是T(n)足的方程，并求解方程，估T(n)的(用表示)。算法EX1入:正整數(shù)n,n=2koexl0)endEX1程exl(h)ifn=lthenprol(h)(3)f(h)=n/bgn-1出算法的復(fù)性gS)二3ng&)=3npro2(h)exl6/S)endifreturnendexl3.用Fbyd算法求下圖每一對頂點之間的最短路徑長度，計算矩陣Do,

5、Di,D2和D3,其中DkEij表示從頂點i到頂點j的不經(jīng)過編號大于k的頂點的最短路徑長度。三.算法填空題（共 34 分）（10分）設(shè)n個不同的整數(shù)按升序存于數(shù)組Al. n中，求使得AKH的下標(biāo)i。下面是求解該問題的分治算法。算法SEARCH輸入：正整數(shù)n,存儲n個按升序排列的不同整數(shù)的數(shù)組Al.no輸出：Al.n中使得AEfl=i的一個下標(biāo)i,若不存在，則輸出nosolution。Ffhd(ifDOthenoutputielseouiput“nosolitibnendSEARCH過程find（bw,hfeh）求Abw.hgh中使得Ai=i的一個下標(biāo)并返回，若不存在,1.0)返回0oif(2)

6、thenreturn0elsemid=(bwh迪h)/2ifG)thenreturnmidelseifAfoilmidthenreturnAid)elsereturnS)endifendifendifendfed2niiHI矩，,M,M,MrrFl,2,n,求算M1M2-Mn所需的最少數(shù)量乘法次數(shù)。Mij=MiMwMj,K=j。C11l8.Ifcrk=frltojx=6）.ifxC11henI!=x.endifendforendfori.iendfor.:0return（5）.jendMATCHA1N.I3.（14分）下面是用回溯法求解馬的周游問題的算法。馬的周游問題：給出一個nxn棋盤，已知

7、一個中國象棋馬在.棋盤上的某個起點位置（xO,yO）,求一條訪問每個棋盤格點恰好一次，最后回到起點的周游路線。（設(shè)馬走日字。）算法HORSETRAVEL!輸入：正整數(shù)n,馬的起點位置（xO,yO）,1=X0,yOlm=nFl;ki=Owhile(1)andnotfhgwhileki(3)ifFmthenfhg=trueeseF(4)(5)endifendifendwhileFil(6)G)endwhileifflag1henoutputoute(k)輸出路徑elseoutput“nosolitbn”endHORSETRAVEL一.填空題:i.元運算I 四.算法設(shè)計題（15 分）I.1.一個旅行

8、者要駕車從A地到B地，A、B兩地間距離為s。A、B兩地之間有n個加油站，已知第i個加油站離起點A的距離為di公里，.:iO=did2dns,車加滿油后可行駛m公里，出發(fā)之前汽車，e.|油箱為空。應(yīng)如何加油使得從A地到B地沿途加油次數(shù)最少？給出.I用貪心法求解該最優(yōu)化問題的貪心選擇策略，寫出求該最優(yōu)化問題I的最優(yōu)值和最優(yōu)解的貪心算法，并分析算法的時間復(fù)雜性。算法設(shè)計與分析期考試卷（A）標(biāo)準(zhǔn)答案2. 03.p(I)tQ)IDn4.將規(guī)模為n的問題分解為子問題以及組合相應(yīng)的子問題的解所需的時間5.分解，遞歸，組合6.在問題的狀態(tài)空間樹上作帶剪枝的DFS搜索(或：DFS+剪枝)7.前者分解出的子問題有重疊的，而后者分解出的子問題是相互獨立(不重疊)的8.局部9.高10.歸并排序算法11.不同12. v=iandom(bw,hh);交換ADow和A切的值隨機選主元13.比較n二.計算題和簡答題：1階的關(guān)系：(Df(n)-Ofe(n)f(n)=(g(n)(3)f(h)=(g(n)f(n)=Ofe(n)(5)f(n)-(g(n)階最低的函數(shù)是：100階最高的函數(shù)是：3n2.該遞歸算法的時間復(fù)雜性T(n)滿足下列遞歸方程：T(h)1,n1T6)T以)bg2n,n1將n-2k,a二1,c=2,g(nbg2n,d=l代入該