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

admin2016-05-10 48

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

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

答案D

解析本题考查快速排序算法。快速排序算法是应用最为广泛的排序算法之一。其基本思想是将n个元素划分为两个部分：一部分元素值小于某个数；另一部分元素值大于某个数，该数的位置确定；然后进一步划分前面部分和后面部分。根据该叙述，可以知道，这里采用的是分治算法设计策略。
由于已知划分操作的时间复杂度为Θ(n)，不需要合并子问题的答案。对于最好的情况，应该是每次划分都把n个元素划分为大约2个n／2个元素的子数组，此时T(n)=2T(n／2)+Θ(n)
解该递归式，可得时间复杂度为Θ(nlgn)。若刚好划分的极度不均衡，即每个划分刚好把n个元素划分为一边0个元素，一边n—1个元素，此时
T(n)=T(n一1)+Θ(n)
解该递归式，可得时间复杂度为Θ(n²)。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

FDDI与Token　Ring的MAC帧格式较为相似，分为上(1)两种，在它们的MAC帧中(2)。在编码方面，FDDI采用的编码方式是(3)，编码效率为(4)，而Token　Ring采用的编码方式是(5)，编码效率为(6)。

系统中有R类资源m个，现有n个进程互斥使用。若每个进程对R资源的最大需求为w，那么当m、n、w取下表的值时，对于表2．2中的a～e五种情况，()两种情况可能会发生死锁。

如果希望别的计算机不能通过ping命令测试服务器的连通情况，可以(1)。如果希望通过默认的Telnet端口连接服务器，则下面对防火墙配置正确的是(2)。(2008年上半年试题)(2)

若工作站不带磁盘，无法上网登录主机，注意到这种情况，当启动时把硬件地址送到主机，但主机拒绝它们，这是因为__________协议没有工作。

基尔霍夫定律是直流电路的定律，对于交流电路是不能应用的。（）

有程序段如下：MOVBL，96HMOVAL，BLMOVCL，1SHRAL，CLMOVBH，ALANDBL，OFHINT3程序执行后

A．酸溶血试验阳性B．抗人球蛋白试验阳性C．高铁血红蛋白还原试验异常D．血红蛋白电泳异常溶血性贫血确定病因：葡萄糖6-磷酸脱氢酶缺乏症

金融界按资金借贷期限长短把金融市场分为()。

(2006年真题)下列关于法治的表述，正确的有

模板对类型的参数化提供了很好的支持，因此()。

(1)ScarlettrecalledbitterlyherconversationwithGrandmaFontaine.Onthatafternoontwomonthsago,whichnowseemedyears

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

软考中级

FDDI与Token Ring的MAC帧格式较为相似，分为上(1)两种，在它们的MAC帧中(2)。在编码方面，FDDI采用的编码方式是(3)，编码效率为(4)，而Token Ring采用的编码方式是(5)，编码效率为(6)。

系统中有R类资源m个，现有n个进程互斥使用。若每个进程对R资源的最大需求为w，那么当m、n、w取下表的值时，对于表2．2中的a～e五种情况，()两种情况可能会发生死锁。

如果希望别的计算机不能通过ping命令测试服务器的连通情况，可以(1)。如果希望通过默认的Telnet端口连接服务器，则下面对防火墙配置正确的是(2)。(2008年上半年试题)(2)

若工作站不带磁盘，无法上网登录主机，注意到这种情况，当启动时把硬件地址送到主机，但主机拒绝它们，这是因为__________协议没有工作。

基尔霍夫定律是直流电路的定律，对于交流电路是不能应用的。（）

有程序段如下：MOVBL，96HMOVAL，BLMOVCL，1SHRAL，CLMOVBH，ALANDBL，OFHINT3程序执行后

A．酸溶血试验阳性B．抗人球蛋白试验阳性C．高铁血红蛋白还原试验异常D．血红蛋白电泳异常溶血性贫血确定病因：葡萄糖6-磷酸脱氢酶缺乏症

金融界按资金借贷期限长短把金融市场分为()。

(2006年真题)下列关于法治的表述，正确的有

模板对类型的参数化提供了很好的支持，因此()。

(1)ScarlettrecalledbitterlyherconversationwithGrandmaFontaine.Onthatafternoontwomonthsago,whichnowseemedyears

FDDI与Token　Ring的MAC帧格式较为相似，分为上(1)两种，在它们的MAC帧中(2)。在编码方面，FDDI采用的编码方式是(3)，编码效率为(4)，而Token　Ring采用的编码方式是(5)，编码效率为(6)。