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

2-1证明Hanoi塔问题的递归算法与非递归算法实际上是一回事11

2-2判断这7个算法的正确性12

2-3改写二分搜索算法15

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

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

2-6矩阵乘法18

2-7多项式乘积18

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

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

2-10段合并排序算法27

2-11自然合并排序算法28

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-5Ackermann函数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-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-25m处理器问题113

第4章贪心算法116

算法分析题4116

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

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

4-3Fibonacci序列的哈夫曼编码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-8d森林问题122

4-9虚拟汽车加油问题123

4-10区间覆盖问题124

4-11删数问题124

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

4-14多元Huffman编码问题127

4-15最优分解问题128

第5章回溯法130

算法分析题5130

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

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

5-30-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-7n色方柱问题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-220-1背包问题174

5-23排列树问题176

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

5-25最短加法链问题179

第6章分支限界法185

算法分析题6185

6-10-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