首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用( )。
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用( )。
admin
2019-06-12
39
问题
对于具有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
采用Kerberos系统进行认证时,可以在报文中加入(44)来防止重放攻击。
在UNIX操作系统中,若用户键入的命令参数的个数为1时,执行cat$l命令;若用户键入的命令参数的个数为2时,执行cat>>$2<$1命令。请将下面所示的Shell程序的空缺部分补齐。Case(25)in1)cat$1;;
网络管理系统中故障管理的目标是(48)。
帧中继网络没有采用流量控制机制,只有拥塞控制功能。采用显式信令控制时,如果LAP-D帧中的FECN比特置1,则表示(33)。
无类别域问路由(CIDR)技术有效地解决了路由缩放问题。使用CIDR技术把4个网络C1:192.24.0.0/21C2:192.24.16.0/20C3:192.24.8.0/22C4:192.24.34.0/23汇
数据流图(DFD)对系统的功能和功能之间的数据流进行建模,其中顶层数据流图描述了系统的__________。(2012年上半年试题)
某网络工程计划图如下所示,边上的标记为任务编码及其需要的完成时间(天),则整个工程的工期为(10)。
在Windows操作系统中,采用(28)命令来测试到达目标所经过的路由器数目及 IP地址。
阅读下列函数说明和C函数,将应填入(n)处。【函数3说明】函数DeleteNode(Bitree*r,inte)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返回-1。二叉查
某公司的主要业务是出租图书和唱碟。由于业务需求,该公司委托希赛公司开发一套信息管理系统。该系统将记录所有的图书信息、唱碟信息、用户信息、用户租借信息等。希赛公司决定采用面向对象的分析和设计方法开发此系统。图14-3所示为某类图书或唱碟被借阅时应记录的信息,
随机试题
根据《中华人民共和国药品管理法实施条例》,实行政府定价或政府指导价的药品是
A.已被撤销批准证明文件的药品B.对已确认发生严重不良反应的药品C.发现不良反应的药品D.发现新的不良反应的药品E.对不良反应大或者其他原因危害人体健康的药品()国家或者省级食品药品监督管理局可以采取停止生产、销售、使用的紧急措施,并应当
下列生产安全事故情形中,属于《安全生产事故报告和调查处理条例》规定的重大事故的有()。
下列账簿的账页,应采用数量金额式的有()。
基金募集申请获得监管部门核准前,基金管理人、基金销售机构不得()。Ⅰ.办理预售业务Ⅱ.公布基金宣传推介材料Ⅲ.发售基金份额Ⅳ.举办客户推介会
中国共产党“两个一百年”奋斗目标的第一个百年目标,其核心的规划是()。
刺激求助者并借此控制会谈方向,这种方法是()。
曹操又称魏武王,河南安阳西高穴大墓中出土了刻有“魏武王常用格虎大戟”的石碑以及刻有“魏武王常用慰项石”的石枕等随葬品。所以西高穴大墓就是曹操墓。为使上述论证成立,需要增加以下哪项作为前提?()
(2012复旦大学模拟题)货币市场
A、Itismainlybasedonitsrhythm.B、Itdoesn’tdependonsinger’sskills.C、Aspecifictypeofsyncopationinwhichmelodic
最新回复
(
0
)