首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
admin
2009-02-15
43
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对于冒泡排序算法的复杂性是(43)。
选项
A、O(n
2
)
B、O(nlog
2
n)
C、O(log
2
n)
2
D、O(n
2
log
2
n)
答案
A
解析
冒泡排序的过程是先将第1个数与第2个数相比较,若为逆序则交换两数,然后比较每两个数与第三个数,依此类推,直到第n-1个数与第n个数进行过比较为止。上述过程称为一趟冒泡排序,结果是最大的数被排在了最后。然后进行第二趟排序,对前面n-1个数进行冒泡排序,结果是次大的数被排到了n-1的位置上。一般来说,第i趟冒泡排序是从第一个数到第n-i+1的位置上,整个排序过程需进行A(1≤k≤n)趟。分析冒泡排序的效率,若初始序列为正序,则只进行一次排序。在排序过程中只进行n-1次比较,不交换数据。若为逆序,则需进行n-1趟排序,需进行n(n-1)/2次比较,交换数据的数量组也相同。因此,冒泡排序的复杂性是O(n
2
)。快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序的数据分成两部分,其中一部分的关键字均比另一部分的关键字小,然后再对这两部分分别进行快速排序,最后达到整个序列有序。因此,快速排序的复杂是O(nlog
2
n)。
转载请注明原文地址:https://kaotiyun.com/show/vJjZ777K
本试题收录于:
程序员上午基础知识考试题库软考初级分类
0
程序员上午基础知识考试
软考初级
相关试题推荐
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)。①可以使用操作系统的文件加密系统(EFS)对文件或文件夹进行加密②可以针对某个文件或文件夹给不同的用户分配不同的权限③可以防止网页中的Applet程序访问硬盘中的文件④
该校园网的部分区域部署了无线网络(WLAN),采用符合IEEE802.11g标准的无线网络设备,该校园网无线网络部分的最大数据传输速率为(1)。A.11Mb/sB.54Mb/sC.100Mb/sD.108Mb/s
请从以下供选择的答案中为index.asp文档程序中(1)~(5)处空缺部分选择正确答案。(1)A.CreateObjectB.ConnectC.ExecuteSQLD.Open()(2)A.<body>B.<ht
阅读以下基于Linux操作系统部署DHCP服务器的技术说明,根据要求回答问题1~问题5。【说明】某图书馆内部局域网划分为办公区、电子阅览室、无线阅览室等3个VLAN,并通过一台带防火墙模块的路由器与Internet网互连.为了便于整个局域网IP地
实现保密通信的SSL协议工作在(1)层和(2)层之间。SSL加密通道的建立过程如下:①首先客户端与服务器建立连接,服务器把它的(3)发送给客户端;②客户端随机生成(4),并用从服务器得到的公钥对它进行加密,通过网络传送给服务器:
阅读下列说明和HTML文本,分析其中嵌入的JavaScrlpt脚本,将应填入(n)处的语句写在对应栏内。[说明]本题实现用鼠标拖拽图片在Web页内移动的功能。将鼠标放在图片上,按下左键,移动鼠标便可带动图片一起移动。[HT
阅读下列说明和HTML文本,分析其中嵌入的JavaScrlpt脚本,将应填入<u>(n)</u>处的语句写在对应栏内。[说明]本题实现用鼠标拖拽图片在Web页内移动的功能。将鼠标放在图片上,按下左键,移动鼠标便可带动图片一起移动。[
以下是路由器R1的配置命令列表,请将(1)~(3)空缺处的命令/参数填写完整,以实现路由器R1的正确配置。Router>enRouter>conftermRouter(config)#hostnameR1(1)
在PC1的DOS命令窗口中运行(1)命令,得到结果如图2-20所示。在其空缺的参数中,PhysicalAddress值为(2);IPAddress值为(3);SubnetMask值为(4);DefaultGateway值为(5)。在图2-1
在以太网的帧结构中,帧首定界符的长度为一个字节,其值为(45)。当以太网中数据传输率提高时,帧的传输时间要求按比例缩短,这样有可能会影响到冲突检测。为了能有效地检测冲突,应该(46)。当收发两站相距S,光速为C,网络的传输速率为R,发送站的物理层时延为tP
随机试题
Therearesome______flowersonthedesk.
正常人吸入下列哪种混合气体时,肺通气量增加最明显
A、痰巾带血、质浊,有胆臭味B、痰多、色黄、质稠C、痰白、质稀D、脓血相兼浊痰、有腥臭味E、痰少、质粘、夹有血丝咳嗽痰热郁肺证,痰的特点是
高层建筑管道工程施工程序中,管道支架安装的紧后工序是()。
某现浇钢筋混凝土板跨度6m,设计无具体要求,底模及支架拆除时要求混凝土强度达到设计混凝土立方体抗压强度标准值的百分率(%)最小值是()。
汉字系统也是计算机操作系统的一个组成部分。()
2009年某企业拥有房产原值共计8000万元,其中拥有一个内部职工医院、一个幼儿园、一个超市和一个学校,房产的原值分别为350万元、100万元、300万元和240万元。当地政府规定计算房产余值的扣除比例为20%,2009年该企业应缴纳房产税()万
《国家中长期教育改革和发展规划纲要(2010—2020年)》提出,到2020年,巩固提高九年义务教育水平,基本普及(),进一步提高高等教育大众化水平,普及()
“出世便是破蒙,进棺材才算毕业。”这体现了()的思想。
越来越多
最新回复
(
0
)