快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了_______算法

admin2019-07-12 51

问题快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了_______算法设计策略。已知确定着基准元素操作的时间复杂度为O(n)，则快速排序算法的最好和最坏情况下的时间复杂度为_______ 。
(62)

选项 A、O(n)和O(nlgn)
B、O(n)和O(n²)
C、O(nlgn)和O(nlgn)
D、O(nlgn)和O(n²)

答案D

解析将数据分成若干份，每份单独处理后再合并，其思想为分治。理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O(nlgn)。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为0(n)，n次操作的总复杂度为O(n²)。

转载请注明原文地址:https://www.kaotiyun.com/show/m2CZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

在存储体系中位于主存与CPU之间的高速缓存(Cache)用于存放主存中部分信息的副本，主存地址与Cache地址之间的转换工作________________。

ATM网络采用了许多通信量管理技术以避免拥塞的出现，其中(34)是防止网络过载的第一道防线。

某文件系统采用位示图(bitmap)记录磁盘的使用情况。若计算机系统的字长为64位，磁盘的容量为1024G，物理块大小为4MB，那么位示图的大小需要()个字。

软件开发中的瀑布模型典型地刻画了软件生存周期的阶段划分，与其最相适应的软件开发方法是(9)。

简述社会规律的客观性。

与Ⅱ型超敏反应无关的成分是

患者，男，39岁，症见肢体筋脉挛痛，关节屈伸不利，疼痛游走不定，腰腿沉重，恶风，舌暗淡，脉沉迟。治疗宜选用

有一台6kW的三相异步电动机，其额定运行转速为1480r／min，额定电压为380V，全压起动转矩是额定运行转矩的1．2倍，现采用△一起动以降低其起动电流，此时的起动转矩为()N．m。

根据增值税法律制度的规定，下列行为中，应视同销售货物，征收增值税的有()。

下面程序的输出结果是【】。　　#include＜stdio．h＞　　main()　　{char*p={"BOOL""OPK"，"H"，"SP"}；　　　inti；　　　for(i=3，i＞＝0；i--，i--)pri

A、Hewillmissthetrain.B、Hewillgetupearlier.C、Hewillnotgotoschool.A此段对话中男方说的是：天啊，只剩两分钟了，我赶不上火车了。女方说的是：下次你应该早点起床。由此

【M1】Applicationfilesarepiledhighlythismonthincollegesacrossthecountry.【M2】Admissionsofficersareporing

软件设计师上午基础知识考试

软考中级

在存储体系中位于主存与CPU之间的高速缓存(Cache)用于存放主存中部分信息的副本，主存地址与Cache地址之间的转换工作________________。

ATM网络采用了许多通信量管理技术以避免拥塞的出现，其中(34)是防止网络过载的第一道防线。

某文件系统采用位示图(bitmap)记录磁盘的使用情况。若计算机系统的字长为64位，磁盘的容量为1024G，物理块大小为4MB，那么位示图的大小需要()个字。

软件开发中的瀑布模型典型地刻画了软件生存周期的阶段划分，与其最相适应的软件开发方法是(9)。

简述社会规律的客观性。

与Ⅱ型超敏反应无关的成分是

患者，男，39岁，症见肢体筋脉挛痛，关节屈伸不利，疼痛游走不定，腰腿沉重，恶风，舌暗淡，脉沉迟。治疗宜选用

有一台6kW的三相异步电动机，其额定运行转速为1480r／min，额定电压为380V，全压起动转矩是额定运行转矩的1．2倍，现采用△一起动以降低其起动电流，此时的起动转矩为()N．m。

根据增值税法律制度的规定，下列行为中，应视同销售货物，征收增值税的有()。

下面程序的输出结果是【】。 #include＜stdio．h＞ main() {char*p={"BOOL""OPK"，"H"，"SP"}； inti； for(i=3，i＞＝0；i--，i--)pri

A、Hewillmissthetrain.B、Hewillgetupearlier.C、Hewillnotgotoschool.A此段对话中男方说的是：天啊，只剩两分钟了，我赶不上火车了。女方说的是：下次你应该早点起床。由此

【M1】______Applicationfilesarepiledhighlythismonthincollegesacrossthecountry.【M2】______Admissionsofficersareporing

下面程序的输出结果是【】。　　#include＜stdio．h＞　　main()　　{char*p={"BOOL""OPK"，"H"，"SP"}；　　　inti；　　　for(i=3，i＞＝0；i--，i--)pri

【M1】Applicationfilesarepiledhighlythismonthincollegesacrossthecountry.【M2】Admissionsofficersareporing