首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
67
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
嵌入式系统设计师上午基础知识考试
软考中级
相关试题推荐
对日志数据进行审计检查,属于__________________类控制措施。
__________________是一种通过对信息进行均衡、全面的防护,提高整个系统最低安全性能的原则。
以下关于IPSec协议的叙述中,正确的是(55)________________。
信息安全风险评估是依照科学的风险管理程序和方法,充分地对组成系统的各部分所面临的危险因素进行分析评价,针对系统存在的安全问题,根据系统对其自身的安全需求,提出有效的安全措施,达到最大限度减少风险、降低危害和确保系统安全运行的目的。风险评估的过程包括(43)
电子邮件已经成为传播恶意代码的重要途径之一,为了有效防止电子邮件中的恶意代码,应该用(25)________________的方式阅读电子邮件。
对信息进行均衡、全面的防护,提高整个系统“安全最低点”的安全性能,这种安全原则被称为(12)________________。
《计算机信息系统安全保护等级划分准则》(GB17859—1999)中规定了计算机系统安全保护能力的五个等级,其中要求对所有主体和客体进行自主和强制访问控制的是(3)________________。
APT攻击是一种以商业或者政治目的为前提的特定攻击,其中攻击者采用口令窃听、漏洞攻击等方式尝试进一步入侵组织内部的个人电脑和服务器,不断提升自己的权限,直至获得核心电脑和服务器控制权的过程被称为(51)________。
对于业主的做法,你认为是否合适?并说明理由。集成商A要对新增和改造软件部分功能进行需求调研和分析,从监理的角度来看,集成商A在本阶段应产出的主要成果是什么?
在下图所示的树型文件系统中,方框表示目录,圆圈表示文件,“/”表示目录名之间的分隔符,“/”在路径之首时表示根目录。假设“..”表示父目录,当前目录是Y1,那么,指定文件F2所需的相对路径是(29);如果当前目录是X2,“DEL’’表示删除命令,那么,删除
随机试题
关于室间隔的膜部的描述,哪项正确()
政协全国委员会行使的职权有()
患者女性,婚后2年同居未孕,月经规律,末次月经后20天出现阴道淋漓出血半月余,止血治疗无效。今日突发下腹痛,测血压90/60mmHg,脉搏110次/分。妇科检查:后穹隆饱满下垂,子宫体水平位,略大,宫颈举痛(+)。此时最佳的检查方法是
A.紫苏B.荆芥C.香薷D.麻黄E.生姜用于止血,宜炒炭用的药物是
桥梁静力荷载试验相对残余变位越大,说明结构越接近弹性工作状态。()
图示平面桁架的尺寸与荷载均已知。其中,杆1的内力FS1为:
按指数计算形式的不同可以分为()。
LessIsMoreItsoundsallwrong—drillingholesinapieceofwoodtomakeitmoreresistanttoknocks.Butitworksbecause
Iwasparkedinfrontofthemallwipingoffmycar.Comingmywayfromacrosstheparkinglotwas【C1】______societywouldconsid
【B1】【B9】
最新回复
(
0
)