第1章 算法概述 1
算法分析题1 1
1-1函数的渐近表达式 1
1-2 O（1）和O（2）的区别 1
1-3按渐近阶排列表达式 1
1-4算法效率 1
1-5硬件效率 1
1-6函数渐近阶 2
1-7 n！的阶 2
1-8 3n＋1问题 2
1-9平均情况下的计算时间复杂性 2
算法实现题1 3
1-1统计数字问题 3
1-2字典序问题 4
1-3最多约数问题 4
1-4金币阵列问题 6
1-5最大间隙问题 8
第2章 递归与分治策略 11
算法分析题2 11
2-1证明Hanoi塔问题的递归算法与非递归算法实际上是一回事 11
2-2判断这7个算法的正确性 12
2-3改写二分搜索算法 15
2-4大整数乘法的O（nm log（3/2））算法 16
2-5 5次n/3位整数的乘法 16
2-6矩阵乘法 18
2-7多项式乘积 18
2-8 O（1）空间子数组换位算法 19
2-9 O（1）空间合并算法 21
2-10 ？n段合并排序算法 27
2-11自然合并排序算法 28
2-12第k小元素问题的计算时间下界 29
2-13非增序快速排序算法 31
2-14构造Gray码的分治算法 31
2-15 网球循环赛日程表 32
2-16二叉树T的前序、中序和后序序列 35
算法实现题2 36
2-1众数问题 36
2-2马的Hamilton周游路线问题 37
2-3半数集问题 44
2-4半数单集问题 46
2-5有重复元素的排列问题 46
2-6排列的字典序问题 47
2-7集合划分问题 49
2-8集合划分问题 50
2-9双色Hanoi塔问题 51
2-10标准二维表问题 52
2-11整数因子分解问题 53
第3章 动态规划 54
算法分析题3 54
3-1最长单调递增子序列 54
3-2最长单调递增子序列的O（nlogn）算法 54
3-3整数线性规划问题 55
3-4二维0-1背包问题 56
3-5 Ackermann函数 57
算法实现题3 59
3-1独立任务最优调度问题 59
3-2最优批处理问题 61
3-3石子合并问题 67
3-4数字三角形问题 68
3-5乘法表问题 69
3-6租用游艇问题 70
3-7汽车加油行驶问题 70
3-8最小m段和问题 71
3-9圈乘运算问题 72
3-10最大长方体问题 78
3-11正则表达式匹配问题 79
3-12双调旅行售货员问题 83
3-13最大k乘积问题 84
3-14最少费用购物问题 86
3-15 收集样本问题 87
3-16最优时间表问题 89
3-17字符串比较问题 89
3-18有向树k中值问题 90
3-19有向树独立k中值问题 94
3-20有向直线m中值问题 98
3-21有向直线2中值问题 101
3-22树的最大连通分支问题 103
3-23直线k中值问题 105
3-24直线k覆盖问题 109
3-25 m处理器问题 113
第4章 贪心算法 116
算法分析题4 116
4-1程序最优存储问题 116
4-2最优装载问题的贪心算法 116
4-3 Fibonacci序列的哈夫曼编码 116
4-4最优前缀码的编码序列 117
算法实现题4 117
4-1会场安排问题 117
4-2最优合并问题 118
4-3磁带最优存储问题 118
4-4磁盘文件最优存储问题 119
4-5程序存储问题 120
4-6最优服务次序问题 120
4-7多处最优服务次序问题 121
4-8 d森林问题 122
4-9虚拟汽车加油问题 123
4-10区间覆盖问题 124
4-11删数问题 124
4-12磁带最大利用率问题 125
4-13非单位时间任务安排问题 126
4-14多元Huffman编码问题 127
4-15 最优分解问题 128
第5章 回溯法 130
算法分析题5 130
5-1装载问题改进回溯法1 130
5-2装载问题改进回溯法2 131
5-3 0-1背包问题的最优解 132
5-4最大团问题的迭代回溯法 134
5-5旅行售货员问题的费用上界 135
5-6旅行售货员问题的上界函数 136
算法实现题5 137
5-1子集和问题 137
5-2最小长度电路板排列问题 138
5-3最小重量机器设计问题 140
5-4运动员最佳配对问题 141
5-5无分隔符字典问题 142
5-6无和集问题 144
5-7 n色方柱问题 145
5-8整数变换问题 150
5-9拉丁矩阵问题 151
5-10排列宝石问题 152
5-11重复拉丁矩阵问题 154
5-12罗密欧与朱丽叶的迷宫问题 156
5-13工作分配问题 158
5-14布线问题 159
5-15 最佳调度问题 160
5-16无优先级运算问题 161
5-17世界名画陈列馆问题 163
5-18世界名画陈列馆问题（不重复监视） 166
5-19算m点问题 169
5-20部落卫队问题 171
5-21子集树问题 173
5-22 0-1背包问题 174
5-23排列树问题 176
5-24一般解空间搜索问题 177
5-25最短加法链问题 179
第6章 分支限界法 185
算法分析题6 185
6-1 0-1背包问题的栈式分支限界法 185
6-2释放结点空间的队列式分支限界法 187
6-3及时删除不用的结点 188
6-4用最大堆存储活结点的优先队列式分支限界法 189
6-5释放结点空间的优先队列式分支限界法 192
6-6团顶点数的上界 194
6-7团顶点数改进的上界 194
6-8修改解旅行售货员问题的分支限界法 195
6-9试修改解旅行售货员问题的分支限界法，使得算法保存已产生的排列树 197
6-10电路板排列问题的队列式分支限界法 199
算法实现题6 201
6-1最小长度电路板排列问题 201
6-2最小权顶点覆盖问题 203
6-3无向图的最大割问题 206
6-4最小重量机器设计问题 209
6-5运动员最佳配对问题 212
6-6 n后问题 214
6-7布线问题 216
6-8最佳调度问题 218
6-9无优先级运算问题 220
6-10世界名画陈列馆问题 223
6-11子集空间树问题 226
6-12排列空间树问题 229
6-13一般解空间的队列式分支限界法 232
6-14子集空间树问题 236
6-15 排列空间树问题 241
6-16一般解空间的优先队列式分支限界法 246
6-17推箱子问题 250
第7章 概率算法 256
算法分析题7 256
7-1模拟正态分布随机变量 256
7-2随机抽样算法 256
7-3随机产生m个整数 257
7-4集合大小的概率算法 258
7-5生日问题 258
7-6易验证问题的拉斯维加斯算法 259
7-7用数组模拟有序链表 260
7-8 O（n3/2）舍伍德型排序算法 260
7-9 n后问题解的存在性 260
7-10整数因子分解算法 262
7-11非蒙特卡罗算法的例子 262
7-12重复3次的蒙特卡罗算法 263
7-13集合随机元素算法 263
7-14由蒙特卡罗算法构造拉斯维加斯算法 265
7-15 产生素数算法 265
7-16矩阵方程问题 265
算法实现题7 266
7-1模平方根问题 266
7-2素数测试问题 268
7-3集合相等问题 269
7-4逆矩阵问题 269
7-5多项式乘积问题 270
7-6皇后控制问题 270
7-7 3-SAT问题 274
7-8战车问题 275
第8章 线性规划与网络流 278
算法分析题8 278
8-1线性规划可行区域无界的例子 278
8-2单源最短路与线性规划 278
8-3网络最大流与线性规划 279
8-4最小费用流与线性规划 279
8-5运输计划问题 279
8-6单纯形算法 280
8-7边连通度问题 281
8-8有向无环网络的最大流 281
8-9无向网络的最大流 281
8-10最大流更新算法 282
8-11混合图欧拉回路问题 282
8-12单源最短路与最小费用流 282
8-13中国邮路问题 282
算法实现题8 283
8-1飞行员配对方案问题 283
8-2太空飞行计划问题 284
8-3最小路径覆盖问题 285
8-4魔术球问题 286
8-5圆桌问题 287
8-6最长递增子序列问题 287
8-7试题库问题 290
8-8机器人路径规划问题 291
8-9方格取数问题 294
8-10餐巾计划问题 298
8-11航空路线问题 299
8-12软件补丁问题 300
8-13星际转移问题 301
8-14孤岛营救问题 302
8-15 汽车加油行驶问题 304
8-16数字梯形问题 307
8-17运输问题 311
8-18分配工作问题 314
8-19负载平衡问题 315
8-20最长k可重区间集问题 317
8-21最长k可重线段集问题 319
第9章 串与序列的算法 323
算法分析题9 323
9-1简单子串搜索算法最坏情况复杂性 323
9-2后缀重叠问题 323
9-3改进前缀函数 323
9-4确定所有匹配位置的KMP算法 324
9-5特殊情况下简单子串搜索算法的改进 325
9-6简单子串搜索算法的平均性能 325
9-7带间隙字符的模式串搜索 326
9-8串接的前缀函数 326
9-9串的循环旋转 327
9-10失败函数性质 327
9-11输出函数性质 328
9-12后缀数组类 328
9-13最长公共扩展查询 329
9-14最长公共扩展性质 332
9-15 后缀数组性质 333
9-16后缀数组搜索 334
9-17后缀数组快速搜索 335
算法实现题9 338
9-1安全基因序列问题 338
9-2最长重复子串问题 342
9-3最长回文子串问题 343
9-4相似基因序列性问题 344
9-5计算机病毒问题 345
9-6带有子串包含约束的最长公共子序列问题 347
9-7多子串排斥约束的最长公共子序列问题 349
参考文献 351