2. 从业资格
  3. 两个递增序列A和B的长度分别为m和n（m＜n且m与n接近），将二者归并为一个长度

两个递增序列A和B的长度分别为m和n（m＜n且m与n接近），将二者归并为一个长度

admin2022-08-02  50
问题 两个递增序列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
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)