29．试画出下面带权无向图的一棵最小生成树。 9 2 a
7 d 6 b
3 9 c 7 8 4 e f 5 30．写出利用希尔排序对关键字序列 (40,24,80,39,43,18,20,10,90,70) 进行从小到大排序的每一趟结果。（假设gap取值分别为5、3、1）
31．设一散列表长为13，采用线性探查法解决冲突。散列函数h(key)=key。 （1）画出在空表中依次插入关键字25,20,36,15,41,52,29,72,67后的散列表。 （2）该散列表在等概率查找成功和不成功的平均查找长度。
四、 综合题（共14分）
32．试对下图所示的AOE网络回答下列问题：
（1） 这个工程最早可能在什么时间结束。（2分）
（2） 求每个活动的最早开始时间e()和最迟开始时间l().（8分） （3） 确定哪些活动是关键活动。（4分）
10
2 1 15 3 4 2 19 4 6 6 5 11 5 数据结构模拟试卷(一)参考答案
一.1-5 A B C D A 6-10 B C D A B 11-15 C D A B C
二.1.非线性结构 2. f(n) 3.O(n) 4.10 5.栈顶
6.可使用性 7.n-1 8. (15,02,21,24,26,57,43,66,80,48,73) 9.稀疏 10. 89 11.((d，e，f))
12. 3 13. 50 14. n(n-1)／2 15. 5
三. × √ × √ × √ × √ × × 四.
1. d g b a e c h i f a b d g c e f h i g d b e i h f c a
2. 邻接矩阵： a b c d e f g
0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0
邻接表：
0 a 1
1 b Λ 6
2 c Λ 1
3 d 2
4 e Λ 3
5 f 0
6 g 2
a b c d e f g
6 Λ 5 Λ 4 3 Λ 5 Λ 3.
18,24,80,39,43,40, 20
18,20,80,39,43,40, 24
18,20,24,39,43,40, 80
18,20,24,39,43,40, 80 18,20,24,39,40,43, 80 18,20,24,39,40,43, 80 4．
4种。 A BC A C B C A B C B A
评分标准：次序不限，写对一种得1分，4种全写对得6分。若在4种正确答案之外，又多写一种则只能得4分，若6种排列顺序全写上则0分。
5.
事件的最早发生时间和最迟发生时间：
活动的最早开始时间和最迟开始时间：
网络中的关键活动：ab,be,eh,hk 关键路径: a?b?e?h?k
数据结构模拟试卷(二)参考答案
一.
1~5 ACABB 6~10 ABABA 11~15 BADCB
二.
逻辑结构 n/2 先进先出 79 中序 快速排序 n-1 head->next==NULL 10,13,27,76,65,97,38 入度为零 三. 26．
参考答案：
1)根结点是：a 4)树的深度：4 5)树的度数：3 27．
参考答案：
28．
参考答案： (1)
2)叶子结点是：d i f j k l 3)g的祖先：a c 19 8 11 5 6 2 4 带权路径长度：WPL=(2+4)*3+5*2+8=36
(2)
（评分标准：每个图3分）
29．
参考答案：
a 2 b 6 3 c 4 f e 5 d 30．
参考答案：
Gap=5时 18, 20, 10, 39, 43, 40, 24, 80, 90, 70 Gap=3时 18, 20, 10, 24, 43, 40, 39, 80, 90, 70 Gap=1时 10, 18, 20, 24, 39, 40, 43, 70, 80, 90 31．
参考答案：
(1)散列表：（2分）
0 1 2 3 4 5 6 7 8 9 10 11 12
52 15 41 29 67 20 72 36 25 (2)ASLSUCC=(5*1+3*2+1*4)/9=5/3 （2分） ASLNSUCC=(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/13 （2分）