首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(6
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(6
admin
2010-01-23
93
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
解析
冒泡排序的过程是先将第1个数与第2个数相比较,若为逆序则交换两数,然后比较每两个数与第三个数,依次类推,直到第n-1个数与第几个数进行过比较为止。上述过程称为一趟冒泡排序,结果是最大的数被排在了最后。然后进行第二趟,对前面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/gYxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
TCP是一个面向连接的协议,它提供连接的功能是(14)的,采用(15)技术实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(16)的分组,这种分组的数量最多可以(17),TCP协议采用滑动窗口协议来解决了(18)。
PPP使用(38)协议。相对于OSI模型,它提供(39)服务。对于PPP,远程服务器可以为本地客户提供一个(40)IP地址。
以太网交换机根据(62)转发数据包。访问交换机的方式有多种,配置一台新的交换机时可以(63)进行访问。在键入交换机命令时可使用缩写形式,在Switch#模式下,如果键入“con”,则表示(64)。
按制定标准的不同层次和适应范围,标准可分为国际标准、国家标准、行业标准和企业标准等,(17)制定的标准是国际标准。
在计算机指令系统中,通常采用多种确定操作数的方式。当操作数直接给出时,这种寻址方式叫作(2);当操作数的地址由某个指定的变址寄存器的内容与位移量相加得到时,叫作(3);如果操作数的地址是主存中与该指令地址无关的存储单元的内容,叫作(4)。
知识产权一般都具有法定的保护期限,一旦保护期限届满,权力将自行终止,成为社会公众可以自由使用的知识。(11)受法律保护的期限是不确定的,一旦为公众所熟悉,即成为公众可以自由使用的知识。
软件能力成熟度模型CMM(CapabilityMaturityModel)描述和分析了软件过程能力的发展与改进的程度,确立了一个软件过程成熟程度的分级标准。在初始级,软件过程定义几乎处于无章可循的状态,软件产品的成功往往依赖于个人的努力和机遇。在(7)
CSMA/CD在CSMA的基础上增加了冲突检测功能。网络中的某个发送站点一旦检测到冲突,它就立即停止发送,并发送一个冲突码,其他站点都会(39)。如果站点发送时间为1,任意两个站之间的传播延迟为t,若能正常检测到冲突,对于基带总线网络,t的值应为(40);
下列有关网络拓扑结构的叙述中,不正确的是(18)。
在面向对象方法中,把一组具有相同数据结构和相同操作的对象的集合定义为______ 。此定义包括一组数据属性和在数据上的一组合法操作。
随机试题
2006年3月20日,上海的甲公司与北京的乙公司签订了一份买卖合同,约定:甲公司向乙公司购买1000吨化工原料,总价款为200万元;乙公司在合同签订后1个月内交货,甲公司在验货后7日内付款。双方没有明确约定履行地点。合同签订后,甲公司以其办公用房作抵押向丙
在Windows7中,如果误删了重要文件则无法恢复,只能重做。()
不属于眼球内容物的结构是
脑内具有生命中枢之称的部位是
有关上颌牙列的纵胎曲线,说法正确的有
患者,男性,77岁。因脑出血入院,患者大小便失禁,需加铺橡胶单,其上端距床头约
依法定方式签发票据并将票据交付给收款人的人是()。
技能是一种活动方式,属于动作经验,与属于认知经验的知识是相同的。()
下列属于无效的民事行为的是()
Muchoftheworldshouldgoonadietin2014.Morethanathirdofadults【C1】______wereestimatedtobe【C2】______orobesein20
最新回复
(
0
)