下面是快速排序的伪代码，请将空缺处(1)～(3)的内容填写完整。伪代码中的主要变量说明如下。 A：待排序数组 p,r：数组元素下标，从p到r q：划分的位置 x：枢轴元素 i：整型变量，用于描述数组下标。下标小于或等于i的元素

admin2010-01-15 69

问题下面是快速排序的伪代码，请将空缺处(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)～(3)的内容填写完整。伪代码中的主要变量说明如下。 A：待排序数组 p,r：数组元素下标，从p到r q：划分的位置 x：枢轴元素 i：整型变量，用于描述数组下标。下标小于或等于i的元素

软件设计师下午应用技术考试

软考中级

计算机的用途不同，对其部件的性能指标要求也有所不同。以科学计算为主的计算机，对(1)要求较高，而且应该重点考虑(2)。

下图是一个软件项目的活动图，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，则里程碑(49)没有按时完成会影响整个项目的进度。若活动0→2完成后，停止3天才开始活动2→6，则完成整个项目的最少时间是(50)天。(50)

下图为某设计模式的类图，类State和Context的关系为(49)，类(50)是客户使用的主要接口。(49)

在面向对象技术中，(43)是一组具有相同结构、相同服务、共同关系和共同语义的(44)集合，其定义包括名称、属性和操作。(44)

在分层体系结构中，(41)实现与实体对象相关的业务逻辑。在基于Java，EE技术开发的软件系统中，常用(42)技术来实现该层。(41)

某公司采用的软件开发过程通过了CMM2认证，表明该公司(30)。

对高级语言源程序进行编译时，可发现源程序中的(21)错误。

计算机各功能部件之间的合作关系如下图所示。假设图中虚线表示控制流，实线表示数据流，那么a、b和c分别表示(5)。

阀门的密封圈常用的材料有()、合金钢、塑料等。

急性胰腺炎诊断中具有特征性的临床指标是

A、摇动B、扭转C、分根D、去骨E、分冠拔除下颌中切牙主要使用的方法是

行政法规的名称通常为()。

()是一种越来越重要的利率风险，源于银行资产，负债和表外业务中所隐含的期权。

以下关于审计档案的表述中，不恰当的是()。

ThetownIliveinisabouttoputcamerasatalltrafficlightstocatchpeoplewhorunredlights.It【C1】______meofhowmany

某单位周一至周五为工作日，周六、周日双休，某年7月，该单位员工小刘共出勤22天(全勤)，则该年的7月8日可能为：

填入下列横线处的词语，最恰当的是()。在物联网、云计算等新技术日趋进步之时，管理软件厂商如何提升自身的市场洞察力和创新能力已经__________。填入画横线部分最恰当的一项是()。

历史研究法主要是用来描述具体的历史事件或历史人物的一种方法。