首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
95
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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)。
DES加密算法中,函数f的输出是(51)位。DES算法是分组密码,数据分组长度是(52)位。用软件方法实现DES一般至少比RSA快100倍。DES通过(53)方法产生密文。
HTFP是WWW的核心,它是一个(59)协议,当访问一个URL为http://www.ccidedu.com.cn/index.htm的网页时,浏览器首先向(60)请求解析http://www.ccidedu.com.cn的IP地址。获得解析后的IP
某计算机字长32位,存储容量8MB。按字编址,其寻址范围为(2)。
以下不是无线介质的是(32)。
在OSI参考模型中,物理层的功能是(25)等。实体在一次交互作用中传送的信息单位称为(26),它包括(27)两部分。上下邻层实体之间的接口称为服务访问点(SAP),网络层的服务访问点也称为(28),通常分为(29)两部分。
码是一些码字组成的集合。一对码字之间的海明距离是(30),一个码的海明距离是所有不同码字的海明距离的(31)。如果要检查出d位错,那么码的海明距离是(32)。如果信息长度为5位,要求纠正1位错,按照海明编码,需要增加的校验位是(33)。以太网中使用的校验码
某计算机的时钟频率为400MHz,测试该计算机的程序使用4种类型的指令。每种指令的数量及所需指令时钟数(CPI)如下表所示,则该计算机的指令平均时钟数约为(4)。
IPv6是下一代IP协议。IPv6的基本报头包含(27)B,此外还可以包含多个扩展报头。基本报头中的(28)字段指明了一个特定的源站向一个特定目标站发送的分组序列,各个路由器要对该分组序列进行特殊的资源分配,以满足应用程序的特殊传输需求。一个数据流由(29
使用CIDR技术把4个C类网络192.24.12.0/24、192.24.13.0/24、192.24.14.0/24和192.24.15.0/24汇聚成一个超网,得到的地址是__________。(2009年上半年试题)
随机试题
质检机构取得计量认证合格后,经()年要进行复查。
每个评价项目都有其自身的专业特点,因此,评价单位不可能事事依靠内部专家,还必须从社会上聘请一定数目的()来参加调查评价工作。
安全检查的内容不仅查管理、查隐患,还应查()。
发包人和承包人就有关工期、质量、造价等产生的建设工程合同争议,是建设工程领域最常见的()。
下列属于资产负债管理原则的有()。
流动性风险管理水平体现了商业银行的整体经营管理水平。()
旅游主管部门在作出行政处罚决定前,应当以()形式告知当事人作出行政处罚决定的事实、理由、依据和当事人依法享有的陈述、申辩权利。
不考虑价格因素,2011年与2003年相比,江苏金融业增加值增长的倍数是()。
《中华人民共和国物权法》第179条规定:“为担保债务的履行,债务人或者第三人不转移财产的占有,将该财产抵押给债权人的,债务人不履行到期债务或者发生当事人约定的实现抵押权的情形,债权人有权就该财产优先受偿。前款规定的债务人或者第三人为抵押人,债权人
TheplantspeciesthatDr.KinghorndiscoveredinPuertoRicoprovedtobe______tohismedicalresearch.
最新回复
(
0
)