首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{Q,H,C,Y,P,A,M,S,R,D,F, X}中的关键码按字母的升序重新排列,则(24)是冒泡排序一趟扫描的结果,(25)是初始步长为4
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{Q,H,C,Y,P,A,M,S,R,D,F, X}中的关键码按字母的升序重新排列,则(24)是冒泡排序一趟扫描的结果,(25)是初始步长为4
admin
2019-03-04
46
问题
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{Q,H,C,Y,P,A,M,S,R,D,F, X}中的关键码按字母的升序重新排列,则(24)是冒泡排序一趟扫描的结果,(25)是初始步长为4的希尔排序一趟扫描的结果,(26)是两路归并(合并)排序一趟扫描的结果,(27)是以第一个元素为分界元素的快速排序一趟扫描的结果,(28)是堆排序初始建堆的结果。
选项
A、F,H,C,D,P,A,M,Q,R,S,Y,X
B、P,A,C,S,Q,D,F,X,R,H,M,Y
C、A,D,C,R,F,Q,M,S,Y,P,H,X
D、H,C,P,A,M,S,R,D,F,X,Y
E、H,Q,C,Y,A,P,M,S,D,R,F,X
答案
C
解析
本题比较容易,直接考查各种排序的方法,但从历年试题看来,再考的概率是比较高的。
1.冒泡排序
冒泡排序将被排序的记录数组R[1..n]垂直排列,每个记录R
看做是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上“飘浮”。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
冒泡排序的具体过程如下。
第一步,先比较k1和k2,若k1>k2,则交换k1和k2所在的记录,否则不交换。继续对k2和k3重复上述过程,直到处理完kn-1,和kn。这时最大的排序码记录转到了最后位置,称第1次起泡,共执行n-1次比较。
与第一步类似,从k1和k2开始比较,到kn-2和kn-1为止,共执行n-2次比较,称第2次起泡。
依次类推,共做n-1次起泡,完成整个排序过程。
在本题中,待排序的序列为{Q,H,C,Y,P,A,M,S,R,D,F,X},按照上述规则,第一趟冒泡结果为{H,C,Q,P,A,M,S,R,D,F,X,Y}。
2.希尔排序
希尔(Shell)排序的基本思想是:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
一般取d1=n/2,di+1=di/2。如果结果为偶数,则加1,保证di为奇数。
在本题中,待排序的序列为{Q,H,C,Y,P,A,M,S,R,D,F,X},规定初始步长d1=4,则(Q,P,R)排在一组。这需要对Q,P,R进行排序,排序得:P,Q, R,所以P应是序列的首字母。在4个选项中,只有B满足要求。
3.归并排序
归并排序是将m(m>1)个有序子表合并成一个新的有序表。初始时,把含有n个结点的待排序序列看做由n个长度都为1的有序子表所组成,将它们依次m归并得到长度为2的若干有序子表,再对它们m合并。直到得到长度为n的有序表,排序结束。
在本题中,待排序的序列为{Q,H,C,Y,P,A,M,S,R,D,F,X},规定m=2 (两路归并)。把题目中的数据进行分组有:[Q,H],[C,Y],[P,A],[M,S],[R,D], [F,X],调整后得:[H,Q],[C,Y],[A,P],[M,S],[D,R],[F,X]。所以正确答案为E。
4.快速排序
快速排序采用了一种分治的策略,通常称其为分治法。其基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序的具体过程如下。
第一步,在待排序的n个记录中任取一个记录,以该记录的排序码为准,将所有记录分成两组,第1组各记录的排序码都小于等于该排序码,第2组各记录的排序码都大于该排序码,并把该记录排在这两组中间。
第二步,采用同样的方法,对左边的组和右边的组进行排序,直到所有记录都排到相应的位置为止。
从上面的介绍中我们知道,对一个序列进行快速排序后有一个非常明显的特征,即“关键字前面的所有元素小于关键字,关键字后面的所有元素大于关键字”。我们往往能以此规则来快速又准确地得到正确答案。在此题中,以序列首字母Q为关键字,我们先看A,此选项满足上述特征。
请读者想想:分析到此处,我们能否断定A是正确答案呢?不能。我们只能说找到不合规则的选项将其排除,最终得到正确答案。一个序列满足上述条件不一定就是快速排序的结果。所以我们继续看B和C在这两个选项中,H比Q小,但在Q后面,不正确。D和E两个选项中A在Q的后面,显然不正确,所以答案应选A。
5.堆排序
有关堆的定义和性质,请读者参考第2题的分析。
堆排序的关键步骤有两个:一是如何建立初始堆:二是当堆的根结点与堆的最后一个结点交换后,如何对少了一个结点后的结点序列做调整,使之重新成为堆。
在本题中,只要求建立初始堆,我们可以按照4.1.2节的方法,判断给定的5个选项中,哪个选项满足堆的定义就可以了,在此不再重复。
转载请注明原文地址:https://kaotiyun.com/show/i3TZ777K
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
某项目计划投资1000万元,经过估算,投产后每年的净收益为200万元,则该项目的静态投资回收期为5年。如果考虑到资金的时间价值,假设贴现率为10%,那么该项目的动态投资回收期(56)。
软件可靠性和可维护性测试评审时,不用考虑的是(14)。
在软件系统的生命周期中,软件度量包括3个维度,即项目度量、产品度量和(8)。
软件需求包括三个不同的层次:业务需求、用户需求和功能需求。其中业务需求(6)。
配置项版本控制过程的步骤是()。①技术评审或领导审批②正式发布③修改处于“草稿”状态的配置项④创建配置项
(2010下项管)某软件开发组针对两个相关联但工作环境可能有些差异的系统1(对应“用户1”)和系统2(对应“用户2”)进行配置管理。产品设计阶段的内部设计模块对应如下:用户1:采用A,B,C,D,E和F模块用户2:采用A,B,C,D,E
(2013上集管)在WebService中用于描述Web服务的语言是______。
(2014下项管)在UML图形上,把一个泛化关系画成______。
(2008上项管)一般说来,变更控制流程的作用不包括______。
(2008下项管)(2009上项管)(2010上项管)某工程包括A、B、C、D、E、F、G七项工作,各工作的紧前工作、所需时间以及所需人数如下表所示(假设每个人均能承担各项工作):该工程的工期应为______(1)天。按此工期,整个工程最少需要____
随机试题
凡具有国家规定基本条件的研究生均可享受()
A.经刺激外周化学感受器兴奋呼吸中枢B.经刺激中枢化学感受器兴奋呼吸中枢C.直接抑制呼吸中枢D.直接兴奋呼吸中枢低O2对呼吸中枢的直接作用是
缺少下列哪种微量元素会导致生长发育停滞、性成熟受抑制()。
不属于药品的是
如下哪项是脑栓塞的栓子最常见来源
根据下面资料回答问题。2009年1~7月全国房地产市场运行情况房地产开发完成情况1~7月,全国完成房地产开发投资17720亿元,同比增长11.6%,增幅比1~6月提高1.7个百分点,比去年同期回落19.3个百分点。其中,商品
施工组织设计除了工程概况、施工部署及施工方案、施工进度计划、施工平面图以外,还应该包括()。
由于受到国内外各种错误思潮、腐朽观念等各种因素的影响,现实中还存在拜金主义、享乐主义和极端个人主义等错误的思想和观念。这些错误的思想和观念产生的原因在于
Whereisthisconversationtakingplace?
A、Maderiawasnotchosenbecauseitsroadsweretoodangerous.B、TheCostaDelSolwasfinallychosenafterthreemonthsofinve
最新回复
(
0
)