首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{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
47
问题
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
软件工程管理继承了过程管理和项目管理的内容,包括启动和范围定义、软件项目计划、软件项目实施、()、关闭、软件工程度量等六个方面。
配置管理是软件生命周期中的重要控制过程,在软件开发过程中扮演着重要的角色。按照GB/T11457一2006《软件工程术语》的描述,以下关于配置管理基线的叙述中,(13)是不正确的。
MVC是模型(Model)一视图(View)一控制器(Controler)架构模式的缩写。以下关于MVC的叙述中,(7)是不正确的。
大数据对产品、企业和产业有着深刻的影响。把信息技术看作是辅助或服务性的工具已经成为过时的观念,管理者应该认识到信息技术的广泛影响,以及怎样利用信息技术来创造有力而持久的竞争优势,__________将是未来经济社会发展的一个重要特征。
在网络系统的设计与实施过程中,需要重点考虑网络在()方面的可扩展性。
(2010下项管)某软件开发组针对两个相关联但工作环境可能有些差异的系统1(对应“用户1”)和系统2(对应“用户2”)进行配置管理。产品设计阶段的内部设计模块对应如下:用户1:采用A,B,C,D,E和F模块用户2:采用A,B,C,D,E
(2009上集管)按照规范的文档管理机制,程序流程图必须在______两个阶段内完成。
(2005下项管)现有两个用例UC1和UC2,其中UC2是一个完整的用例,可被实例化,而UC1需要UC2中的事件流才可被实例化,且UC1指定了使用UC2的精确位置,则UC1和UC2间的关系是“______”。
(2008上项管)一般说来,变更控制流程的作用不包括______。
(2010下软评)加密和解密是明文和密文之间的可逆转换,______不属于加密算法。
随机试题
患者,男,55岁。腹痛拒按,烦渴喜饮,大便秘结,潮热汗出,小便短黄,舌质红,苔黄腻,脉滑数。治法宜选用
甲是现役军人,乙是一般的工人。双方于1997年登记结婚。2002年1月乙生一女孩。此后,两人经常吵架。2004年2月,乙又生一女孩。由于甲封建思想严重,重男轻女。在乙生育两个女孩之后,经常没事找事与乙吵架,最终甲以夫妻感情破裂,性格不合为由于2005年1月
在材料使用过程中,对部分小型及零星材料根据工程量计算出所需材料量,将其折算成费用,由作业者采用()控制。
系统风险又称为()。Ⅰ.可分散风险Ⅱ.不可分散风险Ⅲ.不可回避风险Ⅳ.可回避风险
2007年10月4日,韩国总统卢武铉与朝鲜领导人金正日举行了历史性会晤,签署了《北南关系发展与和平繁荣宣言》,其内容包括
设有二维数组A[0..9,0..19],其每个元素占两个字节,数组按列优先顺序存储,第一个元素的存储地址为100,那么元素A[6,6]的存储地址为【】。
表单文件的扩展名是( )。
计算机病毒的危害表现为()。
A、OK,Iwill.B、Takecare.C、Thankyou.D、Let’sgo.A本题考查对Could引导的提出请求的一般疑问句的回答。对于此类问题的回答分为肯定和否定两种:肯定回答一般为Yes,ofcourse/Certainl
RainforestsDidyouknowtherearetwotypesofRainforest-thetemperateandthetropical?Tropicalrainforestsarefoundc
最新回复
(
0
)