完美WORD格式.整理

解：

A F B

C G DE

K

（4）把下列二叉树还原为森林

A

B

F C D

H I J E G H I 解：还原后的二叉树为：

① ② ③ G A E

（5）假设用于通信的电文仅由A、B、C、D、E、F、G 8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。

解：以权值：2、3、6、7、10、19、21、32构造哈夫曼树：（左子为0，右子为1。） 1000 1

字母编号 对应编码 出现频率

A 1010 7 40 600 1 1 B 00 19 0 . 19 21 专业资料分享 C . 28 32 0 D 1 B C DF H I 10000 1001 11 10001 2 6 32 3 0 11 1 0 17 1 E D 完美WORD格式.整理

（6）有向图如下图所示，画出邻接矩阵和邻接表

①

②

④⑤解：

邻接矩阵

1 2 3 4 5

③1?0?2?03?0?4?15??0邻接表 1 2 3 4 5 1101??0010?0001?

?0000?0010?? 2 4 5 1 4 3 5 ∧ ∧ ∧ ∧ ∧ （7）已知一个无向图有6个结点，9条边，这9条边依次为(0,1)，(0,2)，(0,4)，(0,5)，(1,2)，(2,3)，(2,4)，(3,4)，(4,5)。试画出该无向图，并从顶点0出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。 解：

. 专业资料分享 .

完美WORD格式.整理

0 12 3 从顶点0出发的深度优先搜索遍历的结点序列：0 1 2 3 4 5（答案不唯一） 从顶点0出发的广度优先搜索遍历的结点序列：0 1 2 4 5 3（答案不唯一）

4 5 （8）网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。

?0810110? ??803013 ?? ?103040??? ?110407? ??013070??

解： 最小生成树： 1 8 11 10 8 3 4 3 4 2 2 1 3 4 13 7 3 4 5 5 (9) 对于给定结点的关键字集合K={5，7，3，1，9，6，4，8，2，10}， （1）试构造一棵二叉排序树；

（2）求等概率情况下的平均查找长度ASL。

解：（1）构造二叉排序树 ： （2）ASL=(1*1+2*2+3*4+4*3)/10=2.9

5 3 1 2 4 6 87 9 10

(10) 给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。 设散列表的长度为13，散列函数为：H（K）=K % 13。试画出线性探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。 解：线性探测再散列解决冲突时所构造的散列表：

0 1 14 2 1 3 68 4 27 5 55 6 19 7 20 8 84 9 79 10 23 11 11 12 10 . 专业资料分享 .

完美WORD格式.整理

① ② ① ④ ③ ① ① ③ ⑨ ① ① ③ 平均查找长度ASL=（1*6+2*1+3*3+4*1+9*1）/12=30/3=3

(11) 给定结点的关键字序列为：47，7，29，11，16，92，22，8，3，哈希表的长度为11。 设散列函数为：H（K）=K % 11。试画出平方探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。

解：平方探测再散列解决冲突时所构造的散列表。

0 11 1 22 2 3 3 47 4 92 5 16 6 7 7 8 29 9 8 10 ① ② ② ① ① ① ① ② ②

平均查找长度ASL=（1*5+2*4）/9 = 13/9 = 5/3 （或1.44）

（12）已知数据序列{12，02，16，30，28，10，17，20，06，18}，写出希尔排序每一趟排序的结果。（设d=5、2、1）

解： 12 02 16 30 28 10 17 20 06 18 d=5

10 02 16 06 18 12 17 20 30 28 d=2

12 02 16 06 17 12 18 20 30 28

d=1 02 06 10 12 16 17 18 20 28 30

（13）已知数据序列{10，18，4，3，6，12，9，15}，写出二路归并排序的每一趟排序结果。

[10] [18] [4] [3] [6] [12] [9] [15]

[10 18] [3 4] [6 12] [9 15] 第一趟排序结果

[3 4 10 18] [6 9 12 15] 第二趟排序结果

[3 4 6 9 10 12 15 18] 第三趟排序结果

（14）已知数据序列{53，36，48，36，60，7，18，41}，写出采用简单选择排序的每一趟排序结果。

解：[53 36 48 36 60 7 18 41] （7） [36 48 36 60 53 18 41] （7 18） [48 36 60 53 36 41] （7 18 36） [48 60 53 36 41] （7 18 36 36） [60 53 48 41] （7 18 36 36 41） [53 48 60] （7 18 36 36 41 48） [53 60] （7 18 36 36 41 48 53） [60] （7 18 36 36 41 48 53 60 ）

. 专业资料分享 .

完美WORD格式.整理

（15）已知数据序列{10，1，15，18，7，15}，试画出采用快速排序法，第一趟排序的结果。 解：

10 1 15 18 7 15 low high 交换

7 1 15 18 [10] 15 low high 交换

第一趟排序结果： 7 1 [10] 18 15 15 low high

五、程序设计

第二章一个，第六章一个

. 专业资料分享 .