首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
55
问题
(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分别是哪个用例?类通常不会单独存在，因此当对系统建模时，不仅要识别出类，还必须对类之间的相互关系建模。在面向对象建模中，提供
数据流图1-2中有两条数据流是错误的，请指出这两条数据流的起点和终点。根据系统功能和数据流图填充下列数据字典条目中的(1)和(2)：查询请求信息=【查询读者请求信息|查询图书请求信息】读者情况；读者号+姓名+所在单位+{借书情况}
阅读以下说明和VisualBasic代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】某绘图系统定义了一个抽象类IShape，现有三个类CPoint、CLine和CCircle，它们都具有IShape界面。相应的类图关系如图7-1所示。
根据上述说明，请给出(1)“职员”关系模式的主键和外键。(2)“部门”关系模式的主键和外键。原来的“职员”关系模式存在什么问题?在不增加新关系模式的前提下，请给出修改后的“职员”和“部门”关系模式。
(1)数据流图1-1缺少了一条数据流(在图1-2中也未给出该数据流)，请给出此数据流的起点和终点，并采用说明中的词汇给出此数据流名。(2)数据流图1-2中缺少了与“查询房屋”加工相关的数据流，请指出此数据流的起点和终点。请补齐下列数据字典条目：
请填充图4-1中的空缺(1)、(2)和(3)处。对于本题的作业处理问题，用图4-1的贪心算法策略，能否求得最高收益?(6)。用贪心算法求解任意给定问题时，是否一定能得到最优解?(7)。
阅读下列说明，回答问题1至问题4，将解答填入对应栏内。【说明】某汽车维修站拟开发一套小型汽车维修管理系统，对车辆的维修情况进行管理。1．对于新客户及车辆，汽车维修管理系统首先登记客户信息，包括：客户编号、客户名称、客户性质(个人、单位)
阅读下列说明和C函数，将应填入(n)处的字句写在对应栏内。【说明】已知集合A和B的元素分别用不含头结点的单链表存储，函数Difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A＝{5，10，20，15，
阅读下列说明、流程图和算法，将应填(n)处的字句写在对应栏内。[说明]下面的流程图(如图3所示)用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准
阅读下列说明和图，回答问题1至问题3。[说明]某大型旅店为了便于管理，欲开发一个客房管理系统。希望实现客房预定、入住登记、帐务结算、退房，以及将服务项目记入客人帐单。旅客包括散客和团体，散客预定或入住时需要提供姓名、性别、身份
随机试题
茶艺人员发现有陌生客人进店，此时应该选择
=()
孕41+3周，羊水指数(AFI)7cm，临产后产程进展好，宫口开大3cm，人工破膜，羊水I度胎便污染，合适的处理是
气滞作痛的特点是()
A．复方甘草片B．含可待因复方口服液体制剂C．含麻黄碱复方制剂D．药品类易制毒化学品单方制剂纳入麻醉药品销售渠道经营，零食药店不得销售的是()。
关于刑事诉讼中的证明责任，下列哪些选项是正确的?()
程序存储到磁盘的形式是()。
甲公司系2014年12月成立的股份有限公司．对所得税采用资产负债表债务法核算，适用的企业所得税税率为25％，计提的各项资产减值准备均会产生暂时性差异，当期发生的可抵扣暂时性差异预计能够在未来期间转回。甲公司每年年末按净利润的10％计提法定盈余公积。(1)甲
交际应酬中最简单的、常用的礼节是()。
Thereareabout3.7millionbusinessesintheUK.About75%ofBritishjobsarein【B1】______industries—hotels,restaurants,trav
最新回复
(
0
)
