全部科目 > 软件设计师 >
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




 
 
相关试题     计算机软件知识 

  第4题    2010年下半年  
设用2KX4位的存储器芯片组成16KX8位的存储器（地址单元为0000H~3FFFH，每个芯片的地址空间连续)，则地址单元0B1FH所在芯片的最小地址编号为（4)。

  第64题    2017年上半年  
某汽车加工工厂有两条装配线L1和L2，每条装配线的工位数均为n（Sij，i=1或2，j= 1，2，...，n），两条装配线对应的工位完成同样的加工工作，但是所需..

  第15题    2024年下半年  
数据的物理独立性和逻辑独立性分别是通过修改（51）来完成的。

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



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

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