算法设计与分析考试重点：动态规划与回溯法

"这是一份关于算法设计与分析的考试题及答案，涵盖了填空题和综合题，涉及动态规划、回溯法、算法复杂性分析等核心概念。" 一、填空题 1. 算法的五个重要特性通常是：有穷性、确定性、可行性、输入和输出。这意味着算法必须在有限步骤内结束，每一步都有明确的定义，可以被执行，需要有输入，并产生预期的输出。 2. 算法的复杂性分为时间复杂性和空间复杂性。一个好的算法应尽可能地在时间和空间上都高效，即时间复杂度低且空间复杂度小。 3. 动态规划解决问题的特征是问题的子结构具有重叠性质，且最优解可以通过合并子问题的最优解得出。 4. 序列X和Y的一个最长公共子序列可能是{B, A, C, D}，具体取决于最长公共子序列的定义（是否要求连续）。 5. 回溯法解问题时，解空间应至少包含所有可能的解决方案。 6. 动态规划通过将问题分解成子问题，先求解子问题的最优解，然后构建原问题的最优解。 7. 以深度优先方式系统搜索问题解的算法称为深度优先搜索（DFS）。 8. 对于0-1背包问题，回溯算法的计算时间通常比动态规划算法要长，具体时间复杂度依赖于问题规模，而动态规划通常能提供线性或近似线性的计算时间。 9. 动态规划算法的两个基本要素是状态和决策，以及状态转移方程。 10. 二分搜索算法基于分治策略，通过不断将搜索区间减半来找到目标元素。 二、综合题 1. 设计动态规划算法的主要步骤包括：定义状态，确定状态转移方程，初始化边界条件，最后通过状态转移方程求解。 2. Johnson算法用于流水作业调度，其基本思想是通过调整作业的最早开始时间，使得每个作业在其最早开始时间下都能完成，从而达到最小化总体完工时间的目标。 3. 对于这个问题，可以使用贪心策略或者动态规划来求解。一种可能的最优调度方案是：首先在M2上运行作业3，接着在M1上运行作业1和2，最后在M2上运行作业4。最优值是所有作业完成时间的总和，即12+4+5+9=30。 4. 解空间树对于0/1背包问题的表示，需要列出所有可能的组合（0-1向量），然后根据价值和重量进行剪枝。最优值和最优解需要实际计算所有可能的组合来确定。 5. 这个问题似乎是询问如何构建X集合的二叉查找树，但由于没有具体数值，无法给出具体解答。一般而言，二叉查找树的构造会保证左子树所有元素小于根，右子树所有元素大于根，以此类推。 以上是对考试题目的解析，详细介绍了动态规划、回溯法、算法复杂性等相关知识点，以及如何应用这些方法解决具体问题。