算法设计与分析习题解答

第1章 算法引论

习题1-1 实参交换

习题1-2 方法头签名

习题1-3 数组排序判定

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

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

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

习题1-7 算法效率

习题1-8 硬件效率

习题1-9 函数渐近阶

习题1-10 n!的阶

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

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

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

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

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

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

第2章 递归与分治策略

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

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

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

习题2-4 大整数乘法的O（nm,log（3/2））算法

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

习题2-6 矩阵乘法

习题2-7 多项式乘积

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

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

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

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

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

习题2-13 √n段合并排序算法

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

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

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

习题2-17 整数集合排序

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

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

习题2-20 随机化算法

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

习题2-22 随机排列算法

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

习题2-24 用栈模拟递归

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

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

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

习题2-28 X和y的中位数

习题2-29 网络开关设计

习题2-30 带权中位数问题

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

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

算法实现题2-1 输油管道问题

算法实现题2-2 众数问题

算法实现题2-3 邮局选址问题

算法实现题2-4 马的Hamilton周游路线问题

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

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

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

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

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

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

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

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

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

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

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

……

第3章 动态规划

第4章 贪心算法

第5章 回溯法

第6章 分支限界法

第7章 概率算法

第8章 NP完全性理论

第9章 近似算法

第10章 算法优化策略

第11章 在线算法设计

本书是清华大学出版社出版的普通高等教育“十一五”国家级规划教材《算法设计与分析（第3版）》(主教材)配套的辅助教材，对《算法设计与分析（第3版）》一书中的全部习题做了详尽的解答。本书内容是对《算法设计与分析（第3版）》的较深入的扩展，许多在主教材中无法讲述的、较深入的主题通过习题的形式展现出来。为了加强学生灵活运用算法设计策略解决实际问题的能力，本书将主教材中的许多习题改造成算法实现题，要求学生不仅设计出解决具体问题的算法，而且能够上机实现。作者的教学实践反映出这类算法实现题的教学效果非常好。作者还结合国家精品课程建设，进行了教材的立体化开发，包括主教材、辅助教材、实验与设计、电子课件和教学网站建设。本书内容丰富，观点新颖，理论联系实际。不仅可以用作高等学校计算机科学与技术学科各专业本科生和研究生学习计算机算法设计的辅助教材，而且也适合广大工程技术人员和自学读者学习参考。

本书是《算法设计与分析（第3版）》（ISBN: 9787302348641）配套的辅助教材，对主教材中的全部习题做了详尽的解答，并提供了应用实验型习题的全部测试数据。
本书的内容是对主教材深入的扩展，许多主教材中无法讲述的较深入的主题通过习题的形式展现出来。
为了加强学生灵活运用算法设计策略解决实际问题的能力，本书将主教材中的许多习题改造成算法实现题，要求学生不仅设计出解决具体问题的算法，而且能上机实现。教学实践反映这类算法实现题的教学效果非常好。
作者还结合国家精品课程建设，进行了教材的立体化开发，包括主教材、辅助教材、实验与设计、电子课件和教学网站建设。
本书内容丰富，观点新颖，理论联系实际。不仅可用作高等院校计算机科学与工程专业本科生和研究生学习计算机算法设计的辅教教材，而且也适合广大工程技术人员和自学读者学习参考。
本书是学习算法设计与分析的经典教材学习辅导用书，清华大学出版社配套开发了丰富的在线教学资源，可以在清华大学出版社的在线教学平台上进行练习与测试，实现教学互动、智能学习。另外配有主教材《算法设计与分析（第3版）》（ISBN: 9787302348641）。本书的PPT电子教案、配套的源代码等资源，可到清华大学出版社官网下载。
本教材可适用于国内大多数普通高校计算机及相关专业算法设计与分析课程教学的需要。从2004年8月本书第1版出版到2007年底，共重印了10余次，第2版已经重印了10余次，已经被国内一百余所大学的本科生和研究生选作教材。

相关推荐：
算法设计与分析（第3版）