首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{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
29
问题
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
以下关于外包及外包管理的叙述中,(49)是不正确的。
以下关于WLAN安全机制的叙述中,__________是正确的。
质量控制的方法、技术和工具有很多,其中(1)可以用来分析过程是否稳定、是否发生了异常情况。(2)直观地反映了项目中可能出现的问题与各种潜在原因之间的关系。(1)
为了保护网络系统的硬件、软件及其系统中的数据,需要相应的网络安全工具。以下安全工具中,()被比喻为网络安全的大门,用来鉴别什么样的数据包可以进入企业内部网。
(2011下项管)国家标准《软件产品评价质量特性及其使用指南GB/T16260》规定了软件产品的6个质量特征,它们是______。
(2008下项管)根据《信息技术软件产品评价质量特性及其使用指南GB/T16260-2002》的定义,______不属于质量的功能性子特性。
(2012下集管)GB/T16260-2006对软件质量度量做了详细规定,其中______可用于开发阶段的非执行软件产品,如标书、需求定义、设计规格说明等。
(2008下项管)在项目管理工作中,项目管理师认识到如果只有领导能力而没有管理能力或只有管理能力而没有领导能力,都可能带来不好的结果。以下这些能力中______最能代表项目管理师的领导才能。
(2012上项管)配置管理中有一项工作是变更控制,其中配置状态的过程如下图所示:在这个状态变化过程中,图中的(1)、(2)、(3)三个状态依次为______。
(2012上项管)在配置项版本控制工程中,处于“正式发布”,状态的配置项的版本号格式为______(X、Y、Z均为1-9的数字)。
随机试题
在长度为n的顺序表的表头插入一个元素时,其算法的时间复杂度是【】
坚持独立自主的和平外交政策主要体现在()。
下列法律行为中属于单方法律行为的是()。
以下关于框架一剪力墙结构中剪力墙适宜的部位描述不正确的是()
一定时期流通中所需要的货币量()。
甲股份有限公司为商品流通企业。2013年度财务报表的有关资料如下:(1)2013年12月31日资产负债表有关项目年初、年末数如下(单位:万元):(2)2013年度利润表有关项目本年累计数如下(单位:万元):(3)其他有关资料如下:①本期
村民甲与妻子感情较好,但因其妻接连生了两个女孩而欲离婚,对此法院应如何处理()。
Lotsofcreaturesalreadyreproducewithoutsex.SincethebirthofLouiseBrown,thefirsttest-tubebaby,in1978,(1)_____of
Whentheybrokeopenthedoor,theyfoundastrangemanliedonthefloorunconscious.
Underwhatagecan’tchildrenshootadvertisement?
最新回复
(
0
)