首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{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
67
问题
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{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)是不正确的。
项目经理和项目团队成员需要掌握专门的知识或技能才能较好地管理信息系统项目,以下叙述不正确的是(37)。
自从第一台电子计算机问世以来,信息系统经历了由低级到高级,由单机到网络,由数据处理到智能处理,由集中式计算到云计算的发展历程。以下关于云计算的叙述中,(2)是不正确的。
在编制WBS时,应考虑以下_________基本原则。①每个WBS元素都代表一个独立的、有形或无形的可交付成果②可交付成果中包括最终可交付物和为实现最终结果所需要的中间可交付物③每个WBS元素应只从属一个母层次的WBS元素或子层次的WBS元素④每个
以下关于类和对象关系的叙述中,_________是不正确的。
大数据对产品、企业和产业有着深刻的影响。把信息技术看作是辅助或服务性的工具已经成为过时的观念,管理者应该认识到信息技术的广泛影响,以及怎样利用信息技术来创造有力而持久的竞争优势,__________将是未来经济社会发展的一个重要特征。
使用UML对系统进行分析设计时,需求描述中的“包含”、“组成”、“分为……部分”等词常常意味着存在()关系。下图表示了这种关系。
(2010上系分)某大型移动通信运营商欲开发一个新的应用系统以替换原有系统。在需求分析阶段,为尽快从已有系统文档资料和用户处获取整体系统需求,采用______的方法捕获需求最为合适。
(2007上监理)按照软件配置管理的原始指导思想,受控制的对象应是_____(1)。实施软件配置管理包括4个最基本的活动,其中不包括_____(2)。(2)
(2012下项管)依照招标投标法,项目公开招标的资格预审阶段,在《资格预审须知》文件中可以______。
随机试题
telecommunications
下列著作属于“两汉时期”的是
慢性宫颈炎病人正确的护理是
下列哪个是施工建设阶段的开始日期?[2006-44]
在焊接接头的构造形式中,盖板接头、套管接头、塞焊接头,其实质上属于变形的是()。
受压杆件在下列各种支承情况下,若其他条件完全相同,其中临界应力最小的是()。
2012年6月1日起,上海证券交易所A股交易过户费的收费标准调整为按成交面额的()向买卖双方投资者分别收取。
Don’ttalk:yourcellphonemaybeeavesdropping.Thankstorecentdevelopmentsin"spyphone"software,ado-it-yourselfspook
A、Inarailwaystation.B、Inabusstop.C、Attheairport.C根据“请注意,101航班将在10分钟后起飞”可推断出他们应该在机场。所以应选C。
中国许多地方都出产玉石,以新疆和田玉最为著名。
最新回复
(
0
)