数据结构专升本模拟题及参考答案

C 1 4 G 2 F （5） （6） B C 5 1

G 2 F A 3 D E A 3 6 D B C 1 5 4 G 2 F 4

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、 ?log2k?+1 4、25 5、N-1

6、最优二叉树，最小的二叉树 7、根结点，各子树 三、应用题

1、

答：不唯一，型对即可22 9 13

6 7 3 4 1 2

此树的带权路径长度WPL =9*1+6*2+4*3+(1+2)*4=45 2、 答：

（1）插入10 (2) 插入6 (3) 插入6 3 (4)

（5）插入2 （6）插入5 （7）插入4 （8） 2 3 6 10 2 3 10 5 6 3 10 6 2 4 10 5 3 6 6 10 10 10 6 调3 10 2 调

5 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