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

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

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

本书是与普通高等教育“十一五”国家级规划教材《计算机算法设计与分析（第4版）》配套的辅助教材和国家精品课程教材，分别对主教材中的算法分析题和算法实现题给出了解答或解题思路提示。为了提高学生灵活运用算法设计策略解决实际问题的能力，本书还将主教材中的许多习题改造成算法实现题，要求学生设计出求解算法并上机实现。

• 配套教材

《计算机算法设计与分析（第5版）》有配套教材——《计算机算法设计与分析习题解答（第5版）》 。

第1章 算法概述

算法分析题1

1-1 函数的渐近表达式

1-2 O(1)和O(2)的区别

1-3 按渐近阶排列表达式

1-4 算法效率

1-5 硬件效率

1-6 函数渐近阶

1-7 n!的阶

1-8 3n 1问题

1-9 平均情况下的计算时间复杂性

算法实现题1

1-1 统计数字问题

1-2 字典序问题

1-3 最多约数问题

1-4 金币阵列问题

1-5 最大间隙问题

第2章 递归与分治策略

算法分析题2

2-1 Hanoi塔问题的非递归算法

2-2 7个二分搜索算法

2-3 改写二分搜索算法

2-4 大整数乘法的O(nmlog(3/2))算法

2-5 5次n/3位整数的乘法

2-6 矩阵乘法

2-7 多项式乘积

2-8 O(1)空间子数组换位算法

2-9 O(1)空间合并算法

2-10 n段合并排序算法

2-11 自然合并排序算法

2-12 第k小元素问题的计算时间下界

2-13 非增序快速排序算法

2-14 构造Gray码的分治算法

2-15 网球循环赛日程表

2-16 二叉树T的前序、中序和后序序列

算法实现题2

2-1 众数问题

2-2 马的Hamilton周游路线问题

2-3 半数集问题

2-4 半数单集问题

2-5 有重复元素的排列问题

2-6 排列的字典序问题

2-7 集合划分问题

2-8 集合划分问题

2-9 双色Hanoi塔问题

2-10 标准二维表问题

2-11 整数因子分解问题

第3章 动态规划

算法分析题3

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

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

3-3 整数线性规划问题

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

3-5 Ackermann函数

算法实现题3

3-1 独立任务最优调度问题

3-2 编辑距离问题

3-3 石子合并问题

3-4 数字三角形问题

3-5 乘法表问题

3-6 租用游艇问题

3-7 汽车加油行驶问题

3-8 最小m段和问题

3-9 圈乘运算问题

3-10 最大长方体问题

3-11 正则表达式匹配问题

3-12 双调旅行售货员问题

3-13 最大k乘积问题

3-14 最少费用购物问题

3-15 收集样本问题

3-16 最优时间表问题

3-17 字符串比较问题

3-18 有向树k中值问题

3-19 有向树独立k中值问题

3-20 有向直线m中值问题

3-21 有向直线2中值问题

3-22 树的最大连通分支问题

3-23 直线k中值问题

3-24 直线k覆盖问题

3-25 m处理器问题

第4章 贪心算法

算法分析题4

4-1 程序最优存储问题

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

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

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

算法实现题4

4-1 会场安排问题

4-2 最优合并问题

4-3 磁带最优存储问题

4-4 磁盘文件最优存储问题

4-5 程序存储问题

4-6 最优服务次序问题

4-7 多处最优服务次序问题

4-8 d森林问题

4-9 汽车加油问题

4-10 区间覆盖问题

4-11 删数问题

4-12 磁带最大利用率问题

4-13 非单位时间任务安排问题

4-14 多元Huffman编码问题

4-15 最优分解问题

第5章 回溯法

算法分析题5

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

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

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

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

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

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

算法实现题5

5-1 子集和问题

5-2 最小长度电路板排列问题

5-3 最小重量机器设计问题

5-4 运动员最佳配对问题

5-5 无分隔符字典问题

5-6 无和集问题

5-7 n色方柱问题

5-8 整数变换问题

5-9 拉丁矩阵问题

5-10 排列宝石问题

5-11 重复拉丁矩阵问题

5-12 罗密欧与朱丽叶的迷宫问题

5-13 工作分配问题

5-14 布线问题

5-15 最佳调度问题

5-16 无优先级运算问题

5-17 世界名画陈列馆问题

5-18 世界名画陈列馆问题（不重复监视）

5-19 算m点问题

5-20 部落卫队问题

5-21 子集树问题

5-22 0-1背包问题

5-23 排列树问题

5-24 一般解空间搜索问题

5-25 最短加法链问题

第6章 分支限界法

算法分析题6

6-1 0-1背包问题的栈式分支限界法

6-2 释放结点空间的队列式分支限界法

6-3 及时删除不用的结点

6-4 用最大堆存储活结点的优先队列式分支限界法

6-5 释放结点空间的优先队列式分支限界法

6-6 团顶点数的上界

6-7 团顶点数改进的上界

6-8 修改解旅行售货员问题的分支限界法

6-9 解旅行售货员问题的分支限界法中保存已产生的排列树

6-10 电路板排列问题的队列式分支限界法

算法实现题6

6-1 最小长度电路板排列问题

6-2 最小权顶点覆盖问题

6-3 无向图的最大割问题

6-4 最小重量机器设计问题

6-5 运动员最佳配对问题

6-6 n皇后问题

6-7 布线问题

6-8 最佳调度问题

6-9 无优先级运算问题

6-10 世界名画陈列馆问题

6-11 子集空间树问题

6-12 排列空间树问题

6-13 一般解空间的队列式分支限界法

6-14 子集空间树问题

6-15 排列空间树问题

6-16 一般解空间的优先队列式分支限界法

6-17 推箱子问题

第7章 概率算法

算法分析题7

7-1 模拟正态分布随机变量

7-2 随机抽样算法

7-3 随机产生m个整数

7-4 集合大小的概率算法

7-5 生日问题

7-6 易验证问题的拉斯维加斯算法

7-7 用数组模拟有序链表

7-8 O(n3/2)舍伍德型排序算法

7-9 n后问题解的存在性

7-10 整数因子分解算法

7-11 非蒙特卡罗算法的例子

7-12 重复3次的蒙特卡罗算法

7-13 集合随机元素算法

7-14 由蒙特卡罗算法构造拉斯维加斯算法

7-15 产生素数算法

7-16 矩阵方程问题

算法实现题7

7-1 模平方根问题

7-2 素数测试问题

7-3 集合相等问题

7-4 逆矩阵问题

7-5 多项式乘积问题

7-6 皇后控制问题

7-7 3-SAT问题

7-8 战车问题

第8章 线性规划与网络流 算法分析题8

8-1 线性规划可行区域无界的例子

8-2 单源最短路与线性规划

8-3 网络最大流与线性规划

8-4 最小费用流与线性规划

8-5 运输计划问题

8-6 单纯形算法

8-7 边连通度问题

8-8 有向无环网络的最大流

8-9 无向网络的最大流

8-10 最大流更新算法

8-11 混合图欧拉回路问题

8-12 单源最短路与最小费用流

8-13 中国邮路问题

算法实现题8

8-1 飞行员配对方案问题

8-2 太空飞行计划问题

8-3 最小路径覆盖问题

8-4 魔术球问题

8-5 圆桌问题

8-6 最长递增子序列问题

8-7 试题库问题

8-8 机器人路径规划问题

8-9 方格取数问题

8-10 餐巾计划问题

8-11 航空路线问题

8-12 软件补丁问题

8-13 星际转移问题

8-14 孤岛营救问题

8-15 汽车加油行驶问题

8-16 数字梯形问题

8-17 运输问题

8-18 分配工作问题

8-19 负载平衡问题

8-20 最长k可重区间集问题

8-21 最长k可重线段集问题

参考文献2100433B