首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
36
问题
(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)。
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某指纹门禁系统的体系结构如图3-1所示，其主要部件有：主机(MainFrame)、锁控器(LockController)、指纹采集器(FingerReader)和电控锁(L
阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。【说明】一个印刷电路板的布线区域可分成n×m个方格，如图3-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直
根据题意，补充图2-3中(a)处的空缺，即货物关系模式的属性。写出每种关系模式的主键。
经过进一步分析，设计人员决定定义一个类Itemsonloan，以表示类Book和CD的共有属性和方法。请采用图1-2中属性和方法的名称给出类Items_on_loan应该具有的属性和方法(注意：不同名称的属性和方法表示不同的含义，如CD中的compos
请用120字以内文字，从业务的继承性、升级成本(时间、工作量)和扩展性三个方面简要说明开发人员所提方案的优点。服务注册中心、服务提供者和服务请求者之间的交互和操作构成了WebService的体系结构，如下图所示。请用180字以内文字，说明这三者的主要
阅读下列说明和Java代码，将应填入(n)处的字句写在对应栏内。【说明】已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如下图(a)所示。该遥控器共有4今按钮，编号分别是0至3，按钮0和2能够遥控打开电
[说明]下面是一个Appkt程序，其功能是从3～100之间(包括3和100)每隔0.5秒显示一个新的数字，如果数字为素数，则显示为灰色，其他为绿色。程序运行结果如图4所示。importjava.awt.*
请认真阅读以下关于电子政务信息整合的叙述，根据要求回答问题1～问题4。[说明]公共服务、社会监督和宏观调控是我国政府的3个主要职能。实施电子政务建设，可以改善政府的公共服务质量，提高社会监管的效率和准确性，加强宏观经济调控的科学性。
请使用[说明]中给出的词汇，将该房屋租赁服务系统顶层数据流图(见图5-10)中(1)～(4)空缺处的数据流补充完整。请使用[说明]中给出的词汇，将该房屋租赁服务系统第0层数据流图(见图5-11)中的(5)～(8)空缺处的数据存储补充完整。
随机试题
对于人视网膜盲点的叙述，恰当的是
由于儿童生理解剖方面的特点，应慎重选择给药途径，严格掌握用药剂量。儿童用药最适宜的给药途径是
患者，女，40岁。患有特发性血小板减少性紫癜。下肢皮肤紫斑，月经色紫暗有血块，伴腹痛，头晕目眩，面色黧黑，舌紫暗，脉细涩。治疗应首先考虑的方剂是
招标人根据工程实际情况需要修改投标人须知的有关内容可以在（）进行修改。
中国证监会或者其派出机构对拟任人的能力、品行和资历进行审查的方式有( )。
住房城乡建设部、财政部、国家发展改革委12月6日对外公布《关于公共租赁住房和廉租住房并轨运行的通知》，从2014年起，各地公共租赁住房和廉租住房并轨运行，并轨后统称为()。
2019年12月，《自然资源部农业农村部关于设施农业用地管理有关问题的通知》发布。根据该通知，关于我国设施农业用地管理，下列说法正确的是()。
(中央财经大学初试真题)私营企业不缴纳企业所得税。()
计算机网络的基本分类主要有两种：一种是根据网络所使用的传输技术；另一种是根据_______。
Whenyouaresmall,allambitionsfallintoonegrandcategory:whenI’mgrownup.WhenI’mgrownup,yousay,I’llgoupinspa
最新回复
(
0
)
