算法设计技巧与分析答案.docx
《算法设计技巧与分析答案.docx》由会员分享，可在线阅读，更多相关《算法设计技巧与分析答案.docx（20页珍藏版）》请在冰点文库上搜索。
算法设计技巧与分析答案
算法设计技巧与分析
参考答案
第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
1r
12
12
12
24
24
33
45
45
12
12
12
24
24
33
45
45
1.5
（a）算法MODSELECTIONSORT执行的元素赋值的最少
次数是0,元素已按非降序排列的时候达到最小值。
（b）算法MODSELECTIONSORT执行的元素赋值的最多
次数是3n（;」），元素已按非升序排列的时候达到最小值。
1.7
由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次
1.11
由上图可以得出比较次数为5+6+6+9=26次
1.13
FTF,TTT,FTF,TFF,FTF
1.16
（a）执行该算法，元素比较的最少次数是n-1。
元素已按非
降序排列时候达到最小值。
（b）执行该算法，元素比较的最多次数是"（；一1）。
元素已
按非升序排列时候达到最大值。
（c）执行该算法，元素赋值的最少次数是0。
元素已按非
降序排列时候达到最小值。
（d）执行该算法，元素赋值的最多次数是3^。
元素已
按非升序排列时候达到最大值。
（e）n用O符号和「符号表示算法BUBBLESORT的运行时间：
t=0（n2），tf】（n）
（f）不可以用。
符号来表示算法的运行时间：
。
是用来表示
算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。
1.27
不能用-关系来比较n2和100n2增长的阶
2
..nlim2n:
:
100n2
n2不是o（100n2）的，即不能用-关系来比较n2和100n2增长的阶。
1.32
（a）当n为2的幕时，第六步执行的最大次数是：
n=2k,j=2kJ1时，
nn
、k_、［logn］二nlogn
i4i4
（b）由⑻可以得到：
当每一次循环j都为2的幕时，第六步执行的次数最大，
kk
则当n=3k,j=32m（其中-取整）时，
22
nn
'm—[log（3k-1）]=nlog（n-1）
i4i4
（c）用门符号表示的算法的时间复杂性是O（nlogn）已证明n=2k的情况，下面证明n=2k+1的情况:
2k
2k+1
〔2一
=1
2一
因为有
所以n=2k+l时，第六步执行的最大次数仍是nlogn。
（d）用门符号表示的算法的时间复杂性是i」（n）。
当n满足j=n/2取整为奇数时，算法执行的次数是n次，其
他情况算法执行次数均大于n
（e）O更适合表示算法的时间复杂性。
因为本算法时间复杂性从门（n）到O（nlogn），而心是表示精确阶的。
1.38
对n个数进行排序。
第5章归纳法
5.3（本题不仅有以下一个答案）
1.max（n）
过程：
max（i）
ifn=1returna[1]
t=max（i-1）
ifa[i-1]>treturna[i-1]
elsereturnt
endif
5.6
最多次数:
C（n）二°"1
c（n-1）+（n-1）,nZ2
n（n-1）
2
n
C（n）八
j#
最少次数:
C（n）二n-15.7
参考例5.1
5.14
（a）不稳定，例如:
12
45
45
24
1
12
45
45
24
12
24
45
45
1
r
12
24
45
45
可见SELECTIONSORT中相等元素的序在排序后改变。
（b）（c）（d）（f）稳定
5.17
（a）利用Fn（x）二xR」（x）•ao
取x=3，
R（3）tR（3）tF3（3）tB（3）tR（3）tR（3）
F2（3）=3*R（3）+4=37^R（3）=3*F0（3）+2=1仆F0（3）=3
P3（3）=3*P（3）+1=112t巳（3）=3*PJ3）+2=338t巳（3）=3*巳（3）+5=1019
5.18
（a）p（2,5）p（2/2P（2p1）
y=42*2-y=22=4—y=12*2—y=1
第6章分治
6.3
输入：
A[1,2,…n]
输出：
max,min
1.fori=1tomid
2.j=high-i
3.ifa[i]>a[j],thenexchangea[i],a[j]
4.endfor
5.fori=lowtomid
6.ifa[i+1]7.endfor
8.fori=mid+1tohigh
9.ifa[i+1]>a[high],thenexchangea[high],a[i+1]
10.endfor
6.5
输入：
一个整数数组A[1,2,…,n]
输出：
sum
1.ifhigh-low=1then
2.sum=a[low]+a[high]
3.else
4.mid=（low+high）/2
5sum1=sum（low,mid）
6sum2=sum（mid+1,high）
7.sum=sum1+sum2
8.endif
9.returnsum
算法需要的工作空间为3
6.10.
12
25
17
19
51
32
45
18
22
37
15
12
15
17
18
19
22
25
32
37
45
51
12
25
17
19
51
32
12
17
19
25
32
51
45
18
22
37
15
15
18
22
37
45
12
25
17
12
17
25
J
12
25
12
25
12
25
12
25
19
51
32
19
32
51
45
18
22
18
22
45
37
15
15
37
32
22
37
15
19
51
19
51
17
17
19
51
45
18
18
45
22
18
45
19
51
45
18
37
15
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
32
27
18
45
11
63
12
19
16
25
52
14
14
18
11
12
19
16
23
32
45
27
25
52
63
14
18
11
12
19
16
12
11
14
18
19
16
12
11
11
12
11
11
18
19
16
16
18
19
16
16
19
19
32
45
27
25
52
63
25
27
32
45
52
63
25
27
25
27
27
27
45
52
63
45
52
63
52
63
52
63
63
V
IF
v
V
IF
v
v
V
v
V
V
11
12
14
16
18
19
23
25
27
32
45
52
63
63
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
<0513、
DUj^min{D°[i,j],D0[i,1]+D°[1,j]}120911
43402
<1620」
*0716、
□009co
D1=
4402
<1820」
D2[i,j]=min{U[i,j],皿,2]D1[2,j]}
广0716'
°C0900
D2=
4402
<1820」
13
5
0
1
9
3"
11
D3=
4
4
0
2
6
2
°」
D4[i,j]二min{D3[i,j],D3[i,4]D3[4,j]}
广0
5
1
3、
D4=
12
0
9
11
3
4
0
2
6
2
°>
7.21
0
1
2
3
4
5
6
7
8
9
10
11
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
3
3
3
3
3
3
3
3
3
3
2
0
0
3
4
4
7
7
7
7
7
7
7
3
0
0
3
4
4
7
7
8
9
9
12
12
4
0
0
3
4
4
7
7
8
10
11
12
14
7.23
当物品体积为负值时，运行算法会发生溢出错误。
第八章贪心算法
a然后到t,其结果为4，而从s到t距离为2,所以探索不总是产
□o
28
8.23（共有4棵最小生成树，此处仅举一例）
Q0Q
'3上16
8.24（共有4棵最小生成树，此处仅举一例）
每一个二叉树都取左边为0，右边为1
则最优编码为a:
10b:
001c:
0001
d:
0000e:
01f:
11
注意：
编码不唯一
回溯法
升级会员 