1．将下列由三棵树组成的森林转换为二叉树。

（只要求给出转换结果）
加线：亲兄弟
减线：断裂原来的关系
旋转：调整成二叉树
2．设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。

（2）将这棵二叉树转换成对应的树（或森林）。

A
B
F
D
C
E H
G
3．已知一棵二叉树的对称序和后序序列如下： 对称序：GLDHBEIACJFK 后序： LGHDIEBJKFCA (1) 给出这棵二叉树： (2) 转换为对应的森林：
4.（1）设通信中出现5中字符A 、B 、C 、D 、E 对应的频率为0.2,0.1,0.5,0.15,0.25构造哈夫曼树，并给出对应字符的编码。

（2） 设A 、B 、C 、D 、E 、F 六个字母出现的概率分别为7,19,2,6,32,3。

试写出为这六个字母设计的HUFFMAN 编码, 并画出对应的HUFFMAN 树.
(1)
A
K
C
B
H D
G E L
F
J
I (2) E A B
L D
G
H
I
C
K
J
F
5．已知有向图G=(V,E)，其中V={V 1,V 2,V 3,V 4,V 5,V 6,V 7}，
E={<V 1,V 2>,<V 1,V 3>,<V 1,V 4>,<V 2,V 5>,<V 3,V 5>,<V 3,V 6>,<V 4,V 6>,<V 5,V 7>,<V 6,V 7>},
G 的拓扑序列是V 1,V 3,V 4,V 6,V 2,V 5,V 7
（1）．根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构; （2）．写出从元素A 出发按“广度优先搜索”算法遍历此图的元素序列. 答：
（2）AFEDBC
7．考虑右图：
(1)从顶点A出发，求它的深度优先生成树
(2)从顶点E出发，求它的广度优先生成树
（3）根据普利姆(Prim) 算法或克鲁斯卡尔（Kruskal）
求它的最小生成树
答：设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列(1)ABGFDEC (2)EACFBDG
(3)
8. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为_4__.
（也可以出成作图题）
E
A
B
G
C
D
F
5
3
6
1
4
31
2
5
9. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。

请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。

10. （20,15,7,32,45,28）构成二叉树的构造，平均查找长度
11．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为
12. 对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。

（125，11，22，34，15，44，76，66，100，8，14，20，2，5，1）。

设D=7
D=3
1，11，2，5，15，8，14，34，20，22，66，100，44，76，125
D=1 1，2，5，8，11，14，15，20，22，34，44，66，76，100，125。