首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
以下关于快速排序算法的描述中,错误的是( )。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成,则初始排列为( )时,排序效率最高(令序列的第一个元素为基准元素)。
以下关于快速排序算法的描述中,错误的是( )。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成,则初始排列为( )时,排序效率最高(令序列的第一个元素为基准元素)。
admin
2010-05-08
66
问题
以下关于快速排序算法的描述中,错误的是( )。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成,则初始排列为( )时,排序效率最高(令序列的第一个元素为基准元素)。
选项
A、快速排序算法是不稳定的排序算法
B、快速排序算法在最坏情况下的时间复杂度为0(nlgn)
C、快速排序算法是一种分治算法
D、当输入数据基本有序时,快速排序算法具有最坏情况下的时间复杂度
答案
B
解析
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。因此,快速排序必须做n-1次划分,第i次划分开始时区间长度为n-i+1,所需的比较次数为n-i(1≤i≤n-1),故总的比较次数达到最大值:c
max
=n(n-1)/2=O(
2
)在最好情况下,每次划分所取的基准都是当前无序区的“中值”记录,划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数:O(nlgn)
转载请注明原文地址:https://www.kaotiyun.com/show/QaxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
采用可变长子网掩码VLSM技术可以把大的网络分成小的子网,例如把子网掩码为255.255.0.0的网络40.15.0.0分为两个子网,假设第一个子网为40.15.0.0/17,则第二个子网为(28)。假设用户X1有2000台主机,则至少应给他分配(29)
UML提供了一系列的图支持面向对象的分析与设计,其中(13)给出系统的静态设计视图;(14)对系统的行为进行组织和建模是非常重要的;(15)和(16)都是描述系统动态视图的交互图,其中(15)描述了以时间顺序组织的对象之间的交互活动,(16)强调收发消息的
在ISDN网络中,与ISDN交换机直接相连的是(32)设备,他们通过(33)实现互连。NT1到用户设备之间的连接点是(34)。对于非ISDN设备要通过(35)设备接入ISDN网络,该设备的主要作用是(36)。
在ISDN网络中,与ISDN交换机直接相连的是(32)设备,他们通过(33)实现互连。NT1到用户设备之间的连接点是(34)。对于非ISDN设备要通过(35)设备接入ISDN网络,该设备的主要作用是(36)。
保留给自环测试的IP地址是(27)。
SDLCwasinventedbyIBMtoreplacetheolderBisynchronousprotocolforwideareaconnectionsbetweenIBMequipment.Avarieti
回答以下问题。若设置域名解析服务器,已知该文件服务器上文件named.boot的内容如下:Directory/var/namedCachenamed.rootPrimary0.0.127in-addr.arpanamed
局域网中使用的传输介质有双绞线、同轴电缆和光纤等。10BASE-T采用3类UTP,规定从收发端到有源集线器的距离不超过(44)m。100BASE-TX把数据传输速率提高了10倍,同时网络的覆盖范围(45)。假设tPHY表示工作站的物理层时延,c表示光速,s
图3-2是该系统类图的一部分,依据上述说明中给出的术语,给出类Lock的主要属性。组装(composition)和聚集(aggregation)是UML中两种非常重要的关系。请说明组装和聚集分别表示什么含义?两者的区别是什么?
随机试题
A.G细胞B.A细胞C.D1细胞D.D细胞E.PP细胞分泌生长抑素的是
患者女,50岁。血肌酐P为86.8μmol/L,尿肌酐U为4390μmol/L,24小时尿量为1600ml。则内生肌酐清除率为
哺乳期妇女最好不用的药是()
国家重力控制测量不包括()。
随着宏观经济调控政策的逐步落实,我国经济增速会适度放缓,对石油、天然气资源的需求有所减少,供求矛盾在一定程度上将得到缓解。根据国际能源署的最新预测,今年我国原油产量将达1.75亿吨,比去年增长1%;而原油消费量将有可能突破3亿吨,比去年增长12%左右;进口
下列关于我国改革开放中的对内改革,说法错误的一项是()。
简述环境污染责任的构成要件和归责原则。
A、 B、 C、 D、 D
GoldStarPropertyRentalsStudioApartmentsNowAvailable!AstheCEOofGoldStar,Iamproudtoannounc
中国国画的根源可以追溯到新石器时代的陶器(Neolithicpottery),比如鱼、青蛙、鹿、鸟、花、树叶的形状。最早的中国汉字是象形文字(pictograph)。由于相似的工具被使用于最早期的绘画和书写,绘画被认为是与书法(calligraphy)有
最新回复
(
0
)