以下关于快速排序算法的描述中，错误的是( )。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12，25，30，45，52，67，85}构成，则初始排列为( )时，排序效率最高(令序列的第一个元素为基准元素)。

admin2010-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(²)在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)

转载请注明原文地址:https://www.kaotiyun.com/show/QaxZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

以下关于快速排序算法的描述中，错误的是( )。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12，25，30，45，52，67，85}构成，则初始排列为( )时，排序效率最高(令序列的第一个元素为基准元素)。

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

软考中级

一名攻击者向一台远程主机发送特定的数据包，但是不想远程主机响应这个数据包。它采用的攻击手段可能是(63)。

公钥密码是(39)。常用的公钥加密算法有(40)，它可以实现加密和数字签名，它的一个比较知名的应用是(41)，这种应用的协商层用公钥方式进行身份认证，记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。

《计算机软件产品开发编制指南》(GB8567-1988)是(10)标准。

下列对通道的描述中，错误的是(6)。

E1载波的基本帧由32个子信道组成，其中30个子信道用于传送话音数据，2个子信道()用于传送控制信令，该基本帧的传送时间为()。

以下关于CPIj的叙述中，错误的是()。

在RMON管理信息系统库中，矩阵组存储的信息是()。

石墨炉原子吸收法测定肉、蛋制品中的镉时，使用的基体改进剂为磷酸铵溶液。

呼吸链中的递氢体是呼吸链中以铁卟啉为辅基的单电子传递体是

依次填入文中横线处的语句，顺序恰当的一项是：“土豪”二字重点在“土”，重外在、喜奢华、好显摆，表达着一种与富裕的经济状况不相匹配的素质修养、行事风格以及外在气质。_____。_。_，_____是一种来自骨子

防护区的划分应根据封闭空间的结构特点和位置来划分，其中防护区围护结构及门窗的耐火极限均不宜低于()h。

会计人员如果泄露本单位的商业机密，可能导致的后果将会是()。

保险合同是()与保险人约定权利义务关系的协议。

职位评价主要是为了解决()。

数据库设计的需求分析阶段，业务流程一般采用()表示。