J 27、假定用于通信的电文仅由4个字母a，b，c，d组成，各个字母在电文中出现的频率分别为7，5，2，4。试为这4个字母设计Huffman树。 答案：
a b c d
28、写出有向图的拓扑排序序列。
答案：V3,V1,V4,V5,V2,V6
V4 V5 V3 V1 V2 V6 29、已知散列函数为H(K)=K mod 12,健值序列为25，37，52，43，84，99，120，
15，26，11，70，82，采用拉链法处理冲突，试构造开散列表，并计算查找 成功的平均查找长度。
答案：开散列表省略，
ASL=19/12
30、已知待排序记录的关键字序列为{83，69，41，22，15，33，8}， 要求：（1）用直接选择排序法按从小到大顺序写出每趟排序的结果，直到排序结束；
答案：
第一趟：8，69，41，22，15，33，83 第二趟：8，15，41，22，69，33，83 第三趟：8，15，22，41，69，33，83 第四趟：8，15，22，33，69，41，83 第五趟：8，15，22，33，41，69，83 第六趟：8，15，22，33，41，69，83
31、把下面的树转换为对应的二叉树
答案：
A B E C D L K H I F J
G
32、已知一棵树二叉如下，请分别写出按箭序、中序、后序和层次遍历时得到的结点序列。
A
B C
D E F
G H
前序： 中序： 后序： 层次：
答案：前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 层次：ABCDEFGH
33、已知权值 W={ 8，6, 2, 15，7}，请构造对应的Huffman树。 答案：
8 7 15 6 2
34、写出如下有向图的拓扑排序序列。
V3 V1 V2 V6
V4 V5
答案：V1,V3,V4,V5,V2,V6
35、已知散列函数为H(K)=K mod 8,健值序列为25，37，52，43，84，99，120，15，26，11，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度
答案：开散列表省略，
ASL=1.2
36、已知待排序记录的关键字序列为{55，69，41，22，15，33，8，20}， 要求：（1）用堆排序法找出最大的值，要求写出排序过程；
答案：69；过程略
37、已知一棵二叉树的中序遍历的结果为：ABCEFGHD，后序遍历的结果为：ABFHGEDC
请给出二叉树的前序序列。
要求：（1）画出这棵二叉树：（3分）
（2）写出这棵二叉树的前序遍历序列。（2分） 答案：
C
B A
前序序列：CBADEGFH （2分）
D E G F H 38、试画出下面二叉试画出下面二叉树对应的二叉链表。。
39、假定用于通信的电文仅由4个字母a，b，c，d, e组成，各个字母在电文中
出现的频率分别为3，2, 4，6，5。试为这5个字母设计Huffman树且写出对应的Huffman编码。
c d e a b a :110 b: 111 c: 00 d:01 e :10
40、已知一个图的邻接表如下，请写出从顶点C0出发按深度遍历时得到的顶点序列。
答案：C0—C1—C3—C4—C5—C2