高等学校数据结构课程系列教材算法设计与分析(第2版)学习与实验指导/李春葆
- ISBN:9787302501459
- 装帧:一般胶版纸
- 册数:暂无
- 重量:暂无
- 开本:其他
- 页数:256
- 出版时间:2017-02-01
- 条形码:9787302501459 ; 978-7-302-50145-9
本书特色
本书是《算法设计与分析》(第2版,李春葆等编著,清华大学出版社,以下简称为《教程》)的配套学习与实验指导书。全书分为3章,第1章为练习题及参考答案;第2章为上机实验题及参考答案;第3章为在线编程题及参考答案。 上机实验题共41题,在线编程题共49题,其中包含近几年国内外著名IT企业面试笔题(谷歌、微软、阿里巴巴、腾讯、网易等)和ACM竞赛题。所有题目均上机调试通过或者在相关在线编程环境中调试通过。
内容简介
本书是《算法设计与分析(第2版)》(李春葆等编著,清华大学出版社出版)的配套学习和上机实验指导书,给出了主教材中所有练习题、上机实验题和在线编程题的参考答案,通过研习有助于提高灵活运用算法设计策略解决实际问题的能力。书中列出了所有题目,自成一体,可以脱离主教材单独使用。 本书适合高等院校计算机及相关专业本科生及研究生使用。
目录
目录
第1章练习题及参考答案/
1.1第1章——概论/
1.1.1练习题/
1.1.2练习题参考答案/
1.2第2章——递归算法设计技术/
1.2.1练习题/
1.2.2练习题参考答案/
1.3第3章——分治法/
1.3.1练习题/
1.3.2练习题参考答案/
1.4第4章——蛮力法/
1.4.1练习题/
1.4.2练习题参考答案/
1.5第5章——回溯法/
1.5.1练习题/
1.5.2练习题参考答案/
1.6第6章——分枝限界法/
1.6.1练习题/
1.6.2练习题参考答案/
1.7第7章——贪心法/
1.7.1练习题/
1.7.2练习题参考答案/
1.8第8章——动态规划/
1.8.1练习题/
1.8.2练习题参考答案/
1.9第9章——图算法设计/
1.9.1练习题/
1.9.2练习题参考答案/
1.10第10章——计算几何/
1.10.1练习题/
1.10.2练习题参考答案/
1.11第11章——计算复杂性理论简介/
1.11.1练习题/
1.11.2练习题参考答案/
1.12第12章——概率算法和近似算法/
1.12.1练习题/
1.12.2练习题参考答案/
第2章上机实验题及参考答案/
2.1第1章——概论/
2.1.1实验1统计求*大、*小元素的平均比较次数/
2.1.2实验2求无序序列中第k小的元素/
2.1.3实验3出队第k个元素/
2.1.4实验4设计一种好的数据结构Ⅰ/
2.1.5实验5设计一种好的数据结构Ⅱ/
2.2第2章——递归算法设计技术/
2.2.1实验1逆置单链表/
2.2.2实验2判断两棵二叉树是否同构/
2.2.3实验3求二叉树中*大和的路径/
2.2.4实验4输出表达式树等价的中缀表达式/
2.2.5实验5求两个正整数x、y的*大公约数/
2.3第3章——分治法/
2.3.1实验1求解查找假币问题/
2.3.2实验2求解众数问题/
2.3.3实验3求解逆序数问题/
2.3.4实验4求解半数集问题/
2.3.5实验5求解一个整数数组划分为两个子数组问题/
2.4第4章——蛮力法/
2.4.1实验1求解n」问题/
2.4.2实验2求解钱币兑换问题/
2.4.3实验3求解环绕的区域问题/
2.4.4实验4求解钓鱼问题/
2.5第5章——回溯法/
2.5.1实验1求解查找假币问题/
2.5.2实验2求解填字游戏问题/
2.5.3实验3求解组合问题/
2.5.4实验4求解满足方程解问题/
2.6第6章——分枝限界法/
2.6.1实验1求解4皇后问题/
2.6.2实验2求解布线问题/
2.6.3实验3求解迷宫问题/
2.6.4实验4求解解救Amaze问题/
2.7第7章——贪心法/
2.7.1实验1求解一个序列中出现次数*多的元素问题/
2.7.2实验2求解删数问题/
2.7.3实验3求解汽车加油问题/
2.7.4实验4求解磁盘驱动调度问题/
2.7.5实验5求解仓库设置位置问题/
2.8第8章——动态规划/
2.8.1实验1求解矩阵*小路径和问题/
2.8.2实验2求解添加*少括号数问题/
2.8.3实验3求解买股票问题/
2.8.4实验4求解双核处理问题/
2.8.5实验5求解拆分集合为相等的子集合问题/
2.8.6实验6求解将集合部分元素拆分为两个元素和
相等且尽可能大的子集合问题/
2.9第9章——图算法设计/
2.9.1实验1求解自行车慢速比赛问题/
2.9.2实验2求解股票经纪人问题/
2.9.3实验3求解*大流*小费用问题/
2.10第10章——计算几何/
2.10.1实验1求解判断三角形类型问题/
2.10.2实验2求解凸多边形的直径问题/
2.11第11章——概率算法和近似算法/
第3章在线编程题及参考答案/
3.1第1章——概论/
3.1.1在线编程题1求解两种排序方法问题/
3.1.2在线编程题2求解删除公共字符问题/
3.1.3在线编程题3求解移动字符串问题/
3.1.4在线编程题4求解大整数相乘问题/
3.1.5在线编程题5求解旋转词问题/
3.1.6在线编程题6求解门禁系统问题/
3.1.7在线编程题7求解数字排序问题/
3.2第2章——递归算法设计技术/
3.2.1在线编程题1求解n阶螺旋矩阵问题/
3.2.2在线编程题2求解幸运数问题/
3.2.3在线编程题3求解回文序列问题/
3.2.4在线编程题4求解投骰子游戏问题/
3.3第3章——分治法/
3.3.1在线编程题1求解满足条件的元素对个数问题/
3.3.2在线编程题2求解查找*后一个小于等于指定数的元素问题/
3.3.3在线编程题3求解递增序列中与x*接近的元素问题/
3.3.4在线编程题4求解按“*多排序”到“*少排序”的顺序排列问题/
3.4第4章——蛮力法/
3.4.1在线编程题1求解一元三次方程问题/
3.4.2在线编程题2求解完数问题/
3.4.3在线编程题3求解好多鱼问题/
3.4.4在线编程题4求解推箱子游戏问题/
3.5第5章——回溯法/
3.5.1在线编程题1求解会议安排问题/
3.5.2在线编程题2求解*小机器重量设计问题Ⅰ/
3.5.3在线编程题3求解*小机器重量设计问题Ⅱ/
3.5.4在线编程题4求解密码问题/
3.5.5在线编程题5求解马走棋问题/
3.5.6在线编程题6求解*大团问题/
3.5.7在线编程题7求解幸运的袋子问题/
3.6第6章——分枝限界法/
3.6.1在线编程题1求解饥饿的小易问题/
3.6.2在线编程题2求解*小机器重量设计问题Ⅰ/
3.6.3在线编程题3求解*小机器重量设计问题Ⅱ/
3.6.4在线编程题4求解*少翻译个数问题/
3.7第7章——贪心法/
3.7.1在线编程题1求解*大乘积问题/
3.7.2在线编程题2求解区间覆盖问题/
3.7.3在线编程题3求解Wooden Sticks(POJ 1230)问题/
3.7.4在线编程题4求解奖学金问题/
3.7.5在线编程题5求解赶作业问题/
3.8第8章——动态规划/
3.8.1在线编程题1求解公路上任意两点的*近距离问题/
3.8.2在线编程题2求解袋鼠过河问题/
3.8.3在线编程题3求解数字和为sum的方法数问题/
3.8.4在线编程题4求解人类基因功能问题/
3.8.5在线编程题5求解分饼干问题/
3.8.6在线编程题6求解堆砖块问题/
3.8.7在线编程题7求解小易喜欢的数列问题/
3.8.8在线编程题8求解石子合并问题/
3.8.9在线编程题9求解相邻比特数问题/
3.8.10在线编程题10求解周年庆祝会问题/
3.9第9章——图算法设计/
3.9.1在线编程题1求解全省畅通工程的*低成本问题/
3.9.2在线编程题2求解城市的*短距离问题/
3.9.3在线编程题3求解小人移动*小费用问题/
3.10第10章——计算几何/
3.10.1在线编程题1求解两个多边形公共部分的面积问题/
3.10.2在线编程题2求解*大三角形问题/
3.11第12章——概率算法和近似算法/
节选
第1章练习题及参考答案1.1第1章——概论1.1.1练习题1. 下列关于算法的说法中正确的有()个。Ⅰ. 求解某一类问题的算法是唯一的Ⅱ. 算法必须在有限步操作之后停止Ⅲ. 算法的每一步操作必须是明确的,不能有歧义或含义模糊Ⅳ. 算法执行后一定产生确定的结果A. 1B. 2C. 3D. 42. T(n)表示当输入规模为n时的算法效率,以下算法中效率*优的是()。A. T(n)= T(n-1)+1,T(1)=1B. T(n)= 2n2C. T(n)= T(n/2)+1,T(1)=1D. T(n)=3nlog2n3. 什么是算法?算法有哪些特性?4. 判断一个大于2的正整数n是否为素数的方法有多种,给出两种算法,说明其中一种算法更好的理由。5. 证明以下关系成立: (1) 10n2-2n=θ(n2)(2) 2n+1=θ(2n)6. 证明O(f(n))+O(g(n))=O(max{f(n),g(n)})。7. 有一个含n(n>2)个整数的数组a,判断其中是否存在出现次数超过所有元素一半的元素。8. 一个字符串采用string对象存储,设计一个算法判断该字符串是否为回文。9. 有一个整数序列,设计一个算法判断其中是否存在两个元素的和恰好等于给定的整数k。10. 有两个整数序列,每个整数序列中的所有元素均不相同,设计一个算法求它们的公共元素,要求不使用STL的集合算法。11. 正整数n(n>1)可以写成质数的乘积形式,称为整数的质因数分解。例如,12=2×2×3,18=2×3×3,11=11。设计一个算法求n这样分解后各个质因数出现的次数,采用vector向量存放结果。12. 有一个整数序列,所有元素均不相同,设计一个算法求相差*小的元素对的个数。例如序列4,1,2,3的相差*小的元素对的个数是3,其元素对是(1,2)、(2,3)、(3,4)。13. 有一个map容器,其中已经存放了较多元素,设计一个算法求出其中重复的value并且返回重复value的个数。14. 重新做第10题,采用map容器存放*终结果。15. 假设有一个含n(n>1)个元素的stack栈容器st,设计一个算法出栈从栈顶到栈底的第k(1≤k≤n)个元素,其他栈元素不变。1.1.2练习题参考答案1. 答: 由于算法具有有穷性、确定性和输出性,所以Ⅱ、Ⅲ、Ⅳ正确,而解决某一类问题的算法不一定是唯一的。答案为C。2. 答: 选项A的时间复杂度为O(n),选项B的时间复杂度为O(n2),选项C的时间复杂度为O(log2n),选项D的时间复杂度为O(nlog2n)。答案为C。3. 答: 算法是求解问题的一系列计算步骤。算法具有有限性、确定性、可行性、输入性和输出性5个重要特征。
作者简介
李春葆,武汉大学计算机学院教授。主要研究方向为数据挖掘和算法设计,先后主持和参加多个大型研究项目。主要为本科生讲授数据结构(15年以上)和软件工程等课程,为研究生讲授软件开发新技术、数据仓库与数据挖掘等课程,并出版十多部精品著作。
-
落洼物语
¥8.4¥28.0 -
当代中国政府与政治(新编21世纪公共管理系列教材)
¥33.6¥48.0 -
中国当代文学名篇选读
¥17.0¥53.0 -
中医基础理论
¥50.7¥59.0 -
长征记忆(八品)
¥9.5¥45.0 -
中医基础理论【中医 针灸专业用】
¥18.0¥25.0 -
北大人文课(平装)
¥12.2¥45.0 -
世界现代设计史-[第二版]
¥63.6¥120.0 -
宪法-第二版
¥20.3¥29.0 -
先进防伪技术
¥81.3¥98.0 -
当代中国政府与政治 第二版
¥57.8¥68.0 -
企业法务教程
¥34.8¥49.0 -
习近平新时代中国特色社会主义思想概论
¥18.2¥26.0 -
毛泽东思想和中国特色社会主义理论体系概论(2021年版)
¥8.5¥25.0 -
办公室工作实务(第4版)/黄海
¥27.8¥48.0 -
计算机操作系统教程(第4版)(清华大学计算机系列教材)
¥31.9¥49.0 -
习近平总书记教育重要论述讲义
¥13.3¥35.0 -
无人机概论
¥37.2¥59.0 -
(平装)北大必修课:北大口才课
¥18.2¥45.0 -
海商法-第四版
¥30.2¥48.0