首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
59
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
网络工程师上午基础知识考试
软考中级
相关试题推荐
在项目管理中经常需要在成本与进度之间做出权衡,尽管聘用高级程序员的花费要比初级程序员高得多,却可以获得更高的生产效率。如果项目经理在编制项目质量计划时,希望确定聘用高级程序员和初级程序员的最佳人数比例,同时还要明确质量标准以及达到标准的最佳方法,最适合采用
(2010年下半年)关于计算机机房安全保护方案的设计,以下说法错误的是(32)。
某工作站的使用者在工作时突然发现该工作站不能连接网络,为了诊断网络故障,最恰当的做法是首先______。
(2013年上半年)在利用电子信息技术进行客户关系管理活动中,数据采信和存储是其中非常重要的环节(5)不是其中重点关注的数据。
__________不属于定量风险分析的技术方法。
信息技术服务标准(ITSS)所定义的IT服务四个核心要素是:人员、流程、资源和_________________。
Retailfirmsanalyzeconsumersalestrendsanduserpreferencesthroughinternetuserdata.Thisbelongsto_____________applica
Theproject______isakeyinputtoqualityplanningsinceitdocumentsmajorprojectdeliverables,theprojectobjectivestha
根据上述说明和实体-联系图,得到该住房管理系统的关系模式如下所示,请补充住宿关系。房间(房间号,收费标准,床位数目)客人(身份证号,姓名,性别,出生日期,地址)住宿((1),入住日期,退房日期,预付款额)请给出问题1中住宿关系的
阅读以下说明,回答问题,将解答填入答题纸的对应栏内。【说明】在开发某大型电子商务系统的过程中,为保证项目的开发质量,需要进行软件测试,某测试员被分配完成人事管理模块及某函数的测试任务。某函数的程序流程图如图3-1所示。预期执行的四条执行路径为:
随机试题
简述著作权法所称的作品以及作品类别。
—ProfessorSmith,Ihavearecordofmystudiesforlastyear?—Wouldyouliketoseeit?—Yes,sir.—John,【D1】______—Yes,sir
因致畸因子影响,面部突起联合失败,导致面部畸形的时间是胚胎
影响噪声对机体作用的因素有
套间式组合的特点是()。
在项目决策分析与评价中对项目建设规模应进行合理性分析,主要应分析()。
下列关于工程网络计划工期优化的说法,正确的有()。
一般认为,行为具有盲目性、被动性、不稳定性,随情景的变化而变化,这是态度和品德的形成过程中()的表现。
戒烟:疾病
无线局域网使用扩频的两种方法是直接序列扩频与______扩频。
最新回复
(
0
)