首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946, 314,205,827)进行从小到大的排序时,采用快速排序(以中间元素518为
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946, 314,205,827)进行从小到大的排序时,采用快速排序(以中间元素518为
admin
2009-02-15
55
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946, 314,205,827)进行从小到大的排序时,采用快速排序(以中间元素518为基准)的第一趟扫描结果是(40)。设被排序数据序列有n个元素,快速排序的复杂性是(41)。
选项
A、O(nlbn)
B、O(n
2
)
C、O(1bn)
2
D、O(n
2
lbn)
答案
A
解析
冒泡排序的过程很简单。首先将第1个数与第2个数相比较,若为逆序则交换两数,然后比较前两个数与第3个数,依次类推,直到将第n-1个数与第n个数比较完为止。上述过程称为一趟冒泡排序,结果是最大的数被排到了最后。然后进行第2趟,对前面n-1个数进行冒泡排序,结果是次大的数被移到了n-1的位置上。一般来说,第i趟冒泡排序是将第1个数排到了第n-i+1的位置上,整个排序过程需进行k(1≤k≤ n)趟。
分析冒泡排序的效率时,若初始序列为正序,则只进行一道排序,在排序过程中只进行n-1次比较,不交换数据;若为逆序,则需进行n-1趟排序,需进行n(n-1)/2次比较,交换数据的数量组也相同。因此,冒泡排序的复杂性是O(n
2
)。快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序的数据分成两部分,其中一部分的关键字均比另一部分的关键字小,然后再对这两部分分别进行快速排序,最后达到整个序列有序的目的。快速排序的复杂性是O(nlbn)。
将题中给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小
(132,541,746,518,181,946,314,205,827,984);对于直接选择排序,第1趟操作为 984827,其结果得到的序列为(541,132,827,746,518,181,946,314,205,984)。
采用快速排序(以中间元素518为基准)的第1趟扫描结果是(205,132,314,181, 518,746,946,984,827)。
转载请注明原文地址:https://kaotiyun.com/show/KUWZ777K
本试题收录于:
嵌入式系统设计师上午基础知识考试题库软考中级分类
0
嵌入式系统设计师上午基础知识考试
软考中级
相关试题推荐
信息系统安全测评方法中的模糊测试是一种黑盒测试技术,它将大量的畸形数据输入到目标程序中,通过监测程序的异常来发现被测程序中可能存在的安全漏洞。关于模糊测试,以下说法错误的是__________________。
下列关于公钥密码体制说法不正确的是(66)________________。
对信息进行均衡、全面的防护,提高整个系统“安全最低点”的安全性能,这种安全原则被称为(12)________________。
S/Key口令是一种一次性口令生成方案,它可以对抗(7)________________。
一个密码系统如果用E表示加密运算,D表示解密运算,M表示明文,C表示密文,则下面描述必然成立的是(6)________________。
物理安全是计算机信息系统安全的前提,物理安全主要包括场地安全、设备安全和介质安全。以下属于介质安全的是(56)________。
对于业主的做法,你认为是否合适?并说明理由。集成商A要对新增和改造软件部分功能进行需求调研和分析,从监理的角度来看,集成商A在本阶段应产出的主要成果是什么?
阅读下列说明,回答问题1至问题3。[说明]某“校校通”工程项目的建设内容包括光纤物理网建设、业务网工程建设、应用服务系统集成、机房建设等内容。
阅读下面的叙述,回答问题1、问题2,将解答填入对应栏内。【说明】建设单位重新招标后确定A公司中标,并签定合同。在项目实施过程中发生了导致应用系统崩溃的质量事故。经调查组技术鉴定,认为是A公司项目组为了赶工忽略了软件配置管理,擅自发布未经许可验证的
在下图所示的树型文件系统中,方框表示目录,圆圈表示文件,“/”表示目录名之间的分隔符,“/”在路径之首时表示根目录。假设“..”表示父目录,当前目录是Y1,那么,指定文件F2所需的相对路径是(29);如果当前目录是X2,“DEL’’表示删除命令,那么,删除
随机试题
《德伯家的苔丝》的艺术特色。
A.硼砂B.雄黄C.轻粉D.水银E.朴硝不宜与砒石同用的药物是
男,48岁。因右胫骨平台骨折术后软组织感染1个月余入院治疗。骨科主治医师王某建议进行专家会诊。会诊后决定采用保守治疗,既避免手术治疗造成软组织的进一步损伤,又能节约费用。治疗期间患者经常出现紧张、焦虑,害怕出现组织坏死甚至截肢等严重后果,影响睡眠和康复。
苯海索治疗帕金森病的作用机制主要是( )。
建筑防雷保护装置由()组成。
施工单位中标后与建设工程项目招标人进行合同谈判后达成一致的内容,应以( )方式确定下来作为同的附件。
“蓝洞”是指在海岸或珊瑚礁礁盘的浅水区域被海水覆盖的水下洞穴。我国三沙市永乐环礁中的蓝洞“永乐龙洞”(16°3l'30"N,如下图)深达300.89米,是全球已发现的最深蓝洞。地学家们一般认为“永乐龙洞”应为在第四纪冰期海平面最低时期以前由陆地水溶蚀形成
【2012下】下列现象中,可依法追究刑事责任的是()。
在某计算机中采用了多级存储体系,设计有cache,主存和磁盘。假设访问cache一个字需要花费10ns,若该字不在cache中但是存在在主存中,那么需要100ns载入cache,然后重新开始定位。若该字既不在cache中,也不在主存中,那么需要10m
Justbecausetheycan’tsingoperaorrideabicycledoesn’tmeanthatanimalsdon’thaveculture.There’snobetterexampleof
最新回复
(
0
)