首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(6
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(6
admin
2010-01-23
79
问题
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(61)。设被排序数据序列有n个元素,冒泡排序算法的复杂性是(62)。
选项
A、O(nlog
2
n)
B、O(n
2
)
C、O(log
2
n)2
D、O(n
2
log
2
n)
答案
B
解析
冒泡排序的过程是先将第1个数与第2个数相比较,若为逆序则交换两数,然后比较每两个数与第三个数,依次类推,直到第n-1个数与第几个数进行过比较为止。上述过程称为一趟冒泡排序,结果是最大的数被排在了最后。然后进行第二趟,对前面n-1个数进行冒泡排序,结果是次大的数被移到了n-1的位置上。一般来说,第i趟冒泡排序是从第一个数到第n-i+1的位置上,整个排序过程需进行k(1≤k≤n)趟。对于题中给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大排序,若先选出较大的元素,则对于冒泡排序,第一趟操作为541←→132,984←→746,984←→518,984←→181,984←→ 946,984←→314,984←→205,984←→827,其结果得到的序列为 (132,541,746,518,181,946,314,205,827,984);对于直接选择排序,第一趟操作为984←→827,其结果得到的序列为(541,132,827,746,518,181,946,314,205,984)。请注意,如果采用快速排序(以中间元素518为基准)的第一趟扫描结果是(205,132,314,181,518,746,946,984,827)。分析冒泡排序的效率,若初始序列为正序,则只进行一次排序。在排序过程中只进行n-1次比较,不交换数据。若为逆序,则需进行n-1趟排序,需进行n(n-1)/2次比较,交换数据的数量组也相同。因此,冒泡排序的复杂性是O(n
2
)。快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序的数据分成两部分,其中一部分的关键字均比另一部分的关键字小,然后再对这两部分分别进行快速排序,最后达到整个序列有序。因此,快速排序的复杂是O(nlog
2
n)。
转载请注明原文地址:https://kaotiyun.com/show/gYxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
令牌总线网中,当所有站都有报文要发送时,最坏情况下等待获得令牌和发送报文的时间应等于(30)。
TCP是一个面向连接的协议,它提供连接的功能是(14)的,采用(15)技术实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(16)的分组,这种分组的数量最多可以(17),TCP协议采用滑动窗口协议来解决了(18)。
HTFP是WWW的核心,它是一个(59)协议,当访问一个URL为http://www.ccidedu.com.cn/index.htm的网页时,浏览器首先向(60)请求解析http://www.ccidedu.com.cn的IP地址。获得解析后的IP
某种中继设备提供运输层及运输层以上各层之间的协议转换,这种中继设备是(19),从OSI协议层次来看,用以实现不同网络间的地址翻译、协议转换和数据格式转换等功能的路由器属于(20)范畴,当采用数据报服务时,负责端到端的流量控制的是(21),路由器的主要功能是
一个复杂的系统可由若干个简单的系统串联或并联构成。已知两个简单系统I和J的失效率分别为λI=25×10-5/h和λJ=5×10-4/h,则由I和J经如图1所示的串联和并联构成的复合系统P和Q的失效率分别为πP=(5)/h和πQ=(6)/h,平均无故障时间分
在多个数据字符组成的数据块之前以一个或多个同步字符SYN作为开始,帧尾是另一个控制字符,这种传输方案称为(31)。
在OSI参考模型中,物理层的功能是(25)等。实体在一次交互作用中传送的信息单位称为(26),它包括(27)两部分。上下邻层实体之间的接口称为服务访问点(SAP),网络层的服务访问点也称为(28),通常分为(29)两部分。
码是一些码字组成的集合。一对码字之间的海明距离是(30),一个码的海明距离是所有不同码字的海明距离的(31)。如果要检查出d位错,那么码的海明距离是(32)。如果信息长度为5位,要求纠正1位错,按照海明编码,需要增加的校验位是(33)。以太网中使用的校验码
下面关于ARP木马的描述中,错误的是()。
目前最流行的无线接入技术类型有哪几种?无线局域网可以在普通局域网基础上通过无线hub、无线接入站(accesspoint,ap,亦译作网络桥通器)、无线网桥、无线modem及无线网卡等来实现。在业内无线局域网多种标准并存,太多的ieee802.11标准
随机试题
王某,男,40岁,多年怕热多汗,焦躁易怒,心率118次/分,多食易饿,体重下降。经查FT4及FT增高,昨天体温突然升高达39.5℃,心率161次/分,烦躁不安,呼吸急促,腹泻,急诊为甲状腺功能亢进伴甲状腺危象。其原因是
不属于医学伦理学原则的是( )
婴儿痉挛首选全身强直-阵挛发作与局限性发作
患者,男,79岁。有冠心病病史多年,形神衰败,身体赢瘦,大肉尽脱,伴心悸自汗,神倦嗜卧,心胸憋闷疼痛,形寒肢冷,面色苍白,舌淡苔白,脉细弱。该患者治疗时,宜首选
()特点是油脂、悬浮物和有机物含量高。
过失犯罪的人虽然也受到过刑罚的制裁,但仍然可以申清领取导游证,旅游主管部门也可以对其颁发导游证。()
有三个旅行团同时进住南京某饭店后,惟有A团一位客人的行李未送进房间,短时间内未能找到,地陪导游员下列做法中正确的是()。
民间美术的艺术语言特征是()
牙本质中龋时牙髓受刺激后可造成()。
Humour,whichoughttogiverisetoonlythemostlight-heartedandgayfeelings,canoftenstirupvehemenceandanimosity.Evi
最新回复
(
0
)