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

　　本书是与“十二五”普通高等教育本科国家级规划教材《计算机算法设计与分析（第5版）》配套的辅助教材和国家精品课程教材，分别对主教材中的算法分析题和算法实现题给出了解答或解题思路提示。为了提高学生灵活运用算法设计策略解决实际问题的能力，本书还将主教材中的许多习题改造成算法实现题，要求学生设计出求解算法并上机实现。本书教学资料包含各章算法实现题、测试数据和答案，可在华信教育资源网免费注册下载。本书内容丰富，理论联系实际，可作为高等学校计算机科学与技术、软件工程、信息安全、信息与计算科学等专业本科生和研究生学习计算机算法设计的辅助教材，也是工程技术人员和自学者的参考书。

　　王晓东，男，1957年出生，山东人，中**员，现任福建工程学院副院长，教授，博士生导师，福建省计算机学会理事长。先后担任福州大学计算机系主任、数学与计算机科学学院院长，2007年8月起担任泉州师范学院副院长。主讲课程：算法与数据结构、算法设计与分析、文献阅读与选题报告。

第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