首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
以下关于快速排序算法的描述中,错误的是( )。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成,则初始排列为( )时,排序效率最高(令序列的第一个元素为基准元素)。
以下关于快速排序算法的描述中,错误的是( )。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成,则初始排列为( )时,排序效率最高(令序列的第一个元素为基准元素)。
admin
2010-05-08
41
问题
以下关于快速排序算法的描述中,错误的是( )。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{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://kaotiyun.com/show/QaxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
对欲访问特定信息的发起者的身份或者对传送的报文完整性进行合法性审查或核实的行为称为(50)。在日常生活中,我们可以用手写签名来防止否认的发生。在计算机通信中,要解决这类问题,可采用的方法是(51)。关于客户/服务器应用模式,说法正确的是(52)。在理论上,
在FDM中,主要通过(37)技术,使各路信号的带宽(38)。使用FDM的所有用户(39)。从性质上说,FDM比较适合于传输(40),FDM的典型应用是(41)。
采用可变长子网掩码VLSM技术可以把大的网络分成小的子网,例如把子网掩码为255.255.0.0的网络40.15.0.0分为两个子网,假设第一个子网为40.15.0.0/17,则第二个子网为(28)。假设用户X1有2000台主机,则至少应给他分配(29)
在ISDN网络中,与ISDN交换机直接相连的是(32)设备,他们通过(33)实现互连。NT1到用户设备之间的连接点是(34)。对于非ISDN设备要通过(35)设备接入ISDN网络,该设备的主要作用是(36)。
ODQDB同时支持(33)两种服务。DQDB子网的双总线结构由(34)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(35)访问控制方式,其中能够提供非等时服务是(36),它用于(37)业务。
软件能力成熟度模型CMM(CapabilityMaturityModel)描述和分析了软件过程能力的发展与改进的程度,确立了一个软件过程成熟程度的分级标准。在初始级,软件过程定义几乎处于无章可循的状态,软件产品的成功往往依赖于个人的努力和机遇。在(7)
在Windowseel_行()命令后得到如下图所示的结果。如果要将目标地址为102.217.112.0/24的分组经102.217.115.1发出,需增加一条路由,正确的命令为()。
在Windowseel_行()命令后得到如下图所示的结果。如果要将目标地址为102.217.112.0/24的分组经102.217.115.1发出,需增加一条路由,正确的命令为()。
阅读下列说明和图,回答问题1至问题3。【说明】图书管理系统详细记录图书库存情况、读者信息及读者借阅记录(包括借书日期和还书日期)。新书入库时要为该书编制图书卡片,包括分类目录号、图书流水号(要保证每本书都有唯一的流水号,即使同类图书
随机试题
噪声会导致头痛、头晕、失眠、多梦等。
只能用于心源性哮喘,不能用于支气管哮喘的药物是
下述关于心悸叙述中哪项不恰当
能初步完成循环、呼吸等基本生命现象反射调节的部位是
男性,10岁,1年来尿频、尿急、尿痛和排尿困难,尿流突然中断,改变体位又能继续排尿,应首先考虑
根据《宪法》规定,关于行政建置和行政区划,下列选项正确的是:(2014年卷一96题)
估计总体参数时,评价估计量的三个常用标准是()。[2016年、2010年中级真题]
下列童话故事不属于安徒生童话的是()。
求级数的和.
Oneafternoonrecently,twounrelatedfriendscalledtotellmethat,well,theirmarriages【B1】______.Onewasleavinghiswife
最新回复
(
0
)