首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
35
问题
在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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年下半年)某机构将一大型信息系统集成项目分成3个包进行招标，共有3家承包商中标，发包人与承包商应签署(50)。
(2011年下半年)进度控制的一个重要作用是(39)。
(2011年上半年)某项目经理在进行成本估算时采用(51)方法，制定出如下的人力资源成本估算表。
在项目进度控制中，(28)不适合用于缩短活动工期。
微信创造了移动互联网用户增长增速记录，433天之内完成用户数从零到一亿的增长，千万数量级的用户同时在线使用各种功能，其技术架构具有尽量利用后端处理而减少依赖客户端升级的特点，该设计方法的好处不包括(21)。
(2009年上半年)小王正在负责管理一个产品开发项目。开始时产品被定义为“最先进的个人数码产品”，后来被描述为“先进个人通信工具”。在市场人员的努力下该产品与某市交通局签订了采购意向书，随后与用户、市场人员和研发工程师进行了充分的讨论后，被描述为“成本在1
Java2平台有3个版本，它们是适用于小型设备和智能卡的Java2平台Micro版(20)、适用于桌面系统的Java2平台标准版(Java2PlatformStandardEdition，J2SE)、适用于创建服务器应用程序和服务的Java
阅读以下说明，回答问题，将解答填入答题纸的对应栏内。【说明】在开发某大型电子商务系统的过程中，为保证项目的开发质量，需要进行软件测试，某测试员被分配完成人事管理模块及某函数的测试任务。在人事管理模块中，对加班员工奖励制度：(1)年薪制：月加班超过
Soitistoday．Scheduledisaster,functionalmisfits，andsystembugsallarisebecausethelefthanddoesn’tknowwhattheright
随机试题
互感电动势的大小正比于穿过本线圈磁通的变化率，或()另一线圈中电流的变化率。
患者，女，65岁，因腹胀、进行性腹部增大2周，并腹痛3天就诊。饮食和大小便无异常，既往无特殊病史。体检：腹隆起，软，下腹部压痛(+)，无反跳痛，移动性浊音(+)，肠鸣音正常。可能性最大的疾病和最佳检查方法应选择
控制项目目标的主要措施包括组织措施、管理措施、经济措施和技术措施，其中()是最重要的措施。
某排水管道工程采用承插式混凝土管道，管座为180°；地基为湿陷性黄土，工程沿线范围内有一排高压输电线路。项目部的施工组织设计确定采用机械从上游向下游开挖沟槽，用起重机下管、安管，安管时管道承口背向施工方向。开挖正值雨季，为加快施工进度，机械开挖至槽底高程。
下列个人所得项目中，属于来源于中国境内所得的有()。
下列关于合同管理控制的说法中，错误的是()。
个案工作技巧中的建立关系是社会工作者与服务对象初次接触建立相互信任的()。
提出能力的两因素说的是()。
有多种方案可以在一台服务器中安装Windows和Linux两种网络操作系统，其中可以同时运行、Windows和Linux两种网络操作系统的方案是__________。(2013年上半年试题)
AccordingtoKellyGrant,giftforpurchaseisacceptableonlywhen
最新回复
(
0
)
