首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
64
问题
(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在需求分析阶段，采用UML的用例图(usecasediagram)描述系统功能需求，如图4-4所示。指出图中的A,B,C和D分别是哪个用例?在UML中，重复度(multiplicity)定义了某个类的一个实例可以与另一个类的多个实例相关联。通常把它
阅读下列说明和E-R图，回答问题1至问题3，将解答填入答题纸的对应栏内。说明某网上订书系统的E-R图(已消除了不必要的冗余)如图2-1所示(图中没有标出主码)。图中实体的说明如表2-1所示，相关属性说明如表2-2所示。一个顾客可以在同一天填写
阅读下列说明、图和C代码。[说明5-1]B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树：①树中每个结点最多有m棵子树；②若根结点不是叶子结点，则它至少有两棵子树；⑧除根之外的所有非叶子结点至少有
请用120字以内文字，从业务的继承性、升级成本(时间、工作量)和扩展性三个方面简要说明开发人员所提方案的优点。WebService的三个基本技术是WSDL、SOAP、UDDI，它们都是以XML为基础定义的。请用120字以内文字，简要说明WSDL、SO
阅读以下说明和C++代码。【说明】传输门是传输系统中的重要装置。传输门具有Open(打开)、Closed(关闭)、Opening(正在打开)、StayOpen(保持打开)和Closing(正在关闭)五种状态。触发传输门状态转换的事件有click
用例图解释了活动者与用例之间的交互关系。根据系统设计说明，将系统的顶层用例图补充完整。图10-8为选课注册顺序图，请根据系统设计说明及图中信息，采用说明中的术语将选课注册顺序图补充完整。
软件(32)的提高，有利于软件可靠性的提高。
相比于TCP，UDP的优势为()。
随机试题
开发区土地集约利用评价的对象为()。
不属于建设选址规划管理内容的是()。
抹面砂浆一般可分为()。
证券公司与期货公司签订、变更或者终止委托协议的，双方应当在()个工作日内报各自所在地的中国证监会派出机构备案。
基金单位资产净值的计算公式为()。
某企业2015年支付如下费用：合同工工资105万元，实习生工资20万元，返聘离休人员工资30万元，劳务派遣公司用工费40万元。2015年企业计算企业所得税时允许扣除的职工工会经费限额是()万元。(2016年回忆版)
在《巴塞尔新资本协议》中，违约概率被具体定义为借款人贷款期违约概率与0．03％中的较高者。()
李某为其母亲赵某投保人寿险，在确定具体受益人时李某与赵某发生了分歧，下列关于如何确定受益人的表述中，符合保险法律制度规定的是()。
【倭仁】南京大学2013年历史学基础(中国近现代史)真题
GregLouganis:Thesewerethetrialsforthe1988OlympicsinSeoul,Korea.Untilthisdive,Ihadbeenahead.Butnow,some
最新回复
(
0
)
