首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用(30)。
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用(30)。
admin
2015-06-03
65
问题
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用(30)。
选项
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 15 23 69”的“2 5 89”;得到排序后第3个元素之前的部分排序:即“2 5 8”。但综合题意,第一种理解可以排除,要达到第一种效果,只需将待排序列定为“15 8 9”即可。对于后两种理解,都只有堆最合适,因为希尔排序、直接插入排序和快速排序都不能实现部分排序。若要达到题目要求,只能把所有元素排序完成,再从结果集中把需要的数列截取出来,这样效率远远不及堆排序。
所以本题答案选D。
转载请注明原文地址:https://kaotiyun.com/show/Q3RZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
根据尼奎斯特定理,若信道带宽为6KHz,那么,理想信道的波特率为(193);若采用QPSK调制,其数据速率应为(194);如果该信道信噪比为30dB,则该信道的带宽约为(195)。设信道误码率为10-5,帧长为10K比特,差错为单个错,则帧出错的概率为(1
构造LAN时,一般不采用的方案是(41)。采用粗细电缆混接的条件下,若用100m细电缆,则在没有中继器时网络的最大可延伸距离为(42)。在光纤通信中,单模光纤一般比多模光纤的直径(43)。光纤采用SDH传输方式时,其基本速率可达到(44),在光纤上采用AT
多路复用技术能够提高传输系统的利用率。常用的多路复用技术有(16)。将一条物理信道分成若干个时间片,轮换地给多个信号使用,实现一条物理信道传输多个数字信号,这是(17)。将物理信道的总频带宽分割成若干个子信道,每个信道传输—路信号,这是(18)。在光纤中采
DES加密算法采用的密码技术是(1),它采用(2)位密钥对传输的数据进行加密。著名的网络安全系统Kerberos采用的是(3)加密技术。公钥密码是(4),常用的公钥加密算法有(5),它可以实现加密和数字签名。
关于距离矢量的算法,以下说法错误的是______。
网络安全体系设计可从物理线路安全、网络安全、系统安全、应用安全等方面来进行,其中数据库容灾属于__________。(2009年下半年试题)
假设生产管理网络系统采用B/S工作方式,经常上网用户数为150个,每用户每分钟产生8个事务处理任务,平均事务量大小为0.05MB,则这个系统需要的信息传输速率为__________。(2010年上半年试题)
请采用说明中的词汇,给出数据确认处理所需的数据流在第1层图中的全部可选起点(第0层图和第1层图中均未给出)。打印分户账清单时,必须以下列哪一组数据作为关键字进行排序,才能满足需求?请从下面选项中选择。①储蓄所②账号⑧开户日
根据说明中的描述,使用表3-1给出的类的名称,给出图3-1中的A~F所对应的类。根据图3-2所示的播放器行为UML状态图,给出从“关闭”状态到“播放”状态所经过的最短事件序列(假设电池一开始就是有电的)。
随机试题
磁盘执行一次输入输出操作所花费的时间依次为
第五次反“围剿”失败的最主要原因是()
细菌致病性强弱主要取决于细菌的()
患儿,7岁。浮肿1个月,查体腰腹下肢为甚,按之深陷难起,面色白,腰酸怕冷,尿淡而频,夜间尤甚,舌胖质淡,苔白,脉沉细。辨证为
在客户评级中,违约概率的估计包括()
生产者为防止需求不确定性和供应不确定性带来的缺口而设置的一定数量的存货,被称为()。
丁公司股票的β系数为1.5,无风险利率为8%,市场上股票的平均报酬率为12%。要求:若股票为股利固定增长股,股利增长率为4%,预计一年后的股利为1.4元,则该股票的价值为多少?
A是3阶矩阵,有特征值λ1=λ2=2,对应两个线性无关的特征向量为ξ1,ξ2,λ3=-2对应的特征向量是ξ3.证明:任意3维非零向量β都是A2的特征向量,并求对应的特征值.
下列关于文件类型的叙述中,正确的是(43)。
【B1】【B19】
最新回复
(
0
)