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

　　本书是《算法设计与分析（第4版）》配套辅助教材。本书将结合原教材的内容，进一步讨论和讲解原教材中的重点和难点，问题分析，求解思路和方法，为读者深刻体会问题求解的核心思想提供帮助。由于原教材的内容有一定的深度和难度，读者在学习和解答习题过程中会遇到一定的困难，因此本书选择了原教材的一些典型的习题和难题，给出详细的解答和分析。 本书内容丰富，观点新颖，理论联系实际。不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材，而且也适合广大工程技术人员和自学读者学习参考。

　　王晓东，教授，博士生导师。近年来正式出版学术著作11部。近年在国内外学术刊物上发表学术论文60多篇。参加多项科研项目并获奖。其中获国家科技进步二等奖一项，水电部科技进步一等奖一项，福建省科技进步三等奖一项，省水电厅科技进步一等奖一项。

目录CONTENTS第1章算法引论1
习题11实际参数交换1
习题12方法头签名1
习题13数组排序判定1
习题14函数的渐近表达式2
习题15O(1)和O(2)的区别2
习题16按渐近阶排列表达式2
习题17算法效率2
习题18硬件效率3
习题19函数渐近阶3
习题110n!的阶3
习题111平均情况下的计算时间复杂性4
算法实现题11统计数字问题4
算法实现题12字典序问题5
算法实现题13最多约数问题6
算法实现题14金币阵列问题7
算法实现题15最大间隙问题10
第2章递归与分治策略12
习题21Hanoi 塔问题的非递归算法12
习题227个二分搜索算法13
习题23改写二分搜索算法16
习题24大整数乘法的O(nmlog(3/2))算法16
习题255次n/3位整数的乘法17
习题26矩阵乘法19
习题27多项式乘积19
习题28不动点问题的O(logn)时间算法19
习题29主元素问题的线性时间算法19目录算法设计与分析习题解答（第4版）习题210无序集主元素问题的线性时间算法20
习题211O(1)空间子数组换位算法20
习题212O(1)空间合并算法22
习题213n段合并排序算法28
习题214自然合并排序算法29
习题215最大值和最小值问题的最优算法31
习题216最大值和次大值问题的最优算法31
习题217整数集合排序32
习题218第k小元素问题的计算时间下界32
习题219非增序快速排序算法33
习题220随机化算法34
习题221随机化快速排序算法34
习题222随机排列算法34
习题223算法qSort中的尾递归34
习题224用栈模拟递归34
习题225算法select中的元素划分35
习题226O(nlogn)时间快速排序算法35
习题227最接近中位数的k个数36
习题228X和Y的中位数36
习题229网络开关设计36
习题230带权中位数问题37
习题231构造Gray码的分治算法39
习题232网球循环赛日程表40
算法实现题21输油管道问题44
算法实现题22众数问题44
算法实现题23邮局选址问题45
算法实现题24马的Hamilton周游路线问题46
算法实现题25半数集问题54
算法实现题26半数单集问题55
算法实现题27士兵站队问题56
算法实现题28有重复元素的排列问题57
算法实现题29排列的字典序问题58
算法实现题210集合划分问题（一）60
算法实现题211集合划分问题（二）61
算法实现题212双色Hanoi塔问题62
算法实现题213标准二维表问题64
算法实现题214整数因子分解问题64
算法实现题215有向直线2中值问题65
第3章动态规划68
习题31最长单调递增子序列68
习题32最长单调递增子序列的O(nlogn)算法69
习题33漂亮打印70
习题34整数线性规划问题71
习题35二维背包问题71
习题36Ackermann函数72
算法实现题31独立任务最优调度问题74
算法实现题32最少硬币问题76
算法实现题33序关系计数问题77
算法实现题34多重幂计数问题77
算法实现题35最小m段和问题78
算法实现题36石子合并问题79
算法实现题37数字三角形问题81
算法实现题38乘法表问题82
算法实现题39租用游艇问题83
算法实现题310汽车加油行驶问题84
算法实现题311圈乘运算问题85
算法实现题312最少费用购物91
算法实现题313最大长方体问题93
算法实现题314正则表达式匹配问题94
算法实现题315双调旅行售货员问题98
算法实现题316最大k乘积问题100
第4章贪心算法102
习题41活动安排问题的贪心选择102
习题42背包问题的贪心选择性质102
习题43特殊的01背包问题103
习题44程序最优存储问题103
习题45最优装载问题的贪心算法103
习题46Fibonacci序列的Huffman编码104
习题47最优前缀码的编码序列104
习题48任务集独立性问题104
习题49矩阵拟阵104
习题410最小权最大独立子集拟阵105
习题411整数边权Prim算法105
习题412最大权最小生成树105
习题413最短路径的负边权105
习题414整数边权Dijkstra算法106
算法实现题41会场安排问题106
算法实现题42最优合并问题108
算法实现题43磁带最优存储问题108
算法实现题44磁盘文件最优存储问题109
算法实现题45程序存储问题110
算法实现题46最优服务次序问题111
算法实现题47多处最优服务次序问题112
算法实现题48d森林问题113
算法实现题49汽车加油问题114
算法实现题410区间覆盖问题115
算法实现题411硬币找钱问题116
算法实现题412删数问题116
算法实现题413数列极差问题117
算法实现题414嵌套箱问题118
算法实现题415套汇问题119
算法实现题416信号增强装置问题120
算法实现题417磁带最大利用率问题121
算法实现题418非单位时间任务安排问题122
算法实现题419多元Huffman编码问题124
算法实现题420多元Huffman编码变形125
算法实现题421区间相交问题127
算法实现题422任务时间表问题128
第5章回溯法129
习题5\\|1装载问题改进回溯法（一）129
习题5\\|2装载问题改进回溯法（二）130
习题5\\|301背包问题的最优解130
习题5\\|4最大团问题的迭代回溯法131
习题5\\|5旅行售货员问题的费用上界132
习题5\\|6旅行售货员问题的上界函数134
算法实现题5\\|1子集和问题134
算法实现题5\\|2最小长度电路板排列问题135
算法实现题5\\|3最小重量机器设计问题138
算法实现题5\\|4运动员最佳匹配问题139
算法实现题5\\|5无分隔符字典问题140
算法实现题5\\|6无和集问题142
算法实现题5\\|7n色方柱问题143
算法实现题5\\|8整数变换问题147
算法实现题5\\|9拉丁矩阵问题148
算法实现题5\\|10排列宝石问题150
算法实现题5\\|11重复拉丁矩阵问题152
算法实现题5\\|12罗密欧与朱丽叶的迷宫问题154
算法实现题5\\|13工作分配问题156
算法实现题5\\|14独立钻石跳棋问题157
算法实现题5\\|15智力拼图问题163
算法实现题5\\|16布线问题170
算法实现题5\\|17最佳调度问题171
算法实现题5\\|18无优先级运算问题172
算法实现题5\\|19世界名画陈列馆问题174
算法实现题5\\|20世界名画陈列馆问题（不重复监视）177
算法实现题5\\|21部落卫队问题179
算法实现题5\\|22虫蚀算式问题181
算法实现题5\\|23完备环序列问题184
算法实现题5\\|24离散01串问题186
算法实现题5\\|25喷漆机器人问题188
算法实现题5\\|26n2-1谜问题190
第6章分支限界法197
习题6\\|101背包问题的栈式分支限界法197
习题6\\|2用最大堆存储活结点的优先队列式分支限界法199
习题6\\|3团顶点数的上界202
习题6\\|4团顶点数改进的上界202
习题6\\|5修改解旅行售货员问题的分支限界法202
习题6\\|6解旅行售货员问题的分支限界法中保存已产生的排列树204
习题6\\|7电路板排列问题的队列式分支限界法206
算法实现题6\\|1最小长度电路板排列问题(一)207
算法实现题6\\|2最小长度电路板排列问题(二)210
算法实现题6\\|3最小权顶点覆盖问题213
算法实现题6\\|4无向图的最大割问题216
算法实现题6\\|5最小重量机器设计问题219
算法实现题6\\|6运动员最佳匹配问题221
算法实现题6\\|7n后问题223
算法实现题6\\|8圆排列问题225
算法实现题6\\|9布线问题227
算法实现题6\\|10最佳调度问题229
算法实现题6\\|11无优先级运算问题232
算法实现题6\\|12世界名画陈列馆问题234
算法实现题6\\|13骑士征途问题237
算法实现题6\\|14推箱子问题238
算法实现题6\\|15图形变换问题243
算法实现题6\\|16行列变换问题246
算法实现题6\\|17重排n2宫问题247
算法实现题6\\|18最长距离问题251
第7章概率算法257
习题71模拟正态分布随机变量257
习题72随机抽样算法258
习题73随机产生m个整数258
习题74集合大小的概率算法259
习题75生日问题259
习题76易验证问题的拉斯维加斯算法260
习题77用数组模拟有序链表261
习题78O(n3/2)舍伍德型排序算法261
习题79n后问题解的存在性261
习题710整数因子分解算法262
习题711非蒙特卡罗算法的例子263
习题712重复3次的蒙特卡罗算法264
习题713集合随机元素算法264
习题714由蒙特卡罗算法构造拉斯维加斯算法265
习题715产生素数算法266
习题716矩阵方程问题266
算法实现题71模平方根问题267
算法实现题72集合相等问题268
算法实现题73逆矩阵问题269
算法实现题74多项式乘积问题270
算法实现题75皇后控制问题270
算法实现题763SAT问题273
算法实现题77战车问题274
算法实现题78圆排列问题276
算法实现题79骑士控制问题277
算法实现题710骑士对攻问题278
第8章NP完全性理论与近似算法280
习题81析取范式的可满足性280
习题822SAT问题的线性时间算法280
习题83整数规划问题281
习题84划分问题282
习题85最长简单回路问题283
习题86平面图着色问题的绝对近似算法283
习题87最优程序存储问题284
习题88树的最优顶点覆盖285
习题89顶点覆盖算法的性能比286
习题810团的常数性能比近似算法286
习题811售货员问题的常数性能比近似算法287
习题812瓶颈旅行售货员问题287
习题813最优旅行售货员回路不自相交288
习题814集合覆盖问题的实例289
习题815多机调度问题的近似算法290
习题816LPT算法的最坏情况实例291
习题817多机调度问题的多项式时间近似算法292
算法实现题81旅行售货员问题的近似算法292
算法实现题82可满足问题的近似算法294
算法实现题83最大可满足问题的近似算法295
算法实现题84子集和问题的近似算法297
算法实现题85子集和问题的完全多项式时间近似算法297
算法实现题86实现算法greedySetCover298
算法实现题87装箱问题的近似算法First Fit301
算法实现题88装箱问题的近似算法Best Fit303
算法实现题89装箱问题的近似算法First Fit Decreasing305
算法实现题810装箱问题的近似算法Best Fit Decreasing305
算法实现题811装箱问题的近似算法Next Fit306
第9章串与序列的算法309
习题91简单子串搜索算法最坏情况复杂性309
习题92后缀重叠问题309
习题93改进前缀函数310
习题94确定所有匹配位置的KMP算法311
习题95特殊情况下简单子串搜索算法的改进311
习题96简单子串搜索算法的平均性能312
习题97带间隙字符的模式串搜索312
习题98串接的前缀函数313
习题99串的循环旋转314
习题910失败函数性质314
习题911输出函数性质315
习题912后缀数组类315
习题913最长公共扩展查询316
习题914最长公共扩展性质320
习题915后缀数组性质320
习题916后缀数组搜索321
习题917后缀数组快速搜索322
算法实现题91安全基因序列问题326
算法实现题92最长重复子串问题328
算法实现题93最长回文子串问题329
算法实现题94相似基因序列性问题331
算法实现题95计算机病毒问题332
算法实现题96带有子串包含约束的最长公共子序列问题335
算法实现题97多子串排斥约束的最长公共子序列问题336
第10章算法优化策略338
习题101算法obst的正确性338
习题102矩阵连乘问题的O(n2)时间算法338
习题103货物储运问题的费用343
习题104Garsia算法343
算法实现题101货物储运问题346
算法实现题102石子合并问题346
算法实现题103最大运输费用货物储运问题347
算法实现题104五边形问题349
算法实现题105区间图最短路问题352
算法实现题106圆弧区间最短路问题353
算法实现题107双机调度问题353
算法实现题108离线最小值问题361
算法实现题109最近公共祖先问题363
算法实现题1010达尔文芯片问题365
算法实现题1011多柱Hanoi塔问题367
算法实现题1012线性时间Huffman算法370
算法实现题1013单机调度问题371
算法实现题1014最大费用单机调度问题374
算法实现题1015飞机加油问题377
第11章在线算法设计378
习题111在线算法LFU的竞争性378
习题112多读写头磁盘问题的在线算法378
习题113带权页调度问题378
算法实现题111最优页调度问题378
算法实现题112在线LRU页调度382
算法实现题113k服务问题383
参考文献388