算法設(shè)計(jì)技巧與分析答案精品文檔算法設(shè)計(jì)技巧與分析參考答案第1章算法分析基本概念1.1(a)6(b)5(c)6(d)61.4算法執(zhí)行了 7+6+5+4+3+2+1=28次比較4 3 2 4 1 1 2 11 3 2 4 4 1 2 11 1 2 4 4 3 2 11 1 1 4 4 3 2 21 1 1 2 4 3 4 21 1 1 2 2 3 4 41 1 1 2 2 3 4 41 1 1 2 2 3 4 41.5(a)算法MODSELECTIONSORT 執(zhí)行的元素賦值的最少次數(shù)是0,元素已按非降序排列的時候達(dá)到最小值。收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔(b)算法MODSELECTIONSORT執(zhí)行的元素賦值的最多次數(shù)是3n(n1),元素已按非升序排列的時候達(dá)到最小值。21.7431567291次341次3412次34512次345612次3456716次23456712次23456791由上圖可以看到執(zhí)行的比較次數(shù)為 1+1+2+2+2+6+2=16次。1.11收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔比較9次24578111111比較為624581111711比較為3251148117112 1 5 1 1 1 4 8 1 1 7比較均為2 1 19 5 1 1 4 8 15 1 7由上圖可以得出比較次數(shù)為 5+6+6+9=26次。1.13FTF,TTT,FTF,TFF,FTF1.16執(zhí)行該算法，元素比較的最少次數(shù)是n-1。元素已按非降序排列時候達(dá)到最小值。(b)執(zhí)行該算法，元素比較的最多次數(shù)是n(n1)。元素已2按非升序排列時候達(dá)到最大值。執(zhí)行該算法，元素賦值的最少次數(shù)是0。元素已按非降序排列時候達(dá)到最小值。(d)執(zhí)行該算法，元素賦值的最多次數(shù)是3n(n1)。元素已2按非升序排列時候達(dá)到最大值。(e)n用O符號和符號表示算法BUBBLESORT的運(yùn)行時間：tO(n2)，t(n)收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔(f)不可以用 符號來表示算法的運(yùn)行時間： 是用來表示算法的精確階的，而本算法運(yùn)行時間由線性到平方排列，因此不能用這一符號表示。1.27不能用p關(guān)系來比較 n2和100n2增長的階。∵limn2120n100n100n2不是o(100n2)的，即不能用 p關(guān)系來比較 n2和100n2增長的階。1.32(a)當(dāng)n為2的冪時，第六步執(zhí)行的最大次數(shù)是：n2k,j2k1時，nnk[logn]nlogni1i1(b)由(a)可以得到：當(dāng)每一次循環(huán)j都為2的冪時，第六步執(zhí)行的次數(shù)最大，則當(dāng)n3k,j3k2m（其中3k取整）時，22nnmi[log(3k1)]nlog(n1)i1i1(c)用 符號表示的算法的時間復(fù)雜性是 O(nlogn)已證明n=2k的情況，下面證明n=2k+1的情況：因?yàn)橛?k2k122所以n=2k+1時，第六步執(zhí)行的最大次數(shù)仍是 nlogn。收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除O(nlogn)精品文檔用符號表示的算法的時間復(fù)雜性是(n)。當(dāng)n滿足jn/2取整為奇數(shù)時，算法執(zhí)行的次數(shù)是n次，其他情況算法執(zhí)行次數(shù)均大于n。O更適合表示算法的時間復(fù)雜性。因?yàn)楸舅惴〞r間復(fù)雜性從 (n)到 ，而 是表示精確階的。1.38對n個數(shù)進(jìn)行排序。第5章歸納法5.3（本題不僅有以下一個答案）1.max(n)過程：max(i)ifn=1returna[1]t=max(i-1)ifa[i-1]>treturna[i-1]elsereturntendif收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔5.6最多次數(shù)：0,n 1C(n)c(n 1) (n 1),n 2n(n1)C(n) jj1 2最少次數(shù)：0,n 1C(n)C(n 1) 1,n 2C(n)=n-15.7參考例5.15.14(a)不穩(wěn)定，例如：1 4 4 21 4 4 21 2 4 41 2 4 4可見SELECTIONSORT中相等元素的序在排序后改變。(b)(c)(d)(f)穩(wěn)定5.17(a)利用

Pn(x) xPn1(x) a0收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔取x3，P5(3)P4(3)P3(3)P2(3)P1(3)P0(3)P2(3)3*P1(3)437P1(3)3*P0(3)211P0(3)3P3(3)3*P2(3)1112P4(3)3*P3(3)2338P5(3)3*P4(3)510195.18(a)p(2,5)p(2,2)p(2,1)p(2,0)y42*2y224y12*2y1第6章分治6.3輸入：A[1,2, n]輸出：max,min1.fori=1tomidj=high-iifa[i]>a[j],thenexchangea[i],a[j]4.endfor5.fori=lowtomidifa[i+1]<a[low],thenexchangea[low],a[i+1]7.endfor8.fori=mid+1tohighifa[i+1]>a[high],thenexchangea[high],a[i+1]10.endfor6.5收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔輸入：一個整數(shù)數(shù)組 A[1,2, ,n]輸出：sum1.ifhigh-low=1thensum=a[low]+a[high]3.elsemid=(low+high)/2sum1=sum(low,mid)sum2=sum(mid+1,high)sum=sum1+sum28.endif9.returnsum算法需要的工作空間為 3收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔6.10.收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔31111125111112353114111251115311253111112513111125311111253111112512115341231111181223345121153412311112535112341211534123111219351241312115341231125115314231121541121541收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔6.312 1 3 1 4 1 1 52 1 3 1 4 1 1 52 1 3 1 4 1 1 52 1 1 3 4 1 1 52 1 1 3 4 1 1 52 1 1 1 4 3 1 52 1 1 1 1 3 4 51 1 1 1 2 3 4 5彩色代表i,j所指的數(shù)字j總在i前6.36收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔23214161112511111112342256111111111111111111111111111132452725526325273245526325 2725 27272745 52 6345 52 6352 6352 6363收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除 6311 12 14 16 18 19 23 25 27 32 45 52 6精品文檔6.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.9C[1,5]=C[1,1]+C[2,5]+r[1]*r[2]*r[6]=307C[1,5]=C[1,2]+C[3,5]+r[1]*r[3]*r[6]=252C[1,5]=C[1,3]+C[4,5]+r[1]*r[4]*r[6]=372C[1,5]=C[1,4]+C[5,5]+r[1]*r[5]*r[6]=260所以最優(yōu)括號表達(dá)式為（ M1M2）((M3M4)M5)7.150513D1[i,j]min{D0[i,j],D0[i,1]D0[1,j]}120911D4402316200716D10940241820D2[i,j]min{D1[i,j],D1[i,2]D1[2,j]}收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔0716D20940241820D3[i,j]min{D2[i,j],D2[i,3]D2[3,j]}0513130911D340241620D4[i,j]min{D3[i,j],D3[i,4]D3[4,j]}0513120911D4402316207.2101234567891011000000000000010033333333332003447777777300344778991212400344778101112147.23當(dāng)物品體積為負(fù)值時，運(yùn)行算法會發(fā)生溢出錯誤。第八章貪心算法8.121sa23t收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔由算法從s到t要選擇先到a然后到t,其結(jié)果為4，而從s到t距離為2，所以探索不總是產(chǎn)生從 s到t的距離8.1319224114532641351593192241145326413515932019224114532641931554133811922614145326241835154313

8192241145326413515438119226154221436841351543138.23（共有4棵最小生成樹，此處僅舉一例）收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系管理員刪除精品文檔135135135246