首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(6
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(6
admin
2009-02-15
25
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(61)。设被排序数据序列有n个元素,冒泡排序算法的复杂性是(62)。
选项
A、O(nlog
2
n)
B、O(n
2
)
C、O(log
2
n)
2
D、O(n
2
log
2
n)
答案
B
解析
冒泡排序的过程是先将第一个数与第二个数相比较,若为逆序则交换两数,然后比较每两个数与第三个数,依次类推,直到第n-1个数与第n个数进行过比较为止。上述过程称为一趟冒泡排序,结果是最大的数被排在了最后。然后进行第二趟,对前面n-1个数进行冒泡排序,结果是次大的数被移到了n-1的位置上。一般来说,第i趟冒泡排序是从第一个数到第n-i+1的位置上,整个排序过程需进行k(1≤k≤n)趟。
对于题中给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大排序,若先选出较大的元素,则对于冒泡排序,第一趟操作为541←→132,984←→746,984←→518,984←→181,984←→946,984←→314,984←→205,984←→827,其结果得到的序列为(132,541,746, 518,181,946,314,205,827,984):对于直接选择排序,第一趟操作为984←→827,其结果得到的序列为(541,132,827,746,518,181,946,314,205,984)。注意如果采用快速排序(以中间元素 518为基准)的第一趟扫描结果是(205,132,314,181,518,746,946,984,827)。
分析冒泡排序的效率,若初始序列为正序,则只进行一次排序。在排序过程中只进行n-1次比较,不交换数据。若为逆序,则需进行n-1趟排序,需进行n(n-1)/2次比较,交换数据的数量组也相同。因此,冒泡排序的复杂性是O(n
2
)。快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序的数据分成两部分,其中一部分的关键字均比另一部分的关键字小,然后再对这两部分分别进行快速排序,最后达到整个序列有序。快速排序的复杂是O(nlog
2
n)。
转载请注明原文地址:https://kaotiyun.com/show/5qPZ777K
本试题收录于:
网络工程师上午基础知识考试题库软考中级分类
0
网络工程师上午基础知识考试
软考中级
相关试题推荐
从信息系统开发的角度来看,信息系统的生命周期包括______________。
(2011年上半年)在进行项目团队的激励时,一般不会采用的方法是(46)。
在计算机软件质量保证计划规范GB/T12504-2008中规定,为了保证软件的实现满足需求,需要的基本文档中可以不包括(15)。
“十二五”期间,电子政务促进行政体制改革和服务型政府建设的作用更加显著,其发展目标不包括_______。
(2011年上半年)下列工具或方法均可用来描述项目组织,以下说法中,不正确的是(45)。
某大型信息系统集成项目组建了一个变更控制委员会来负责项目变更请求的审查与处理工作,并且确立了支配其运作的具体程序和规则。这个程序要求所有得到批准的变更都必须反映到______中。
合同的内容就是当事人订立合同时的各项合同条款。下列不属于项目合同主要内容的是(52)。
微信创造了移动互联网用户增长增速记录,433天之内完成用户数从零到一亿的增长,千万数量级的用户同时在线使用各种功能,其技术架构具有尽量利用后端处理而减少依赖客户端升级的特点,该设计方法的好处不包括(21)。
Packet-switching wireless networks are preferable(66)when transmissions are(67)because of the way charges are(68)per packet. Cir
随机试题
关于寰椎下列说法错误的是
拍卖成交后,()应当签署成交确认书。
计算机的输出设备主要有()、打印机、绘图仪等。
甲企业将其拥有的技术授权乙企业使用,每年向乙企业收取300万元的技术使用费,这种交易方式属于()。
根据增值税税法规定,企业下列()行为视同销售货物,计征增值税。
因扰乱体育比赛秩序被处以拘留处罚的,可以同时责令其()个月内不得进人体育场馆观看同类比赛。
地球两极地区所有的冰都是由降雪形成的。特别冷的空气不能保持很多的湿气,所以不能产生大量降雪。近年来,两极地区的空气无一例外地特别冷。以上信息最有力的支持以下哪一个结论?
经常硬目(CurrentAccount)(首都经贸大学2004年;北京工商大学2004年)
EvenbeforeeconomistHowardDaviesthinkingwheretoputextraairportcapacityinBritain,rejectingtheideaofbuildingabi
A.supplementedB.directC.expectationD.latterE.predominantlyF.outbreakG.la
最新回复
(
0
)