首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
递增序列A(a1，a2，…，abn)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为_____________时，归并过程中元素的比较次数最多。
递增序列A(a1，a2，…，abn)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为_____________时，归并过程中元素的比较次数最多。
admin
2021-01-13
43
问题
递增序列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，将解答填入答题纸的对应栏内。【说明】某学校的教学系统描述如下：学生信息包括：学号(Sno)、姓名(Sname)、性别(Ssex)、年龄(Sage)、入学年份(Syear)、主修专业(Smajor)，其中学号是入学
阅读以下函数说明和C代码，将应填入(n)处的字句写在答题纸对应栏内。【说明】在某些系统中，存在非常复杂的对象，可以采用循序渐进的方式，进行组合将小对象组合成复杂的对象。以下实例展示了Builder(生成器)模式。该实例用来建立“文件”，文件内容包括：一
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某网上药店允许顾客凭借医生开具的处方，通过网络在该药店购买处方上的药品。该网上药店的基本功能描述如下：(1)注册。顾客在买药之前，必须先在网上药店注册。注册过程中需填写顾客资料
阅读下列说明和C语言代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。
某大型商场内安装了多个简易的纸巾售卖机，自动出售2元钱一包的纸巾，且每次仅售出一包纸巾。纸巾售卖机的状态图如图16-2所示。采用状态(State)模式来实现该纸巾售卖机，得到如图16-3所示的类图。其中类State为抽象类，定义了投币、退币、
某集团公司拥有多个大型连锁商场，公司需要构建一个数据库系统以方便管理其业务运作活动。【需求分析结果】(1)商场需要记录的信息包括商场编号(编号唯一)、商场名称、地址和联系电话。某商场信息如表13-1所示。(2)每个商场包含不
(2012年下半年下午试题二)阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某会议策划公司为了方便客户，便于开展和管理各项业务活动，需要构建一个基于网络的会议预定系统。【需求分析】(1)会
关系R、S如下图所示，元组演算表达式{t|(u)(R(t)∧S(u)∧t[3]＞u[1])}的结果为(47)。
设关系模式R(A，B，C)，传递依赖指的是(55)；下列结论错误的是(56)。
为了大幅度提高处理器的速度，当前处理器中采用了指令及并行处理技术，如超标量(Superscalar)，它是指(1)。流水线组织是实现指令并行的基本技术，影响流水线连续流动的因素除数据相关性、转移相关性外，还有(2)和(3)；另外，要发挥流水线的效率，还必须
随机试题
脾肾虚寒，火不生土之五更肾泄之证。治宜用
药物临床试验必须符合
参与式社会评价必须反馈的信息不包括( )。
国务院期货监督管理机构应当制定期货公司持续性经营规则，对期货公司及其分支机构的()提出要求。
ABC公司2015年有关的财务数据如下：要求：假设该公司实收资本一直保持不变，计算回答以下互不关联的4个问题：保持目前的全部财务比率，2016年可实现的销售收入是多少?
设f(x)=nx(1-x)n(n为自然数)，(Ⅰ)求f(x)；(Ⅱ)求证：
在VB6.0中，用于设置ADO结果集的内容，这个内容可以是一张表，也可以来自一个查询语句，还可以来自一个存储过程的执行结果的属性是________。
某商场商品经营管理系统使用SQLServer2008数据库管理系统，此系统上线运行1年后，业务人员使用某统计功能(此功能每月使用一次)时发现速度很慢。该统计功能主要执行的SQL语句如下：SELECT商品号，SUM(销售数量*销售价格)销售额
下列软件中，属于系统软件的是()。
_____we’lldoistoleaveMumanotetotellherthatwewon’tbebacktilltomorrowmorning.
最新回复
(
0
)
