首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的三个步骤如下: 分解:选择一个枢轴
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的三个步骤如下: 分解:选择一个枢轴
admin
2015-06-03
22
问题
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的三个步骤如下:
分解:选择一个枢轴
递归求解:通过递归的调用快速排序,对子数组A[p..q-1]和A[q+1..r]分别排序。
合并:快速排序在原地排序,故不需合并操作。
(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响,因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素,下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作,请填充其中的空缺处。其中,RANDOM(i,j)表示随机取i到j之间的一个数,包括i和j。
RANDOMIZED-PARTITION(A,p,r){
i=RANDOM(p,r);
交换(8)和(9); //空(8)和空(9)答案可互换,但两空全部答对方可得分
return PART工TION(A,p,r);
}
(2)随机化快速排序是否能够消除最坏情况的发生?(10)。(是或否)
选项
答案
(8)A[i]。 (9)A[r]。 (10)否。
解析
该题主要考查考生对分治算法的快速排序的理解,对伪代码、快速排序的复杂度的掌握,做题的关键是要读懂题干,理解题干中对算法的描述。
问题1考查的是算法的伪代码表示。分治法的设计思想是将一个难以直接解决的问题,分解成一些规模较小的相同问题,各个击破。其快速排序算法的核心处理是进行划分,根据枢轴元素的值,把一个较大的数组分成两个较小的子数组。一个子数据组的所有元素的值小于等于枢轴元素的值,一个子数组的所有元素的值大于枢轴元素的值,而子数组内的元素不排序。以最后一个元素为枢轴元素进行划分,从左到右依次访问数组的每一个元素,与枢轴元素比较大小,并进行元素的交换。在问题1给出的伪代码中,当循环结束后,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(nlgn);算法的最坏情况是每次为极不均匀划分,即长度为n的数组划分后一个子数组为n-1,一个为0,其时间复杂度为T(N)=T(n-1)+O(N),即时间复杂度为O(n
2
);算法的平均情况分析起来比较复杂,假设数组每次划分为9/10:1/10,此时时间复杂度可以通过计算得到为O(nlgn);也就是说在平均情况下快速排序仍然有较好的性能。问题2中假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度,属于最坏情况,因为每次都划分为长度为n-1和0的两个子数组。
问题3中,由于随机化的快速排序的划分调用了PARTITION操作,而传统划分每次以数组的最后一个元素作为枢轴元素。随机化的快速排序消除了输入数据的不同排列对算法性能的影响,降低了极端不均匀划分的概率,但不能保证不会导致最坏情况的发生。
转载请注明原文地址:https://kaotiyun.com/show/hdDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
假定提供Web服务的两台Linux服务器IP地址分别为192.168.1.10和192.168.1.20。为了使用DNS循环机制,由主机名www.test.com对外提供一致的服务,需要在DNS服务器的test.com区域文件中增加下列内容:www
在Windows2003中,(1)不能实现NAT功能。A.终端服务管理器B.Internet连接共享C.路由和远程访问在部门B的服务器2中,如果将ISP分配的可用公网IP地址添加到地址池(如左下图所示),那么服务器1收到来
以下是使用E1线路实现多个64Kbit/s专线连接。当链路为T1时,channel-group编号为0~23,Timeslot范围为1~24;当链路为E1时,channel-group编号为0~30,Timeslot范围为1~31.路由器
若采用电话线方式上网,并按要求在计算机连入网络的同时能通电话,连网速率高于500Kbps,可以选用哪种技术方案?其最高通信速率为多少?依据ISO/OSI参考模型对无线扩频网络设备进行分类,可以分为哪几种类型?用无线扩频设备实现网络互连需要何种配套设备
在RAS上存在着两个RJ45的端口,分别为“Console”与“AUX”,请问这两个端口的用途是什么?(控制在100个字以内)在第四步中,进入虚拟操作台后,在IOS环境下输入了如下的配置,请解释(1)~(4)处的标有下划线部分配置命令的含义(“◇”后为
简述网络规划阶段需求分析的方法和解决的问题。(控制在100个字以内)在需求分析过程中应对已有网络的现状及运行情况作调研,如果要在已有的网络上作新的网络建设规划,如何保护用户已有投资?(控制在100个字以内)
阅读以下应用L2TPv2协议实现VPN安全接入的技术说明,根据要求回答问题1至问题5。【说明】某企业应用L2TPv2协议部署企业的虚拟专用网(VPN),以方便企业的VIP用户及出差员工通过公共Internet安全地访问企业内部LAN资源,其网络拓
认真阅读以下关于架构Apache安全服务器的技术说明,根据要求回答问题1至问题5。【说明】某些商务公司要求其网站的部分信息资源只对经过身份认证后的用户开放。因此在Linux+Apache架构Web服务器方案中,需利用mod-ss1模块给Apach
L2TP协议是一种基于(1)协议的二层隧道协议,它结合了Cisco的L2F和MicrosoftPPTP的优点。该协议报文在传输层封装(2)协议之上,为了保证传输的可靠性,L2TP协议对控制报文采取了(3)机制,并要求tunne1对端设备在隧道(tunne
随机试题
A施工单位承建某新建单线铁路工程中有1座隧道工程长2600m,其余路段为路基土石方。根据设计图纸,正洞中围岩的绝大部分是Ⅱ级围岩,局部有节理较发育的Ⅲ级围岩,进口处50m为埋深较深且比较破碎的V级围岩,拟采用小断面弱爆破暗挖法,并辅助进行超前支护。出口处4
党的十七届四中全会对建设马克思主义学习型政党提出的目标是
无菌性骨坏死最常见的部位是
四神丸属于甘麦大枣汤属于
早期中心型肺癌的常见症状是
我国法律规定,人工授精时,一名供精者最多供给几名妇女受孕?()
甲侵占乙财产,乙向法院提起自诉。一审法院判处甲2年有期徒刑,甲提起上诉。关于本案的二审,下列说法正确的是?
(2007年)Windows98或Windows2000系统中的“剪贴板”是()。
社会主义道德建设的核心内容集中体现为()。
中文“海”字的区位码是2603,则它的机内码是(5)。
最新回复
(
0
)