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

(b) 算法MODSELECTIONSORT执行的元素赋值的最多次数是3n(F)，元素已按非升序排列的时候达到最小值。

1.71次由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次1.11由上图可以得出比较次数为5+6+6+9=26次1.13FTF,TTT,FTF,TFF,FTF 1.16⑻ 执行该算法，元素比较的最少次数是 n-1。

元素已按非 降序排列时候达到最小值。

(b)执行该算法，元素比较的最多次数是 吨严。

元素已按非升序排列时候达到最大值。

(c) 执行该算法，元素赋值的最少次数是 0。

元素已按非降序排列时候达到最小值。

(d) 执行该算法，元素赋值的最多次数是 空严。

元素已按非升序排列时候达到最大值。

(e) n 用o 符号和「符号表示算法 BUBBLESORT 的运行时 间：t =O(n 2)， t"(n)(f) 不可以用0符号来表示算法的运行时间：0是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列， 因此不能用这一符号表示。

1.27不能用「关系来比较n 2和100n 2增长的阶2 .. n lim 2n ::100n 2n 2不是o(100n 2)的，即不能用•关系来比较n 2和100n 2增长 的阶。

1.321 100=0(a) 当n 为2的幕时，第六步执行的最大次数是：^2k , j =2kJ 时，nn、k _、［log n ］二 n log ni 4i 4(b) 由⑻可以得到：当每一次循环j 都为2的幕时，第六步 执行的次数最大，n n m — [log(3k -1)H nlog( n-1)i 4i 4(c)用0符号表示的算法的时间复杂性是 O(nlog n) 已证明n=2k的情况，下面证明 n=2k+1的情况:所以n=2kn log n 。

(d)用门符号表示的算法的时间复杂性是 门(n)。

当n 满足j =n/2取整为奇数时，算法执行的次数是 n 次，其他情况算法执行次数均大于n(e) O 更适合表示算法的时间复杂性。

因为本算法时间复 杂性从门(n)到O(nlog n)，而心是表示精确阶的。

1.38对n 个数进行排序。

因为有则当3k=2mk(其中占取整)时，第5章归纳法5.3 (本题不仅有以下一个答案)1. max( n)过程：max(i)if n=1 retur n a[1]t=max(i-1)if a[i-1]>t return a[i-1]else retur n tend if5.6最多次数:C(n) = 0，n[c(n —1) + (n— 1),nnC(n)八jj1最少次数:C( n)二n-1 5.7n(n 1) 2C(n)0,n =1C(n _ 1)+1,n M2参考例5.15.14(a)不稳定，例如:可见SELECTIONSORT中相等元素的序在排序后改变。

(b)(c)(d)(f)稳定5.17(a)利用R(x)二xP n」(x) a o取x =3，P5(3) > 巳(3) > 巳(3) > 巳(3) > R(3) > P°(3)P2(3) =3* R(3) 4 P(3) =3* P°(3) 2 =11 P°(3) =3:P3(3) =3* F2(3) 1 =112 > F4(3) =3* P3(3) - 2 =338 > F5(3) =3* F4(3) 5=10195.18(a) p(2,5)p (2,2p (2p1)2 2 2 y=4 *2 ：—y=2 =4：—y=1 *2 ：—y=1第6章分治6.3输入：A[1,2,…n]输出：max,min1. for i=1 to mid2. j=high-i3. if a[i]>a[j], then exchange a[i],a[j]4. end for5. for i=low to mid6. if a[i+1]<a[low], then exchange a[low],a[i+1]7. end for8. for i=mid+1 to high9. if a[i+1]>a[high], then exchange a[high],a[i+1]10. end for6.5输入：一个整数数组A[1,2,…,n]输出：sum1.if high-low=1 then2. sum=a[low]+a[high]3. 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.12 25 17 19 51 32 45 18 22 37 1512 15 17 18 19 22 25 32 37 45 5112 25 17 19 51 3212 17 19 25 32 514518 2237 151518 2237 4512 25 1712 17 2519 51 3219 32 514518 2218 224537 1515 3717 32 22 37 1512251225 171225122519 5119 51 32195145181845 2218451951451837 156.31彩色代表i,j所指的数字j总在i前6.36共享知识分享快乐23 32 27 18 45 11 63 12 19 16 25 52 1414 18 11 12 19 16 23 32 45 27 25 52 6314 18 11 12 19 1612 11 14 18 19 1612 1111 12111118 19 1616 18 191616191932 45 27 25 52 6325 27 32 45 52 6325 2725 27272745 52 6345 52 6352 6352 63636・42Quicksort 不是稳定的。

6.43bcefg 均为适应的，a 、h 不是适应的第7章动态规划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]=307 C[1,5]=C[1,2]+C[3,5]+r[1]*r[3]*r[6]=252 C[1,5]=C[1,3]+C[4,5]+r[1]*r[4]*r[6]=372 C[1,5]=C[1,4]+C[5,5]+r[1]*r[5]*r[6]=260所以最优括号表达式为(M1M2)((M3M4)M5) 7.15'07 1 6 'Di =oO0 94 4 0 2J8 2 0」D 2【i,j] =mi"{Dji, j], D/,2]D/2, j]}oO7 0 1 9 6、D2 =4 4 0 2<1 8 2 0」D 3【i,j] = min{ D 2【i, j],D 2【i,3] D 2【3, j]}Ddi,j]二min{D °[i, j], D °[i,1] D °[1,j]} D 41 0 5 1 312 0 9 11 3 4 0 2 、1 6 2 0「 5 1 3 'D3 = 13 0 9 11 4 4 0 26 2 °」D4【i,j]二min{ D3【i, j],D3【i,4] D3A j]}广° 5 1 3、D4 =12 °9 113 4 ° 26 2 °」7.21当物品体积为负值时，运行算法会发生溢出错误。

第八章贪心算法由算法从s到t要选择先到a然后到t,其结果为4，而从s到t距离为2,所以探索不总是产生从s到t的距离8.23 （共有4棵最小生成树，此处仅举一例）□0 28Q 0 Q 12 1 ：1 ；8.31每一个二叉树都取左边为0，右边为1则最优编码为a:10 b:001 c:0001d:0000 e:01 f:11注意：编码不唯一回溯法。