下列选项中,不可能是快速排序第2趟排序结果的是()
A.2,3,5,4,6,7,9
B.2,7,5,6,4,3,9
C.3,2,5,4,7,6,9
D.4,2,3,5,7,6,9
参考答案:C
答案解析:快排...
用户登录可进行刷题及查看答案
答案解析:快排的阶段性排序结果的特点是,第 i 趟完成时,会有 i 个以上的数出现在它最终将要出现的位置,即它左边的数都比它小,它右边的数都比它大。题目问第二趟排序的结果,即要找不存在 2 个这样的数的选项。A 选项中 2、3、6、7、9 均符合,所以 A 排除;B选项中,2、9 均符合,所以 B 排除;D 选项中 5、9 均符合,所以D选项排除;最后看C选项,只有9一个数符合,所以C不可能是快速排序第二趟的结果。
其它方法
第一步:
检查快速排序,首先利用快速排序的性质,快速排序每一趟至少能够保证一个元素落在最终位置,即枢轴一定落在最终位置。这里进行了两趟快速排序,至少两个元素落在最终位置。
我们求出排好序后的序列为:2, 3, 4, 5, 6, 7, 9,然后依次和四个选项进行比对,看有没有不符合要求的。
A中有5个落位,待定。
B中有2个落位,待定。
C中有1个落位,错误。
D中有2个落位,待定。
由于这里C选项已经确定错误,无需进行第二步。
第二步是判断枢轴左边元素是否都小于枢轴,右边元素是否都大于枢轴。
第三步是画出序列对应的递归树,判断是否为快速排序的递归树。
本题过于简单,到第一步就结束了。
本题选C。
登录后提交答案
暂无评论,来抢沙发