首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
递增序列A(a1，a2，…，abn)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为_____________时，归并过程中元素的比较次数最多。
递增序列A(a1，a2，…，abn)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为_____________时，归并过程中元素的比较次数最多。
admin
2021-01-13
40
问题
递增序列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代码，将应填入(1)～(6)处的字句写在答题纸的对应栏内。【说明】现欲开发一个软件系统，要求能够同时支持多种不同的数据库，为此采用抽象工厂模式设计该系统。以SQILServer和Access两种数据库以及系统中的数
【说明】假定用一个整型数组表示一个长整数，数组的每个元素存储长整数的一位数字，则实际的长整数m表示为：m=a[k]×10k-2+a[k一1]×10k-3+…+a[3]×10+a[2]其中a[1]保存该长整数的位数，a[0]保存该长整数的符号：0表示正数、
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某汽车数字仪表系统将完成下述功能：(1)通过模．数转换，实现传感器和微处理器的接口。(2)在发光二极管面板上显示数据。(3)指示速度(mph)、行驶里程、油耗(mpg)等。
阅读下列说明和E—R图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】建立一个供应商零件数据库，数据库要满足如下要求：(1)供应商代码不能为空，且是值唯一的，供应商的名也是唯一的。(2)零件号不能为空，且值是唯一的，零件号不能为空。(3
阅读下列函数说明和C++代码，将应填入(n)处的字句写在答题纸对应栏内。【说明】在某些系统中，存在非常复杂的对象，可以采用循序渐进的方式进行组合，将小对象组合成复杂的大对象。以下实例展示了Builder(生成器)模式。该实例用来建立“文件”，文件内容包
阅读下列说明和图，回答问题l至问题3，将解答填入答题纸对应栏内。【说明】某城市拟开发一个基于web的城市黄页，公开发布该城市重要的组织或机构(以F统称为客户)的基本信息，方便城市生活。该系统的主要功能描述如下：(1)搜索信息：任何使用Internet的
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】某应用中需要对100000个整数元素进行排序，每个元素的取值在0～5之间。排序算法的基本思想是：对每一个元素x，确定小于等于x的元素个数(记为m)，将x放在输出元素序列的第m
阅读下列说明、图和C代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】一般的树结构常采用孩子一兄弟表示法表示，即用二叉链表作树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如，题图4-1(a)所示的树
为了大幅度提高处理器的速度，当前处理器中采用了指令及并行处理技术，如超标量(Superscalar)，它是指(1)。流水线组织是实现指令并行的基本技术，影响流水线连续流动的因素除数据相关性、转移相关性外，还有(2)和(3)；另外，要发挥流水线的效率，还必须
高度为h的堆中，最多有(52)个元素，最少有(53)个元素，在大根堆中，关键字最小的元素可能存放在堆的(54)地方。
随机试题
下列哪些是癃闭的病因
心力衰竭患者哪种情况下不宜用血管扩张剂治疗
蔓延到子宫和输卵管以外的其他盆腔组织，无腹膜种植仅转移到输卵管
A．膝关节B．肘关节C．前臂D．上臂E．大腿最容易发生骨筋膜室综合征的是
当采用S曲线比较法时，如果实际进度点位于计划S曲线的右侧，则该点与计划S曲线的垂直距离表明实际进度比计划进度()。
下列对蒸汽状态污染物描述不正确的是( )。
根据《企业破产法》的规定，申请人在提出破产申请后可以请求撤回破产申请的时间是()。
法律事实分为两类，一类是法律事件，一类是()。
芒果、荔枝、桂圆这些南方水果珍品，大庆人过去只能在电视上看到或在罐头中尝过。现在它们已经摆在大庆市各农贸市场、楼区居民点的水果摊上。寻常百姓不必远涉千山万水到广东、海南水果的产地或驱车几百千米到哈尔滨去买，只需走几步就可大饱口福了。这段短文的主要内容是：
简述杨贤江“全人生指导”思想的基本内容。
最新回复
(
0
)
