首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下算法说明,根据要求回答问题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
23
问题
阅读以下算法说明,根据要求回答问题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
软件设计师下午应用技术考试
软考中级
相关试题推荐
零件关系P(零件名,条形码,供应商,产地,价格)中的(12)属性可以作为该关系的主键。查询产于西安且名称为“P2”的零件,结果以零件名、供应商及零件价格分列表示,对应的SQL语句为:SELECT零件名,供应商,价格FROMPWHE
对于基于用户名/口令的用户认证机制来说,___________不属于增强系统安全性所应使用的防范措施。
在Windows系统中设置默认路由的作用是(68)。
以下不属于系统测试范畴的是_______。
下图为某设计模式的类图,类State和Context的关系为(49),类(50)是客户使用的主要接口。(49)
软件测试的基本方法包括白盒测试和黑盒测试方法,以下关于二者之间关联的叙述,错误的是(61)。
POP3协议采用(29)模式进行通信,当客户机需要服务时,客户端软件与POP3服务器建立(30)连接。(30)
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(28)
在数据库逻辑结构设计阶段,需要(20)阶段形成的(21)作为设计依据。(20)
国标16260中,在描述外部(内部)效率度量时,给出了若干针对计算机系统时间消耗的定义,以下描述项中正确的有(31)。①响应时间是指从按下传送键到得到结果为止所需要的时间。②处理时间是指从接受一个消息到送出它的结果之间计算机的历时时间。③周转时间是指
随机试题
居住建筑的有效面积是指:(2012年第94题)
常见的桩基不包含()。
日本A商在我沿海某地采取定牌来料加工某电器产品。成品返销日本市场后,日本另一B电器生产厂商控告A冒用其牌子。事后查明B厂商上述牌子在日本和我国均已办妥商标注册。在上述情况下,A商应承担什么责任?我国厂家有何教训?
银行业消费者一般性投诉处理的基本原则不包括()。
甲公司将一张银行承兑汇票转让给乙公司,乙公司以质押背书方式向W银行取得贷款。贷款到期,乙公司偿还贷款,收回汇票并转让给丙公司。票据到期后,丙公司作成委托收款背书,委托开户银行提示付款。根据票据法律制度的规定,下列背书中,属于非转让背书的有()。(
设有如下简单经济模型:Y=C+I+G,C=80+0.75YdYd=Y-TT=-20+0.2YI=50+0.1y,G=200式中,Y为收入;C为消费;Yd为可支配收入;T为税收;I为投资;G为政府支出。
旅行社应当与通过其取得导游证的导游订立不少于()期限的劳动合同。
既希望较快地查找,又便于线性表动态变化的查找方法是(53)。
窗体如图l所示。要求程序运行时,在文本框Textl中输入一个姓氏,单击”删除”按钮(名称为Commandl),则可删除列表框Listl中所有该姓氏的项目。若编写以下程序来实现此功能:PrivateSubCommandI_Click()D
下列关于列表框和组合框的叙述中,正确的是()。
最新回复
(
0
)