首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61)
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61)
admin
2016-05-10
41
问题
快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61) 算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n),则快速排序算法的最好和最坏情况下的时间复杂度为 (62) 。
(62)
选项
A、Θ(n)和Θ(nlgn)
B、Θ(n)和Θ(n
2
)
C、Θ(nlgn)和Θ(nlgn)
D、Θ(nlgn)和Θ(n
2
)
答案
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
2
)。
转载请注明原文地址:https://kaotiyun.com/show/KkRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
ATM网络的协议数据单元称为(36)。ATM适配层分为(37)两个子层。(38)是对应于A类业务的ATM适配层,它提供的业务特点是(39)。如果要传送IP数据报,则需要(40)业务的支持。
RS-232C是(11)之间的接口标准,它是(12)协议,其机械特性规定RS-232C的D型连接器有(13)个插脚,使用RS-232C接口进行数据通信时,至少需用的信号线有(14)。当Modem和计算机相连时,按此标准需要连接的最少线数是(15)。
为了进行差错控制,必须对传送的数据帧进行校验。在局域网中常采用的校验技术是(6)。CRC-CCITT的生成多项式是(7);假设一个CRC生成多项式为G(X)=4+X+1,要发送的信息码为101011,则算出的CRC校验码为(8)。假设采用的生成多项式为 G
在带宽为3 kHz且没有噪声的信道中,传输二进制信号能够达到的极限数据数率为(81)。而在一个带宽为3 kHz信噪比为30dB的信道中,其极限数据传输率为(82)。由此可知(83)。由奈奎斯特第一定理,为了保证传输质量,达到3kb/s的数据传输率需要的带宽
Linux是使用最为广泛得网络操作系统之一。在linux网络配置文件中有几个较为重要的配置文件:用于存放本机主机名以及经常访问IP地址的主机名的是(34)。Linux下存在两个网络服务守候进程的配置文件。通过修改(35),可以达到关闭或开放某种对应服务的目
下面叙述中正确的是(16)。不是进程调度时机的是(17)。多道程序系统中,当(18)时,进程从执行状态转变为就绪状态。系统中有4个并发进程,都需要某类资源3个。试问该类资源最少为(19)个时,不会因竞争该资源而发生死锁。若P/V操作的信号量S的初值为3,则
依据著作权法,计算机软件著作权保护的对象是指(3)。
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句写在对应栏内。[预备知识]①对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句填写完整。[说明](1)对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d)及其权值2、7、4、5,可构造如
(43)设计模式将抽象部分与它的实现部分相分离,使它们都可以独立地变化。下图为该设计模式的类图,其中,(44)用于定义实现部分的接口。
随机试题
治疗甘温除热的代表方是
骨盆腔是指
足少阳胆经位于小腿部的穴位,在腓骨前缘的是
总承包单位甲公司将其承揽的部分专业工程依法分包给乙公司,分包合同约定,如因施工问题导致建设单位索赔,双方各自承担索赔额的50%。由于专业工程施工过程中出现了严重事故隐患,甲公司要求乙公司停工整改,但乙公司以保证施工进度为由迟迟不予整改,最终导致重大生产安全
基金管理人必须按规定对基金净资产进行估值,基金无权暂停估值的情形是()。
目前我国银行间债券交易的结算主要采用()。[2015年12月真题]
旅游安全事故的处理原则是()。
公民在受到()侵害时,可以针对行政机关提起人身权的国家赔偿。
The data station usually means a(71)unit that provides data for transmission, that accepts transmitted data, and that performs a
A、Itlacksthestabilityoftheprintedword.B、Itcontainsmanygrammaticalerrors.C、Itisheavilydependentonthecontext.D
最新回复
(
0
)