首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
递增序列A(a1,a2,…,abn)和B(b1,b2,…,bn)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为_____________时,归并过程中元素的比较次数最多。
递增序列A(a1,a2,…,abn)和B(b1,b2,…,bn)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为_____________时,归并过程中元素的比较次数最多。
admin
2021-01-13
46
问题
递增序列A(a
1
,a
2
,…,ab
n
)和B(b
1
,b
2
,…,b
n
)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为_____________时,归并过程中元素的比较次数最多。
选项
A、a
1
,a
2
,…,a
n
,b
1
,b
2
,…,b
n
B、b
1
,b
2
,…,b
n
,a
1
,a
2
,…,a
n
C、 a
1
,b
1
,a
2
,b
2
,…,a
i
,b
i
,…,a
n
,b
n
D、 a
1
,a
2
,…,a
i/2
,b
1
,b
2
,…,b
i/2
,a
i/2+1
,a
i/2+2
,…,a
n
,b
i/2
+1,b
i/2+2
,…,b
n
答案
C
解析
归并排序是将两个排好序的序列合并成一个有序的序列。由选项A给出的结果可知,递增序列B的每一个元素都比A中的元素要大,也就是说a
i
(1≤i≤n)比b
1
小,在排序的过程中,只需要将a
i
与b
1
进行比较,共比较了n次。由选项B给出的结果可知,递增序列B的每一个元素都比A中的元素要小,在排序的过程中,只需要将b
i
(1≤i≤n)与a
1
进行比较,共比较了n次。由选项C给出的结果可知,a
i
i
i+1,在排序的过程中,将a
1
与b
1
进行比较,a
1
小,然后将a
2
与b
1
进行比较,a
2
大,则已排好的部分为a
1
b
1
,共比较了2次;然后将a
2
与b
2
进行比较,a
2
小,再将a
3
与b
2
进行比较,a
3
大,则已排好的部分为a
1
b
1
a
2
b
2
,共比较了4次;以此类推,完全排好时共比较了2(n一1)+1=2n一1次。由选项A给出的结果可知,递增序列B的前i/2个元素都比A中的前i/2个元素要大,但比A中的后i/2个元素要小,B的后i/2个元素都比A中的后i/2个,因此在排序的时候,a的前i/2个元素只需与b
1
进行比较,当比较到a
i/2+1
时,a
i/2+1
比b
1
大,则已排好的部分为a
1
,a
2
,…,a
i/2
,共比较了i/2+1次;然后将b
2
,b
3
,…,b
i/2
与a
i/2+1
进行比较,都比与a
i/2+1
小,当比较到b
i/2+1
时,b
i/2+1
比a
i/2+1
大,则已排好的部分为a
1
,a
2
,…,a
i/2
,b
1
.b
2
,…,b
i/2
,共比较了i+1次;然后将a
i/2+2
…,a
n
分别与b
i/2+1
进行比较,共比较了n一i/2—2次,完全排好时共比较了i+1+n—i/2—2=n+j/2—1次。
转载请注明原文地址:https://kaotiyun.com/show/fCCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某大型旅店为了便于管理,欲开发一个客房管理系统。希望实现客房预定、入住登记、帐务结算、退房,以及将服务项目记入客人帐单。旅客包括散客和团体,散客预定或入住时需要提供姓名、性别、身
阅读下列说明和图,回答问题l至问题3,将解答填入答题纸对应栏内。【说明】某城市拟开发一个基于web的城市黄页,公开发布该城市重要的组织或机构(以F统称为客户)的基本信息,方便城市生活。该系统的主要功能描述如下:(1)搜索信息:任何使用Internet的
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某大型企业的数据中心为了集中管理、控制用户对数据的访问并支持大量的连接需求,欲构建数据管理中间件,其主要功能如下:(1)数据管理员可通过中间件进行用户管理、操作管理和权限管理。
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某医院拟开发一套住院病人信息管理系统,以方便对住院病人、医生、护士和手术等信息进行管理。【需求分析】(1)系统登记每个病人的住院信息,包括:病案号、病人的姓名、性别、地址、身
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
两个公司希望通过Internet进行安全通信,保证从信息源到目的地之间的数据传输以密文形式出现,而且公司不希望由于在传输节点使用特殊的安全单元而增加开支,最合适的加密方式是(10),使用的会话密钥算法应该是(11)。
请根据下面叙述的场景选用适当的设计模式。若某面向对象系统中的某些类有且只有一个实例,那么采用(42)设计模式能够有效达到该目的;该系统中的某子模块需要为其他模块提供访问不同数据库系统(Oracle、SQLServer、DB2UDB等)的功能,这些数据库系统
在过程式程序设计(①)、数据抽象程序设计(②)、面向对象程序设计(③)、泛型(通用)程序设计(④)中,C++语言支持(16),C语言支持(17)。
从下列叙述中选出5条正确的叙述,并把编号按从小到大次序排列,它们是(30)。 ①解释程序是接受源程序,将其转换成中间代码,然后对其解释执行,它并不产生机器代码 ②编译程序是把高级语言书写的程序,翻成中间代码,然后逐条执行,产生机器代码
下列叙述中正确的是(28)。
随机试题
下列行为中构成专利侵权的是()。
从造字法来看,“明”是_____字。
女,65岁,因头痛、右侧肢体无力7天入院。胸片:右肺可见圆形病灶,头部CT提示脑转移瘤,肿瘤周围脑水肿明显。本例瘤周水肿系
某研究者收集了2种疾病患者痰液内嗜酸性粒细胞的检查结果,整理成下表:若要比较2种疾病患者痰液内的嗜酸性粒细胞数是否有差别应选择
在下列关于财务管理“引导原则”的说法中,错误的是()。
关于老年人的权益,尤其是精神方面的保护,最近进行了立法,谈谈对这一问题的看法。
关于香港特别行政区的政府,说法正确的有()。
Whyare"HowTo"booksingreatdemandintheUnitedStates?
Whatistherelationshipbetweenthetwopersons?
A—thechiefcoachB—thechiefrefereeC—thedefenderD—centreforwardE—thesecon
最新回复
(
0
)