首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用______(62),使用分治(Divide and Conquer)策略的是______(63)算法。 (62)
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用______(62),使用分治(Divide and Conquer)策略的是______(63)算法。 (62)
admin
2018-07-23
55
问题
对于具有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
中断响应时间是指(35)。
在计算机处理器中,若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的运行时间分别是:取指时间=2ns,分析时间=2ns,执行时间=1ns。200条指令全部执行完毕需(33)ns。
设信道带宽为3400Hz,调制为4种不同的码元,根据尼奎斯特定理,理想信道的数据速率为()。
关于距离矢量的算法,以下说法错误的是______。
在负载稳定、拓扑结构变化不大的网络中可达到很好的运行效果的路由策略为(104)。
下图中第23条记录是某客户机收到的TCP报文,从结果中可以看出该客户机的IP地址为(29),该TCP报文是(30)。(29)
某主机本地连接属性如下图所示,下列说法中错误的是____________。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的值表示完成活动所需要的时间,则____________在关键路径上。
下图中主机A和主机B通过三次握手建立TCP连接,图中(1)处的状态是_________(20),(2)处的数字是___________(21)。(21)
随机试题
对于作曲线运动的物体,以下几种说法中哪一种是正确的()
A、Positive.B、Cautious.C、Supportive.D、Negative.B从父亲说的“peoplewilllookatyoudifferentlyandyou’llsenseprejudicesherean
A.Chadwick征B.蒙氏结节C.Hegar征D.Braxton-Hicks收缩E.乳腺增生妊娠12~14周起出现的无痛性收缩为
医生白某因挪用公款用于个人经营,被判有期徒刑一年
(2008年)重W的物块能在倾斜角为α的粗糙斜面上滑下(图4—31)。为了维持物块在斜面上的平衡,在物块上作用向左的水平力FQ。在求解力FQ的大小时,物块与斜面间的摩擦力F方向为()。
当任何工作已准备就绪,在将其包装、覆盖或隐蔽之前,承包商应及时通知( )。
假设李莉女士是你的新客户,她和儿子组成了单亲家庭,一个人需要负担儿子教育费、抚养费、本人养老等问题。她面对未来很茫然,需要金融理财师协助规划。经过初步沟通面谈后,你获得了以下家庭、职业与财务等信息:一、案例成员四、假设条件1.假设通货膨胀率为4%;
财务控制的方式包括()。
设计任务:阅读下面学生信息和语言素材,设计20分钟的英语写作教学方案。教案没有固定格式,但必须包含下列要点:teachingobjectivesteachingcontentskeyanddifficultpo
凯恩斯开创的流动性偏好理论利用债券的供给和需求来说明均衡利率的决定。()
最新回复
(
0
)