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

admin2016-05-10 32

问题快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 (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://kaotiyun.com/show/KkRZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

动态主机配置协议DHCP具有(158)机制，这是与BOOTP的主要区别。DHCP协议支持的中继代理(Relay　Asent)是一种(159)，可以在不同的网段之间传送报文。在DHCP的地址分配方案，(160)是最适合移动终端的分配方案。使用Windows2

DES加密算法采用的密码技术是(1)，它采用(2)位密钥对传输的数据进行加密。著名的网络安全系统Kerberos采用的是(3)加密技术。公钥密码是(4)，常用的公钥加密算法有(5)，它可以实现加密和数字签名。

下面关于二级目录的叙述中，错误的是(1)。多级目录结构的特点是(2)。文件系统实现按名存取主要用来实现(3)。文件系统采用二级文件目录可以(4)。为了解决不同用户文件的“命名冲突”问题，通常在文件系统中采用(5)。

配置FTP服务器的属性窗口如图12．16所示，默认情况下“本地路径”文本框中的值为()。

以下()不是影响缺页中断率的因素。

Certificates　are(16)documents　attesting　to　the(17)of　a　public　key　to　an　individual　or　other　entity.　They　allow　verification　of　t

与青霉素合用时可产生拮抗作用的药物是

肾虚型喘证不宜选用

下列除哪项外，均可导致渴不多饮()

易引起严重低血糖不良反应的口服降糖药是

房地产抵押的特征是()。

衡量决策科学化的标准不包括()。

比率指标的类型不包括()。

简述和平共处五项原则的内容及意义。

因不可抗力或者其他正当理由耽误法定行政复议申请期限的，申请期限自障碍消除之日起继续计算。()

无因管理是指没有法律上的义务而管理他人事务的行为。下列行为属于无因管理的是(　)。

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

软考中级

动态主机配置协议DHCP具有(158)机制，这是与BOOTP的主要区别。DHCP协议支持的中继代理(Relay Asent)是一种(159)，可以在不同的网段之间传送报文。在DHCP的地址分配方案，(160)是最适合移动终端的分配方案。使用Windows2

DES加密算法采用的密码技术是(1)，它采用(2)位密钥对传输的数据进行加密。著名的网络安全系统Kerberos采用的是(3)加密技术。公钥密码是(4)，常用的公钥加密算法有(5)，它可以实现加密和数字签名。

下面关于二级目录的叙述中，错误的是(1)。多级目录结构的特点是(2)。文件系统实现按名存取主要用来实现(3)。文件系统采用二级文件目录可以(4)。为了解决不同用户文件的“命名冲突”问题，通常在文件系统中采用(5)。

配置FTP服务器的属性窗口如图12．16所示，默认情况下“本地路径”文本框中的值为()。

以下()不是影响缺页中断率的因素。

Certificates are(16)documents attesting to the(17)of a public key to an individual or other entity. They allow verification of t

与青霉素合用时可产生拮抗作用的药物是

肾虚型喘证不宜选用

下列除哪项外，均可导致渴不多饮()

易引起严重低血糖不良反应的口服降糖药是

房地产抵押的特征是()。

衡量决策科学化的标准不包括()。

比率指标的类型不包括()。

简述和平共处五项原则的内容及意义。

因不可抗力或者其他正当理由耽误法定行政复议申请期限的，申请期限自障碍消除之日起继续计算。()

无因管理是指没有法律上的义务而管理他人事务的行为。下列行为属于无因管理的是( )。

动态主机配置协议DHCP具有(158)机制，这是与BOOTP的主要区别。DHCP协议支持的中继代理(Relay　Asent)是一种(159)，可以在不同的网段之间传送报文。在DHCP的地址分配方案，(160)是最适合移动终端的分配方案。使用Windows2

Certificates　are(16)documents　attesting　to　the(17)of　a　public　key　to　an　individual　or　other　entity.　They　allow　verification　of　t

无因管理是指没有法律上的义务而管理他人事务的行为。下列行为属于无因管理的是(　)。