首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
)