《算法分析与设计》期末考试复习重点及答案解析

该资源是一份《算法设计与分析》的考试题目及答案，涵盖了算法设计、分析及其在实际问题中的应用，如流水作业调度、汉诺塔问题、动态规划等核心概念。 在这些题目中，我们可以看到以下几个关键知识点： 1. 动态规划算法：动态规划是一种解决最优化问题的有效方法，它通过将大问题分解为子问题来求解。题目中提到的Johnson法则在流水作业调度中应用的就是动态规划算法。动态规划的关键要素包括最优子结构（即一个最优解可以通过其子问题的最优解来构造）和重叠子问题（即在求解过程中会重复遇到相同的子问题）。 2. 汉诺塔问题：这是一个经典的递归问题，题目给出了Hanoi塔的图形表示以及递归算法的代码。正确的递归算法是选项B，其中`hanoi`函数通过递归地移动n-1个圆盘到辅助柱，然后移动最大的圆盘，最后再递归地将剩余的n-1个圆盘从辅助柱移动到目标柱。 3. 算法分析的记号：在算法复杂度分析中，`O`表示渐进上界，它描述了算法运行时间增长的上限；`Ω`表示渐进下界，描述了算法运行时间增长的下限；而`Θ`表示紧渐进界，表示算法运行时间的增长率精确地介于上下界之间。题目中还提到了非紧上界`O`和非紧下界`Ω`的概念。 4. 渐进记号的性质：题目中的选项A正确地阐述了渐进记号的性质，即如果`f(n)`是`g(n)`的渐进上界，`g(n)`是`h(n)`的渐进上界，那么`f(n)`也是`h(n)`的渐进上界。 5. 贪心算法：贪心算法在每一步都选择当前看起来最优的选择，以期望达到全局最优解。一个可以使用贪心算法求解的问题通常具备最优子结构和贪心选择性质，但不包含重叠子问题，因为贪心算法通常不回溯。 这份资源涵盖了动态规划、递归、算法分析以及贪心算法等基础且重要的算法理论知识，是学习和复习算法设计与分析的良好材料。理解并掌握这些知识点对于理解和解决问题至关重要，特别是在计算机科学和软件工程领域。