首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下算法说明,根据要求回答问题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
22
问题
阅读以下算法说明,根据要求回答问题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
软件设计师下午应用技术考试
软考中级
相关试题推荐
下列关于软件开发的叙述中,与提高软件可移植性相关的是(19)。
计算机的用途不同,对其部件的性能指标要求也有所不同。以科学计算为主的计算机,对(1)要求较高,而且应该重点考虑(2)。
设有学生实体Students(学号,姓名,性别,年龄,家庭住址,家庭成员,关系,联系电话),其中“家庭住址”记录了邮编、省、市、街道信息;“家庭成员,关系,联系电话”分别记录了学生亲属的姓名、与学生的关系以及联系电话。学生实体Students中的“
在面向对象技术中,(43)是一组具有相同结构、相同服务、共同关系和共同语义的(44)集合,其定义包括名称、属性和操作。(44)
模块A、B和C都包含相同的5个语句,这些语句之间没有联系,为了避免重复,把这5个语句抽取出来组成一个模块D,则模块D的内聚类型为(39)内聚。以下关于该类内聚的叙述中,不正确的是(40)。(39)
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数已经排好序,将第i个整数依次和第i-1,i-2,…个整数进行比较,找到应该插入的位置。现采用插入排序算法对6个整数{5,2,4,6,1,3}进行从小到大排序,则需要进行(31)
以下测试内容中,属于系统测试的是()。①单元测试②集成测试③安全性测试④可靠性测试⑤兼容性测试⑥可用性测试
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(27)
在以阶段划分的编译器中,符号表管理和()贯穿于编译器工作始终。
随机试题
肝尾状叶分为_______________、_______________和_______________三部分和_______________、_______________、_______________3个突起。
对于标准的应用来说,()一般不宜作为招标项目的标准使用。
在正常使用下,装修工程最低保修期限为()。
下列各项中,属于会计工作基础的是()。
根据我国有关法律规定,()不能成为合同的当事人。
以下说法正确的有()。
把房地产价格的无理飞涨,________于中国的老百姓太有钱,那简直是荒谬之极,这样的经济学家应该________,是否还具有________的社会良知。填入划横线部分最恰当的一项是()。
某商品的成本为240元,若按该商品标价的8折出售,利润率是15%,则该商品的标价为().
Onwhatdayoftheweekwillthemagazinearrive?
PedestrianSafetyRoadsaredangerousplacesforpeopleonfoot./So,itisimportantforpedestrianstobeaware/thattr
最新回复
(
0
)