} }
四、应用题 1、 答：
2、 答： （1）
C （3） （5）
（6）
G C 1 2 F G 2 F C 1 4 A 3 D
（4）
A 3 D G 1 C 1 G 2 F
（2）
G
2
F
G
B C 1 5 4 B C 1 5 2 F A 3 D A E 6 4 3 D 3、答：由于地址空间为10，且从100开始，故散列函数选为H（key）=key%7+100。
用线性探测再散列解决冲突，ASLsucc=27/10
4、答：成功查找平均比较查找长度为：（n+1）/n[log2（n+1）]-1。
作业题二参考答案： 一、单项选择题
1、C 2、C 3、B 4、C 5、D 6、C 7、C 8、B 9、A 10、C 二、填空题 1、2n0-1 2、6，261 3、 log2k4、25 5、N-1
6、最优二叉树，最小的二叉树 7、根结点，各子树 三、应用题
+1
1、
答：不唯一，型对即可
1 6 3 2 7 4 9 22 13
此树的带权路径长度WPL =9*1+6*2+4*3+(1+2)*4=45 2、 答： （1）插入10
（6）插入5
（7）插入4
（8）
6 6
(2) 插入6
10 (3) 插入3 (4)
6 10
10 调整 3 10 （5）插入2 2 3 6 6 6 10 2 5 2 5 3 10 3 10 3 5 6 4 10
调整 2 3、答：当关键字为3时，比较次数为4； 当关键字为8时，比较次数为1； 当关键字为19时，查找不成功；
4、答：（2）略
（3）深度优先遍历序列：ABCDE广度优先遍历序列：ABCED（4）关键路径A--B（长100）
作业题三参考答案： 一、单项选择题
1、D 2、B 3、A 4、C 5、D 6、A 7、B 8、C 9、B 10、D 二、填空题 1、2，3 2、4 3、n-1 4、e
5、相同类型数据，地址连续 6.三元组顺序表，三元组 7. 矩阵转置 三、应用题 1、 答：
①
二叉链表 2、答：
B C D ② ∧ ③
∧ ④ ⑦ ∧ ∧ ⑤ ∧ ⑥ ∧
(2 ∧ ⑧ ∧ ∧ ⑨ ∧ A
E
3. 答：Prim算法构造最小生成树的步骤如24题所示，为节省篇幅，这里仅用Kruskal算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）
即：
4. 答：由完全二叉树的定义可知，除最后一层外，其他各层的结点是满的。设该完全二叉树有d层，则除最后一层外各层的结点个数分别为：1，2，4，8，16，32，…，即第i层的结点个数为2i-1。这里第8层有8个结点，显然第8/层是最后的一层，那么第7层的结点个数为27-1=64个，其中的4个结点有8个叶子结点，余下的为叶子结点，个数为64-4=60，所以该完全二叉树的叶子结点个数为60+8=68个。 5. 答：对应的二叉树形式如图所示：
作业题四参考答案： 一、单项选择题
1. A 2. B 3. D 4. B 5. D
数据结构专升本模拟题及参考答案
