13．给定一个权集W={2，6，3，12，13，9，17，18}，请画出相应的赫哈夫曼树,并计算其带权路径长度WPL。 解：（1）图正确3分
2 3
（2）WPL公式对1分，答案正确1分，共2分
WPL=(16+18)*2+(9+12+13)*3+6*4+(1+3)*5=68+102+24+20=214
14． 对于给定的五个字母A、B、C、D、E，它们的频度依次为2，5，6，8，13，试构造Huffman树；并求出它们的哈夫曼编码。 解：
34 1 0
E 13 0 D 8 21 1 13 C 6 A 2
B 5 1 7 1 5 6 17 80 3518 9 20 45 25 1311 12哈夫曼编码： E：13——0 D：8 ——10 C：6 ——110 B：5 ——1111
0 0 A：2 ——1110
15．按图画出逆邻接矩阵，并写出以①为顶点的广度优先搜索序列 ⑥
① ② ④ ③ ⑤
解： 1 2 3 4 5 6 （1）画出逆邻矩阵3分， 1 0 0 0 0 0 0 2 0 0 0 1 1 1
3 4 5 6
1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
（2）
广度优先搜索序列：1、3、4、6、5、2 （或1、6、4、3、2、5）
写对广度优先搜索序列2分
16． 根据如下有向图，画出邻接矩阵和逆邻接表。
① ② ③
④⑤解：（1）邻接矩阵 2.5 1 2 3 4 5
1?1101?2?0?00010??3??00001?? 4?10000?5??00010??（2）逆邻接表 1 4 ∧ 2 1 ∧ 3 1 ∧
4 2 5 ∧ 5 1 3 ∧
17．带权无向图（网络）如图三-2-3所示， （1）画出该网络的邻接矩阵； （2）用Prim算法构造最小生成树。
图三-2-3
分
2.5分
解：
（1） 邻接矩阵 （2） 最小生成树
A=
?0?2??4??0?0???02031054300520100430054020??5?2??3?2??0??18．无向图G如图所示， （1）试画出邻接矩阵；
（2）写出从A出发的深度优先遍历的序列。 （3）写出从D出发的广度优先遍历的序列。
AC B D F E G 解：（1） 邻接矩阵 （2）从A出发的深度优先遍历的序列：
?0?1??1??0?0??0?0?100100010010000110110000100100010010??0?0??0?1??1?0?? A B D C E G F（不唯一）
或A B D E G F C
（3）从D出发的广度优先遍历的序列： D B C E F A G（不唯一）
或D E F B C G A 5 1 2 5 1 4 3 ∧ ∧ 19． 已知图G的邻接表如图三-4-2，以顶点1为出发点，完成下列问题
1 2 3 4 5 2 3 5 1 4 ∧ ∧ ∧ 图三-4-2
（1）写出以顶点1为出发点的广度优先遍历序列；
（2）画出以顶点1为出发点的深度优先搜索得到的一棵二叉树。 解：（1）广度优先遍历序列：1，2，5，4，3 （2）深度优先搜索得到的一棵二叉树：
21 4 21 4 3 5 3 5 20．给定结点的关键字序列为：30，36，26，52，46，38，34，设散列函数： H(key)=key mod 6。
采用线性探测法解决冲突，要求： （1）构造此散列表；
（2）试问查找34需要比较的次数；
（3）求出其平均查找长度。 解：（1） 线性探测再散列解决冲突时所构造的散列表：
0 30 1 36 2 26 3 37 4 52 5 46 6 34 ① ① ① ② ① ② ③ （2）查找34需要比较3次 （3）ASL=(1*4+2*2+3*1)/7=11/7
21．给定结点的关键字序列为：87，25，11，8，27，28，68，95，70，6，83，63，18，47，已知设散列函数为：H（K）=K % 13。
（1）试画出链地址法解决冲突时所构造的哈希表； （2）求其平均查找长度。 解：
（1） 链地址法解决冲突时所构造的哈希表。
0 1 2 3 4 5 6 7 8 9 ∧
27 ∧ 28 ∧ 68 ∧ 95 ∧ 70 6 8 ∧ 83 18 ∧
∧ 47 ∧ 87 ∧ 11 10 ∧ 11 12 63 ∧ 25 ∧ （2） 平均查找长度ASL=（1*10+2*3+3*1）/14 = 19/14
22．设关键字序列为：{35，25，55，10，28，85，68，50，25，52}，试构造二叉排序树，并求等概率情况下的平均查找长度。 （1）3分
10 35 55 28 50 85 2525 52 68 AVL=A（1*1+2*2+3*4*+4*3）/10=2.9 （2）AVL公式对1分，答案正确1分，共2分
23．对于给定结点的关键字集合K={15，9，20，12，17，4，18，10，29，6}， （1） 构成一棵二叉排序树；
（2） 查找关键字18，要比较几次才能找到，先后与哪些关键字比较。 （3） 试问如何得到该二叉排序树的有序序列。 （1）构造二叉排序树
9 4 6 10 12 1718 15 20 29
（2）查找关键字18要比较4次才能找到，先后与关键字15、20、17、18比较。
（3）中序遍历能得到二叉排序树的有序序列：4，6，9，10，12，15，17，18，20，29。
24．关键字序列为：49，38，65，97，76，13，27，35，写出直接插入算法每一趟排序的结果。
49，38，65，97，76，13，27，35
49 38，65，97，76，13，27，35 38，49 65，97，76，13，27，35 38，49，65 97，76，13，27，35 38，49，65，97 76，13，27，35 38，49，65，76，97 13，27，35 13，38，49，65，76，97 27，35 13，27，38，49，65，76，97 35
13，27，35，38，49，65，76，97