算法設(shè)計(jì)技巧與分析答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法設(shè)計(jì)技巧與分析參考答案第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,元素已按非降序排列的時候達(dá)到最小值。(b) 算法MODSELECTIONSORT執(zhí)行的元素

2、賦值的最多次數(shù)是,元素已按非升序排列的時候達(dá)到最小值。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)

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

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

5、=max(i-1)if ai-1>t 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 ai>aj, then exchange ai,aj4.end for5.for i

6、=low to mid6. if ai+1<alow, then exchange alow,ai+17.end for8.for i=mid+1 to high9. if ai+1>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 s

7、um算法需要的工作空間為36.10.321514151117255132141515251114151517253251141515321117511125175132151532141514151117111725512551323215151414151511111717252551511225191715371845325122121518175145322522193712251917325115371845221225171932511845221537122517195132184522371512122525171919515132454518182237151217251951

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

9、6161919324527255263632527324552252725272727455263455263526352636363111214161819232527325263456.42Quicksort不是穩(wěn)定的。6.43bcefg均為適應(yīng)的，a、h不是適應(yīng)的。第7章 動態(tài)規(guī)劃7.1(c),算法BOTTOMUPSORT7.5字符串A=”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*

10、r3*r6=252C1,5=C1,3+C4,5+r1*r4*r6=372C1,5=C1,4+C5,5+r1*r5*r6=260所以最優(yōu)括號表達(dá)式為（M1M2）(M3M4)M5)7.157.2101234567891011000000000000010033333333332003447777777300344778991212400344778101112147.23當(dāng)物品體積為負(fù)值時，運(yùn)行算法會發(fā)生溢出錯誤。第八章貪心算法18.12ats23由算法從s到t要選擇先到a然后到t,其結(jié)果為4，而從s到t距離為2，所以探索不總是產(chǎn)生從s到t的距離8.13132654912121513454313265491215134543132654912151345431326549121513454313265491215134543132654912151345434999204884161328816131212121212281348.23（共有4棵最小生成樹，此處僅舉一例）1234561234561234561234561234568