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

admin2016-05-10 28

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

分组交换可以采用虚电路方式或(26)方式实现。虚电路方式在通信前需建立一条虚电路，其路径由(27)决定。每条虚电路都有虚电路号码，该号码(28)。虚电路建立后，各数据分组(29)到达目的地，然后(30)。

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

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

依据《计算机软件保护条例》，对软件的保护包括()。

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用连接存储结构进行存储，root指向根接点，p所指结点为任一给定的结点，编写一个求从根结点到p所指结点之间路径的函数。voidpath(root,p)

甲亢手术后护理措施正确的是()。

蒙古公民高娃因民事纠纷在蒙古某法院涉诉。因高娃在北京居住，该蒙古法院欲通过蒙古驻华使馆将传票送达高娃，并向其调查取证。依中国法律规定，下列哪一选项是正确的？（2016年卷一第39题）

下列属于财政政策优势的是()。

在信用证业务的有关当事人之间，存在契约关系的有()。

下列选项属于行政层级式组织形式的决定因素的有(　　)。

中国人民银行规定3年期的整存整取定期储蓄的年利率是2．7％(不计复利)，按这种方式存入5000元，存期3年，3年到期时必须按利息的20％交纳利息税，则到期后取出的总金额是()元。

旅行社为散客提供的旅游服务类型主要有()。

魏源在《海国图志》、徐继畲在《瀛环志略》中都较详细地介绍了英、法、美等国的资产阶级政治制度，并给予较高评价，新思潮倡导者们这样做()。

DININGOUTAAboyneTheoriginalLuigi’sItalianRestaurantisnowbackinAboyne231BeachRoad,Aboyne(ampleparkingavailabl

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

软考中级

分组交换可以采用虚电路方式或(26)方式实现。虚电路方式在通信前需建立一条虚电路，其路径由(27)决定。每条虚电路都有虚电路号码，该号码(28)。虚电路建立后，各数据分组(29)到达目的地，然后(30)。

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

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

依据《计算机软件保护条例》，对软件的保护包括()。

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]假设二叉树采用连接存储结构进行存储，root指向根接点，p所指结点为任一给定的结点，编写一个求从根结点到p所指结点之间路径的函数。voidpath(root,p)

甲亢手术后护理措施正确的是()。

蒙古公民高娃因民事纠纷在蒙古某法院涉诉。因高娃在北京居住，该蒙古法院欲通过蒙古驻华使馆将传票送达高娃，并向其调查取证。依中国法律规定，下列哪一选项是正确的？（2016年卷一第39题）

下列属于财政政策优势的是()。

在信用证业务的有关当事人之间，存在契约关系的有()。

下列选项属于行政层级式组织形式的决定因素的有( )。

中国人民银行规定3年期的整存整取定期储蓄的年利率是2．7％(不计复利)，按这种方式存入5000元，存期3年，3年到期时必须按利息的20％交纳利息税，则到期后取出的总金额是()元。

旅行社为散客提供的旅游服务类型主要有()。

魏源在《海国图志》、徐继畲在《瀛环志略》中都较详细地介绍了英、法、美等国的资产阶级政治制度，并给予较高评价，新思潮倡导者们这样做()。

DININGOUTAAboyneTheoriginalLuigi’sItalianRestaurantisnowbackinAboyne231BeachRoad,Aboyne(ampleparkingavailabl

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

下列选项属于行政层级式组织形式的决定因素的有(　　)。