本书是《算法设计与分析(第2版)》(李春葆等编著,清华大学出版社出版)的配套学习和上机实验指导书,给出了主教材中所有练习题、上机实验题和在线编程题的参考答案,通过研习有助于提高灵活运用算法设计策略解决实际问题的能力。书中列出了所有题目,自成一体,可以脱离主教材单独使用。
本书适合高等院校计算机及相关专业本科生及研究生使用。

第1章练习题及参考答案






1.1第1章——概论
1.1.1练习题

1. 下列关于算法的说法中正确的有()个。

Ⅰ. 求解某一类问题的算法是**的
Ⅱ. 算法必须在有限步操作之后停止
Ⅲ. 算法的每一步操作必须是明确的,不能有歧义或含义模糊
Ⅳ. 算法执行后一定产生确定的结果
A. 1B. 2C. 3D. 4
2. T(n)表示当输入规模为n时的算法效率,以下算法中效率*优的是()。
A. T(n)= T(n-1)+1,T(1)=1B. T(n)= 2n2
C. T(n)= T(n/2)+1,T(1)=1D. T(n)=3nlog2n
3. 什么是算法?算法有哪些特性?
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个重要特征。

目录

第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章——概率算法和近似算法/