计算机算法设计与分析习题解答（第5版） PDF下载

目    录
第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(nmlog(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  段合并排序算法	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