首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的三个步骤如下: 分解:选择一个枢轴
快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的三个步骤如下: 分解:选择一个枢轴
admin
2015-06-03
70
问题
快速排序是一种典型的分治算法。采用快速排序对数组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
软件设计师下午应用技术考试
软考中级
相关试题推荐
由图1-1可见,网络中心与图书馆相距700米,而且两者之间采用千兆连接,那么两个楼之间的通信介质应选择(1),理由是(2)。备选答案:(1)A.单模光纤B.多模光纤C.同轴电缆D.双绞线校园网在进行IP地址部署
阅读下列说明,回答问题1至问题6,将解答填入解答栏内。【说明】某公司的两个部门均采用Windows2003的NAT功能共享宽带连接访问Internet,其网络结构和相关参数如下图所示。ISP为该公司分配的公网IP地址段为202.117.12.3
阅读以下说明,回答问题1至问题5,将解答填入对应的解答栏内。【说明】某公司内部服务器S1部署了重要的应用,该应用只允许特权终端PC1访问,如下图所示。为保证通信安全,需要在S1上配置相应的IPSec策略。综合考虑后,确定该IPSec策略如下。
为了使DNS_Server1能正确解析本地Web站点的域名,需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中,新建的区域名称是(1);在图2所示的对话框中,添加的新建主机名称为(2),IP地址栏应填入(3)。DNS_Server
下图为RouterB上的路由表信息,写出查询路由表的命令:(1)。该路由器上运行的路由协议为(2)。行政办公楼部门A所属网络地址是(3),部门B所属网络地址是(4)。在主机D上使用命令TracertDNSServer,显示结
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)该21层教学综合大楼网络规则方案不仅要体现所设计的网络能满足现有及未来几年信息系统的应用需求,还需具有较高的平均无故障时间和尽可能低的平均故障
阅读以下有关网络接入方案的说明,回答问题1~3。【说明】某单位己完成了主干网络的建设任务,现在需要对其职工住宅区的用户接入主干网的技术方案作选型设计。职工住宅已有的通信条件是:(1)电话线(2)电视铜缆。在不重新布线的前提下,以下5种技术方
在路由器上采用了NAT技术,请用300字以内的文字简要说明NAT技术中的动态地址翻译和IP地址伪装各有什么技术特点?阅读图5-18中给出的网络拓扑结构图,结合边界路由器Router的NAT表,将以下关于主机B向内部网络发出请求时,边界路由器Router
请指出图1-12中(1)空缺处传输的是模拟信号,还是数字信号?图1-12中(2)空缺处是什么设备?该设备在本宽带网络中完成哪些功能?
下面是Web页面处理中3个步骤,请将其进行正确排序。①Web服务器接收到Web页面请求后,寻找所请求的Web页面,并将所请求的Web页面传送给Web浏览器。②Web浏览器接收到所请求的Web页面,并将它显示出来。③Web浏览器向一个
随机试题
直接分布到胃的动脉是
骨与()相连接的部位称为骨连接。
溃疡性结肠炎患者应用肾上腺糖皮质激素的不良反应有()
简述当代国外行政组织编制管理的新理论与方法。
中央银行可以采取()的货币政策工具增加货币供应量。
一般说来,造成一个产业分散的经济原因包括()因素。
体内()缺乏或过高时均可导致心律失常。
酝酿效应:指的是“难题一直没有解决,经过一段时间后意外得到满意答案”的现象。下列不涉及酝酿效应的是()。
产品/服务和其他支持性资源生命周期的四个阶段,常常用来逻辑地识别和组合过程。下列不属于生命周期的四个阶段的是
使用VC++2010打开考生文件夹下modi1中的解决方案。此解决方案的项目中包含一个源程序文件modi1.c。在此程序中,函数fun的功能是:读入一个字符串(长度<20),将该字符串中的所有字符按ASCII码值升序排序后输出。例如,若输入“edcba”,
最新回复
(
0
)