首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
69
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
嵌入式系统设计师上午基础知识考试
软考中级
相关试题推荐
文件型病毒不能感染的文件类型是(49)________________。
一个密码系统如果用E表示加密运算,D表示解密运算,M表示明文,C表示密文,则下面描述必然成立的是(6)________________。
常见的恶意代码类型有:特洛伊木马、蠕虫、病毒、后门、Rootkit、僵尸程序、广告软件。2017年5月爆发的恶意代码WannaCry勒索软件属于(62)________。
已知DES算法S盒如下:如果该S盒输入110011,则其二进制输出为(26)________。
计算机取证是指能够为法庭所接受的、存在于计算机和相关设备中的电子证据的确认、保护、提取和归档的过程。以下关于计算机取证的描述中,不正确的是(22)________。
认证是证实某事是否名副其实或者是否有效的一个过程。以下关于认证的叙述中,不正确的是(16)________。
在事件1中,A公司的分包过程是否妥当?为什么?监理单位的做法妥当吗?阐述监理在实施进度控制时,可以采用的基本措施是什么?
综合布线系统一般由哪几个子系统组成?请列出。请简要叙述采购设备到货监理的工作重点。
在下图所示的树型文件系统中,方框表示目录,圆圈表示文件,“/”表示目录名之间的分隔符,“/”在路径之首时表示根目录。假设“..”表示父目录,当前目录是Y1,那么,指定文件F2所需的相对路径是(29);如果当前目录是X2,“DEL’’表示删除命令,那么,删除
随机试题
采用正反冲砂方式,在改反冲砂前正洗井应不小于()。
Mostpeopleagreethatthedirect,assertive(过分自信的)Americanpersonalityisavirtue,butitsometimessurprisesforeigners.In
取半坐卧位时,床头支架的角度应为
某工业安装项目通过招标,建设单位与土建施工单位和设备安装单位分别签订了施工合同。设备安装时,监理工程师发现土建单位施工的某一设备基础预埋地脚螺栓位置与设备底座相应的尺寸不符,设备安装单位无法将设备安装就位,造成设备安装单位工期延误和费用损失。经调整,土建单
在同一平面图上,任何两条等产量线不能相交。()
营业税的计税依据是()。
教师的终身发展有四个层次。其中,能够研究教学,追求教师在教学工作中的个人价值的实现,在学生的成长中求得自我发展。这属于哪个层次?()
如果政府的主导和介入过强,就容易_______甚至打破政府与社会组织的职责边界,甚至出现政府_______的现象,挤占社会组织自主发展的空间。填入画横线部分最恰当的一项是:
Alan"Ace"GreenbergchosehisnicknametoimprovehischanceswithgirlsattheUniversityofMissouri.Butitisanapt(1)___
John.D.Rockefeller,______,owned90percentofallAmericanoilrefineries.
最新回复
(
0
)