首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
57
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(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
嵌入式系统设计师上午基础知识考试
软考中级
相关试题推荐
1949年,__________________发表了题为《保密系统的通信理论》的文章,为密码技术的研究奠定了理论基础,由此密码学成了一门科学。
当防火墙在网络层实现信息过滤与控制时,主要针对TCP/IP协议中的IP数据包头制定规则匹配条件并实施过滤,该规则的匹配条件不包括(63)________________。
以下关于VPN的叙述中,正确的是(61)________________。
计算机犯罪是指利用信息科学技术且以计算机为犯罪对象的犯罪行为,与其他类型的犯罪相比,具有明显的特征,下列说法中错误的是(46)________________。
下列说法中,错误的是(23)________________。
《计算机信息系统安全保护等级划分准则》(GB17859—1999)中规定了计算机系统安全保护能力的五个等级,其中要求对所有主体和客体进行自主和强制访问控制的是(3)________________。
APT攻击是一种以商业或者政治目的为前提的特定攻击,其中攻击者采用口令窃听、漏洞攻击等方式尝试进一步入侵组织内部的个人电脑和服务器,不断提升自己的权限,直至获得核心电脑和服务器控制权的过程被称为(51)________。
研究密码破译的科学称为密码分析学。密码分析学中,根据密码分析者可利用的数据资源,可将攻击密码的类型分为四种,其中适于攻击公开密码体制,特别是攻击其数字签名的是(6)________。
指出该工程招投标过程中的不妥之处,为什么?监理单位认为建设单位采取邀请招标的方式不妥当的依据是什么?
随机试题
霍奇金淋巴瘤伴有大量淋巴细胞弥漫增生的组织学类型是
男,38岁,吸烟10年,已戒烟1年。检查:双颊黏膜及舌背黏膜有片状白色均质的斑块,表面高低不平,质地稍硬,不能被擦掉。该患者白色病损最可能的临床印象是
患儿,3岁。低热恶寒,鼻塞流涕,全身皮肤成批出疹,为红色斑疹和斑丘疹,继有疱疹,疱浆清亮,头面、躯干多见,舌红,苔薄白,脉浮数。其诊断是
口服补液盐按规定冲后其中含钠液相当于
行业自律与行政监督对于维护和规范招标投标秩序的不同作用主要体现在()。
室外消防给水管道的最小直径不应小于()mm。
背景资料沿海地区某住宅工程,该工程由4栋地上12层,地下1层,结构形式完全相同的单体组成,其中地下室为整体连接地下室。该工程地下水系发达,地下水对钢筋混凝土结构有侵蚀作用。屋面设计为不上人屋面,炉渣保温后细石混凝土封面找坡,最上层敷设SBS卷材防水层一道
下列业务中,“营改增”试点纳税人可以选择简易计税方法计算缴纳增值税的是()。(2014年)
生活贫困、疾病流行、文化落后以及不和谐的家庭环境,是影响学前儿童生长发育的(。)因素。
口腔牙种植成功的生物学基础是()。
最新回复
(
0
)