首页
登录
从业资格
两个递增序列A和B的长度分别为m和n(m<n且m与n接近),将二者归并为一个长度
两个递增序列A和B的长度分别为m和n(m<n且m与n接近),将二者归并为一个长度
admin
2022-08-02
59
问题
两个递增序列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进行自然连
随机试题
【C1】______peopledon’twakeupinthemorning,combtheirhair,and【C2】_____
AreBadEconomicTimesGoodforHealth?[A]Mostpeopleareworr
泡沫混凝土外墙保温板是一种防水、保温效果都较好的新型外墙保温材料,当用于空心砖外
A.0.6 B.0.7 C.0.8 D.0.9
为了使得内外网用户均能访问,Web服务器应放置在()区域。A.外网 B.内
某企业计划从事一个固定资产投资项目,投资总额1000万元,固定资产项目寿命期预计
下列哪项为羚角钩藤汤的主要功效A.疏风除湿,清热养血B.凉肝息风,增液舒筋C.祛
下列选项中是该立体图形侧视图的是( ) A.如上图所示 B.如上图所示
当学生取得好的成绩后,老师、家长给予表扬和鼓励。这符合桑代克学习规律中的()A.
简述现代企业人力资源管理各个历史发展阶段的特点。
最新回复
(
0
)