首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
57
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
网络工程师上午基础知识考试
软考中级
相关试题推荐
引导技术是指团队领导者诱发团队成员积极参与团队活动的方法,来帮助团队和个人完成相关项目活动。_______一般不作为引导技术在项目中应用。
可以通过多种方法实现对项目团队的管理,随着远程通信方式的快速发展,虚拟团队成为了项目管理的方式。作为项目经理,想要管理好虚拟团队,采用_____________方法更合适。
(2013年上半年)信息系统开发是一项艰巨的工作,为实现信息系统开发在效率、质量、成本方面的要求,选择合理的开发方法起着非常重要的作用,(10)的主要特点是:严格区分工作阶段,每个阶段都有明确的任务和明确的成果,强调系统的整体性和系统开发过程顺序、开发过程
Internet中的每个主机都有一个IP地址和域名,通过DNS服务器来完成IP地址和域名的对应。关于DNS服务器的功能,(21)是不正确的。
(2009年下半年)有关信息系统集成的说法错误的是(14)。
在没有路由的本地局域网中,以Windows操作系统为工作平台的主机可以同时安装______协议,其中前者是至今应用最广的网络协议,后者有较快速的性能,适用于只有单个网络或桥接起来的网络。
阅读以下说明,回答问题1至问题3,将解答填入对应栏内。[说明]某公司拟开发一套小区物业收费管理系统。初步的需求分析结果如下:(1)业主信息主要包括:业主编号、姓名、房号、房屋面积、工作单位、联系电话等。房号可唯一标识一条业主信息,且
通过局域网连接Internet,需要设置TCP/IP协议的属性。对于固定IP的配置需要指定3个地址,即本机地址,(6)地址和(7)的地址。
Soitistoday.Scheduledisaster,functionalmisfits,andsystembugsallarisebecausethelefthanddoesn’tknowwhattheright
Softwareentitiesaremorecomplexfortheirsizethanperhapsanyotherhumanconstruct,becausenotwopartsarealike(atleast
随机试题
胆道蛔虫病的临床特点是
一孕妇走进产科急诊,对值班医师说:"大夫,我还差5天到预产期,臀位,30分钟前阴道流水,量很大。"
某双柱下条形基础梁,由柱传至基础梁顶面的上部结构竖向力设计值分别为F1和F2。基础梁尺寸及工程地质剖面如下图所示。假定基础梁为无限刚度,地基反力按直线分布。
丁单位是实行国库集中支付的事业单位,20X2年9月,按照预算安排,丁单位拟采购一台纳入政府采购集中采购目录的仪器A设备用于药品检验,设备价款为200万元,由于A设备具有特殊性,只能从有限范围的供应商处采购,丁单位以投标邀请书的方式邀请了5家供应商参与投标,
“营改增”试点地区的纳税人提供技术转让、技术开发和与之相关的技术咨询、技术服务免征增值税。()
下列发文除()外,都应加盖发文机关的印章。
被宣告死亡人的死亡日期是()。
Oneproblemwithmuchpersonalityresearchisthatitexaminesandrateswhatevertraitstheresearchersareinterestedinatth
Itusedtobesostraightforward(直接的).Ateamofresearchersworkingtogetherinthelaboratorywouldsubmittheresultsofthe
下列关于数据备份方法的描述中,错误的是()。
最新回复
(
0
)