1.27
不能用 关系来比较 和 增长的阶。
∵
不是 的，即不能用 关系来比较 和 增长的阶。
1.32
(a)当n为2的幂时，第六步执行的最大次数是：
时，
(b)由(a)可以得到：当每一次循环j都为2的幂时，第六步执行的次数最大，
则当 （其中 取整）时，
(c)用 符号表示的算法的时间复杂性是
已证明n=2k的情况，下面证明n=2k+1的情况：
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
6.10.
6.31
彩色代表i,j所指的数字j总在i前
6.36
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
6. if a[i+1]<a[low], thenexchangea[low],a[i+1]
7.end for
8.for i=mid+1 to high
9. if a[i+1]>a[high],thenexchangea[high],a[i+1]
10.end for
6.5
输入：一个整数数组A[1,2,…,n]
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
最多次数：
最少次数：
C(n)=n-1
5.7
参考例5.1
5.14
(a)不稳定，例如：
可见SELECTIONSORT中相等元素的序在排序后改变。
因为有
所以n=2k+1时，第六步执行的最大次数仍是n log n。
(d)用 符号表示的算法的时间复杂性是 。
当 满足 取整为奇数时，算法执行的次数是 次，其他情况算法执行次数均大于 。
(e)O更适合表示算法的时间复杂性。因为本算法时间复杂性从 到 ，而 是表示精确阶的。
1.38
对 个数进行排序。
第5章归纳法
(b)(c)(d)(f)稳定
5.17
(a)利用
取 ，
5.18
(a)
第6章分治
6.3
输入：A[1,2,…n]
输出：max,min
1.for i=1 tomid
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
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)执行该算法，元素比较的最多次数是 。元素已按非升序排列时候达到最大值。
所以最优括号表达式为（M1M2）((M3M4)M5)
7.15
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
当物品体积为负值时，运行算法会发生溢出错误。
第八章贪心算法
注意：编码不唯一
回溯法
8.12
由算法从s到t要选择先到a然后到t,其结果为4，而从s到t距离为2，所以探索不总是产生从s到t的距离
8.13
8.23（共有4棵最小生成树，此处仅举一例）
8.24（共有4棵最小生成树，此处仅举一例）
8.31
每一个二叉树都取左边为0，右边为1
则最优编码为a:10 b:001 c:0001
d:0000 e:01 f:11
算法设ቤተ መጻሕፍቲ ባይዱ技巧与分析
参考答案
第1章算法分析基本概念
1.1
(a)6(b)5(c)6(d)6
1.4
算法执行了7+6+5+4+3+2+1=28次比较
1.5
(a)算法MODSELECTIONSORT执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。
(b)算法MODSELECTIONSORT执行的元素赋值的最多次数是 ,元素已按非升序排列的时候达到最小值。
(c)执行该算法，元素赋值的最少次数是0。元素已按非降序排列时候达到最小值。
(d)执行该算法，元素赋值的最多次数是 。元素已按非升序排列时候达到最大值。
(e) 用O符号和 符号表示算法BUBBLESORT的运行时间： ，
(f)不可以用 符号来表示算法的运行时间： 是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。
输出：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
