首页
登录
从业资格
两个递增序列A和B的长度分别为m和n(m<n且m与n接近),将二者归并为一个长度
两个递增序列A和B的长度分别为m和n(m<n且m与n接近),将二者归并为一个长度
admin
2022-08-02
66
问题
两个递增序列A和B的长度分别为m和n(m<n且m与n接近),将二者归并为一个长度为m+n的递增序列。当关系为( )时,归并过程中元素的比较次数最少。A.a1<a2<…<am-1<am<b1<b2<…<bn-1<bnB.b1<b2<…<bn-1<bn<a1<a2<…<am-1<amC.a1<b1<a2<b2<…<am-1<bm-1<am<bm<bm+1<…<bn-1<bnD.b1<b2<…<bm-1<bm<a1<a2<…<am-1<am<bm+1<…<bn-1<bn
选项
A.a1<a2<…<am-1<am<b1<b2<…<bn-1<bn
B.b1<b2<…<bn-1<bn<a1<a2<…<am-1<am
C.a1<b1<a2<b2<…<am-1<bm-1<am<bm<bm+1<…<bn-1<bn
D.b1<b2<…<bm-1<bm<a1<a2<…<am-1<am<bm+1<…<bn-1<bn
答案
A
解析
对于本题,求解归并比较次数最少。可分为3种情况:
1)A[m]数值全小于B[n],取A[1]<B[1],R[1]=A[1],接下来比较A[2]与B[1],R[2]=A[2]…直到取完A[m],A[m]<B[1],R[m]=A[m],将B序列复制到R[K],(m+1)~(m+n)的位置,完成归并排序,此时,共比较m次;
2)A[m]数值全大于B[n],取B[1]<A[1],R[1]=B[1],接下来直到取完B[n],将A[m]序列复制到(n+1)~(n+m)的位置,完成归并排序,此时,共比较n次,题干指出m<n,因此第一种情况比较次数较少;
3)A[m]数值与B[n]数值大小交叉,则归并排序过程,对于R[1]~R[k]位置上数值的确定会比较>=1次,最终复制剩余序列时,长度也会小于m(因为交叉排序,有部分序列会经过比较插入结果数列),此时复制序列所缩减的比较次数会体现在前面交叉排序的过程中,总的比较次数会较大。
因此,比较次数最少的情况是第一种A[m]数值全小于B[n]。
转载请注明原文地址:https://tihaiku.com/congyezige/2410691.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
某二叉树的先序遍历序列为ABCDEF,中序遍历序列为BADCFE,则该二叉树的高
数据字典中“数据项”的内容包括:名称、编号、取值范围、长度和()A.处理频率
完整的软件测试需要经过()。A.白盒测试、黑盒测试两个步骤 B.人工测试、机
MD5是()算法,对任意长度的输入计算得到的结果长度为(请作答此空)位。A.5
两个工作站可以直接互相通信的连接方式是__()__A.采用交叉双绞线直接相连
以下关于并发调度的说法中,正确的是()。A.以不同串行方式调度执行两个事务,
如下表所示,有两个关系E和F,若它们经过某一关系运算后的结果为{计算机学院},这
一个栈的输入序列为1,2,3,4,5,不可能得到的输出序列是()。A.2,3
( )是构成我国保护计算机软件著作权的两个基本法律文件。单个自然人的软件著作权
将一个关系r分解成两个关系r1和r2,再将分解之后的两个关系r1和r2进行自然连
随机试题
A—WorldTelecommunicationsDayB—WorldMeteorologicalDayC—WorldTuberculosisD
[originaltext]W:Well,tonightwehaveAndrewGreeninourstudiototalkabout
卫生计划按时间划分,可分为A.长期计划 B.中央计划 C.短期计划 D.地
B
A.病程超过2周 B.病程超过1个月 C.病程超过2个月 D.病程超过半年
下列哪一项是衣原体的繁殖型A.原体B.包涵体C.溶原体D.始体E.吞噬体
下列哪项是胎膜早破最简单的判断方法A.腹部超声检查 B.胎心音听诊 C.胎儿
空调的安装位置和安装方式的选定,主要考虑()。A:建筑物外观美观和统一性B:
结定两种债券,除到期期限外其他要素相同,那么到期期限长的债券利率敏感性相对要低一
下列关于全面预算编制方法的表述中,不正确的有( )。 A.增量预算法的前提条
最新回复
(
0
)