首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{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
66
问题
在内排序的过程中,通常需要对待排序的关键码集合进行多遍扫描。采用不同排序方法,会产生不同的排序中间结果。设要将序列{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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
软件工程管理继承了过程管理和项目管理的内容,包括启动和范围定义、软件项目计划、软件项目实施、()、关闭、软件工程度量等六个方面。
以下关于UML的叙述中,(27)是正确的。
域名服务器上存放有Internet主机的(20)。
__________属于第四代移动通信技术标准。
下图是一个选择出行路线的“决策树图”,统计路线1和路线2堵车和不堵车的用时和其发生的概率(P),计算出路线1和路线2的加权平均用时,根据计算结果选择出行路线。以下结论中,正确的是:()。
对象模型技术OMT把需求分析时收集的信息构造在三类模型中,即对象模型、动态模型和()。下图显示了这三个模型的建立次序。
某项目范围基准发生变化,经(62)同意,对需求规格说明书进行变更,则该配置项的状态应从(63)。(63)
(2005下项管)需求跟踪矩阵的作用是______。
(2008下项管)在项目管理工作中,项目管理师认识到如果只有领导能力而没有管理能力或只有管理能力而没有领导能力,都可能带来不好的结果。以下这些能力中______最能代表项目管理师的领导才能。
(2005下项管)为了保障数据的存储和传输安全,需要对一些重要数据进行加密。由于对称密码算法______(1),所以特别适合对大量的数据进行加密。国际数据加密算法IDEA的密钥长度是______(2)位。(1)
随机试题
在SDH传输体系中,STM-N的N值可取()。
破坏组织修复最常见的原因是()
革兰阴性菌细胞壁的特殊组分是
项目形象定位应遵循以下原则()。
甲企业为增值税一般纳税人,2014年2月份购进一批原材料,用于生产免征增值税货物A和应计算缴纳增值税的货物B,取得的增值税专用发票上注明价款8600元,增值税1462元。当月销售A货物取得销售收入9300元,销售B货物取得含税销售收入14040元,已知增值
下列各项中,引起企业长期股权投资账面价值发生变动的有()。
政协委员提出某些城市大搞亮丽工程.浪费财力物力。应注重节约能源,对此有人说美化城市很有必要.也有人认为要倡导节能环保,你怎么看?
Internet上的计算机地址有两种表示形式:【】与域名。
下列关于顺序文件的描述中,正确的是
OnApril20,2000,inAccra,Ghana,theleadersofsixWestAfricancountriesdeclaredtheirintentiontoproceedtomonetaryun
最新回复
(
0
)