我要评论1.考虑用哈夫曼算法来找字符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。
2.
设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表:
每个选手必须与其他n-1名选手比赛各一次;每个选手一天至多只能赛一次;
循环赛要在最短时间内完成.
(1)（4分）循环赛最少需要进行( n-1 )天.
(2)（6分）当n=23=8时,请画出循环赛日程表:
| 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 |
3.
请用分治策略设计递归的归并排序算法，并分析其时间复杂性（要求：分别给出divide、conquer、combine这三个阶段所花的时间，并在此基础上列出递归方程，最后用套用公式法求出其解的渐进阶）。
答 ： template <class type>
void mergesort (type a[ ], int left, int right)
{ if (left<right)
{ int i=（left+right）/2;
mergesort（a, left, i）;
mergesort（a, i+1, right）;
merge(a, b, left, right);
copy(a, b, left, right);
}
}
divide 阶段的时间复杂性： o(1)
conquer阶段的时间复杂性： 2t(n)
combine阶段的时间复杂性： θ(n) 
用套用公式法：a=2, b=2, nlog ba = n , f(n)=n, 因为f(n)与nlog ba 同阶，
∴t(n) =θ(nlogn)
4.
对下图所示的连通网络g，用克鲁斯卡尔(kruskal)算法求g的最小生成树t,请写出在算法执行过程中，依次加入t的边集te中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。
te={(3,4), (2,3),(1,5),（4,6）（4,5）}
贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。
基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。
时间复杂度为：o(eloge)
5.
用动态规划策略求解最长公共子序列问题：
（1）给出计算最优值的递归方程。
（2）给定两个序列x={b,c,d,a}，y={a,b,c,b}，请采用动态规划策略求出其最长公共子序列，要求给出过程。
（1）
发表评论