首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用(30)。
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用(30)。
admin
2015-06-03
48
问题
对于具有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://jikaoti.com/ti/6Df7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
CSMA(载波监听多路访问)控制策略中有三种坚持退避算法,其中(317)算法是指:一旦介质空闲就发送数据,假如介质是忙的,继续监听,直到介质空闲后立即奉送数据;如果有冲突就退避,然后再会试。这种算法的主要特点是(318)。CSMA/CD是带冲突检测的CSM
如图3.1所示,如果为曼彻斯特编码,则表示的数据可能为(283),下面的各种网络中,适用这种编码的是(284)。为了在广域网上高速传输数字信号,可用(285)的编码方式,其编码效率为(286)。设某编码体制的编码方法为:输入数据(m=1,2,…),发送时,
网络设备按其主要用途可以分为接入设备、网络互联设备和网络服务设备。下列设备中,属于网络服务设备的是(21)。网络设备按工作层次可以分为物理层、数据链路层和网络层设备。下列设备中,工作在物理层的是(22),工作在网络层的是(23)。网桥工作在(24),采用(
可使网络服务器中充斥着大量要求回复的信息,消耗带宽,导致网络或系统停止正常服务,这属于(1)攻击类型。典型的针对系统漏洞的DoS攻击方式是(2)。向有限的空间输入超长的字符串是(3)攻击手段?用户收到了一封可疑的电子邮件,要求用户提供银行帐户及密码,这是属
公开密钥方法的主要优点之一是(1)。RSA算法的基础是(2)。当N个用户采用公开密钥方法进行通信时,系统中共有(3)个密钥,每个用户要小心保管好(4)个密钥,为了防止用户否认他们曾经通过计算机发送过的文件,较方便的方法是利用公开密钥的方法完成(5)。
某CPU的主振频率为100 MHz,平均每个机器周期包含4个主振周期。各类指令的平均机器周期数和使用频度如表2.9所示,则该计算机系统的速度为平均约(5)兆指令/秒。若某项事务处理工作所要执行的机器指令数是控制程序(以访内、比较与转移等其他指令为主)220
下列关于OSPF协议的说法不正确的是______。
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(58);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(59)。(58)
CDMAforcellularsystemscanbedescribedasfollows.AswithFDMA,eachcellisallocatedafrequency(71),whichissplitinto
阅读以下说明,回答问题,将解答填入对应的解答栏内。[说明]将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。main(){intn,i;printf("\npleaseinputa
随机试题
甲企业为生产并销售A产品的增值税一般纳税人,适用增值税税率为17%。现有X、Y、Z三家公司可以为其提供生产所需原材料,其中X为一般纳税人,且可以提供增值税专用发票,适用的增值税税率为17%;Y为小规模纳税人,可以委托税务机关开具增值税税率为3%的发票;Z为
编制概、预算时,开挖基坑定额的计量单位为“m3”,其工程量等于()。
自然界游离(或自由)核苷酸中磷酸最常见的是与戊糖(核糖或脱氧核糖)的哪个碳原子形成酯键
患者,男,65岁,近日持续出现腰膝酸软,筋骨无力,大便秘结等症状。经医生诊断后,处方药物为肉苁蓉等。下列有关肉苁蓉的说法不正确的是()。
如何进行计量标准的维护?
测定沥青混合料试件的表观密度,毛体积密度的试验温度为25℃±0.5℃,而测定沥青密度的试验温度为15℃或25℃,控制准确至0.1℃。()
以世界知名品牌餐饮为特色,以港、澳、台明星投资为亮点的休闲街是()。
下列分泌胆汁的器官是()。
中国旧式农民战争的最高峰是()
Vendingmachines(自动售货机)sellmanydifferentkindsofthings.Someofthemsellcolddrinkslikecokeororangejuice,orhotdr
最新回复
(
0
)