2011算法复习资料.doc

"2011算法复习资料.doc" 本文档是关于算法的复习资料，涵盖了选择题、判断题、时间复杂度分析题、程序填空题和问答题等多个方面。其中，选择题和判断题考察了算法的基本概念和定义，如贪心算法、动态规划算法、分支限界法等。时间复杂度分析题则考察了算法的时间复杂度计算和分析。程序填空题和问答题则考察了算法的实现和应用。 一、选择题 1. 贪心算法的基本要素是什么？ 答案：贪心选择性质和最优子结构性质。 2. 动态规划算法的基本要素是什么？ 答案：最优子结构性质和子问题重叠性质。 二、判断题 1. 贪心算法是否总是能找到最优解？ 答案：否，贪心算法不一定能找到最优解。 2. 动态规划算法是否总是能找到最优解？ 答案：是，动态规划算法可以找到最优解。 三、时间复杂度分析题 1. 分支限界法的时间复杂度是多少？ 答案：O(2^n)。 2. 动态规划算法的时间复杂度是多少？ 答案：O(nW)。 四、程序填空题 1. 用队列式分支限界法求解 0-1 背包问题的代码如下： ```c void queueBranchAndBound(int n, int c, int* P, int* W) { ... } ``` 2. 用递归回溯算法求解四后问题的代码如下： ```c void backtrack(int t) { if (t > n) { _Output(x)_; } else { for (int i = f(n, t); i <= g(n, t); i++) { x[t] = h(i); if (constraint(t) && bound(t)) { _Backtrack(t + 1)_; } } } } ``` 五、问答题 1. 用队列式分支限界法求解四城市旅行商问题的过程是什么？ 答案：画出解空间树，然后用队列式分支限界法搜索解空间树，输出最优解。 2. 用递归回溯算法求解图的 m 着色问题的过程是什么？ 答案：定义状态变量和约束条件，然后用递归回溯算法搜索解空间，输出最优解。 3. 贪心算法和动态规划算法的区别是什么？ 答案：贪心算法是一种自顶向下的算法，选择当前最优解，而动态规划算法是一种自下而上的算法，选择子问题的最优解。 4. 分支限界法和回溯法的区别是什么？ 答案：分支限界法是一种自下而上的算法， Search 解空间树，而回溯法是一种自顶向下的算法，Search 解空间树。 5. 什么是最优子结构性质？ 答案：某个问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质。