首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
递增序列A(a1，a2，…，abn)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为_____________时，归并过程中元素的比较次数最多。
递增序列A(a1，a2，…，abn)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为_____________时，归并过程中元素的比较次数最多。
admin
2021-01-13
32
问题
递增序列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://jikaoti.com/ti/hGG7FFFM
本试题收录于：
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图，回答以下问题，将解答填入答题纸的对应栏内。【说明】某大学欲开发一个基于Web的课程注册系统，该系统的主要功能如下：1．验证输入信息(1)检查学生信息：检查学生输入的所有注册所需信息。如果信息不合法，返回学生信息不合法提示；如果合法
阅读以下函数说明和Java代码，将应填入(n)处的字句写在答题纸对应栏内。【说明】很多时候，希望某些类只有一个或有限的几个实例，典型解决方案是所谓单身(Singleton)模式。但在多线程情况下，Singleton模式有可能出现问题，需要进行同步检查。
阅读以下说明和图，回答问题l至问题3．将解答填入答题纸的对应栏内。【说明】某时装邮购提供商拟开发订单处理系统，用于处理客户通过电话、传真、邮件或web站点所下订单。其主要功能如下：(1)增加客户记录。将新客广信息添加到客户文件，并分配一个客户号以备后
阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某物流公司为了整合上游供应商与下游客户，缩短物流过程，降低产品库存，需要构建一个信息系统以方便管理其业务运作活动。【需求分析结果】(1)物流公司包
阅读下列说明和C++代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】某大型商场内安装了多个简易的纸巾售卖机，自动售出2元钱一包的纸巾，且每次仅售出一包纸巾。纸巾售卖机的状态如图10．35所示。采用状态(State)
阅读下列说明，回答以下问题，将解答填入答题纸的对应栏内。【说明】某大学拟开发一个用于管理学术出版物(Publication)的数字图书馆系统，用户可以从该系统查询或下载已发表的学术出版物。系统的主要功能如下：1．登录系统。系统的用户(User)仅限
在UML提供的图中，可以采用(30)对逻辑数据库模式建模：(31)用于接口、类和协作的行为建模，并强调对象行为的事件顺序；(32)用于系统的功能建模，并强调对象间的控制流。
在一个单CPU的计算机系统中，采用可剥夺式(也称抢占式)优先级的进程调度方案，且所有任务可以并行使用I/O设备。下表列出了三个任务T1、T2、T3的优先级、独立运行时占用CPU和I/O设备的时间。如果操作系统的开销忽略不计，这三个任务从同时启动到全部结束的
若每一条指令都可以分解为取指、分析和执行三步。已知取指时间t取指=4△t，分析时间t分析=3△t，执行时间t执行=5△t。如果按串行方式执行完100条指令需要(4)△t。如果按照流水方式执行，执行完100条指令需要(5)△t。
从下列叙述中选出5条正确的叙述，并把编号按从小到大次序排列，它们是(51)、(52)、(53)、(54)、(55)。(51)～(55)：A．解释程序是接受参数、按照某一样板产生机器语言的计算机程序B．编译程序是把高级语言书写的计算机程序翻
随机试题
在Word2010中，将光标移至文档尾的快捷键是___________。
激动型G蛋白被激活后可直接激活
下列可以列入集合资产管理计划费用的是()。
1975年，()开展房地产抵押券的期货交易，标志着金融期货交易的开始。
没有一个植物学家的寿命长到足以研究一棵长白山红松的完整生命过程。但是，通过观察处于不同生长阶段的许多棵树，植物学家就能拼凑出一棵树的生长过程。这一原则完全适用于目前天文学对星团发展过程的研究。这些由几十万个恒星聚集在一起的星团，大都有100亿年以上的历史。
A、 B、 C、 D、 C题干第二个图的右下角与C项的右下角相似，第三个图的左下角与C项的左下角相似，进一步组合得到C项。如图所示：
A、正确B、错误A
—Youwillhearacollegelecturertalkingtoaclassofbusinessstudentsaboutamergerbetweentwosupermarketchains.—For
Sincewritinghometotheirparentsformoney,theyhadlived______hope.
MoreattentionwaspaidtothequalityofproductioninFranceatthetimeofReneCoty.CharlesDeschanelwasthenthefinancia
最新回复
(
0
)
