首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用(30)。
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用(30)。
admin
2015-06-03
47
问题
对于具有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
ISDN是由(6)定义的一种网络设备标准。在ISDN的各种设备之间可定义(7)个参考点,其中,把网络终端设备和用户终端设备分开的参考点为(8)。若一个大的企业要连入ISDN,则要用到一个叫NT2的设备,NT2实际上就是(9)。ISDN网络的构成不包括(10
X.25是一种三层通信协议,在这种网络中,计算机通常与网络的(322)相连接。x.25网络的数据链路层使用的标准是(323),它允许在收到应答前连续发送(324)帧数据,为用户提供的最高速率为(325)Kbps。两个X.25网络之间互联时使用(326)协议
帧中继网的虚电路建立在(26),在用户平面采用的协议是(27)。这种网络没有流量控制功能,但增加了拥塞控制功能。如果沿着帧的传送方向出现了拥塞,则把地址字段中的(28)位设置为1,这样接收方就可通过(29)协议要求发送方降低数据速率。最适合提供帧中继业务的
帧中继网的虚电路建立在(26),在用户平面采用的协议是(27)。这种网络没有流量控制功能,但增加了拥塞控制功能。如果沿着帧的传送方向出现了拥塞,则把地址字段中的(28)位设置为1,这样接收方就可通过(29)协议要求发送方降低数据速率。最适合提供帧中继业务的
分组交换可以采用虚电路方式或(26)方式实现。虚电路方式在通信前需建立一条虚电路,其路径由(27)决定。每条虚电路都有虚电路号码,该号码(28)。虚电路建立后,各数据分组(29)到达目的地,然后(30)。
FTP是基于(36)实现的文件传输协议,使用此协议进行文件传输时,FTP客户和服务器之间建立的连接是(37),用于传输文件的是(38)连接。TFTP是基于UDP实现的简单文件传输协议,它共有五种协议数据单元PDU,其中数据PDU一次可以携带的数据最多为(3
常规密钥密码体制又称为(1),它是指(2)的密码体制。属于常规密钥密码体制的密码是(3)。采用密钥流序列作为密钥序列的属于(4)。国际数据加密算法IDEA属于(5)。
一台PC计算机系统启动时,首先执行的是(36),然后加载(37)。在设备管理中,虚拟设备的引入和实现是为了充分利用设备,提高系统效率,采用(38)来模拟低速设备(输入机或打印机)的工作。已知A、B的值和表达式A2/(5A+B)的求值过程,且A、B已
关于距离矢量的算法,以下说法错误的是______。
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(58);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(59)。(59)
随机试题
1992年,当明尼苏达州矿产和制造公司(MinnesotaMiningandManufacturing,3M)以全球收入68亿元成为世界100强企业之一时,无疑向世人说明了一个成功的全球观念。3M公司成立90年中几乎有一半时间是投身于国际事业的。它的
A.诊断试验B.队列研究C.筛检D.病例对照研究E.现况研究
当民用建筑顶棚或墙面局部采用多孔或泡沫状塑料时,其厚度不应大于( )。
通风方式在选择时应注意()。
清孔是指()。
普惠制原产地证明书(FORMA)中的原产地标准栏目,如果出口商品为完全原产品,不含有任何进口成分,出口到所有给惠国,正确填写代码是()
我国货币政策工具主要包括公开市场业务、存款准备金、再贷款与再贴现、利率政策、汇率政策和窗口指导六大类。其中被现代中央银行应用最为广泛,称为货币政策的“三大法宝”的不包括()。
中国是一个农业社会,聚族而居、( )在农业大环境下,成了传统家庭的重心,由此而衍生出来的道德价值观,首先是儒家倡导的“亲亲”,形成长幼有序、孝悌仁爱的道德观念,并用家庭成员( )和继承下来的风俗习惯,有效地维护血缘秩序,履行个人在血缘等级关系中被确认的
有以下程序:#include<stdio.h>main(){charch1,ch2;intn1,n2;ch1=getchar();ch2=getchar();n1=ch1-’0’;n2=n
Accordingtothenews,Japan’seconomyisstillweakbecauseofallthereasonsEXCEPT______.
最新回复
(
0
)