首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的三个步骤如下: 分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q一1]和A[q+l_.r],使得A[q]大于等于Alp..q-1]
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的三个步骤如下: 分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q一1]和A[q+l_.r],使得A[q]大于等于Alp..q-1]
admin
2017-08-31
73
问题
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的三个步骤如下:
分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q一1]和A[q+l_.r],使得A[q]大于等于Alp..q-1]中的每个元素,小于A[q+1..r]中的每个元素。q的值在划分过程中计算。
递归求解:通过递归的调用快速排序,对子数组A[p—q一1]和A[q+1..r]分别排序。
合并:快速排序在原地排序,故不需合并操作。
【问题1】
下面是快速排序的伪代码,请填补其中的空缺。伪代码中的主要变量说明如下:
A:待排序数组。
P,r:数组元素下标,从P到r。
q:划分的位置。
x:枢轴元素。
i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值。
j.循环控制变量,表示数组元素下标。
QUICKSORT(A,p,r){
if (p
q=PARTITION(A,p,r) ;
QUICKSORT(A,p,q一1);
QUICKSORT(A, q+1, r);
}
}
PARTITION(A,p,r){
x=A[r];
i=p一1;
for (j=p ;j<=r一 1; j++ ){
if (A[j] <=x){
i=i+ 1 ;
交换A
和A[j];
}
}
交换(1)和(2)
//注:空(1)和空(2)答案可互换,但两空全部答对方可得分
return (3)
}
【问题2】
(1)假设要排序包含n个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度,用O记号。最佳情况为(4),平均情况为(5),最坏情况为(6)。
(2)假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况?(7)。(最佳、平均、最坏)
【问题3】
(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响,因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素,下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作,请填充其中的空缺处。其中,RANDOM(i,j)表示随机取i到j之间的一个数,包括i和j。
RANDOMIZED—PART工T工ON(A,p,r){
i=RANDOM(p,r);
交换(8)和(9); //空(8)和空(9)答案可互换,但两空全部答对方可得分
return PART工TION(A,p,r);
}
(2)随机化快速排序是否能够消除最坏情况的发生?(10)。(是或否)
选项
答案
【问题1】 (1)A[i+1]或A[r]。 (2)A[r]或A[i+1]。 (3)i+1。 【问题2】 (4)O(nlgn)或O(nlog
2
n)。 (5)O(nigh)或O(nlog
2
n)。 (6)O(n
2
)。 (7)最坏。 【问题3】 (8)A[i]。 (9)A[r]。 (10)否。
解析
该题主要考查考生对分治算法的快速排序的理解,对伪代码、快速排序的复杂度的掌握,做题的关键是要读懂题干,理解题干中对算法的描述。
问题1考查的是算法的伪代码表示。分治法的设计思想是将一个难以直接解决的问题,分解成一些规模较小的相同问题,各个击破。其快速排序算法的核心处理是进行划分,根据枢轴元素的值,把一个较大的数组分成两个较小的子数组。一个子数据组的所有元素的值小于等于枢轴元素的值,一个子数组的所有元素的值大于枢轴元素的值,而子数组内的元素不排序。以最后一个元素为枢轴元素进行划分,从左到右依次访问数组的每一个元素,与枢轴元素比较大小,并进行元素的交换。在问题l给出的伪代码中,当循环结束后,A[p..i]中的值小于等于枢轴元素值x,而A[i+1..r-1]中的值应大于x。此时A[i+1]是第一个比A[r]大的元素,于是A[r]与A[i+1]交换,得到划分后的两个子数组。由于划分操作(即PARTITION操作)返回枢轴元素的值,因此返回值为i+1。
问题2考查的是算法的时间复杂度分析。当每次都能做均匀划分时,是算法的最佳情况,其时间复杂度为T(N)=2T(n/2)+O(N),即时间复杂度为O(nigh):算法的最坏情况是每次为极不均匀划分,即长度为n的数组划分后一个子数组为n-1,一个为0,其时间复杂度为T(N)=T(n—1)+O(N),即时间复杂度为O(n
2
);算法的平均情况分析起来比较复杂,假设数组每次划分为9/10:1/10,此时时间复杂度可以通过计算得到为O(nigh);也就是说在平均情况下快速排序仍然有较好的性能。问题2中假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度,属于最坏情况,因为每次都划分为长度为n一1和0的两个子数组。
问题3中,由于随机化的快速排序的划分调用了PARTITION操作,而传统划分每次以数组的最后一个元素作为枢轴元素。随机化的快速排序消除了输入数据的不同排列对算法性能的影响,降低了极端不均匀划分的概率,但不能保证不会导致最坏情况的发生。
转载请注明原文地址:https://kaotiyun.com/show/qODZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下基于Windows2003操作系统服务器实施负载平衡策略的技术说明,根据要求回答问题1至问题5。【说明】随着各行业信息化建设的不断深入,对网络应用服务器的处理能力、高可用性提出了更高的要求。尤其是高度信息化的企业中,关键性网络服务已经成
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在第4步中,进入虚拟操作台后,在IOS环境下输入了如下的配置,请解释(1)~(4)处的标有下划线部分配置命令的含义(“◇”后为配置内容
阅读以下说明,回答问题1~7。【说明】在IMail管理器中,选中MailUser邮件主机,然后在它右边的面板中选中"General"选项卡,出现一个邮件配置窗口,如图2-3所示。
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。简述WLAN用户通过RADIUS服务器登录的过程。
根据该单位防火墙与外部网络相关的网络连接参数,请将以下命令行中(1)~(4)空缺处的内容填写完整,以完成对防火墙相应的网络接口进行地址初始化的配置。FireWall(config)#ipaddressinside(1)(2)
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。项目管理就是以项目为对象的系统管理方法,通过一个临时性的专门的柔性组织,对项目进行高效率的计划、组织、指导和控制,以实现项目全过程的动态管理和项目目标的综合协调与优化。除了本题涉及到
阅读以下交换机Switch01的部分配置信息,结合图2-8所示的网络拓扑图将(1)~(8)空缺处的内容(命令或解释)填写完整。Switch>enable(进入特权模式)S
请说出图9-1的拓扑结构名称与特点。根据IP地址与子网掩码,请判断它们是否属于同一个网段?如果不是,请说出他们分别属于哪个网段。
阅读以下有关网络设计的叙述,分析网络结构,回答问题1、问题2和问题3。某企业从20世纪50年代中期开始使用PC,历经3+网络、NOVELL网络的应用,后着手组建企业网络。经过需求分析和论证,设计出网络方案如图3-2所示。
随机试题
在新民主主义经济中,国家资本主义经济具有()
30岁男性患者,车祸右额颞部着地,伤后意识不清,约半小时后清醒,醒后头痛,有呕吐,3小时后又出现意识障碍。正侧位颅片示右颞线状骨折,骨折线跨过脑膜中动脉沟;CT示右颞梭形高密度形,脑室中线受压移位。入院时右瞳孔散大。诊断是
【背景资料】某段新建铁路路基工程,主要施工内容为深路堑开挖和软土路堤填筑。其中路堑段长度为200m,最大开挖深度为20m,设计分三级边坡防护,主要地质为黏土和强风化、中风化泥岩,主要工作内容为土石方开挖和边坡防护;路堤所经水塘地段设计采用抛石挤淤
关于商标注册申请的分割,下列说法错误的是()。
2016年1月1日某企业所有者权益情况如下:股本100万元,资本公积34万元,盈余公积19万元,未分配利润64万元。则该企业2016年1月1日留存收益为()万元。
王某在一次福利彩票抽奖中,花2000己抽中一辆价值400000元;的小汽车及现金400000元。则王某就该收入应缴纳的个人所得税税额为()。
山泉:景点:矿泉水
________是瑞吉欧教育方案的灵魂和核心。
Whatarethetwospeakerstalkingabout?
PleaseUsecoolwatertowashthissweater,otherwise,itwill______.
最新回复
(
0
)