首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
67
问题
(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)。
图3-2是该系统类图的一部分,依据上述说明中给出的术语,给出类Lock的主要属性。组装(composition)和聚集(aggregation)是UML中两种非常重要的关系。请说明组装和聚集分别表示什么含义?两者的区别是什么?
阅读以下说明和VisualBasic代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某绘图系统定义了一个抽象类IShape,现有三个类CPoint、CLine和CCircle,它们都具有IShape界面。相应的类图关系如图7-1所示。
阅读下列说明和图,回答问题1~问题3。[说明]某公司的主要业务是出租图书和唱碟。由于业务需求,该公司委托软件开发公司A开发一套信息管理系统。该系统将记录所有的图书信息、唱碟信息、用户信息、用户租借信息等。A公司决定采用面向对象的分析和设计方法开发
识别关联的多重度是面向对象建模过程中的一个重要步骤。根据说明中给出的描述,完成图10-4中的(1)~(6)。关联(Association)和聚集(Aggregation)是UML中两种非常重要的关系。请说明关联和聚集的关系,并说明其不同点。
阅读下列说明和有关的图表,回答问题1至问题3。[说明]A公司决定为该市车站开发自动售票系统,系统的要求如下:1.乘客能按以下三步操作购票:选定目的地;投入钱币;获得一张票。2.当且仅当乘客选定目的地后,系统才接收投钱,每次投
阅读下列程序说明和C++代码,将应填入(n)处的字句写在对应栏内。[说明]①为类Circle增加一个构造函数,该函数有一个参数,并在构造时将该参数值赋给成员radius。将该函数实现为一个非内联函数,并且使用参数列表的方式将类成员赋值。
在(1)空缺处填入所需的实体、联系及其属性,完成概念模型设计。如果允许企业通过互联网修改本企业的基本信息,应对数据库的设计做哪些修改?请用200字以内的文字叙述实现方案。[附]关系模式的标记规则如下:关系名(属性名1,属性名2,
某软件公司现欲开发一款飞机飞行模拟系统,该系统主要模拟不同种类飞机的飞行特征与起飞特征。需要模拟的飞机种类及其特征如表16—4所示。为支持将来模拟更多种类的飞机,采用策略设计模式(Strategy)设计的类图如图16一12所示。图16—12中,Ai
高速的外部设备进行输入输出操作时,采用程序中断方式传送数据,因为速度较慢而不能满足要求,现在多采用直接存储器访问方式(DMA方式),其重要特点是不需要保存现场和恢复现场。这种方式依靠(7)实现直接存储器访问。DMA传送数据时,周期窃取方式要求每传送一个数据
随机试题
A.Aα类纤维B.Aγ类纤维C.B类纤维D.C类纤维自主神经节后纤维属于
膀胱开阖主要依赖于肾气的
我国高程系统采用正常高系统,地面点的正常高的起算面是()。
基础测绘项目目前主要以()的方式确定承担单位。
为了预防旅游者丢失证件、行李、钱物,导游人员应多做()工作。
马丘比丘城是哪个时期的文化遗物()
有些画家有经济头脑,因此,有些有经济头脑的人是炒股高手。为使上述推理成立,必须补充以下哪项作为前提?
Onereasonwhyshareholderactivismhasbeenincreasingisthatregulatorshaveencouragedit,especiallyonpay.ForadecadeB
按照“后进先出”原则组织数据的数据结构是()。
A、Shegot100onthelasttestB、SheisafriendofKaven.C、Shereviewedtheproblems.D、Shegivesthewomanacall.A男士说他希望认识他
最新回复
(
0
)