计算机算法设计与分析第5版习题及答案电子版pdf免费版|百度网盘下载
编者的话:计算机算法设计与分析的答案和练习
十二五普通高等教育本科国家规划教材、国家精品课程教材、计算机算法设计与分析第5版习题答案pdf电子版,可结合计算机算法设计与分析(第5版)一起用来巩固知识和实践。
计算机算法设计与分析第5版习题及答案电子版PDF预览
简介
本书是“十二五”普通高等教育本科生国家规划教材《计算机算法设计与分析(第五版)》的补充教材和国家级精品课程教材。问题和算法实施问题为解决方案或解决问题的想法提供提示。为了提高学生灵活运用算法设计策略解决实际问题的能力,本书还将主课本中的许多习题转化为算法实现问题,要求学生设计求解算法并在计算机上实现。本书教材包括算法实现题、测试数据及各章答案,可在华信教育资源网免费下载。本书内容丰富,理论联系实际。可作为高校计算机科学与技术、软件工程、信息安全、信息与计算科学等专业本科生和研究生学习计算机算法设计的辅助教材。参考书。
作者介绍
王晓东,男,1957年出生,山东籍,中共中央委员,现任福建工业大学副校长,教授、博士生导师,福建省计算机学会理事长. 2007年8月起先后担任福州大学计算机系主任、数学与计算机学院院长、泉州师范学院副院长。主要课程:算法与数据结构、算法设计与分析,文献阅读和选题报告。
目录
目录
第1章算法概述1
算法分析第11题
1-1 函数的渐近表达式 1
1-2O(1)和O(2)的区别1
1-3 按渐近顺序排列表达式 1
1-4 算法效率1
1-5 硬件效率1
1-6函数渐近阶2
1-7n 的第 2 次!
1-83n+1 问题 2
计算时间复杂度在1-9的平均情况下为2
算法实现问题13
1-1统计题3
1-2 词典学题4
1-3 直到除数问题 4
1-4 金币阵列问题6
1-5最大间隙问题8
第2章递归和分而治之的策略11
算法分析题211
2-1 证明河内铁塔问题的递归和非递归算法其实是一回事11
2-2 判断这7种算法的正确性 12
2-3 重写二分查找算法15
2-4大整数乘法的O(nmlog(3/2))算法16
n/3 位整数 16 的 2-55 次乘法
2-6矩阵乘法18
2-7多项式积18
2-8O(1)空间子阵转置算法19
2-9O(1) 空间合并算法21
2-10段合并排序算法27
2-11 自然归并排序算法28
2-12 第k个小元问题的计算时间下界29
2-13 非递增快速排序算法31
2-14 构造格雷码的分治算法31
2-15 网球循环赛赛程 32
2-16二叉树T35的前序、中序和后序序列
算法实现问题236
2-1 模式问题36
2-2匹马汉密尔顿旅游路线问题37
2-3 半套题 44
2-4半单集第46题
2-5 重复元素的排列问题 46
2-6排列的词典编纂问题47
2-7 设置分区问题49
2-8 设置分区问题50
2-9 双色河内塔第 51 期
2-10 标准二维表题52
2-11 整数分解问题 53
第 3 章动态规划 54
算法分析题354
3-1最长的单调递增子序列54
3-2个最长单调递增子序列54的O(nlogn)算法
3-3整数线性规划问题55
3-4 2D 0-1 背包问题56
3-5阿克曼函数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-16 最优时间表问题89
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-3 斐波那契数列的霍夫曼码 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-13 非单位时间任务调度问题126
4-14 多元霍夫曼编码问题 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
6-10 电路板排列问题199的队列分支定界法
算法实现问题 6201
6-1 最小长度电路板布置问题201
6-2 最小权重顶点覆盖问题 203
6-3无向图206的最大割问题
6-4 最小重量机器设计问题 209
6-5 运动员最佳匹配题 212
6-6n 后的问题 214
6-7 接线问题216
6-8 最优调度问题218
6-9 无优先操作问题220
6-10世界名画展厅第223题
6-11 子集空间树问题226
6-12 排列空间树第229题
6-13 通用解空间232的队列式分支定界法
6-14 子集空间树问题236
6-15 排列空间树问题241
6-16 通用解空间246的优先队列分支定界法
6-17推箱子问题250
第 7 章概率算法 256
算法分析题7256
7-1 模拟正态分布随机变量 256
7-2随机抽样算法256
7-3随机生成m个整数257
7-4 集大小 258 的概率算法
7-5 生日问题 258
7-6 简单验证问题 259 的拉斯维加斯算法
7-7 使用数组模拟有序链表260
7-8O(n3/2) 舍伍德排序算法 260
7-9n 260后解的存在
7-10 整数分解算法262
7-11 非蒙特卡洛算法示例 262
7-12重复3次蒙特卡洛算法263
7-13 设置随机元素算法263
7-14 从蒙特卡洛算法构造拉斯维加斯算法265
7-15 生成素数算法265
7-16 矩阵方程第265题
算法实现题7266
7-1 模平方根问题 266
7-2素数测试题268
7-3 设置相等问题269
7-4 逆矩阵问题 269
7-5 多项式积问题 270
7-6 皇后控制问题 270
7-73-SAT 问题 274
7-8 坦克第 275 期
第 8 章线性规划和网络流 278
算法分析题8278
8-1 线性规划的无界可行域示例 278
8-2 单源最短路径和线性规划 278
8-3 网络最大流量和线性规划279
8-4 最小成本流和线性规划 279
8-5 运输计划问题 279
8-6 单纯形算法 280
8-7 边缘连通性问题281
8-8有向无环网络最大流量为281
8-9无向网络最大流量为281
8-10 最大流更新算法 282
8-11 混合图欧拉电路问题 282
8-12单源最短路径和最小成本流282
8-13中国邮政问题282
算法实现题 8283
8-1 Pilot Matching Program Question 283
8-2 太空飞行计划问题 284
8-3 最小路径覆盖问题 285
8-4 魔法球第286题
8-5圆桌问题287
8-6最长递增子序列问题287
8-7题库第290题
8-8 机器人路径规划问题291
8-9平方数题294
8-10 餐巾项目题 298
8-11 航线问题 299
8-12 软件补丁问题 300
8-13 星际转移问题301
8-14海岛救援问题302
8-15汽车加油问题304
8-16 数字梯形问题 307
8-17 运输问题 311
8-18 作业作业题 314
8-19 负载平衡问题 315
8-20最长k可重复区间集问题317
8-21最长k可重复段集问题319
第 9 章字符串和序列的算法 323
算法分析题9323
9-1 简单子串搜索算法最坏情况复杂度 323
9-2后缀重叠问题323
9-3 改进前缀功能323
9-4 KMP算法324确定所有匹配位置
9-5 特殊情况下简单子串搜索算法的改进325
9-6 简单子串搜索算法的平均性能是325
9-7 带间隙字符的模式搜索 326
9-8 级联前缀函数 326
9-9串循环旋转327
9-10 失效函数属性 327
9-11 输出函数属性328
9-12后缀数组类328
9-13 最长公共扩展查询 329
9-14 最长公共扩展属性 332
9-15 后缀数组属性 333
9-16后缀数组搜索334
9-17后缀数组快速搜索335
算法实现题9338
9-1 安全基因序列问题 338
9-2最长重复子串问题342
9-3最长回文子串问题343
9-4 相似基因序列问题344
9-5 计算机病毒问题 345
9-6 子串包含约束 347 的最长公共子序列问题
9-7 具有多个子串排除约束的最长公共子序列问题 349
参考 351
前言阅读
前言
在他们关于计算机科学教育的论述中,一些著名的计算机科学家认为计算机科学是一种创造性思维活动,教育必须以设计为导向。 《计算机算法设计与分析》是一门以设计为导向、以计算机科学为核心的教育课程。通过对计算机算法系统的学习和研究,了解和掌握算法设计的主要方法,培养正确分析算法计算复杂度的能力,为独立设计算法和计算复杂度打下扎实的理论基础算法分析。从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者是非常重要和必不可少的。本课程结合我国高等教育现状,跟踪国际计算机科学技术发展水平,更新教学内容和教学方法,以算法设计策略为知识单元,精心选材,深入掌握,系统化和可用性。专为满足高校本科生教学时长和知识结构的要求而设计。
本书是国家“十二五”期间普通高等教育本科生规划教材《计算机算法设计与分析(第五版)》(ISBN 978-7-121-34439-8)的补充教材)。 《计算机算法设计与分析(第5版)》一书中的所有习题都有完整的解答,旨在让老师教得更轻松,学生学得更轻松。为便于对比阅读,本书章节顺序与《计算机算法设计与分析(第5版)》章节顺序一致,一一对应。
本书的内容是对《计算机算法设计与分析(第5版)》的深入延伸,很多课本无法涵盖的深入话题以习题的形式呈现。为加强学生灵活运用算法设计策略解决实际问题的能力,本书将主课本中的许多习题转化为算法实现问题,要求学生不仅设计算法解决具体问题,而且在一台电脑。笔者的教学实践反映,这类算法实现问题的教学效果非常好。笔者还结合国家级精品课程建设建立了“算法设计与分析”教学网站。全国精品资源共享课程地址:http://www.icourses.cn/sCourse/course_2535.html。欢迎读者访问作者的教学网站,提出宝贵意见。
在本书编写过程中,福州大学计算机与信息工程“211工程”重点学科实验室为本书的编写提供了优良的设备和工作环境。电子工业出版社负责本书编辑出版的全体同仁为本书的出版付出了很多心血。他们兢兢业业、一丝不苟的工作精神,保证了本书的出版质量。在此,向关心和支持本书编写的各位表示衷心的感谢!