首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
54
问题
(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://www.kaotiyun.com/show/VmCZ777K
本试题收录于：
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明以及图4-4和图4-5，回答问题1、问题2和问题3，将解答填入答题纸的对应栏内。[说明]某电话公司决定开发一个管理所有客户信息的交互式网络系统。系统的功能如下。1．浏览客户信息：任何使用因特网的用户都可以浏览电话公司所有
阅读下列说明和数据流图，回答问题1至问题4，将解答填入答题纸的对应栏内。[说明]某基于微处理器的住宅安全系统，使用传感器(如红外探头、摄像头等)来检测各种意外情况，如非法进入、火警、水灾等。房主可以在安装该系统时配置安全监控设备(如
阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。【说明】一个印刷电路板的布线区域可分成n×m个方格，如图3-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直
如果将数据库服务器(记为DB)作为一个外部实体，那么在绘制该系统的数据流图时，还应有哪些外部实体和数据存储?根据说明结合问题1的解答，指出在该系统的顶层数据流图中应有哪些数据流。请采用说明中的词汇给出这些数据流的起点、终点以及数据流名称，下表给出了数据
阅读下列说明以及数据流图，回答问题1、问题2和问题3。[说明]某学校建立了一个网上作业提交与管理系统，基本功能描述如下：(1)账号和密码。任课老师用账号和密码登录系统后，提交所有选课学生的名单。系统自动为每个选课学生创建登录系统的账
【说明】下面是一个Applet程序，其功能是通过一个按钮控制一个窗口的创建，显示与隐藏，并且以按钮文字作为提示，可以随着窗口的状态改变，即如果窗口出现，则按钮文字为"HidemyFrm"，提示用户点击按钮，则隐藏窗口，反之亦然。请将横线处语句补充
阅读下列程序说明和C++代码，将应填入(n)处的字句写在对应栏内。[说明]①为类Circle增加一个构造函数，该函数有一个参数，并在构造时将该参数值赋给成员radius。将该函数实现为一个非内联函数，并且使用参数列表的方式将类成员赋值。
阅读下列说明和c++代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】现欲构造一文件／目录树，采用组合(Composite)设计模式来设计，得到的类图如6—7所示：【c++代码】#include#include#include
某一非确定性有限自动机(NFA)的状态转换图如下图所示，与该NFA等价的正规式是(28)，与该NFA等价的DFA是(29)。
设计高质量的软件是软件设计追求的一个重要目标。可移植性、可维护性、可靠性、效率、可理解性和可使用性等都是评价软件质量的重要方面。可移植性反映出把一个原先在某种硬件或软件环境下正常运行的软件移植到另—个硬件或软件环境下，使该软件也能正确地运行的难易程度。为了
随机试题
骨肉瘤的临床表现包括
下列对操作系统层次结构描述错误的是
下列哪些室性心动过速可以使用直流电复律治疗
会计核算的相关性原则要求会计核算以实际发生的经济业务及证明经济业务发生的合法凭证为依据。()
[2009年第026题]适用于我国大部分地区住宅南向外窗的有效而简单的遮阳方式是：
下列不属于货币市场特点的是()。
经复议机关复议，复议机关改变原具体行政行为的，复议机关是被告。()
乙自认为甲需要一栋别墅，于是伪称自己是甲的代理人，以甲的名义与不知情的丙开发商签订买卖合同约定：丙开发商将一栋别墅以500万元的价格卖与甲。关于买卖合同，下列说法正确的有()。
设y=y(x)是由方程确定的隐函数，则y’’=_________。
在考生文件夹下打开EXCEL．XLS文件，将Sheet1工作表的A1：G1单元格合并为一个单元格，内容水平居中；计算“总成绩”列的内容和按“总成绩”递减次序的排名(利用RANK函数)；如果计算机原理、程序设计的成绩均大于或等于75在备注栏内给出信息“有资格
最新回复
(
0
)
