算法设计技巧与分析答案

算法设计技巧与分析

参考答案

第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 12 12 33 24 45 45 12 24 12 12 12 24 45 45 33 24 12 12 12 12 45 45 33 24 24 12 12 12 24 45 33 45 24 12 12 12 24 24 33 45 45 12 12 12 24 24 33 45 45 12 12 12 24 24 33 45 45

1.5

(a)算法MODSELECTIONSORT执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。

(b) 算法MODSELECTIONSORT执行的元素赋值的最

精品资料

______________________________________________________________________________________________________________

多次数是3n(n1),元素已按非升序排列的时候达到最小值。

21.7

4 3 12 5 6 7 2 9 1次 3 4 1次 3 4 12 2次 3 4 5 12 2次 3 4 5 6 12 2次 3 4 5 6 7 12 6次 2 3 4 5 6 7 12 2次 2 3 4 5 6 7 9 12 由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。 1.11

比较9次 2 4 5 7 8 11 12 13 15 17 19 比较为6次 2 4 5 8 11 13 17 19 7 12 15 比较为3次， 2次，1次 2 5 17 19 4 8 11 13 7 12 15 比较均为1次，共5次 2 2 17 5 19 11 13 4 8 12 15 7 17 19 5 13 11 4 8 15 12 7 精品资料

______________________________________________________________________________________________________________

由上图可以得出比较次数为5+6+6+9=26次。 1.13

FTF,TTT,FTF,TFF,FTF 1.16

(a) 执行该算法，元素比较的最少次数是n-1。元素已按非降序排列时候达到最小值。

(b) 执行该算法，元素比较的最多次数是n(n1)。元素已

2按非升序排列时候达到最大值。

(c) 执行该算法，元素赋值的最少次数是0。元素已按非降序排列时候达到最小值。

(d) 执行该算法，元素赋值的最多次数是3n(n1)。元素已

2按非升序排列时候达到最大值。

(e)n用O符号和符号表示算法BUBBLESORT的运行时间：tO(n2)，t(n)

(f)不可以用符号来表示算法的运行时间：是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。 1.27

不能用关系来比较n2和100n2增长的阶。

n210 ∵limn100n2100精品资料

______________________________________________________________________________________________________________

n2不是o(100n2)的，即不能用关系来比较n2和100n2增长

的阶。 1.32

(a)当n为2的幂时，第六步执行的最大次数是：

n2k,j2k1时，

k[logn]nlogn

i1i1nn(b)由(a)可以得到：当每一次循环j都为2的幂时，第六步执行的次数最大，

3k3km则当n3,j2（其中

22k取整）时，

m[log(3ii1i1nnk1)]nlog(n1)

(c)用符号表示的算法的时间复杂性是O(nlogn) 已证明n=2k的情况，下面证明n=2k+1的情况：

2k2k1因为有

22所以n=2k+1时，第六步执行的最大次数仍是n log n。 (d) 用符号表示的算法的时间复杂性是(n)。

当n满足jn/2取整为奇数时，算法执行的次数是n次，其他情况算法执行次数均大于n。

(e) O更适合表示算法的时间复杂性。因为本算法时间复杂性从(n)到O(nlogn)，而是表示精确阶的。 1.38

精品资料

______________________________________________________________________________________________________________

对n个数进行排序。

第5章 归纳法

5.3（本题不仅有以下一个答案）

1.max(n) 过程：max(i)

if n=1 return a[1] t=max(i-1)

if a[i-1]>t return a[i-1] else return t end if

5.6 最多次数：

0,n1 C(n)c(n1)(n1),n2C(n)jj1nn(n1) 2最少次数：

精品资料

______________________________________________________________________________________________________________

0,n1 C(n)C(n1)1,n2C(n)=n-1 5.7

参考例5.1 5.14

(a)不稳定，例如：

12 45 45 24 12 45 45 24 12 24 45 45 12 24 45 45

可见SELECTIONSORT中相等元素的序在排序后改变。 (b)(c)(d)(f)稳定 5.17

(a)利用Pn(x)xPn1(x)a0 取x3，

P5(3)P4(3)P3(3)P2(3)P1(3)P0(3)

P2(3)3*P1(3)437P1(3)3*P0(3)211P0(3)3

P3(3)3*P2(3)1112P4(3)3*P3(3)2338P5(3)3*P4(3)510195.18

(a) p(2,5)p(2,2)p(2,1)p(2,0)

精品资料

______________________________________________________________________________________________________________

y42*2y224y12*2y1

第6章 分 治

6.3

输入：A[1,2,…n] 输出：max,min 1.for i=1 to mid 2. j=high-i

3. if a[i]>a[j], then exchange a[i],a[j] 4.end for 5.for i=low to mid

6. if a[i+1]8.for i=mid+1 to high

9. if a[i+1]>a[high], then exchange a[high],a[i+1] 10.end for 6.5

输入：一个整数数组A[1,2,…,n] 输出：sum 1.if high-low=1 then 2. sum=a[low]+a[high] 3.else

4. mid=(low+high)/2

精品资料

______________________________________________________________________________________________________________

5 sum1=sum(low,mid) 6 sum2=sum(mid+1,high) 7. sum=sum1+sum2 8.end if 9.return sum

算法需要的工作空间为3 6.10.

精品资料

______________________________________________________________________________________________________________

32 11 15 14 14 15 15 15 11 17 17 25 25 32 51 51 32 14 15 15 14 15 15 32 11 11 17 17 25 25 51 51 32 15 15 32 14 14 15 15 11 11 17 17 25 25 51 51 32 32 15 15 14 14 15 15 11 11 17 17 25 25 51 51 12 12 25 15 17 17 19 18 51 19 32 22 45 25 18 32 22 37 37 45 15 51 12 12 25 17 17 19 19 25 51 32 32 51 45 15 18 18 22 22 37 37 15 45 12 12 25 17 17 25 19 19 51 32 32 51 45 18 18 22 22 45 37 15 15 37 12 12 25 25 17 17 19 19 51 51 32 32 45 18 18 45 22 22 37 37 15 15 12 12 25 25 19 19 51 51 45 45 18 18

精品资料

______________________________________________________________________________________________________________

6.31

27 13 31 18 45 16 17 53 27 13 31 18 45 16 17 53 27 13 31 18 45 16 17 53 27 13 18 31 45 16 17 53 27 13 18 31 45 16 17 53 27 13 18 16 45 31 17 53 27 13 18 16 17 31 45 53 17 13 18 16 27 31 45 53

彩色代表i,j所指的数字j总在i前

精品资料

______________________________________________________________________________________________________________

6.36

精品资料

______________________________________________________________________________________________________________

23 14 32 18 27 11 18 12 45 19 11 16 63 23 12 32 19 45 16 27 25 25 52 52 14 63 14 12 18 11 11 14 12 18 19 19 16 16 12 11 11 12 11 11 18 16 19 18 16 19 16 16 19 19 32 25 45 27 27 32 25 45 52 52 63 63 25 25 27 27 27 27 45 45 52 52 52 52 63 63 63 63 63 精品资料 63 27 32 45 52 63 11 12 14 16 18 19 23 25 ______________________________________________________________________________________________________________

6.42

Quicksort不是稳定的。 6.43

bcefg均为适应的，a、h不是适应的。

第7章 动态规划

7.1

(c),算法BOTTOMUPSORT 7.5

字符串A=”xzyzzyx”和B=”zxyyzxz”的最长公共子序列长度为4，共有6个最长公共子序列，分别是：①zyyx ②zyzz ③zyzx ④xyyx ⑤xyzz ⑥xyzx

7.9

C[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

012D1[i,j]min{D0[i,j],D0[i,1]D0[1,j]}D43130911

40262051精品资料

______________________________________________________________________________________________________________

0D141609402820

71D2[i,j]min{D1[i,j],D1[i,2]D1[2,j]}

0D241609402820

71D3[i,j]min{D2[i,j],D2[i,3]D2[3,j]}

013D34130911402620

51D4[i,j]min{D3[i,j],D3[i,4]D3[4,j]}

012D43130911402620

517.21

0 1 2 3 4 0 0 0 0 0 0 1 0 0 0 0 0 2 0 3 3 3 3 3 0 3 4 4 4 4 0 3 4 4 4 5 0 3 7 7 7 6 0 3 7 7 7 7 0 3 7 8 8 8 0 3 7 9 10 9 0 3 7 9 11 10 0 3 7 12 12 11 0 3 7 12 14 精品资料

______________________________________________________________________________________________________________

7.23

当物品体积为负值时，运行算法会发生溢出错误。

第八章贪心算法

8.12

由算法从s到t要选择先到a然后到t,其结果为4，而从s到t距离为2，所以探索不总是产生从s到t的距离

2 t 3 s 1

a 精品资料

______________________________________________________________________________________________________________

8.13

12 9 1 4 3 13 5 4 2 5 4 12 3 15 6 9 12 9 1 4 3 13 4 2 5  4 12 3 5 15 6 9 8 2 12 4 12 3 5  9 12 20 9 2 4 12 5 4 3 1 6 4 15 3 5 13 4 13 8 12 9 1 4 3 4

13 4 2 5 16 4 12 3 5 13

15 6 28

8.23（共有4棵最小生成树，此处仅举一例）

 1 4 6 4 3 13 4 5 15 8 12 2 16 9 4 12 3 1 4 5 6 28 4 3 4 13 5 13 15

精品资料

______________________________________________________________________________________________________________

1 1 2 2 3 3 4 4 5 5 6 6 1 3 5 2 4 6 1 3 5 1 3 5 2 4 6 2 4 6 1 3 5 2 4 6

8.24（共有4棵最小生成树，此处仅举一例）

1 3 5 1 3 5 2 4 6 2 4 6 1 3 5 1 3 5 2 4 6 2 4 6 1 3 5 1 3 5 2 4 6 2 4 6

精品资料

______________________________________________________________________________________________________________

8.31

38 22 10 16 5 2 d

3 c 5 b 12 e 7 a 9 f

每一个二叉树都取左边为0，右边为1 则最优编码为a:10 b:001 c:0001 d:0000 e:01 f:11 注意：编码不唯一

回溯法

精品资料

______________________________________________________________________________________________________________

Welcome To Download !!!

欢迎您的下载，资料仅供参考！

精品资料