发布时间 : 星期日 文章算法设计与分析复习题目及答案更新完毕开始阅读
或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）、根据题中数据构造哈夫曼树如下图所示。 由此可以得出 a,b,c,d,e,f 的一组最优的编码：01,0000,00010,00011, 1,001。 7.考虑在序列A[1..n]中找最大最小元素的问题。一个分治算法描述如下：如果n≤2 就直接求解。否则，将序列等分成两个子序列A[1..n/2]和A[n/2+1..n]，分别找出这两子序列的最大最小元素x1,y1 和x2,y2；然后据此求出A[1..n]的最大元素x=max{x1,x2}及最小元素y=min{y1,y2}。请给出该算法计算时间T(n)满足的递归方程，并解方程来确定算法的时间复杂度。假定n=2k（k 为正整数）。 答： 算法时间复杂度满足如下递归方程： T(n)=2T(n/2)+2（n>2）；T(2)=1。 因为 n=2 k（k 为正整数），所以， T(n)= T(2 k)= 2T(2 k-1)+2= 22T(2 k-2)+ 22+2 ? = 2k-1T(2)+ 2k-2+?+23+22+2