题12

题12

题目

Q:下列序列中，（ ） 可能是执行第一趟快速排序后所得到的序列（按从大到小排序和从小到大排序来分别讨论).
I. II.
III. IV.
A. I、IV B. II、III C. III、IV D. 只有 IV

分析

A:判断某个序列是不是快排的某一趟排序结果, 可以看是否有元素处于最终位置。

解

C
显然,若按从小到大排序,则最终有序的序列是 ;
若按从大到小排序,则最终有序的序列是 。
对比可知选项 I、II 中没有处于最终位置的元素, 所以 I、II 项都不可能。
III 项中 73 和 93 处于从大到小排序后的最终位置, 而且 73 将序列分割成大于 73 和小于 73 的两部分, 所以 III 项是有可能的。IV 项中 73 和 93 处于从小到大排列后的最终位置, 73 也将序列分割成大于 73 和小于 73 的两部分。