计算机算法设计与分析习题解答

《计算机算法设计与分析习题解答(第2版)》

第1章算法概述

算法分析题1

1-1函数的渐近表达式

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

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

1-4算法效率

1-5硬件效率

1-6函数渐近阶

1-7n!的阶

1-83n+1问题

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

算法实现题1

1-1统计数字问题

1-2字典序问题

1-3最多约数问题

1-4金币阵列问题

1-5最大间隙问题

第2章递归与分治策略

算法分析题2

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

2-27个二分搜索算法

2-3改写二分搜索算法

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

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

2-6矩阵乘法

2-7多项式乘积

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

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

2-10n段合并排序算法

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-5ackermann函数

算法实现题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-25m处理器问题

第4章贪心算法

算法分析题4

4-1程序最优存储问题

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

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

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

算法实现题4

4-1会场安排问题

4-2最优合并问题

4-3磁带最优存储问题

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

4-5程序存储问题

4-6最优服务次序问题

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

4-8d森林问题

4-9汽车加油问题

4-10区间覆盖问题

4-11删数问题

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

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

4-14多元huffman编码问题

4-15最优分解问题

第5章回溯法

算法分析题5

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

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

5-30-1背包问题的最优解

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

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

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

算法实现题5

5-1子集和问题

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

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

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

5-5无分隔符字典问题

5-6无和集问题

5-7n色方柱问题

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-220-1背包问题

5-23排列树问题

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

5-25最短加法链问题

第6章分支限界法

算法分析题6

6-10-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-6n皇后问题

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-8o(n3/2)舍伍德型排序算法

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

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-73-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可重线段集问题

参考文献