发布时间 : 星期六 文章算法设计与分析复习题目及答案资料更新完毕开始阅读
动态规划方法的条件：子问题的重叠性质。
可用贪心方法的条件：最优子结构性质；贪心选择性质。
动态规划：自底向上求解；贪心方法： 自顶向下求解。可用贪心法时，动态规划方法可能不适用；可用动态规划方法时，贪心法可能不适用。 23. 请说明动态规划方法为什么需要最优子结构性质。
答：最优子结构性质是指大问题的最优解包含子问题的最优解。
动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构. 24. 请说明：
(1)优先队列可用什么数据结构实现？ (2)优先队列插入算法基本思想？ (3)优先队列插入算法时间复杂度？ 答：（1）堆。
（2）在小根堆中，将元素x插入到堆的末尾，
然后将元素x的关键字与其双亲的关键字比较， 若元素x的关键字小于其双亲的关键字，
则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。 （3）O( log n)
26. 在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么？在忽略常数因子的情况
下，O、Ω、Θ分别提供了算法运行时间的什么界？ 答：
如果存在两个正常数c和N0,对于所有的N≥N0，有|f(N)|≤C|g(N)|，则记作：f(N)= O(g(N))。这时我们说f(N)的阶不高于g(N)的阶。
若存在两个正常数C和自然数N0，使得当N ≥ N0时有|f(N)|≥C|g(N)|，记为f(N)=?(g(N))。这时我们说f(N)的阶不低于g(N)的阶。
如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(N)| ≤|f(N)| ≤ c2|g(N)| 则记作 f(N)= (g,(N)
?
O、Ω、Θ分别提供了算法运行时间的上界、下界、平均 五、算法设计与分析题
1．用动态规划策略求解最长公共子序列问题： （1）给出计算最优值的递归方程。
（2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出
其最长公共子序列，要求给出过程。
答：1
当i?0或j?0时?0?c[i,j]??c[i?1,j?1]?1当i,j?0且xi?yi时
?max(c[i,j?1],c[i?1,j])当i,j?0且xi?yi时?(2)
Ｙ Ａ Ｂ Ｃ Ｂ Ｘ 0 0 0 0 Ｂ 0 0 1 1 1 Ｃ 0 0 1 2 2 Ｄ 0 0 1 2 2 Ａ 0 1 1 2 2 最长公共子序列：｛ＢＣ｝
2．对下列各组函数f (n) 和g (n)，确定f (n) = O (g (n)) 或f (n) =Ω(g (n))或f(n) =
θ(g(n))，并简要说明理由。
(1) f(n)=2n； g(n)=n! (2) f(n)=n； g (n)=log n2 (3) f(n)=100； g(n)=log100 (4) f(n)=n3； g(n)= 3n (5) f(n)=3n； g(n)=2n 答：
(1) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。 (2) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。
(3) f(n) = θ(g(n)) 因为g(n)与f(n)同阶。 (4) f(n) = O(g(n)) 因为g(n)的阶比f(n)的阶高。 (5) f(n) = Ω(g(n)) 因为g(n)的阶比f(n)的阶低。
3．对下图所示的连通网络G，用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。
1 11 5 18 21 26 6 17 19 15 2 9 4 6 7 3 答：
TE={(3,4), (2,3),(1,5),（4,6）（4,5）}
贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。 基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。
时间复杂度为：O(eloge)
4. 请用分治策略设计递归的归并排序算法，并分析其时间复杂性（要求：分别给出divide、conquer、combine这三个阶段所花的时间，并在此基础上列出递归方程，最后用套用公式法求出其解的渐进阶）。 答 ： Template
void MergeSort (Type a[ ], int left, int right) { if (left } Divide 阶段的时间复杂性： O(1) Conquer阶段的时间复杂性： 2T(n) Combine阶段的时间复杂性： Θ(n) θ(1)当n?1?T(n)?? ? 2T(n/2) ? θ(n) 当n ? 1 用套用公式法：a=2, b=2, nlog ba = n , f(n)=n, ∴T(n) =Θ(nlogn) f(n)与nlog ba 同阶， 因为