首页
登录
从业资格
两个递增序列A和B的长度分别为m和n(m<n且m与n接近),将二者归并为一个长度
两个递增序列A和B的长度分别为m和n(m<n且m与n接近),将二者归并为一个长度
admin
2022-08-02
58
问题
两个递增序列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进行自然连
随机试题
TheScienceofAnthropologyAThroughvariousmethodsof
Whileradiobroadcastingwasstill【C1】_____________itsearlystagethewon
Insomewaystheemploymentinterviewislikeapersuasivespeechbecauseth
Longbeforethefirst【B1】______arrivedinAmerican,astrangelookinganim
Formanypeopletoday,readingisnolongerrelaxation.Tokeepuptheirwo
(9)主要负责接收用户的请求,对用户的输入、输出进行检查与控制,处理客户端的一
下列不良资产不得进行批量转让的是()。A.个人贷款 B.抵债资产 C.公司
在个贷业务流程中,应严格落实三查。这“三查”不包括()。A.贷前调查 B.贷
藿胆丸注意事项的表述,正确的有A.慢性病严重者应在医师指导下服用 B.脾虚便溏
银行承兑汇票的承兑银行,应当按照票面金额向出票人收取()的手续费。A:千分之一
最新回复
(
0
)