首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
58
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
嵌入式系统设计师上午基础知识考试
软考中级
相关试题推荐
工控系统广泛应用于电力、石化、医药、航天等领域,已经成为国家关键基础设施的重要组成部分。作为信息基础设施的基础,电力工控系统安全面临的主要威胁不包括__________________。
ISO制定的安全体系结构描述了5种安全服务,以下不属于这5种安全服务的是__________________。
身份识别在信息安全领域有着广泛的应用,通过识别用户的生理特征来认证用户的身份是安全性很高的身份认证方法。如果把人体特征用于身份识别,则它应该具有不可复制的特点,必须具有__________________。
在PKI中,关于RA的功能,描述正确的是(60)________________。
IP地址分为全球地址和专用地址,以下属于专用地址的是(42)________________。
常见的恶意代码类型有:特洛伊木马、蠕虫、病毒、后门、Rootkit、僵尸程序、广告软件。2017年5月爆发的恶意代码WannaCry勒索软件属于(62)________。
APT攻击是一种以商业或者政治目的为前提的特定攻击,其中攻击者采用口令窃听、漏洞攻击等方式尝试进一步入侵组织内部的个人电脑和服务器,不断提升自己的权限,直至获得核心电脑和服务器控制权的过程被称为(51)________。
信息安全风险评估是指确定在计算机系统和网络中每一种资源缺失或遭到破坏对整个系统造成的预计损失数量,是对威胁、脆弱点以及由此带来的风险大小的评估。在信息安全风险评估中,以下说法正确的是(43)________。
指出该工程招投标过程中的不妥之处,为什么?监理单位认为建设单位采取邀请招标的方式不妥当的依据是什么?
随机试题
论述专利取得中的先申请原则。
肥大细胞主要参与
必须进行药品集中采购的药品是
A、羌活B、前胡C、白芷D、南沙参E、北沙参体轻,质松泡,上部多有深陷横纹,呈断续的环纹的药材为
企业可以通过股票投资实现对其他企业的控股或参股,也可以将暂时闲置的资金通过自营或委托专业机构进行证券投资以获取收益。( )
按提供服务的种类划分,第三方物流企业分为()。
世界七大古迹之一的亚历山大灯塔遗迹位于埃及的()。
下列生活常识说法正确的有:
对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为
SpeakerA:Whatseemstobetheproblemwiththeblouse,miss?SpeakerB:______
最新回复
(
0
)