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

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

= 2k-1+?+23+22+2。因此，T(n)=?(n)。

8. 考虑使用动态规划方法求解下列问题：

01背包数据如下表，求：能够放入背包的最有价值的物品集合。

物品 i 1 2 3 4

如设： V(i, j) —— 前 i 个物品中能够装入承重量 j 的背包中的最大总价值。请将如下递推式填写完整：

V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0）

V(i, j) = V(i-1, j) 第 i 个物品不能装入， j < wi （超重）

V(i, j) = max { , } j > wi （不超重） i在最优子集中 i不在最优子集中

自底向上：按行或列填写下表。 V i=0 1 2 3 4

j=0 0 0 0 0 0 1 0 2 0 3 0 4 0 5 0

重量 wi w1=2 w2=1 w3=3 w4=2 价值 vi v1=12 v2=10 v3=20 v4=15 W=5 承重量 W

答：

V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0）

V(i, j) = V(i-1, j) 第 i 个物品不能装入， j < wi （超重）

V(i, j) = max { vi + V(i-1,j-wj) , V(i-1, j) } j > wi （不超重） i在最优子集中 i不在最优子集中 V i=0 1 2 3 4

9.请画出用回溯法解4皇后问题的解空间树和搜索空间树： 解空间树：

j=0 0 0 0 0 0 1 0 0 10 10 10 2 0 12 12 12 15 3 0 12 22 22 25 4 0 12 22 30 30 5 0 12 22 32 37