算法设计技巧与分析 答案整理
《算法设计技巧与分析（沙特版）》
这书答案真难找啊…
东拼西凑薅出这么些
https://wenku.baidu.com/view/279b9245561252d380eb6ea4.html
https://wenku.baidu.com/view/af57e4f5b4daa58da1114a4b.html?rec_flag=default
还有几个文档
文章目录
第1章 算法分析基本概念
1.4
算法执行了7+6+5+4+3+2+1=28次比较
1.5
(a) 算法MODSELECTIONSORT执行的元素赋值的最少次数是0,按非降序排列时候达到最小值
(b) 算法MODSELECTIONSORT执行的元素赋值的最多次数是
按非升序排列时候达到最小值，按降序排列时达到最大
1.7
由上图可以看到算法INSERTIONSORT执行的比较次数为1+1+2+2+2+6+2=16
1.9
1.11
由上图可以得出比较次数为5+6+6+9=26次
1.13
FTF,TTT,FTF,TFF,FTF
1.14
1.16
1.17
1.25
1.27
1.31
1.32
1.33
1.37
1.38
对n个数进行排列。
第2章 数学预备知识
2.10
2.16
2.18
2.19
2.20
第3章 数据结构
第4章 堆和不相交集数据结构
4.13
第5章 归纳法
5.3
5.6
5.7
参看例5.1
5.8
5.12
5.14
(a)不稳定
(b)©(d)(f)稳定
5.33
第6章 分治
6.3
6.5
令解：
6.6
6.10
6.16
6.31
6.35
6.36
6.42
b是稳定的算法
c不是稳定的算法
6.43
bcefg均为适应的
ah不是适应的
6.52
算法可参考寻找中相（第k小元素）构造
6.53
用反例说明（4个顶点即可）。形状为普通的生成树
6.54
第7章 动态规划
7.1
( c ) 算法BOTTOMUPSORT
7.3
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
7.21
7.23
结果是溢出
7.26
7.30
7.34
第8章 贪心算法
8.5
8.12
由算法从s到t要选择先到a然后到t,其结果为4，而从s到t距离为2，所以探索不总是产生从s到t的距离
8.16
8.23
解一：
8.24
8.23与8.24答案均不唯一
8.31
每一个二叉树都取左边为0，右边为1
则最优编码为
a:010
b:001
c:0001
d:0000
e:1
f:011
注意：编码不唯一
第9章 图的遍历
9.3
参照例9.1
9.5
更改算法9.1的dfs(v)过程即可
9.7
9.14
9.15
9.17
第10章 NP完全问题
10.3
修改深度优先算法即可
10.5
10.9
10.19
10.22
第13章 回溯法
13.2
13.3
13.6
修改3着色问题的递归算法，或者4皇后算法即可
13.10
13.12
判定子集和问题。题目要求判定是否存在，不是枚举全部
13.17
使用分支限界法
13.21
(i,j)对应(1,3) (2,4) (3,1) (4,2) bound=13