算法设计与分析考试重点：动态规划、贪心、回溯与分支限界

"该文档是'算法设计与分析考试题目与答案.doc'，包含了多项选择题，涵盖了算法设计与分析的多个核心概念，如贪心算法、动态规划、Hanoi塔问题、算法分析中的渐进记号、回溯法、分支限界法等。" 在算法设计与分析领域，这些题目涉及了以下几个关键知识点： 1. **动态规划**：动态规划是一种解决最优化问题的方法，其基本要素包括最优子构造性质（即局部最优解能够推导出全局最优解）和重叠子问题（同一个子问题在不同阶段会被多次求解）。题目中提到的Johnson法则是动态规划的一种应用。 2. **贪心算法**：贪心算法是在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优。它依赖于最优子结构和贪心选择性质。题目中指出，能采用贪心算法求最优解的问题通常具备这两个性质。 3. **Hanoi塔问题**：这是一个经典的递归问题，目标是将所有盘子从一个柱子移动到另一个柱子，每次只能移动一个盘子，并且任何时候大盘子都不能位于小盘子之上。 4. **算法分析的渐进记号**：O表示渐进上界，表示算法运行时间的上限；Ω表示渐进下界，表示算法运行时间的下限；Θ表示紧渐进界，表示算法运行时间的精确界限。题目中还提到了非紧上界和非紧下界的概念。 5. **回溯法**：这是一种通过尝试所有可能的解决方案并逐步构建潜在解来解决问题的方法，当发现当前路径无法得到有效解时，会回退到之前的决策点，尝试其他路径。回溯法在解空间树中采用深度优先策略进行搜索。 6. **分支限界法**：与回溯法类似，也是搜索解空间树，但通常使用广度优先策略。分支限界法用于寻找全局最优解，而不是所有解。 7. **空间复杂性**：在算法分析中，空间复杂性衡量的是执行算法所需要的内存空间。题目中的k带图灵机的空间复杂性S(n)指的是处理特定长度输入时，在所有条带上使用的最大方格数。 这些题目涵盖了算法设计与分析的基础理论和应用，对于理解和掌握相关算法具有重要的价值。