首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
49
问题
(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
根据E-R图中给出的词汇，按照“关系模式名(属性，属性，…)”的格式，将此E-R图转换为4个关系模式，并指出每个关系模式中的主码和外码，其中模式名根据需要取实体名或联系名。如下的SQL语句是书店用于查询“所有订购了bid为‘123-456’图书的用户
阅读以下说明和C++代码，将应填入(n)处。[说明]在一公文处理系统中，开发者定义了一个公文类OfficeDoc，其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时，关注此OfficeDoc类对象的相应的DocExplor
请在下列选项中选择合适的答案，填入图3-1、图3-2的方框a和方框b。B的公钥，B的私钥，摘要算法，A的私钥，A的公钥，会话密钥按照图3-2中的方法发送邮件时，使用不同的密码体制加密消息和消息摘要，请用150字以内文字简要说明这样做的理由。
阅读下列说明以及UML类图，回答问题1、问题2和问题3。[说明]某客户信息管理系统中保存着两类客户的信息。(1)个人客户，对于这类客户，系统保存了其客户标识(由系统生成)和基本信息(包括姓名、住宅电话和E-mail)。(
根据上述说明和实体-联系图，得到该住房管理系统的关系模式如下所示，请补充住宿关系。房间(房间号，收费标准，床位数目)客人(身份证号，姓名，性别，出生日期，地址)住宿((1)，入住日期，退房日期，预付款额)为提交SQL语句的执行效
请采用说明中的词汇，给出数据确认处理所需的数据流在第1层图中的全部可选起点(第0层图和第1层图中均未给出)。加工1(录入比对处理)除能够检查出初录数据和复录数据不一致外，还应当检测出下列哪些错误。①输入的无效字符②输入的半个
阅读以下说明和C代码，将应填入(n)处的字句写在的对应栏内。【说明】在一个简化的绘图程序中，支持的图形种类有点(point)和圆(circle)，在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形(shape)，并定义了类型shape
阅读下列函数说明和C代码，回答下面问题。[说明]冒泡排序算法的基本思想是：对于无序序列(假设扫描方向为从前向后，进行升序排列)，两两比较相邻数据，若反序则交换，直到没有反序为止。一般情况下，整个冒泡排序需要进行众(1≤k≤n)趟冒泡操作，冒泡排序
收费部门业务活动数据流图如图8-6所示，图中缺少了与“票根上缴”相关的数据流，请指出该数据流的起点和终点。
随机试题
下述各类药物属于佐药范畴的是()(1995年第147题)
束臂加压试验(Trousseau征)及面神经叩击征(Chvostek征)阳性及腱反射亢进是以下哪项电解质异常的特征性表现()
甲亢危象治疗过程中禁用的药物是
死亡人数在2人以下，重伤3人以上，19人以下，直接经济损失在10万元以上，不满30万元的事故属于( )。
预应力张拉是桥梁施工中的关键工序，下列说法正确的是()。
根据行政复议法律制度的规定，具体行政行为有下列()情形之一的，行政复议机关应当予以撤销、变更或者确认违法。
我国《证券法》规定，公开发行公司债券，累计债券余额不超过公司净资产的()。
为考察词的类型(靶子词、非靶子词)以及辨别条件(高辨别、低辨别)对双耳追随效果的影响。研究者将60名被试随机分成两组，每组30名，一组即接受靶子词——高辨别条件的处理，也接受靶子词——低辨别条件的处理；另一组则接受非靶子词——高辨别条件处理，也接受非靶子词
迄今为止，年代最久远的智人遗骸在非洲出现，距今大约20万年。据此，很多科学家认为，人类起源于非洲，现代人的直系祖先_一一智人在约20万年前于非洲完成进化后，在约15万年到20万年前，慢慢向北迁徙，穿越中东到达欧洲和亚洲，逐步迁徙至世界其他地方。以下哪项如果
关于甲班体育达标测试，三位老师有如下预测：张老师说：“不会所有人都不及格。”李老师说：“有人会不及格。”王老师说：“班长和学习委员都能及格。”如果三位老师中只有一人的预测正确，则以下哪项一定为真?
最新回复
(
0
)
