搜索成功时的平均搜索长度为：ASLsucc=2.5
12、已知待排序记录的关键字序列为{83，69，41，22，15，33，8，20}，
要求：（1）用归并排序法按从小到大顺序写出每趟排序的结果，直到排序结束； 答案：8，15，20，22，33，41，69，83
13、设二叉树t的中序序列为BADCE，后序序列为BDECA，请给出二叉树的前序序列。
要求：（1）画出这棵二叉树：（3分） （2）写出这棵二叉树的前序遍历序列。 (1)
C B
E D
（3分）
(2)前序序列：ABCDE
14、假定用于通信的电文仅由8个字母a，b，c，d，e，组成，各个字母在电文中出现的频率
分别为5，3，6，10，4。试为这5个字母设计Huffman树。
A 答案：
a c d b e
15、把下面的二叉树转换为相应的森林。
答案：
b a c e f h
d g
16、已知一个图的邻接矩阵如下，请分别写出从顶点V0出发按深度和广度优先遍历时得到的顶点序列。
01234567011000000100110001100001102010000013010000014001000015001000016000111107
答案：深度遍历：VO,V1,V3,V7,V4,V5,V2,V6
广度遍历：V0,V1,V2,V3,V4,V5,V6,V7
17、已知散列函数为H(K)=K mod 6,健值序列为25，37，52，43，84，99，120， 15，26，11采用拉链法处理冲突，试构造开散列表，并计算查找 成功的平均查找长度。
答案：开散列表省略，
ASL=1.3
18、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对
象为基准而得到的第一次划分结果为多少？
答案：{40，38，46，56，79，84}
19、已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。
前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G
后序序列：
答案：后序序列：CBFEIJHGDA
20、把下面的二叉树转换为对应的森林
E
H A
答案：
C B D G I
A E F H I D G
C B 21、已知无向图G的邻接表如下，请画出其所有的连通分量。
答案： V3 V1 V2
V5 V4 22、给出如图所示的有向图G的邻接矩阵的存储结构。
23、已知散列函数为H(K)=K mod 9,健值序列为19，14，25，01，68，28，84，27，56，12采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。 答案：
开散列表省略， ASL= 1.5
24、对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15， 请给出采用起泡排序法对该序列作升序排序时的每一趟的结果。
25、已知某二叉树的中序序序列为ABCDEGFHI，后序序列为ACDBGIHFE，请给出二叉树的前序序列。
要求：（1）画出这棵二叉树：（3分）
（2）写出这棵二叉树的前序遍历序列。（2分） 答案：
B F
A D G C
（3分）
先序序列：EBADCFGHI （2分）
26、把下面的二叉树转换为对应的森林。
E
E H I
A D C J B H G I K
答案：
A E H D G I K
C B