2. 从业资格
  3. 以下关于快速排序算法的描述中，错误的是（　　）。在快速排序过程中，需要设立基准元

以下关于快速排序算法的描述中，错误的是（　　）。在快速排序过程中，需要设立基准元

考试题库2022-08-02  63
问题 以下关于快速排序算法的描述中，错误的是（　　）。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素｛12，25，30，45，52，67，85｝构成，则初始排列为（　　）时，排序效率最高（令序列的第一个元素为基准元素）。问题1选项A.快速排序算法是不稳定的排序算法B.快速排序算法在最坏情况下的时间复杂度为O(nlgn)C.快速排序算法是一种分治算法D.当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度问题2选项A.45，12，30，25，67，52，85B.85，67，52，45，30，25，12C.12，25，30，45，52，67，85D.45，12，25，30，85，67，52
选项
答案 BA
解析 本题考查快速排序算法。
快速排序算法是一种经典的排序算法，其基本思想是选择一个基准元素（通常选择第一个元素或者最后一个元素），通过一趟排序将待排序序列分成两部分，一部分比基准元素小，一部分大于等于基准元素，此时基准元素在其排好序后的正确位置；然后再递归地排序划分的两部分，因此本质上快速排序是一种分治算法。由于在排序的过程中，各元素与基准元素比较大小，若小于基准元素则与基准元素交换位置，因此该算法是不稳定的排序算法。当每一趟排序进行后，选择的基准元素恰好最大或者最小时，就把序列分成极端不均衡的两部分，即一部分为空，另一部分为待排序序列的元素个数减1，此时算法处于最坏情况，其时间复杂度为O（n2）。当输入数据基本有序或者所有元素值相等时，不论选择第一个元素还是最后一个元素作为基准元素，都恰好把序列分成极端不均衡的两部分，快速排序算法具有最坏情况下的时间复杂度。
对于选项A，以45作为基准元素进行第一趟划分，先从后向前找出比45小的元素，67、52、85这三个元素保持不动，找到25，将其与45交换后，第一趟划分完成，序列为25，12，30，45，67，52，85。第二趟先对子序列25，12，30进行划分，使得25与12对调，形成子序列12，25，30；然后对67，52，85进行划分，使得67与52交换，形成子序列52，67，85。至此，整个排序过程完成。期间，第一趟划分中元素的比较次数为6次、交换1次，第二趟划分中元素的比较次数共4次、交换次数为2次，因此，排序过程中比较次数共10次，交换次数为3次。
对于选项B，以85作为基准元素，因12比它小，所以将85与12交换，由于剩下的元素都比85小，因此保持不动，第一趟划分之后的元素序列为12，67，52，45，30，25，85，期间元素比较次数为6次、交换1次，第二趟对85之前的6个元素进行划分，由于67、52、45、30、25都比基准元素12大，因此它们保持不动，完成第二趟划分，形成的子序列为12，67，52，45，30，25，期间比较次数为5、交换次数为0。接下来第三趟对子序列67，52，45，30，25进行划分，以67为基准元素，情况与第一趟相同，进行4次比较、l次交换后，形成子序列25，52，45，30，67。第四趟对子序列25，52，45，30进行划分，情况与第二趟相同。依此类推，完成排序时比较次数为21次（6＋5＋4＋3＋2＋1）。
对于选项C，以12作为基准元素，因为后面的所有元素都比它大，所以所有元素是持不动，第一趟划分之后的元素序列为12，25，30，45，52，67，85，期间元素比较次数为6次、交换0次。第二趟对子序列25，30，45，52，67，85进行划分，以25作为基准元素，因为后面的所有元素都比它大，所以所有元素保持不动，第一趟划分之后的元素序列为25，30，45，52，67，85，期间元素比较次数为5次、交换0次。接下来对子序列30，45，52，67，85进行划分，同理，元素保持不动，期间元素比较次数为4次、交换0次。依此类推，完成整个排序比较次数为21次、交换0次。
对于选项D，以45作为基准元素进行第一趟划分，先从后向前找出比45小的元素，85、67、52这三个元素保持不动，找到30，将其与45交换后，第一趟划分完成，序列30，12，25，45，85，67，52，期间元素比较次数为6次、交换1次。第二趟先对子序列30，12，25进行划分，以30为基准元素，30与25交换，经过2次比较、1次交换后子序列为25，12，30，需要再次对子序列25，12进行划分；同理，对子序列85，67，52进行划分后，结果为51，67，87，还需对子序列51，67进行划分。排序过程中比较次数共12次。
转载请注明原文地址:https://tihaiku.com/congyezige/2409865.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)