首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
63
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
网络工程师上午基础知识考试
软考中级
相关试题推荐
信息的传输模型中包括信源、编码器、信道、解码器、信宿、噪声等要素。噪声主要对_______形成干扰或影响。
在项目管理中经常需要在成本与进度之间做出权衡,尽管聘用高级程序员的花费要比初级程序员高得多,却可以获得更高的生产效率。如果项目经理在编制项目质量计划时,希望确定聘用高级程序员和初级程序员的最佳人数比例,同时还要明确质量标准以及达到标准的最佳方法,最适合采用
(2012年上半年)(22)不是光纤接口类型。
软件开发项目中选用了配置管理工具对文档进行管理,下面关于配置权限符合配置管理要求的是()。
在云计算服务类型中,_________________向用户提供虚拟的操作系统、数据库管理系统、Web应用等服务。
____________不是质量控制的方法、技术和工具。
在审查项目需求规格说明书时,发现该文档图表编号混乱。建立()可以帮助解决上述问题。①文档管理制度②文档书写规范③图标标号规则④文档加密规则
Packet-switchingwirelessnetworksarepreferable(66)whentransmissionsare(67)bemuseofthewaychargesare(68)perpacket.Circ
Packet-switching wireless networks are preferable(66)when transmissions are(67)because of the way charges are(68)per packet. Cir
随机试题
左主支气管的持点是()
女,26岁,孕1产0孕38周,中度妊高征,因胎膜早破入院,入院时血压21.3/13.3kPa(160/100mmHg),尿蛋白(+),宫缩强,总产程2小时50分钟。产后检查胎盘胎膜完整,阴道与宫颈裂伤处经修补阴道内仍有阵阵暗红色血流出伴有血块,子宫时软时硬
A、缓冲溶液B、丁醇C、乙酸乙酯D、甲醇E、石蜡油反相分配色谱的固定相为()。
张某有20间房屋:自用居住2间;自用于开设餐馆8间;2016年1月1日出典6间,典期2年;其余4间自2010年1月1日起出租给刘某,租期10年。根据房产税法律制度的规定,有关张某2016年房产税的缴纳,下列说法正确的是()。
某私营企业经税务机关核准采取核定征收方式计算征收企业所得税。经核实,全年成本费用支出180万元,应税所得率为10%,则该企业应纳企业所得税为5.94万元。()
关于选拔性素质测评的表述,正确的有()。
在一门课程或教学活动结束后进行的教学评价属于()
WhyisMr.Smithinagoodmood?
IamafraidIhavelittleinfluenceoverheroncehermindismadeuponanysubject.
A、Maryshouldgetridofherpetassoonaspossible.B、Marywillnotbeabletokeepadoginthebuilding.C、Maryisnothappy
最新回复
(
0
)