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

图书标准信息

• 作者 王晓东
• 出版社 电子工业出版社
• 出版时间 2018-10
• 版次 5
• ISBN 9787121344381
• 定价 56.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸

【内容简介】

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

【作者简介】

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

【目录】

目    录

第1章  算法概述1

算法分析题11

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

算法实现题13

1-1  统计数字问题3

1-2  字典序问题4

1-3  最多约数问题4

1-4  金币阵列问题6

1-5  最大间隙问题8

第2章  递归与分治策略11

算法分析题211

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

算法实现题236

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

算法分析题354

3-1  最长单调递增子序列54

3-2  最长单调递增子序列的O(nlogn)算法54

3-3  整数线性规划问题55

3-4  二维0-1背包问题56

3-5  Ackermann函数57

算法实现题359

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

算法分析题4116

4-1  程序最优存储问题116

4-2  最优装载问题的贪心算法116

4-3  Fibonacci序列的哈夫曼编码116

4-4  最优前缀码的编码序列117

算法实现题4117

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

算法分析题5130

5-1  装载问题改进回溯法1130

5-2  装载问题改进回溯法2131

5-3  0-1背包问题的最优解132

5-4  最大团问题的迭代回溯法134

5-5  旅行售货员问题的费用上界135

5-6  旅行售货员问题的上界函数136

算法实现题5137

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

算法分析题6185

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

算法实现题6201

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

算法分析题7256

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

算法实现题7266

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

算法分析题8278

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

算法实现题8283

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

算法分析题9323

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

算法实现题9338

9-1  安全基因序列问题338

9-2  最长重复子串问题342

9-3  最长回文子串问题343

9-4  相似基因序列性问题344

9-5  计算机病毒问题345

9-6  带有子串包含约束的最长公共子序列问题347

9-7  多子串排斥约束的最长公共子序列问题349

参考文献351