首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2012年上半年上午试题61)递增序列A(a1,a2,…,an)和B(b1,b2,…,bn)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为________时,归并过程中元素的比较次数最多。
(2012年上半年上午试题61)递增序列A(a1,a2,…,an)和B(b1,b2,…,bn)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为________时,归并过程中元素的比较次数最多。
admin
2019-07-12
50
问题
(2012年上半年上午试题61)递增序列A(a
1
,a
2
,…,a
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
<b
i
<a
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次。由选项D给出的结果可知,递增序列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
i/2+3
,…,a
n
分别与b
i/2+1
进行比较,共比较了n-i/2-2次,完全排好时共比较了i+1+n-i/2-2=n+i/2-1次。
转载请注明原文地址:https://kaotiyun.com/show/VmCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
软件开发中的瀑布模型典型地刻画了软件生存周期的阶段划分,与其最相适应的软件开发方法是(9)。
数据流图4-1(住宅安全系统顶层图)中的A和B分别是什么?试说明逻辑数据流图(logicaldataflowdiagram)和物理数据流图(physicaldataflowdiagram)之间的主要差别。
阅读以下说明和Java代码,将应填入(n)处。[说明]在一公文处理系统中,开发者定义了一个公文类OfficeDoc,其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时,关注此OfficeDoc类对象的相应的DocExplo
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。[说明]某公司计划与客户通过Internet交换电子邮件和数据(以下统一称为“消息”)。为保障安全,在对传输的数据进行加密的同时,还要对参与通信的实体进行身份认证。因此,需同时使用
根据题意,补充图2-3中(a)处的空缺,即货物关系模式的属性。写出每种关系模式的主键。
阅读以下说明和图,填补流程图中的空缺。【说明】某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。(1)e0和e1表示底盘分别进入装配线0和
请采用说明中的词汇,给出数据确认处理所需的数据流在第1层图中的全部可选起点(第0层图和第1层图中均未给出)。加工1(录入比对处理)除能够检查出初录数据和复录数据不一致外,还应当检测出下列哪些错误。①输入的无效字符②输入的半个
阅读下列说明,回答问题1至问题4,将解答填入对应栏内。【说明】某汽车维修站拟开发一套小型汽车维修管理系统,对车辆的维修情况进行管理。1.对于新客户及车辆,汽车维修管理系统首先登记客户信息,包括:客户编号、客户名称、客户性质(个人、单位)
阅读下列说明和Java代码,将应填入(n)处的字句写在对应栏内。【说明】已知某企业欲开发一家用电器遥控系统,即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如下图(a)所示。该遥控器共有4今按钮,编号分别是0至3,按钮0和2能够遥控打开电
阅读下列程序说明和C程序,将应填入(n)处的字句写在答卷纸的对应栏内。【程序说明】该程序定义了两个子函数strsort和strmerge。它们分别实现了将一个字符串按字母顺序排序和将两个字符串合并排序,并删去相同字符。在主函数里,先输入两个
随机试题
某商业建筑,东西长100m,南北宽60m,建筑高度26m,室外消火栓设计流量为40L/s,南侧布置消防扑救面。沿该建筑南侧消防扑救面设置的室外消火栓数量,不宜少于()个。
患者因受精神刺激突发二便失禁,骨酸痿厥或遗精。其病机是患者因受精神刺激而气逆喘息,面红口赤,呕血,昏厥卒倒。其病机是
下列有抗原性的纤维蛋白溶解药是
外加剂储存时应当至少离地的高度和离墙的距离分别是()。
下列各项中,可能与“应付职工薪酬”科目贷方对应的有()。
沂源:苹果:水果
某种商品有小箱和大箱两种包装,一大箱这种商品有400件,张和王同时开始制造这种商品,制造一小箱和一大箱这种商品后,张比王多做50件。如果王此时的效率提高100%,并与张再共同制造一大箱这种商品,则王制造的总件数比张多50件。问一小箱这种商品有多少件:
下列成语及其出处的对应关系错误的是()。
Manhasbeenstoringupusefulknowledgeabouthimselfandtheuniverseattheratewhichhasbeenspiralingupwardfor10,000y
【B1】【B8】
最新回复
(
0
)