首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
递增序列A(a1,a2,…,abn)和B(b1,b2,…,bn)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为_____________时,归并过程中元素的比较次数最多。
递增序列A(a1,a2,…,abn)和B(b1,b2,…,bn)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为_____________时,归并过程中元素的比较次数最多。
admin
2021-01-13
44
问题
递增序列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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】欲开发一个绘图软件,要求使用不同的绘图程序绘制不同的图形。以绘制直线和圆形为例,对应的绘图程序如表6.1所示。该绘图软件的扩展性要求,将不断扩充
阅读下列说明和C程序,将应填入(n)处的字句写在答题纸对应栏内。【说明】借助一个栈结构,可实现二叉树的非递归遍历算法。InOrderTraverse函数实现中序非递归遍历,遍历过程如下:若不是空树,根节点入栈,进入左子树;若已经是空树,则栈顶元素出栈,
阅读下列说明和数据流图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】下面给出的是某房产管理系统的一套分层数据流图。其功能描述如下:(1)系统随时根据住房送来的入住单更新住户基本信息文件;(2)每月初系统根据物业管理委员会提供的月附加费(
阅读以下说明和Java代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】在销售系统中常常需要打印销售票据,有时需要在一般的票据基础上打印脚注。这样就需要动态地添加一些额外的职责。如下展示了Decorator(修饰)模式。Salesorder对象使
阅读以下函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】在某些系统中,存在非常复杂的对象,可以采用循序渐进的方式,进行组合将小对象组合成复杂的对象。以下实例展示了Builder(生成器)模式。该实例用来建立“文件”,文件内容包括:一
阅读以下说明,根据要求回答问题1~问题3。【说明】某快递公司为了方便管理公司物品运送的各项业务活动,需要构建一个物品运送信息管理系统。【需求分析结果】(1)快递公司有多个分公司,分公司信息包括分公司编号、名称、经理、办公电话和地址。每个分公司可以
阅读以下说明和C代码,根据要求回答问题1~问题3。【说明】某工程计算中要完成多个矩阵相乘(链乘)的计算任务。两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数,计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法,计算Am×n*Bn×p,需要m
某大型商场内安装了多个简易的纸巾售卖机,自动出售2元钱一包的纸巾,且每次仅售出一包纸巾。纸巾售卖机的状态图如图16-2所示。采用状态(State)模式来实现该纸巾售卖机,得到如图16-3所示的类图。其中类State为抽象类,定义了投币、退币、
网络的几种拓扑结构中,在使用(61)时,各节点与中央单元进行连接,导致中央单元负荷重。
(8)主要包括网络模拟攻击、报告服务进程、漏洞检测、提取对象信息,以及评测风险、提供安全建议和改进措施等功能。
随机试题
下列关于最密切联系原则应用的说法中,不正确的是()
试排牙时发现,患者微笑时可见上前牙龈缘,口微闭时上前牙切缘位于唇下2mm,第二前磨牙近中面位于口角。此时应该
某设计单位为拟建工业厂房提供三种屋面防水保温工程设计方案,供业主选择。方案一,硬泡聚氨酯防水保温材料(防水保温二合一);方案二,三元乙丙橡胶卷材(δ=2×1.2mm)加陶粒混凝土;方案三,SBS改性沥青卷材(δ=2×3mm)加陶粒混凝土。三种方案的综合单价
南方电子电气有限公司(建设单位)新建液晶屏(LCD)生产车间,其生产线由建设单位从国外订购,A施工单位承包安装。A施工单位进场时,生产车间的土建工程和机电配套工程(B施工单位承建)已基本完工。A施工单位按合同工期要求,与建设单位、生产线供应商和B施工单位洽
被审计单位作出了不恰当会计估计,但所涉及金额远远低于重要性水平。在不考虑其他因素的情况下,注册会计师应出具的审计报告类型是()。
一、注意事项1.申论考试是对应考者阅读理解能力、综合分析能力、提出和解决问题能力、文字表达能力的测试。2.参考时限:阅读资料40分钟,作答110分钟。3.仔细阅读给定资料,按照后面提出的“作答要求”作答。二、给定资料
(1)植物进行光合作用(2)阳光普照大地(3)煤炭自地下被开采出来(4)马达轰鸣、机器飞转(5)火电厂发电并网
下列情形符合法律规定的是()。
–Est-cequevouspouvezfairevotretoilettedansvotrechampe?--Non,maisnousavons_____grandlavabo_____bout_____coul
Honeybeepopulationsdeclinedby13.6%overthewinter,accordingtoasurveyofbeekeepersacrossEngland.Lossesweremostsev
最新回复
(
0
)