首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用______(62),使用分治(Divide and Conquer)策略的是______(63)算法。 (62)
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用______(62),使用分治(Divide and Conquer)策略的是______(63)算法。 (62)
admin
2018-07-23
48
问题
对于具有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://kaotiyun.com/show/HfRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
系统测试是将软件系统与硬件、外设和网络等其他因素结合,对整个软件系统进行测试,目的是为了发现系统不符合用户需求的部分。(4)不是系统测试的内容。
设某流水线计算机主存的读/写时间为100ns,有一个指令和数据合一的Cache,己知该Cache的读/写时间为10ns,取指令的命中率为98%,取数的命中率为95%。在执行某类程序时,约有1/5指令需要存/取一个操作数。假设指令流水线在任何时候都不阻塞,则
在计算机处理器中,若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的运行时间分别是:取指时间=2ns,分析时间=2ns,执行时间=1ns。200条指令全部执行完毕需(33)ns。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则里程碑(6)在关键路径上。若在实际项目进展中,活动AD在活动.AC开始3天后才开始,而完成活动DG过程中,由于有临时事件发生,实际需要15天才能完成,则完成该项目的最短时间比
WindowsServer200.3中的IIS为Web服务器提供了许多选项,利用这些选项可以更好地配置Web服务的性能、行为和安全等。如下图所示属性页中,“限制网络带宽”选项属于__________选项卡。(2008年下半年试题)
某主机本地连接属性如下图所示,下列说法中错误的是____________。
下图中12位曼彻斯特编码的信号波形表示的数据是(14)。
下图中主机A和主机B通过三次握手建立TCP连接,图中(1)处的状态是_________(20),(2)处的数字是___________(21)。(21)
随机试题
癌和肉瘤的区别不包括
依据《生产经营单位安全培训规定》,煤矿、非煤矿山、危险化学品、烟花爆竹等生产经营单位主要负责人和安全生产管理人员安全资格培训时间不得少于()学时;每年再培训时间不得少于()学时。
某施工单位承担了一项直埋光缆工程,光缆进场时,施工人员除了查看光缆出厂检验记录外,还抽测了部分光缆的光电性能且留有记录,路由复测时,初步确定了与另一光缆交越位置,并做了标识。工程施工中,发生如下事件:事件一:因天气预报傍晚有大雨,为减少损失,施工人员在
下列不需要一级负荷供电的是()。
影响贷款偿还的非财务因素在内容和形式上都是复杂多样的,一般可以从()分析非财务因素对贷款偿还的影响程度。
关于回族的描述,正确的有()。
下面的程序随机产生10个小于100的整数,并找出其最大值、最小值和平均值,请将程序补充完整。(此程序是VB语言编写)PrivateSubFormClickoDima(1To10)AsIntegerDimmmaxAsInteger,mminAsInte
生产关系中具有决定意义的因素是()。
在KeyUp事件过程中,通过KeyCode参数判断用户的按键。假定键“B”的KeyCode值为66,则以下正确的说法是______。
IntheAmericanfamilythehusbandandwifeusuallyshareimportantdecision-making.Whenthechildrenareoldenough,theytake
最新回复
(
0
)