首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。 A:待排序数组 p,r:数组元素下标,从p到r q:划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。 A:待排序数组 p,r:数组元素下标,从p到r q:划分的位置 x:枢轴元素 i:整型变量,用于描述数组下标。下标小于或等于i的元素
admin
2010-01-15
51
问题
下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。
A:待排序数组
p,r:数组元素下标,从p到r
q:划分的位置
x:枢轴元素
i:整型变量,用于描述数组下标。下标小于或等于i的元素的值,小于或等于枢轴元素的值
j:循环控制变量,表示数组元素下标
(1)假设要排序包含n个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度(用 O记号)。最佳情况为(4),平均情况为(5),最坏情况为(6)。
(2)假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况? (7)。 (最佳、平均、最坏)
选项
答案
这是一道考查快速排序算法时间复杂度的分析题。当每次能作均匀划分时,算法为最佳情况,此时时间复杂度可以通过计算递归式T(n)=2T(n/2)+O(n),得到时间复杂度为O(nlogn)。当每次为极端不均匀划分时,即长度为n的数组划分后一个子数组为n-1,一个为0,算法为最坏情况,此时时间复杂度可以通过计算递归式T(n)=T(n-1)+O(n),得到时间复杂度为O(n2)。 对于平均情况的分析较为复杂,假设数组每次划分为9/10:1/10,此时时间复杂度可以通过计算递归式 T(n)=T(9/10)+T(1/10)+O(n),得到时间复杂度为O(nlogn),因此在平均情况下快速排序仍然有较好的性能,时间复杂度为O(nlogn)。 当所有的n个元素具有相同的值时,可以认为数组已经有序,此时每次都划分为长度为n-1和0的两个子数组,属于最坏情况。
解析
转载请注明原文地址:https://kaotiyun.com/show/a0DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
计算机的用途不同,对其部件的性能指标要求也有所不同。以科学计算为主的计算机,对(1)要求较高,而且应该重点考虑(2)。
设有学生实体Students(学号,姓名,性别,年龄,家庭住址,家庭成员,关系,联系电话),其中“家庭住址”记录了邮编、省、市、街道信息;“家庭成员,关系,联系电话”分别记录了学生亲属的姓名、与学生的关系以及联系电话。学生实体Students中的“
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则里程碑(49)没有按时完成会影响整个项目的进度。若活动0→2完成后,停止3天才开始活动2→6,则完成整个项目的最少时间是(50)天。(50)
下图为某设计模式的类图,类State和Context的关系为(49),类(50)是客户使用的主要接口。(49)
数据库系统通常采用三级模式结构:外模式、模式和内模式。这三级模式分别对应数据库的__________。
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(28)
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(27)
在数据库逻辑结构设计阶段,需要(20)阶段形成的(21)作为设计依据。(21)
银行系统数据流图中,某个加工根据客户的多个不同属性的值来执行不同的操作,则对该加工最适宜采用()描述。
随机试题
基金销售机构的主要工作包括()。Ⅰ.宣传推介基金Ⅱ.发售基金份额Ⅲ.办理基金份额申购和赎回Ⅳ.办理基金份额登记
望形神的改变对诊断疾病有重要的参考作用,若头晕困倦,面色苍白,肢冷汗出,甚则昏不知人,多为( )
在经济活动中,因()产生的经济关系,属经济管理关系。
信达公司是一家上市公司,2015年发生了下列有关交易或事项:(1)信达公司于2015年6月10日购入乙公司股票1000万股作为可供出售金融资产核算,每股购入价为10元,另支付相关税费20万元。2015年6月30日,该股票的收盘价为每股8元,201
(2018年)2018年年初,某公司购置一条生产线,有以下四种方案。方案一:2020年年初一次性支付100万元。方案二:2018年至2020年每年年初支付30万元。方案三:2019年至2022年每年年初支付24万元。方案四:2020年至2024年每
受到国家地理标志产品保护,拥有亚洲最大的生产基础的周边特色水果是()。
针对邻里纠纷引起的情节较轻的打架斗殴,根据治安管理处罚法,下列说法正确的是()。
从所给四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性:
关于软件测试过程,请回答以下问题。应当如何正确选取过程模型?
设数据集合为D={1,2,3,4,5}。下列数据结构B=(D,R)中为非线性结构的是()。
最新回复
(
0
)