首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
92
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在windows2000操作系统中,配置IP地址的命令是(59)。若用ping命令来测试本机是否安装了TCP/IP协议,则正确的命令是(60)。如果要列出本机当前建立的连接,可以使用的命令是(61)。
商品条码是在流通领域中用于标识商品的(10)通用的条码。条码中的(11)供人们直接识读,或通过键盘向计算机输入数据。
避免死锁的一个著名的算法是(26)。
DHCP协议的功能是(58)。在Linux中提供DHCP服务的程序是(59);DHCP服务将主机的MAC地址和IP地址绑定在一起的方法是在(60)文件中添加:“host主机名{hardwareEthernetxx.xx.xx.xx.xx.xxfixe
公钥密码是(39)。常用的公钥加密算法有(40),它可以实现加密和数字签名,它的一个比较知名的应用是(41),这种应用的协商层用公钥方式进行身份认证,记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。
A向B发送消息P,并使用公钥体制进行数字签名。设E表示公钥,D表示私钥,则B要保留的证据是(45)。基于数论原理的RSA算法的安全性建立在(46)的基础上。Kerberos是MIT为校园网设计的身份认证系统,该系统利用智能卡产生(47)密钥,可以防止窃听
Internet是全球最大的、开放的、由众多网络互联而形成的计算机网络,狭义Internet是指由上述提到网络中采用IP协议的网络互联而成的,广义Internet是指狭义Internet加上所有(12)的网络。Internet体系结构具有良好扩充性的主要原
在OSI参考模型中,物理层的功能是(25)等。实体在一次交互作用中传送的信息单位称为(26),它包括(27)两部分。上下邻层实体之间的接口称为服务访问点(SAP),网络层的服务访问点也称为(28),通常分为(29)两部分。
自标准实施之日起,至标准复审重新确认、修订或废止的时间,称为标准的有效期。我国在国家标准管理办法中规定,国家标准的有效期一般为(11)年。
随机试题
简述公务员考核的原则。
A.藿香正气散B.玉枢丹C.葛根芩连汤D.香连丸治疗湿热泄泻的主方是
患者男,28岁。O型血,患再生障碍性贫血半年,血红蛋白70g/L,白细胞2.2×109/L,血小板20×109/L。该患者早晨刷牙时发现出血,应立即给予的措施是
下列关于阑尾的描述正确的是
对宫颈黏液结晶描述不正确的是
关于幕墙工程后置埋件(锚栓)施工要求的说法,正确的是()。
下列关于党的领导、人民民主专政和依法治国三者关系的说法中,表述正确的是()。①依法治国的本质是保障人民当家作主②党的领导是人民当家作主和依法治国的根本保证③依法治国是党领导人民治理国家的基本方略④人民当家作主是社会主义民主政治的本质要求
AstheSenatepreparestovoteonlegislationtoempowertheFoodandDrugAdministrationtoregulatetobaccoproducts,itsmemb
输入VB源程序时,若一个命令行中包含两个语句,则两个语句之间的分隔符应使用
若有以下程序#include#defineS(x)(x)*(x)#defineT(x)S(x)/S(x)+1main(){intk=3,j=2;printf("%d,%d\n",S(k+j),T(k+j));}则程序的输出结果是()
最新回复
(
0
)