首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
28
问题
(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://jikaoti.com/ti/LgG7FFFM
本试题收录于：
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
[程序]STARTPRUGBCLDGR0，DATALEAGR1，0LEAGR3，48LOOP1
图3-2是该系统类图的一部分，依据上述说明中给出的术语，给出类Lock的主要属性。组装(composition)和聚集(aggregation)是UML中两种非常重要的关系。请说明组装和聚集分别表示什么含义?两者的区别是什么?
请在下列选项中选择合适的答案，填入图3-1、图3-2的方框a和方框b。B的公钥，B的私钥，摘要算法，A的私钥，A的公钥，会话密钥请在下列选项中选择合适的答案，填入图3-2的方框c至方框f。B的公钥，B的私钥，摘要算法，A的私钥，A的公钥
请采用说明中的词汇，给出数据确认处理所需的数据流在第1层图中的全部可选起点(第0层图和第1层图中均未给出)。请使用数据字典条目定义形式，给出第0层DFD中的“手工分户账”数据流和第1层DFD中的“初录分户账”、“复录分户账”的关系。
阅读以下说明和VisualBasic代码，将应填入(n)处的字名写在对应栏内。[说明]以下代码实现了当用户推出界面时，判断TextEdit中的文字是否发生改变，弹出对话框判断，让用户选择选择是否保存文件或取消退出界面操作。阅读下面代码，补
阅读以下说明和图，回答问题1至问题3。[说明]图书馆藏书管理系统，完成用户信息管理，借阅归还信息管理，馆藏书目的信息管理，违规处罚管理和各种查询等功能。系统的用户可分为超级用户和普通用户两类，超级用户负责系统维护，包括对藏书信息，用户信
阅读下列说明和图，回答问题1至问题3。【说明】某大型旅店为了便于管理，欲开发一个客房管理系统。希望实现客房预订、入住登记、账务结算、退房，以及将服务项目记入客人账单。旅客包括散客和团体，散客预订或入住时需要提供姓名、性别、身份证和联系
阅读以下说明和图，回答问题1～问题3，将解答写在对应栏内。[说明]通行费征收计算机管理系统包括收费部门业务活动管理和固定资产管理两大功能。收费部门采取站(库)、队、收费员三级管理模式。站是一个基层收费单位，由几个征收队组成，收费员是
请根据标准书号校验码的技术说明，将图5-13和图5-14程序流程图中(1)～(4)空缺处的内容填补完整。假设《应试捷径——典型考题解析与考点贯通_系统分析师考试》书籍标准书号前9个数字为7-121-04715，请写出其对应的校验码。
设计高质量的软件是软件设计追求的一个重要目标。可移植性、可维护性、可靠性、效率、可理解性和可使用性等都是评价软件质量的重要方面。可移植性反映出把一个原先在某种硬件或软件环境下正常运行的软件移植到另—个硬件或软件环境下，使该软件也能正确地运行的难易程度。为了
随机试题
A．30％B．50％C．80％D．100％我国现行基本药物制度中规定基本药物报销的比例是
城市道路目前大量采用()适宜于机械化施工、技术经济较合理的水泥、石灰及工业废渣稳定材料做路面基层，通常称为无机结合料稳定基层。
居住国政府对其居民来自国外的所得不征税，只对其居民的国内所得征税，但在决定对其居民的国内所得征税所适用的税率时，有权将这笔免于征税的国外所得与国内所得汇总一并加以综合考虑。这种做法称为()。
下图是以北极为中心的半球图，甲、乙两地位于同一大洋。据此回答问题。从甲地到乙地走最短航程的航向是()。
简述《师说》中的主要教育思想。
以下关于货币市场工具的说法中()是错误的。
设y=f(x，t)，而t是由方程F(x，y，t)=0所确定的x，y的函数，其中f，F均具有一阶连续偏导数，则=()．
(96年)设ξ和η是两个相互独立且均服从正态分布N(0，)的随机变量，则E(|ξ-η|)=________
Theworldhasneverbeenmorecloselyandintricatelyconnected.Ourbehavior【C1】______theenvironmentweallshare,andweare
Withonlyabout1,000pandasleftintheworld,Chinaisdesperatelytryingtoclonetheanimalandsavetheendangeredspecies.
最新回复
(
0
)
