全部科目 > 软件设计师 >
2009年下半年 上午试卷 综合知识
第 65 题
知识点 快速排序  
章/节 计算机软件知识  
 
 
以下关于快速排序算法的描述中，错误的是（64)。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成，则初始排列为(65) 时，排序效率最高（令序列的第一个元素为基准元素）。
 
  A.  45,12,30,25,67,52,85
 
  B.  85,67,52,45,30,25,12
 
  C.  12,25,30,45,52,67,85
 
  D.  45,12,25,30,85,67,52




 
 
相关试题     计算机软件知识 

  第60题    2010年下半年  
某一维数组中依次存放了数据元素15, 23, 38, 47, 55, 62, 88, 95, 102, 123, 采用折半（二分）法查找元素95时，依次与（60)进行了比较。

  第6题    2023年下半年  
已知一个二叉树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、 ④、③、⑤，则该二叉树的后序遍历序列为（57)。对于任意一棵二叉树，叙述错误的是..

  第40题    2021年上半年  
最大尺寸和问题描述为，在n个整数(包含负数)的数组A中，求之和最大的非空连续子数组,如数组A=(-2,11,-4,13,-5,-2) ，其中子数组B=(11,-4,13)具有最大子段和20(11..

 
知识点讲解
· 快速排序
 
        快速排序
        快速排序的基本思想是：通过一趟排序将待排的记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。
        具体做法是：附设两个指针low和high，它们的初值分别指向文件的第一个记录和最后一个记录。设枢轴记录的关键字为Pivotkey，则首先从high所指位置起向前搜索，找到第一个关键字小于Pivotkey的记录并与枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于Pivotkey的记录并与枢轴记录相互交换，重复这两步直至low=high为止。
        在所有同数量级(O(nlog2n))的排序方法中，快速排序被认为是平均性能最好的一种，但是，若初始记录序列按关键字有序或基本有序时，快速排序将退化为冒泡排序，此时算法的时间复杂度为O(n2)。



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2026 All Rights Reserved
软考在线版权所有