算法設計技巧與分析答案

1、算法設計技巧與分析參考答案第1章 算法分析基本概念1.1(a)6 (b)5 (c)6 (d)6 1.4算法執(zhí)行了7+6+5+4+3+2+1=28次比較453324451212241245454545454545333333333333332424242424244545454545451212121212121212121212242424241212121212121224242445241212121.5(a)算法modselectionsort執(zhí)行的元素賦值的最少次數(shù)是0,元素已按非降序排列的時候達到最小值。(b) 算法modselectionsort執(zhí)行的元素賦值的最多次數(shù)是,元素已按

2、非升序排列的時候達到最小值。1.7431256729344444333334121212121212555556667724321次9761次2次2次6次2次2次由上圖可以看到執(zhí)行的比較次數(shù)為1+1+2+2+2+6+2=16次。1.111924751917131211815458111317219134811151271571217521119517248137151221719513114815127比較均為1次，共5次比較為3次，2次，1次比較為6次比較9次由上圖可以得出比較次數(shù)為5+6+6+9=26次。1.13ftf,ttt,ftf,tff,ftf1.16(a) 執(zhí)行該算法，元素比較的最

3、少次數(shù)是n-1。元素已按非降序排列時候達到最小值。(b) 執(zhí)行該算法，元素比較的最多次數(shù)是。元素已按非升序排列時候達到最大值。(c) 執(zhí)行該算法，元素賦值的最少次數(shù)是0。元素已按非降序排列時候達到最小值。(d) 執(zhí)行該算法，元素賦值的最多次數(shù)是。元素已按非升序排列時候達到最大值。(e)用o符號和符號表示算法bubblesort的運行時間：，(f)不可以用符號來表示算法的運行時間：是用來表示算法的精確階的，而本算法運行時間由線性到平方排列，因此不能用這一符號表示。1.27不能用關系來比較和增長的階。不是的，即不能用關系來比較和增長的階。1.32(a)當n為2的冪時，第六步執(zhí)行的最大次數(shù)是：時，(

4、b)由(a)可以得到：當每一次循環(huán)j都為2的冪時，第六步執(zhí)行的次數(shù)最大，則當（其中取整）時，(c)用符號表示的算法的時間復雜性是已證明n=2k的情況，下面證明n=2k+1的情況：因為有所以n=2k+1時，第六步執(zhí)行的最大次數(shù)仍是n log n。(d) 用符號表示的算法的時間復雜性是。當滿足取整為奇數(shù)時，算法執(zhí)行的次數(shù)是次，其他情況算法執(zhí)行次數(shù)均大于。(e) o更適合表示算法的時間復雜性。因為本算法時間復雜性從到，而是表示精確階的。1.38對個數(shù)進行排序。第5章 歸納法5.3（本題不僅有以下一個答案）1.max(n) 過程：max(i)if n=1 return a1t=max(i-1)if a

5、i-1t return ai-1else return t end if 5.6最多次數(shù)：最少次數(shù)：c(n)=n-15.7參考例5.15.14(a)不穩(wěn)定，例如：12454524124545244545241245452412可見selectionsort中相等元素的序在排序后改變。(b)(c)(d)(f)穩(wěn)定5.17(a)利用取，5.18(a) 第6章 分 治6.3輸入：a1,2,n輸出：max,min1.for i=1 to mid2. j=high-i 3. if aiaj, then exchange ai,aj4.end for5.for i=low to mid6. if ai+1

6、ahigh, then exchange ahigh,ai+110.end for6.5輸入：一個整數(shù)數(shù)組a1,2,n輸出：sum1.if high-low=1 then2. sum=alow+ahigh3.else4. mid=(low+high)/25 sum1=sum(low,mid)6 sum2=sum(mid+1,high)7. sum=sum1+sum28.end if9.return sum算法需要的工作空間為36.10.32151415111725513214151525111415151725325114151532111751112517513215153214151415

7、111711172551255132321515141415151111171725255151122519171537184532512212151817514532252219371225191732511537184522122517193251184522153712251719513218452237151212252517191951513245451818223715121725195132453718152212172519513222184537151225195145186.31271331184516175327531331184516172753133118451617

8、53272713183145161753131831451617532731131816453117534527131718161753131816274531彩色代表i,j所指的數(shù)字j總在i前6.36233227184511631219162552141418111219162332452725526314181112191612111418191612111112181618191619111116161919324527255263632527324552252725272727455263455263526352636363111214161819232527325263456.42q

9、uicksort不是穩(wěn)定的。6.43bcefg均為適應的，a、h不是適應的。第7章 動態(tài)規(guī)劃7.1(c),算法bottomupsort7.5字符串a(chǎn)=”xzyzzyx”和b=”zxyyzxz”的最長公共子序列長度為4，共有6個最長公共子序列，分別是：zyyx zyzz zyzx xyyx xyzz xyzx7.9c1,5=c1,1+c2,5+r1*r2*r6=307c1,5=c1,2+c3,5+r1*r3*r6=252c1,5=c1,3+c4,5+r1*r4*r6=372c1,5=c1,4+c5,5+r1*r5*r6=260所以最優(yōu)括號表達式為（m1m2）(m3m4)m5)7.157.2101

10、234567891011000000000000010033333333332003447777777300344778991212400344778101112147.23當物品體積為負值時，運行算法會發(fā)生溢出錯誤。第八章貪心算法18.12ats23由算法從s到t要選擇先到a然后到t,其結果為4，而從s到t距離為2，所以探索不總是產(chǎn)生從s到t的距離8.13132654912121513454313265491215134543132654912151345431326549121513454313265491215134543132654912151345434999204884161328816131212121212281348.23（共有4棵最小生成樹，此處僅舉一例）123456123456123456123456123