内容发布更新时间 : 2024/4/28 10:23:19星期一 下面是文章的全部内容请认真阅读。

答：（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? 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）、根据题中数据构造哈夫曼树如下图所示。