1、2008 年中国科技大学计算机专业基础综合（数据结构）真题试卷及答案解析(总分：26.00，做题时间：90 分钟)一、单项选择题(总题数：5，分数：10.00)1. （分数：2.00）_2. （分数：2.00）_3. （分数：2.00）_4. （分数：2.00）_5. （分数：2.00）_二、简答题(总题数：4，分数：8.00)6. （分数：2.00）_7. （分数：2.00）_8. （分数：2.00）_9. （分数：2.00）_三、计算题(总题数：3，分数：6.00)10. （分数：2.00）_12. （分数：2.00）_四、设计题(总题数：1，分数：2.00)13. （分数：2.00）_2
2、008 年中国科技大学计算机专业基础综合（数据结构）真题试卷答案解析(总分：26.00，做题时间：90 分钟)一、单项选择题(总题数：5，分数：10.00)1. （分数：2.00）_解析：2. （分数：2.00）_解析：3. （分数：2.00）_解析：4. （分数：2.00）_解析：5. （分数：2.00）_解析：二、简答题(总题数：4，分数：8.00)6. （分数：2.00）_正确答案：(正确答案：不是。因为简单插入排序算法的运行时间与数据的分布有关。在最理想的情况其运行时间为 O（n），优于相同情况下归并排序算法的运行时间。)解析：7. （分数：2.00）_正确答案：(正确答案：一棵有 1
3、9 个关键字的 3 阶 B 一树至少有 11 个非叶节点。)解析：8. （分数：2.00）_正确答案：(正确答案：合理的出栈序列共有 42 种。)解析：9. （分数：2.00）_正确答案：(正确答案：1088)解析：三、计算题(总题数：3，分数：6.00)10. （分数：2.00）_正确答案：(正确答案：Next112=0,1,1,1,2,3,4,1,2,3,4,5。)解析：_正确答案：(正确答案：1 至 2 距离为 1；1 至 3 距离为 2；1 至 4 距离为 3；1 至 5 距离为 1；1 至 6 距离为 2；1 至 7 距离为 4；1 至 8 距离为 3。)解析：12. （分数：2.00）_正确答案：(正确答案：在等概率情况下查找成功时关键字的平均比较次数为 14/10=1.4)解析：四、设计题(总题数：1，分数：2.00)13. （分数：2.00）_正确答案：(正确答案： )解析：
