算法设计与分析复习题目及答案

答:(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)

Y A B C B

X 0 0 0 0 B 0 0 1 1 1 C 0 0 1 2 2 D 0 0 1 2 2 A 0 1 1 2 2 最长公共子序列:{BC}

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? T(n) ?? ?1? 2T(n/2) ? θ(n) 当n ? 1 用套用公式法:a=2, b=2, nlog ba = n , f(n)=n, ∴T(n) =Θ(nlogn)

f(n)与nlog ba 同阶, 因为

1 2 3 4 5 6 7

1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4

3 2 1

5、设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表: 每个选手必须与其他n-1名选手比赛各一次;每个选手一天至多只能赛一次; 循环赛要在最短时间内完成.

(1)(4分)循环赛最少需要进行( n-1 )天.

(2)(6分)当n=23=8时,请画出循环赛日程表:

6、考虑用哈夫曼算法来找字符a,b,c,d,e,f 的最优编码。这些字符出现在文件中 的频数之比为 20:10:6:4:44:16。要求:

(1)(4 分)简述使用哈夫曼算法构造最优编码的基本步骤;

(2)(5 分)构造对应的哈夫曼树,并据此给出a,b,c,d,e,f 的一种最优编码。 解:1)、哈夫曼算法是构造最优编码树的贪心算法。其基本思想是,首先所 有字符对应n 棵树构成的森林,每棵树只有一个结点,根权为对应字符的频率。然后,重复

下列过程n-1 次:将森林中的根权最小的两棵树进行合并产生一个新树,该新树根的两个子

树分别是参与合并的两棵子树,根权为两个子树根权之和。

2)、根据题中数据构造哈夫曼树如下图所示。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4