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

"算法设计与分析的考试题目和答案，涉及算法基础概念、复杂性分析、动态规划、回溯法、0-1背包问题、二分搜索等核心知识点。" 一、填空题 1. 算法的五个重要特性是：可行性、确定性、有限性、输入和输出。这意味着算法必须能够被执行，每一步都有明确的定义，有开始和结束，并且需要接收输入并产生输出。 2. 算法的复杂性分为时间复杂性和空间复杂性。衡量算法好坏的标准通常是时间复杂性的渐进上界，即在最坏情况下的运行时间。 3. 动态规划算法求解问题的显著特征是问题的重叠子问题和最优子结构，即解决大问题的方法可以通过解决小问题的最优解组合得出。 4. 序列X和Y的一个最长公共子序列可能是"B,C,A,D"，具体取决于所采用的匹配策略。 5. 回溯法解问题时，解空间应至少包含所有可能的解或状态。 6. 动态规划通过将问题分解成子问题，先解决局部最优解，再构建全局最优解。这里的子问题通常指的是原问题的更小实例。 7. 深度优先搜索（DFS）是一种以深度优先方式系统搜索问题解的算法。 8. 回溯法解0-1背包问题的计算时间通常比动态规划算法高，因为回溯法可能需要尝试许多无效的路径。具体时间复杂性依赖于问题规模，而动态规划算法通常具有更好的时间效率。 9. 动态规划算法的两个基本要素是状态和决策，以及状态转移方程，它们描述了如何从一个状态转移到另一个状态以达到最优解。 10. 二分搜索算法是基于分治思想实现的，它将目标值与数组中间元素比较，缩小搜索范围，直至找到目标或确定目标不存在。 二、综合题 1. 设计动态规划算法的主要步骤包括：(1)识别和定义问题的状态；(2)确定状态转移方程，描述从一个状态到另一个状态的决策过程；(3)找出初始条件或边界条件；(4)构建并初始化状态表；(5)根据状态转移方程填充状态表，最后从最后一个状态反推得到最优解。 2. 流水作业调度问题的Johnson算法主要思想是首先找到一个最小的环，通过调整这个环中作业的顺序，使得每个作业在每个机器上的总加工时间减少，最终达到全局最优。 3. 对于4个作业的最优调度问题，可以使用贪心策略或者动态规划方法，目标是最小化总加工时间。具体解需要计算每个作业在两台机器上的最优分配，这里给出的是作业时间和机器时间，需要计算每个作业在每台机器上的完成时间，然后选择总时间最小的调度方案。 4. 解0-1背包问题的回溯法解空间树，需要构建一个节点代表一个0-1向量，表示选取物品的决策。解空间树是完全二叉树，每个节点代表一个可能的子集，叶子节点表示一个可行的解。最优值是所有叶子节点中最大价值的解，最优解是对应最优值的0-1向量。 5. 在二叉搜索树中搜索元素X，二叉搜索树的性质保证了搜索过程中左子节点的值小于当前节点，右子节点的值大于当前节点。搜索过程会沿着树的分支进行，直到找到目标元素或到达叶子节点。 以上内容涵盖了算法设计与分析的基本概念、动态规划、回溯法、搜索算法和优化策略，这些都是理解和解决复杂问题的关键工具。