数据结构复习题（考试用的），求高手解答，有点急（第三部分）三、应用题：1、已知某系统在通信联络中只可能出现8种字符，其频率分别为9，17，6，19，11，21，5，12。试设计哈夫曼编码

Question

数据结构复习题（考试用的），求高手解答，有点急（第三部分）
三、应用题：
1、已知某系统在通信联络中只可能出现8种字符，其频率分别为9，17，6，19，11，21，5，12。试设计哈夫曼编码。（必须画出哈夫曼树）
5、已知一棵二叉树的中根序列：BECDAHGF，后根序列：EDCBHGFA，画出这棵二叉树。

6、已知待排序列如下：30，12，52，45，32，15，65，31，58，20，63，78。试分别用快速排序、希尔排序和冒泡排序的方法进行排序，写出排序过程。
7、 有如下有序序列：8，17，20，23，32，37，45，50，58，67，79。采用二分法进行查找，画出描述其查找过程的判定树，并求出其平均查找长度（ASL） 。
8、有如下有序序列：6，12，18，23，28，32，41，45，51，57，69，80。采用二分法进行查找，画出描述其查找过程的判定树，并求出其平均查找长度（ASL） 。

Answer 1

1 2000+(4*6+3-1)*2
2 1000+(6*2+5-1)*2
3 -+a*bcd答案是C吧，画语法树遍历就知道了。
1 n-i+1;
2 n n
3 初始low=2 high=100 mid=20 20>12
于是low=2 high=20 mid=6
于是low=6 high=20 mid=12
ok!
4 数据的物理结构
5 数据元素的个数
6 FIFO
7 1056 1086
8 2^（4-1）=8
9 n0=n2+1 所以有13个
10 1 1000 1000
11 20 (ps:sqrt(400)=20)