武汉大学数据结构考试试题(附答案)(3)

8.假定对长度n＝50的有序表进行折半搜索，则对应的判定树高度为 ,判定树中前5层的结点数为 ,最后一层的结点数为 。 9. 假定一组记录的排序码为（46，79，56，38，40，80），对其进行归并排序的过程中，第二趟归并后的结果为____ 。10. 假定一组记录的排序码为（46，79，56，38，40，80），对其进行快速排序的一次划分的结果为____。

三、简答题 1.假定有四个元素A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列？2.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？ 3. 设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用哪种方法最好？为什么？（快速排序，堆排序，基数排序）

一、选择题1. B 2. B 3. C 4. B 5．C 6．B 9．C 10．A 11．B 12. C 13. B 14. C 15. C 16. A 17. C 18. A 19. C

二、填空题1.复杂度 2． 物理结构 ， 逻辑结构 ，算法 , 原来的 3． q-next; 4. 4,3 5. 前驱 ， 后续 6． 线性结构 , 顺序结构 7. 5 8. 5 , 31 , 19 。 9. [38 46 56 79][40 84] 。10. (84,79,56,38,40,46) 。 三、问答题 1.答：共有14种可能的出栈序列为：ABCD, ABDC, ACBD, ACDB, BACD, ADCB, BADC, BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA 2. 答： 显然能达到最大深度的是单支树其深度为n；深度最小的是完全k叉树。

3. 答： 用堆排序最好，因为堆排序不需要等整个排序结束就可挑出前10个最大元素，而快速排序和基数排序都需等待整个排序结束才能知道前10个最大元素。