首页
登录
从业资格
两个递增序列A和B的长度分别为m和n(m<n且m与n接近),将二者归并为一个长度
两个递增序列A和B的长度分别为m和n(m<n且m与n接近),将二者归并为一个长度
admin
2022-08-02
60
问题
两个递增序列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进行自然连
随机试题
Readthefollowingpassageandfillineachblankwithoneword.Choosethecorr
[originaltext]W:CanIhelpyou?M:Yes.I’mlookingforabookinthelibrary.
[originaltext]M:Excuseme,what’sthedifferencebetweentheregularsubwayti
关于工程索赔说法错误的是()。A.合同双方均享有工程索赔的权利 B.有经济索
下面有关动脉瘤的描述,正确的是A.典型临床表现是搏动性肿块和舒张期杂音 B.手
监理人收到工程设计文件后编制监理规划,并在第一次工地会议()天前报委托人。A、7
为区别小原粒细胞性白血病与急性淋巴细胞白血病首选( )。A.铁染色 B.AC
黄田村系某县西侧城郊结合部的一个村庄,村东侧建有一处公园,村西北侧建有一座工厂,
上颌第一磨牙有三个牙根,即A.近中根、远中根、舌根 B.颊根、近中舌根、远中舌
建设跨河、穿河、穿堤、临河的桥梁、码头、道路、取水、排水等工程设施,应当符合(
最新回复
(
0
)