首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下算法说明,根据要求回答问题1~问题3。 [说明] 快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。 1.分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空
阅读以下算法说明,根据要求回答问题1~问题3。 [说明] 快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。 1.分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空
admin
2010-01-15
24
问题
阅读以下算法说明,根据要求回答问题1~问题3。
[说明]
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。
1.分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r],使得A[q]大于等于A[p..q-1]中的每个元素,小于A[q+1..r]中的每个元素。q的值在划分过程中计算。
2.递归求解:通过递归的调用快速排序,对子数组A[p..q-1]和A[q+1..r]分别排序。
3.合并:快速排序在原地排序,故无需合并操作。
选项
答案
这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进,其基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分,即PARTITION操作:根据枢轴元素的值,把一个较大的数组分成两个较小的子数组,一个子数组的所有元素的值小于等于枢轴元素的值,一个子数组的所有元素的值大于枢轴元素的值,而子数组内的元素不排序。划分时,以最后一个元素为枢轴元素,从左到右依次访问数组的每一个元素,判断其与枢轴元素的大小关系,并进行元素的交换,如图2-30所示。 [*] 在[问题1]所给出的伪代码中,当for循环结束后,A[p..i]中的值应小于等于枢轴元素值x,而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素,因此A[r]与A[i+1]进行交换,得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置,因此返回值为i+l。
解析
转载请注明原文地址:https://kaotiyun.com/show/40DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在WindowsXP操作系统中,用户利用“磁盘管理”程序可以对磁盘进行初始化、创建卷,(23)。通常将“C:\Windows\nyprogram.exe”文件设置成只读和隐藏属性,以便控制用户对该文件的访问,这一级安全管理称之为(24)安全管理。
零件关系P(零件名,条形码,供应商,产地,价格)中的(12)属性可以作为该关系的主键。查询产于西安且名称为“P2”的零件,结果以零件名、供应商及零件价格分列表示,对应的SQL语句为:SELECT零件名,供应商,价格FROMPWHE
在面向对象系统中,对象的属性是()。
在Windows系统中设置默认路由的作用是(68)。
下图为某设计模式的类图,类State和Context的关系为(49),类(50)是客户使用的主要接口。(50)
()不是RISC的特点。
假设系统中有三类互斥资源R1、R2和R3,可用资源数分别为10、5和3。在T0时刻系统中有P1、P2、P3、P4和P5五个进程,这些进程对资源的最大需求量和已分配资源数如下表所示,此时系统剩余的可用资源数分别为(22)。如果进程按(23)序列执行,那么系统
开发专家系统时,通过描述事实和规则由模式匹配得出结论,这种情况下适用的开发语言是(19)。
国标16260中,在描述外部(内部)效率度量时,给出了若干针对计算机系统时间消耗的定义,以下描述项中正确的有(31)。①响应时间是指从按下传送键到得到结果为止所需要的时间。②处理时间是指从接受一个消息到送出它的结果之间计算机的历时时间。③周转时间是指
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天)。活动EH最多可以晚开始①天而不影响项目的进度。由于某种原因,现在需要同一个工作人员完成BC和BD,则完成该项目的最少时间为②天
随机试题
某男性患者,急性高热,皮肤苍白和出血。最能提示病人为急性白血病的是
为了限制系统短路容量,简化继电保护,环式配电系统应采取开环方式。()
下列关于危险废物贮存设施(仓库式)的设计原则叙述不正确的是( )。
发展资本市场不但需要不断的金融创新,建立规范、高效、适用的资本交易市场和健全的资本运营机制,而且完善的资本市场要求信息公开、透明和可获得性,必须对企业规范化运作提出更高要求。这体现了资本市场()的功能。
一家电子产品的生产企业,为改进企业的质量检验工作,发动检验人员进行研讨,对质量检验的改革进行探索,他们涉及了以下问题:[2007年真题]讨论后得出以下的共识:在产品形成过程中()的情况宜用专检。
产品的心理定价策略包括()。
下列情形中,可能导致法律责任的有()。
近年来,在体检中发现的甲状腺疾病日益增多,有专家怀疑这与人们平时食用加碘盐有关。以下哪项为真,最能削弱专家的怀疑?
(2005年真题)在公民享有的宪法基本权利体系中,最基础的权利是
以下关于民事权利能力的表述中正确的是()。
最新回复
(
0
)