算法设计与分析习题解答 第2版PDF电子书下载

第1章　算法引论 1

习题1-1　实参交换 1

习题1-2　方法头签名 1

习题1-3　数组排序判定 1

习题1-4　函数的渐近表达式 2

习题1-5　O（1）和O（2）的区别 2

习题1-7　按渐近阶排列表达式 2

习题1-8　算法效率 2

习题1-9　硬件效率 3

习题1-10　函数渐近阶 3

习题1-11　n！的阶 4

习题1-12　平均情况下的计算时间复杂性 4

算法实现题1-1　统计数字问题 4

算法实现题1-2　字典序问题 5

算法实现题1-3　最多约数问题 6

算法实现题1-4　金币阵列问题 8

算法实现题1-5　最大间隙问题 11

第2章　递归与分治策略 14

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

习题2-2　7个二分搜索算法 15

习题2-3　改写二分搜索算法 18

习题2-4　大整数乘法的O（nmlog（3/2））算法 19

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

习题2-6　矩阵乘法 21

习题2-7　多项式乘积 21

习题2-8　不动点问题的O（logn）时间算法 22

习题2-9　主元素问题的线性时间算法 22

习题2-10　无序集主元素问题的线性时间算法 22

习题2-11　O（1）空间子数组换位算法 23

习题2-12　O（1）空间合并算法 25

习题2-13　？段合并排序算法 32

习题2-14 自然合并排序算法 32

习题2-15　最大值和最小值问题的最优算法 35

习题2-16　最大值和次大值问题的最优算法 35

习题2-17　整数集合排序 35

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

习题2-19　非增序快速排序算法 37

习题2-20　随机化算法 37

习题2-21　随机化快速排序算法 38

习题2-22　随机排列算法 38

习题2-23　算法qSort中的尾递归 38

习题2-24　用栈模拟递归 38

习题2-25　算法select中的元素划分 39

习题2-26　O（nlogn）时间快速排序算法 40

习题2 27　最接近中位数的k个数 40

习题2-28　X和Y的中位数 40

习题2-29　网络开关设计 41

习题2-32　带权中位数问题 42

习题2-34　构造Gray码的分治算法 43

习题2-35　网球循环赛日程表 44

算法实现题2-1　输油管道问题（习题2-30） 49

算法实现题2-2　众数问题（习题2-31） 50

算法实现题2-3　邮局选址问题（习题2-32） 51

算法实现题2-4 马的HamiIton周游路线问题（习题2-33） 51

算法实现题2-5　半数集问题 60

算法实现题2-6　半数单集问题 62

算法实现题2-7　士兵站队问题 63

算法实现题2-8　有重复元素的排列问题 63

算法实现题2-9　排列的字典序问题 65

算法实现题2-10　集合划分问题（一） 67

算法实现题2-11　集合划分问题（二） 68

算法实现题2-12　双色Hanoi塔问题 69

算法实现题2-13　标准二维表问题 71

算法实现题2-14　整数因子分解问题 72

算法实现题2-15　有向直线2中值问题 72

第3章　动态规划 76

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

习题3-2　最长单调递增子序列的O（nlogn）算法 77

习题3-7　漂亮打印 78

习题3-11　整数线性规划问题 79

习题3-12　二维背包问题 80

习题3-14 Ackermann函数 81

习题3-17　最短行驶路线 83

习题3-19　最优旅行路线 83

算法实现题3-1 独立任务最优调度问题（习题3-3） 83

算法实现题3-2　最少硬币问题（习题3-4） 85

算法实现题3-3　序关系计数问题（习题3-5） 86

算法实现题3-4　多重幂计数问题（习题3-6） 87

算法实现题3-5　编辑距离问题（习题3-8） 87

算法实现题3-6　石子合并问题（习题3-9） 89

算法实现题3-7　数字三角形问题（习题3-10） 91

算法实现题3-8　乘法表问题（习题3-13） 92

算法实现题3-9　租用游艇问题（习题3-15） 93

算法实现题3-10　汽车加油行驶问题（习题3-16） 95

算法实现题3-11 圈乘运算问题（习题3-18） 96

算法实现题3-12　最少费用购物（习题3-20） 102

算法实现题3-13　最大长方体问题（习题3-21） 104

算法实现题3-14　正则表达式匹配问题（习题3-22） 105

算法实现题3-15　双调旅行售货员问题（习题3-23） 110

算法实现题3-16　最大k乘积问题（习题5-24） 111

算法实现题3-17　最小n段和问题 113

算法实现题3-18　红黑树的红色内结点问题 115

第4章　贪心算法 123

习题4-2　活动安排问题的贪心选择 123

习题4-3　背包问题的贪心选择性质 123

习题4-4　特殊的0-1背包问题 124

习题4-10　程序最优存储问题 124

习题4-13　最优装载问题的贪心算法 125

习题4-18　Fibonacci序列的Huffman编码 125

习题4-19　最优前缀码的编码序列 125

习题4-21　任务集独立性问题 126

习题4-22　矩阵拟阵 126

习题4-23　最小权最大独立子集拟阵 126

习题4-27 整数边权Prim算法 126

习题4-28　最大权最小生成树 127

习题4-29　最短路径的负边权 127

习题4-30　整数边权Dijkstra算法 127

算法实现题4-1　会场安排问题（习题4-1） 128

算法实现题4-2　最优合并问题（习题4-5） 129

算法实现题4-3　磁带最优存储问题（习题4-6） 130

算法实现题4-4　磁盘文件最优存储问题（习题4-7） 131

算法实现题4-5　程序存储问题（习题4-8） 132

算法实现题4-6　最优服务次序问题（习题4-11） 133

算法实现题4-7　多处最优服务次序问题（习题4-12） 134

算法实现题4-8　d森林问题（习题4-14） 135

算法实现题4-9　汽车加油问题（习题4-16） 137

算法实现题4-10　区间覆盖问题（习题4-17） 138

算法实现题4-11　硬币找钱问题（习题4-24） 138

算法实现题4-12　删数问题（习题4-25） 139

算法实现题4-13　数列极差问题（习题4-26） 140

算法实现题4-14　嵌套箱问题（习题4-31） 140

算法实现题4-15　套汇问题（习题4-32） 142

算法实现题4-16　信号增强装置问题（习题5-17） 143

算法实现题4-17　磁带最大利用率问题（习题4-9） 144

算法实现题4-18　非单位时间任务安排问题（习题4-15） 145

算法实现题4-19　多元Huffman编码问题（习题4-20） 147

算法实现题4-20　多元Huffman编码变形 149

算法实现题4-21 区间相交问题 151

算法实现题4-22　任务时间表问题 151

第5章　回溯法 153

习题5-1　装载问题改进回溯法（一） 153

习题5-2　装载问题改进回溯法（二） 154

习题5-4　0-1背包问题的最优解 155

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

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

习题5-8　旅行售货员问题的上界函数 158

算法实现题5-1　子集和问题（习题5-3） 159

算法实现题5-2　最小长度电路板排列问题（习题5-9） 160

算法实现题5-3　最小重量机器设计问题（习题5-10） 163

算法实现题5-4　运动员最佳匹配问题（习题5-11） 164

算法实现题5-5　无分隔符字典问题（习题5-12） 165

算法实现题5-6　无和集问题（习题5-13） 167

算法实现题5-7　n色方柱问题（习题5-14） 168

算法实现题5-8　整数变换问题（习题5-15） 173

算法实现题5-9　拉丁矩阵问题（习题5-16） 175

算法实现题5-10　排列宝石问题（习题5-16） 176

算法实现题5-11　重复拉丁矩阵问题（习题5-16） 179

算法实现题5-12　罗密欧与朱丽叶的迷宫问题 181

算法实现题5-13　工作分配问题（习题5-18） 183

算法实现题5-14　独立钻石跳棋问题（习题5-19） 184

算法实现题5-15　智力拼图问题（习题5-20） 191

算法实现题5-16　布线问题（习题5-21） 198

算法实现题5-17　最佳调度问题（习题5-22） 200

算法实现题5-18　无优先级运算问题（习题5-23） 201

算法实现题5-19　世界名画陈列馆问题（习题5-25） 203

算法实现题5-20　世界名画陈列馆问题（不重复监视）（习题5-26） 207

算法实现题5-21　部落卫队问题（习题5-6） 209

算法实现题5-22　虫蚀算式问题 211

算法实现题5-23　完备环序列问题 214

算法实现题5-24　离散01串问题 217

算法实现题5-25　喷漆机器人问题 218

算法实现题5-26　n2-1谜问题 221

第6章　分支限界法 229

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

习题6 2　用最大堆存储活结点的优先队列式分支限界法 231

习题6-3　团顶点数的上界 234

习题6-4 团顶点数改进的上界 235

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

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

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

算法实现题6-1 最小长度电路板排列问题一（习题6-8） 241

算法实现题6-2　最小长度电路板排列问题二（习题6-9） 244

算法实现题6-3　最小权顶点覆盖问题（习题6-10） 247

算法实现题6-4　无向图的最大割问题（习题6-11） 250

算法实现题6-5　最小重量机器设计问题（习题6-12） 253

算法实现题6-6　运动员最佳匹配问题（习题6-13） 256

算法实现题6-7　n后问题（习题6-15） 259

算法实现题6-8　圆排列问题（习题6-16） 260

算法实现题6-9　布线问题（习题6-17） 263

算法实现题6-10　最佳调度问题（习题6-18） 265

算法实现题6-11 无优先级运算问题（习题6-19） 268

算法实现题6-12　世界名画陈列馆问题（习题6-21） 271

算法实现题6-13　骑士征途问题 274

算法实现题6-14　推箱子问题 275

算法实现题6-15　图形变换问题 281

算法实现题6-16　行列变换问题 284

算法实现题6-17　重排n2宫问题 285

算法实现题6-18　最长距离问题 290

第7章　概率算法 296

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

习题7-2　随机抽样算法 297

习题7-3　随机产生m个整数 297

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

习题7-5　生日问题 299

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

习题7-7　用数组模拟有序链表 300

习题7-8　O（n3/2）舍伍德型排序算法 300

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

习题7-11　整数因子分解算法 302

习题7-12　非蒙特卡罗算法的例子 302

习题7-13　重复3次的蒙特卡罗算法 303

习题7-14　集合随机元素算法 304

习题7-15 由蒙特卡罗算法构造拉斯维加斯算法 305

习题7-16　产生素数算法 306

习题7-18　矩阵方程问题 306

算法实现题7-1　模平方根问题（习题7-10） 307

算法实现题7-2　集合相等问题（习题7-17） 309

算法实现题7-3　逆矩阵问题（习题7-19） 309

算法实现题7-4　多项式乘积问题（习题7-20） 310

算法实现题7-5　皇后控制问题 311

算法实现题7-6　3-SAT问题 314

算法实现题7-7　战车问题 315

算法实现题7-8　圆排列问题 317

算法实现题7-9　骑士控制问题 319

算法实现题7-10　骑士对攻问题 320

第8章　NP完全性理论 322

习题8-1 RAM和RASP程序 322

习题8-2 RAM和RASP程序的复杂性 322

习题8-3　计算nn的RAM程序 322

习题8-4 没有MULT和DIV指令的RAM程序 324

习题8-5 MULT和DIV指令的计算能力 324

习题8-6 RAM和RASP的空间复杂性 325

习题8-7　行列式的直线式程序 325

习题8-8　求和的3带图灵机 325

习题8-9　模拟RAM指令 325

习题8-10　计算22n的RAM程序 325

习题8-11　计算g（m,n）的程序 326

习题8-12 图灵机模拟RAM的时间上界 326

习题8-13 图的同构问题 326

习题8-14　哈密顿回路 327

习题8-15　P类语言的封闭性 327

习题8-16　NP类语言的封闭性 328

习题8-17　语言的2o（nk）时间判定算法 328

习题8-18 P？CO-NP 329

习题8-19 NP≠CO-NP 329

习题8-20　重言布尔表达式 329

习题8-21　关系？p的传递性 329

习题8-22　L？p？ 330

习题8-23　语言的完全性 330

习题8-24　？的CO-NP完全性 330

习题8-25 判定重言式的CO-NP完全性 331

习题8-26　析取范式的可满足性 331

习题8-27　2-SAT问题的线性时间算法 331

习题8-28　整数规划问题 332

习题8-29　划分问题 333

习题8-30　最长简单回路问题 334

第9章　近似算法 336

习题9-1　平面图着色问题的绝对近似算法 336

习题9-2　最优程序存储问题 336

习题9-4　树的最优顶点覆盖 337

习题9-5　顶点覆盖算法的性能比 339

习题9-6 团的常数性能比近似算法 339

习题9-9　售货员问题的常数性能比近似算法 340

习题9-10　瓶颈旅行售货员问题 340

习题9-11　最优旅行售货员回路不自相交 342

习题9-14　集合覆盖问题的实例 342

习题9-16　多机调度问题的近似算法 343

习题9-17　LPT算法的最坏情况实例 345

习题9-18　多机调度问题的多项式时间近似算法 345

算法实现题9-1　旅行售货员问题的近似算法（习题9-9） 346

算法实现题9-2　可满足问题的近似算法（习题9-20） 348

算法实现题9-3　最大可满足问题的近似算法（习题9-21） 349

算法实现题9-4　子集和问题的近似算法（习题9-15） 351

算法实现题9-5 子集和问题的完全多项式时间近似算法 352

算法实现题9-6　实现算法greedySetCover（习题9-13） 352

算法实现题9-7　装箱问题的近似算法First Fit（习题9-19） 356

算法实现题9-8　装箱问题的近似算法Best Fit（习题9-19） 358

算法实现题9-9 装箱问题的近似算法First Fit Decreasing（习题9-19） 360

算法实现题9-10 装箱问题的近似算法Best Fit Decreasing（习题9-19） 361

算法实现题9-11　装箱问题的近似算法Next Fit 361

第10章　算法优化策略 365

习题10-1　算法obst的正确性 365

习题10-2　矩阵连乘问题的O（n2）时间算法 365

习题10-6　货物储运问题的费用 371

习题10-7　Garsia算法 371

算法实现题10-1　货物储运问题（习题10-3） 374

算法实现题10-2　石子合并问题（习题10-4） 374

算法实现题10-3　最大运输费用货物储运问题（习题10-5） 375

算法实现题10-4　五边形问题 377

算法实现题10-5 区间图最短路问题（习题10-8） 381

算法实现题10-6 圆弧区间最短路问题（习题10-9） 381

算法实现题10-7　双机调度问题（习题10-10） 382

算法实现题10-8　离线最小值问题（习题10-11） 390

算法实现题10-9　最近公共祖先问题（习题10-12） 393

算法实现题10-10　达尔文芯片问题 395

算法实现题10-11　多柱Hanoi塔问题 397

算法实现题10-12　线性时间Huffman算法 400

算法实现题10-13　单机调度问题 402

算法实现题10-14　最大费用单机调度问题 405

算法实现题10-15　飞机加油问题 408

第11章　在线算法设计 410

习题11-1　在线算法LFU的竞争性 410

习题11-4　多读写头磁盘问题的在线算法 410

习题11-6　带权页调度问题 410

算法实现题11-1　最优页调度问题（习题11-2） 411

算法实现题11-2　在线LRU页调度（习题11-3） 414

算法实现题11-3　k服务问题（习题11-5） 416