首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
以下关于快速排序算法的描述中,错误的是( )。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成,则初始排列为( )时,排序效率最高(令序列的第一个元素为基准元素)。
以下关于快速排序算法的描述中,错误的是( )。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成,则初始排列为( )时,排序效率最高(令序列的第一个元素为基准元素)。
admin
2010-05-08
67
问题
以下关于快速排序算法的描述中,错误的是( )。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{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
软件设计师上午基础知识考试
软考中级
相关试题推荐
一名攻击者向一台远程主机发送特定的数据包,但是不想远程主机响应这个数据包。它采用的攻击手段可能是(63)。
公钥密码是(39)。常用的公钥加密算法有(40),它可以实现加密和数字签名,它的一个比较知名的应用是(41),这种应用的协商层用公钥方式进行身份认证,记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。
在计算机指令系统中,通常采用多种确定操作数的方式。当操作数直接给出时,这种寻址方式叫作(2);当操作数的地址由某个指定的变址寄存器的内容与位移量相加得到时,叫作(3);如果操作数的地址是主存中与该指令地址无关的存储单元的内容,叫作(4)。
《计算机软件产品开发编制指南》(GB8567-1988)是(10)标准。
下列对通道的描述中,错误的是(6)。
软件能力成熟度模型CMM(CapabilityMaturityModel)描述和分析了软件过程能力的发展与改进的程度,确立了一个软件过程成熟程度的分级标准。在初始级,软件过程定义几乎处于无章可循的状态,软件产品的成功往往依赖于个人的努力和机遇。在(7)
在使用路由器R的TCP/IP网络中,两主机通过一路由器互联,提供主机A和主机B应用层之间通信的层是(52),提供机器之间通信的层是(53),具有IP层和网络接口层的设备(54);在A与R和R与B使用不同物理网络的情况下,主机A和路由器R之间传送的数据帧与路
E1载波的基本帧由32个子信道组成,其中30个子信道用于传送话音数据,2个子信道()用于传送控制信令,该基本帧的传送时间为()。
以下关于CPIj的叙述中,错误的是()。
在RMON管理信息系统库中,矩阵组存储的信息是()。
随机试题
石墨炉原子吸收法测定肉、蛋制品中的镉时,使用的基体改进剂为磷酸铵溶液。
呼吸链中的递氢体是呼吸链中以铁卟啉为辅基的单电子传递体是
依次填入文中横线处的语句,顺序恰当的一项是:“土豪”二字重点在“土”,重外在、喜奢华、好显摆,表达着一种与富裕的经济状况不相匹配的素质修养、行事风格以及外在气质。_________。_________。_________,_________是一种来自骨子
防护区的划分应根据封闭空间的结构特点和位置来划分,其中防护区围护结构及门窗的耐火极限均不宜低于()h。
会计人员如果泄露本单位的商业机密,可能导致的后果将会是()。
保险合同是()与保险人约定权利义务关系的协议。
职位评价主要是为了解决()。
以下为一位教师引导学生赏析《蝶恋花•答李淑一》的教学设计。《蝶恋花•答李淑一》这节课的具体环节是:一、导入:对比北方鼓词和南方弹词的特点,《蝶恋花•答李淑一》。二、听赏:1.介绍音乐背景、思考。2.音乐特点——《蝶恋花•答李淑一》是中华人民共和国后弹
某单位为了建设健全的公路桥梁养护管理档案,拟开发一套公路桥梁在线管理系统。在系统的需求分析与架构设计阶段,用户提出的需求、质量属性描述和架构特性如下:(a)系统用户分为高级管理员、数据管理员和数据维护员等三类;(b)系统应该具备完善的安全防护措施,能够
数据库设计的需求分析阶段,业务流程一般采用()表示。
最新回复
(
0
)