首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
23
问题
(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明和Java代码，将应填入(n)处的字句写在答题纸的对应栏内。说明类Queue表示队列，类中的方法如下表所示。类Node表示队列中的元素；类EmptyQueueException给出了队列操作中的异常处理操作。Java代码
阅读以下说明、图和C代码。【说明】一般的树结构常采用孩子-兄弟表示法表示，即用二叉链表作树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，图10-8(a)所示的树的孩子-兄弟表示如图10-8(b)所示。
阅读以下说明以及数据流图，回答问题1至问题5。【说明】某银行已有一套基于客户机/服务器模式的储蓄系统A和一套建账软件。建账软件主要用于将储蓄所手工处理的原始数据转换为系统A所需的数据格式。该建账软件具有以下功能。(1)分户账录入：手工办理
图(a)中只有一个外部实体E1。使用【说明】中的词语，给出E1的名称。使用【说明】中的词语，给出图(b)中的数据存储D1～D4的名称。
指出哪张图的哪个文件可以不必画出。指出数据流图4-1和数据流图4-2中错误的数据流。
阅读以下说明，回答问题1～5，将解答填入对应的解答栏内。[说明]若s和t是用单链表存储的两个串，设计一个函数将s串中首次与串t匹配的字串逆置。linkstring*invert-substring(s,t)linkstr
数据流图13-6中有两条数据流是错误的，请指出这两条数据流的起点和终点。根据系统功能和数据流图填充下列数据字典条目中的(1)和(2)：查询请求信息=[查询读者请求信息｜查询图书请求信息]读者情况=读者号+姓名+所在单位+{借书情况}管理工作请求单
阅读下列说明和图，回答问题1至问题3。[说明]某大型旅店为了便于管理，欲开发一个客房管理系统。希望实现客房预定、入住登记、帐务结算、退房，以及将服务项目记入客人帐单。旅客包括散客和团体，散客预定或入住时需要提供姓名、性别、身份
在下图所示的系统中，若部件R1的可靠性是0.98，R2的可靠性是0.95，R3的可靠性是0.9，则整个系统的可靠性约为(6)；若各个部件的失效率都是L那么整个系统的失效率是(7)。
自然语言的优势有（）。
随机试题
会计师事务所、审计项目组成员或其主要近亲属拥有审计客户的重大间接经济利益，将导致没有防范措施能够将对独立性的不利影响降至可接受的低水平。以下情形中属于间接经济利益的是()。
作为一个防护体系，当入侵者要发起攻击时，每一步都需要花费时间，攻击成功花费的时间就是___________。
InMarch2004，JoeRyangotanoticefromabillingagencyforahospitalnearDenver，Colorado.Thehospitalwantedpaymentfors
下列作品中，属于散文诗的是
下列错误事项能通过试算平衡查找的有()。
某公司2007年提取了公积金后的税后净利润为800万元，2008年投资计划所需资金为700万元，公司的目标资本结构为自有资本占70％，借入资本占30％。按照目标资本结构的要求，公司投资方案所需的自有资本数额为()万元。
在我国，对110kV及以上的配电装置，一般()。
以下关键字不能用来声明类的访问权限的是()。
TheIdentificationofGoalsI.Introduction1)theimportanceofidentificationofgoalsforyourlifeandfuture2)twoquestions
Thewholepassagedealswith______.Thearticlegivesusapiecegoodadviceabouthowtoevaluateyourchild’sworkathome.
最新回复
(
0
)
