首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用( )。
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用( )。
admin
2019-06-12
42
问题
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用( )。
选项
A、直接插入排序
B、希尔排序
C、快速排序
D、堆排序
答案
D
解析
此题考的是常见的内部排序算法。
直接插入排序的基本思想:每步将一个待排序的记录按其排序码值的大小,插到前面已经排好的文件中的适当位置,直到全部插入完为止。
希尔排序的基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2
直接选择排序的基本思想:首先在所有记录中选出排序码最小的记录,把它与第1个记录交换,然后在其余的记录内选出排序码最小的记录,与第2个记录交换……依此类推,直到所有记录排完为止。
堆排序的基本思想:堆排序是一种树形选择排序,是对直接选择排序的有效改进。它通过建立初始堆和不断地重建堆,逐个地将排序关键字按顺序输出,从而达到排序的目的。
冒泡排序的基本思想:将被排序的记录数组R[1..n]垂直排列,每个记录R
看作是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上“飘浮”。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
快速排序的基本思想:采用了一种分治的策略,将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
归并排序的基本思想:将两个或两个以上的有序子表合并成一个新的有序表。初始时,把含有n个结点的待排序序列看作由n个长度都为1的有序子表所组成,将它们依次两两归并得到长度为2的若干有序子表,再对它们两两合并,直到得到长度为n的有序表为止,排序结束。
基数排序的基本思想:从低位到高位依次对待排序的关键码进行分配和收集,经过d趟分配和收集,就可以得到一个有序序列。
了解这些算法思想以后,解题就容易了。现在看题目具体要求,题目中“若只需得到其中第k个元素之前的部分排序”有歧义。例如,现在待排序列:
15 8 9 2 23 69 5
现要求得到其中第3个元素之前的部分排序。第一种理解:得到“15 8 9”的排序;第二种理解:得到排序后序列“2 5 8 9 1 5 23 69”的“2 5 8 9”;得到排序后第3个元素之前的部分排序:即“2 5 8”。但综合题意,第一种理解可以排除,要达到第一种效果,只需将待排序列定为“15 8 9”即可。对于后两种理解,都只有堆最合适,因为希尔排序、直接插入排序和快速排序都不能实现部分排序。若要达到题目要求,只能把所有元素排序完成,再从结果集中把需要的数列截取出来,这样效率远远不及堆排序。所以本题答案选D。
转载请注明原文地址:https://kaotiyun.com/show/LECZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
以下关于VLAN标记的说法中,错误的是_____________。
5个64kb/s的信道按统计时分多路复用在一条主线路上传输,主线路的开销为4%,假定每个子信道利用率为90%,那么这些信道在主线路上占用的带宽为_____________kb/s。
以太网的最大帧长为1518字节,每个数据帧前面有8个字节的前导字段,帧间隔为9.6μs,对于10BASE-5网络来说,发送这样的帧需要多少时间?(64)
4G移动通信标准TD一LTE与FDD一LTE的区别是(64)。
阅读以下说明和VisualBasic代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某绘图系统定义了一个抽象类IShape,现有三个类CPoint、CLine和CCircle,它们都具有IShape界面。相应的类图关系如图7-1所示。
根据说明中的描述,使用表3-1给出的类的名称,给出图3-1中的A~F所对应的类。根据图3-2所示的播放器行为UML状态图,给出从“关闭”状态到“播放”状态所经过的最短事件序列(假设电池一开始就是有电的)。
阅读下列Java程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】StringEditor类的功能是:已知一个字符串,返回将字符串中的非字母字符都删除后的字符串。public(1){publicstati
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某公司的主要业务是出租图书和唱碟。由于业务需求,该公司委托希赛公司开发一套信息管理系统。该系统将记录所有的图书信息、唱碟信息、用户信息、用户租借信息等。希赛公司决
随机试题
下列属于行政许可的有()。
“桃红和青白色的杂花在眼前还明亮,到远处就成为斑斓的烟霭了”一句运用了________________的修辞手法。
上个世纪80年代,医院的药学工作模式发生的重大变化是
下列各项,除哪项外,均属消渴的常见变证
某商业建筑,设置了预作用自动喷水灭火系统,共设计有3000个喷头保护吊顶下方空间。该建筑自动喷水灭火系统报警阀组的设置数量不应少于()个。
(2015·内蒙古)在学习过程中有效地培养学生的内部学习动机,实质上就是要培养那些能直接转化为内部学习动机的有关心理因素。()
一、注意事项1.申论考试,与传统作文考试不同,是对分析驾驭材料的能力与表达能力并重的考试。2.作答参考时限:阅读材料40分钟,作答110分钟。3.仔细阅读给定的材料,然后按申论要求依次作答,答案写在指定位置。二、给定资料
副词的语法特点是一般只能充当_____。
Mr.Simpson’sbookbecomeshisquesttouncovertheirhistory,________withthenarrativeofhisfamily’sdecline.
HowSwearingWorksWeallknowwhat"badwords"are.Unlikemostotherlanguagerules,welearnaboutswearwordsandhowto
最新回复
(
0
)