首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用______(62),使用分治(Divide and Conquer)策略的是______(63)算法。 (62)
对于具有n个元素的一个数据序列,若只需得到其中第k个元素之前的部分排序,最好采用______(62),使用分治(Divide and Conquer)策略的是______(63)算法。 (62)
admin
2018-07-23
37
问题
对于具有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在光纤通信标准中,OC—3的数据速率是()。
ATM网络的协议数据单元是()。
HDLC是一种数据链路控制协议,它是一种(117)协议。
在负载稳定、拓扑结构变化不大的网络中可达到很好的运行效果的路由策略为(104)。
我国在国家标准管理办法中规定,国家标准的有效期(自标准实施之日起,至标准复审重新确认、修订或废止的时间)一般为(2)年。(2)
假设某分时系统采用简单时间片轮转发,当系统中的用户数为n,时间片为q时,系统对每个用户的响应时间T为__________。(2013年上半年试题)
下图中第23条记录是某客户机收到的TCP报文,从结果中可以看出该客户机的IP地址为(29),该TCP报文是(30)。(29)
设备A的可用性为0.98,如下图所示将设备A并联以后的可用性为()。
随机试题
某单线铁路隧道要求工期36个月,全长7.5km,只有进出口有进洞条件,隧道中间高洞口低,出口洞口段有20m长的坡积层,厚度较厚;进口段为风化岩有部分节理判定为Ⅲ级围岩,进洞施工时为旱季。问题:隧道应采用何种施工方案?
预定火车票说明:假设你是公司的后勤人员,写信预定火车票。内容:1.数量:5张火车票;2.日期:7月20日星期天;3.时间:下午5:00;4.要求:非吸烟车厢,从合肥到杭州;5.随函附:250元支票,一个贴好邮票、写好地址的信封。
鉴别肝外胆管结石或肿瘤性梗阻,有利于结石诊断的是
与恒牙不相似的乳牙是
纳税人有特殊困难,不得按期缴纳税款的,经县级以上税务机关核准,可延期申报,但最长不得超过()。
采用统计模型法来计算违约概率的理论依据是( )。
操作风险报告的主要内容不包括()。
政府用于偿还国债的资金来源有( )。
宫某系某大学教授,2009年1~12月收入情况如下:(1)每月取得工资薪金4000元。(2)出版图书,取得收入80000元。(3)接受出版社委托审核稿件,取得收入30000元。(4)购买体育彩票,一次性中奖收入5万元,将其中的1万
上海老街从东到西的建筑风格和业态布局展示了老上海从明清向民国西洋文化涌入时期的一段历史文化演变。()
最新回复
(
0
)