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

"算法设计与分析考试题及答案.doc" 这篇文档包含了关于算法设计与分析的考试题目及其答案，主要涉及了算法的基础概念、复杂性、动态规划、回溯法、0-1背包问题以及二分搜索算法等多个核心知识点。 1. 算法的五个重要特性通常指的是：可行性、确定性、有限性、输入和输出。这意味着算法必须能够被执行，每一步都有明确的定义，有终止条件，接收输入并产生输出。 2. 算法的复杂性分为时间复杂性和空间复杂性，评价一个算法的好坏主要看它在时间和空间资源上的效率。时间复杂性是指算法运行所需要的计算时间，而空间复杂性则是算法执行过程中所占用的内存空间。 3. 动态规划算法适用于解决的问题特征是：问题的最优解可以通过子问题的最优解来构造，即存在重叠子问题和最优子结构。 4. 序列X和Y的最长公共子序列可以是"B,C,A,D"，这是通过比较两个序列并找到共享元素的最大连续子序列得到的。 5. 回溯法解问题时，解空间应包含所有可能的解决方案，包括有效和无效的。 6. 动态规划算法通常将大问题分解为子问题，先求解子问题的最优解，然后逐步构建原问题的最优解。 7. 以深度优先搜索（DFS）方式系统搜索问题解的算法，通常用于解决图或树的遍历问题。 8. 回溯法解0-1背包问题的计算时间依赖于问题规模，而动态规划算法的时间复杂度相对较低，一般为O(nC)，其中n是物品数量，C是背包容量。 9. 动态规划算法的两个关键要素是状态和状态转移方程，状态表示问题的部分解决方案，状态转移方程描述了如何从一个状态过渡到另一个状态。 10. 二分搜索算法是基于分治策略实现的，它在有序数据中查找目标值，每次比较后将搜索范围减半。 综合题部分涉及了动态规划算法的设计步骤，如定义状态、找到状态之间的关系、构建解决方案等；流水作业调度问题的Johnson算法旨在最小化总完工时间；优化4个作业在两台机器上的调度方案，需要计算每个作业在不同机器上的执行时间以找到最小总时间；使用回溯法解决0-1背包问题，需要构建解空间树并找到最优解；最后，介绍了二叉搜索树在搜索元素时的行为。 这些题目覆盖了算法设计与分析的关键概念和技术，适合于检验和提升学生在这门课程中的理解和应用能力。