算法设计技巧与分析答案.doc

1、算法设计技巧与分析参考答案第 1 章 算法分析基本概念1.1(a)6 (b)5 (c)6 (d)6 1.4算法执行了 7+6+5+4+3+2+1=28 次比较45 33 24 45 12 12 24 1245 454545454545333333333333332424242424244545454545451212121212 121212121212 242424241212 12121212 12 242424452412 12 121.5(a)算法 MODSELECTIONSORT 执行的元素赋值的最少次数是 0,元素已按非降序排列的时候达到最小值。(b) 算法 MODSELECTIO

2、NSORT 执行的元素赋值的最多次数是 ,元素已按非升序排列的时候达到最小值。3(1)2n1.74 3 12 5 6 7 2 93 4444433333 412121212121255555666772 4321 次9761 次2 次2 次6 次2 次2 次由上图可以看到执行的比较次数为 1+1+2+2+2+6+2=16 次。1.11192 4 75 19171312118 154 5 8 11 13 17219 134 8 11 15127157 12175211195172 4 813 715122 17 19 5 13 11 4 8 15 12 7比较均为 1次，共 5 次比较为 3 次

3、，2 次，1 次比较为 6 次比较 9 次由上图可以得出比较次数为 5+6+6+9=26 次。1.13FTF,TTT,FTF,TFF,FTF1.16(a) 执行该算法，元素比较的最少次数是 n-1。元素已按非降序排列时候达到最小值。(b) 执行该算法，元素比较的最多次数是 。元素已(1)2n按非升序排列时候达到最大值。(c) 执行该算法，元素赋值的最少次数是 0。元素已按非降序排列时候达到最小值。(d) 执行该算法，元素赋值的最多次数是 。元素已3(1)2n按非升序排列时候达到最大值。(e) 用 O 符号和 符号表示算法 BUBBLESORT 的运行n时间： ，2()t()tn(f)不可以用

4、符号来表示算法的运行时间： 是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。1.27不能用 关系来比较 和 增长的阶。2n210 21lim00n不是 的，即不能用 关系来比较 和 增长22()on2n210的阶。1.32(a)当 n 为 2 的幂时，第六步执行的最大次数是：时，1,kkj1loglniin(b)由(a) 可以得到：当每一次循环 j 都为 2 的幂时，第六步执行的次数最大，则当 （其中 取整）时，3,2kkmnj32k11log()log(1)kiimn(c)用 符号表示的算法的时间复杂性是(log)On已证明 n=2k 的情况，下面证明 n

5、=2k+1 的情况：因为有 21所以 n=2k+1 时，第六步执行的最大次数仍是 n log n。(d) 用 符号表示的算法的时间复杂性是 。()当 满足 取整为奇数时，算法执行的次数是 次，n/2j其他情况算法执行次数均大于 。n(e) O 更适合表示算法的时间复杂性。因为本算法时间复杂性从 到 ，而 是表示精确阶的。()n(log)n1.38对 个数进行排序。第 5 章 归纳法5.3（本题不仅有以下一个答案）1.max(n) 过程：max(i)if n=1 return a1t=max(i-1)if ai-1t return ai-1else return t end if 5.6最多次数

6、： 0,1()(,2nCcn1()nj最少次数： 2,1)(0)(nCnC(n)=n-15.7参考例 5.15.14(a)不稳定，例如：12 45 45 2412 45 45 244545241245452412可见 SELECTIONSORT 中相等元素的序在排序后改变。(b)(c)(d)(f)稳定5.17(a)利用 10()()nnPxa取 ，3543210()()(3)P21 0*7*21(3)P P324354()()()()8*()51095.18(a) (,5)(,2)(,1)(2,0)pp2 24*4*yyyy第 6 章 分 治6.3输入：A1,2,n输出：max,min1.fo

7、r i=1 to mid2. j=high-i 3. if aiaj, then exchange ai,aj4.end for5.for i=low to mid6. if ai+1ahigh, then exchange ahigh,ai+110.end for6.5输入：一个整数数组 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算法需

8、要的工作空间为 36.10.32 15 14 15 11 17 25 5132 1415 152511 14 15 15 17 25 32 5114 1515 32 11 17 5111 2517 5132 1515 3214 1514 1511 1711 1725 5125 513232151514141515111117172525515112 25 1917 153718453251 2212 15 1817 514532252219 3712 25 1917 3251 15371845 2212 25 17 19 3251 1845 22 153712 25 17 19 51 32 1

9、845 22 37151212 2525171919 5151324545181822 371512 17 2519 5132 45371815 2212 17 25 19 5132 2218 45 371512 25 19 51 45186.3127 13 31 18 45 16 17 5327 5313 31 18 45 16 17275313 31 18 45 16 17 532727 13 18 31 45 16 17 5313 18 31 45 16 17 53273113 18 16 45 31 17 534527 131718 16 17 5313 18 16 27 4531彩色代表 i,j 所指的数字 j 总在 i 前6.36