为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：
0 1 0 29 1 0 5 1 3 0 14 7 0 1 1 1 8 0 1 0
23 11 赫夫曼编码为：概率为0.23的字符编码为：00 概率为0.11的字符编码为：010
概率为0.05的字符编码为：0110 概率为0.03的字符编码为：0111 概率为0.29的字符编码为：10
概率为0.14的字符编码为：110 概率为0.07的字符编码为：1110
概率为0.08的字符编码为：1111
14、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。 答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图：
A
E B F C G D H IJ 这棵二叉树的后序遍历序列为：EDCBIHJGFA 15、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。
16、 对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树, 其最大高度是多少? 最小高度是多少?
答案：设高度为h(空树的高度为-1)的AVL树的最少结点为Nh，则Nh = Fh+3 -1。 Fh 是斐波那契数。又设AVL树有n个结点，则其最大高度不超过3/2*log2(n+1), 最小高度为「log2(n+1) ┐-1。
17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
答案：折半搜索时的判定树为： 509 154 677 275
ASLSUCC=1/14（1+2*2+3*4+4*7）=45/14 ASLUNSUCC=1/15（3*1+4*14）=59/15
18、试对下图所示的AOE网络
017 553 503 897 094 170 512 612 765 908
(1) 这个工程最早可能在什么时间结束。
(2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。 (3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。
(4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。
答案：按拓朴有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl，然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l,根据l-e是否等于0来确定关键活动，从而确定关键路径。 Ve Vl
① 0 0 ③ 19 19 ② 15 15 ④ 29 37 ⑤ 38 38 ⑥ 43 43
e L l-e <1,2> 0 17 17 <1,3> 0 0 0 <3,2> 15 15 0 <2,4> 19 27 8 <2,5> 19 19 0 <3,5> 15 27 12 <4,6> 29 37 8 <5,6> 38 38 0 此工程最早完成时间为43，关键路径为<1,3><3,2><2,5><5,6>
19、已知有五个待排序的记录，其关键字分别为：256，301，751，129，937,863，742，694，076，438请用快速排序的方法将它们从小到大排列。 答案：
第一次排序：（076，129），256，（751，937，863，742，694，301，439） 第二次排序：076，129，256，（438，301，694，742），751，（863，937） 第三次排序：076，129，256，301，438，（694，742），751，（863，937） 第四次排序：076，129，256，301，438，694，742，751，（863，937） 第五次排序：076，129，256，301，438，694，742，751，863，937
20、设有150个记录要存储到散列表中, 并利用线性探查法解决冲突, 要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ (设?是散列表的装载因子，则有ASLsucc = ( 1+1/ (1-?) )/2)。
答案：已知要存储的记录数为n=150,查找成功的平均查找长度为ASLsucc ≤2，则有：ASLsucc =1/2（1+1/（1-?））≤2 解得 ?≤2/3 ，又有：?=n/m=150/m 两式联立得：150/m≤2/3,解得：m≥225. 所以散列表需要设计225个单位。 五、算法分析题
1、给出下列递归过程的执行结果 void unknown ( int w ) {
if ( w ) {
unknown ( w-1 );
for ( int i = 1; i <= w; i++ ) cout << w<<' ';
cout << endl;
} }
调用语句为 unknown (4)。 答案：
(1) 1 2 2
3 3 3
4 4 4 4
2、给出递归过程的执行结果 void unknown ( int n ) {
cout << n % 10 ;
if ( int ( n / 10 ) ) unknown ( int ( n / 10 ) ); }
调用语句为unknown ( 582 )。 答案： 285
3、给出递归过程的执行结果
int unknown ( int m ) {