首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用______(62),使用分治(Divide and Conquer)策略的是______(63)算法。 (62)
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用______(62),使用分治(Divide and Conquer)策略的是______(63)算法。 (62)
admin
2018-07-23
79
问题
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用______(62),使用分治(Divide and Conquer)策略的是______(63)算法。
(62)
选项
A、希尔排序
B、直接插入排序
C、快速排序
D、堆排序
答案
D
解析
本题考查常见内部排序算法的思想。
①希尔排序的思想是:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
②直接插入排序的思想是:每次从无序表中取出第一个元素,把它插入有序表的合适位置,使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入有序表中;第二趟把第三个数与前两个数从后向前扫描,把第三个数按大小插入有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
③快速排序的思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
④堆排序的思想是(在此介绍用大顶堆排序的基本思想):a.先将初始文件R[1..n]建成一个大顶堆,此堆为初始的无序区;b.再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key;c.由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆,然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1.n一2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。以此类推,直到无序区只有一个元素为止。
⑤冒泡排序的思想是:在排序过程中总是小数往前放,大数往后放,相当于气泡往上升。
题目要求得到其中第k个元素之前的部分排序,显然堆排序最合适,因为希尔排序、直接插入排序和快速排序都不能实现部分排序。若要把所有元素排序完成,再从结果集中把需要的数列截取出来,很明显效率远远不及堆排序。
对于第(63)题,可以从快速排序基本思想得到答案。
转载请注明原文地址:https://www.kaotiyun.com/show/HfRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在计算机处理器中,若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的运行时间分别是:取指时间=2ns,分析时间=2ns,执行时间=1ns。200条指令全部执行完毕需(33)ns。
HDLC是一种数据链路控制协议,它是一种(117)协议。
在负载稳定、拓扑结构变化不大的网络中可达到很好的运行效果的路由策略为(104)。
某系统由下图所示的冗余部件构成。若每个部件的千小时可靠度都为R,则该系统的千小时可靠度为___________。
WindowsServer200.3中的IIS为Web服务器提供了许多选项,利用这些选项可以更好地配置Web服务的性能、行为和安全等。如下图所示属性页中,“限制网络带宽”选项属于__________选项卡。(2008年下半年试题)
某主机本地连接属性如下图所示,下列说法中错误的是____________。
设置计算机的无线网卡,使该计算机与实验室的无线访问点LabAP之间的通信能够受密码保护,指定密钥为2350AD9FE0,则下图中应设置(43)。
下图中12位曼彻斯特编码的信号波形表示的数据是(14)。
下图中主机A和主机B通过三次握手建立TCP连接,图中(1)处的状态是_________(20),(2)处的数字是___________(21)。(21)
随机试题
机动车仪表板上(如图所示)这个符号表示什么?
前期象征主义文学
在性方面ad.s_______
下列选项中,通过粪一口途径传播的传染病是
按唇裂裂隙程度分类的是
关于对乙酰氨基酚理化性质描述正确的是( )。
目前上海证券交易所、深圳证券交易所均规定,权证自上市之日起存续时间为6个月以上24个月以下。( )
在公众场合,有些领导人穿着西服,所有的领导人都能出口成章。因此( )
单边的
班主任老师对一个学习优秀的学生说,你之所以取得这样好的成绩,主要是因为我教学有方。以下哪项如果为真,将最有力地反驳老师的说法?
最新回复
(
0
)