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

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

最全题库2022-08-02  74
问题 两个递增序列A 和B的长度分别为m和n（m＜n），将二者归并为一个长度为m+n的递增序列时，（），归并过程中元素的比较次数最少。A.当A 的最大元素大于B 的最大元素时B.当A 的最大元素小于B 的最小元素时C.当A 的最小元素大于B 的最小元素时D.当A 的最小元素小于B 的最大元素时
选项 A.当A 的最大元素大于B 的最大元素时
B.当A 的最大元素小于B 的最小元素时
C.当A 的最小元素大于B 的最小元素时
D.当A 的最小元素小于B 的最大元素时
答案 B
解析 本题考查归并排序基本过程。
    两个递增序列A、B进行归并时，从序列的第一个元素开始，分别从这两个序列中取一个元素并进行比较，将较小者输出，然后从较小者所在序列取下一个元素再进行比较，循环往复，直到某个序列的全部元素己经输出，再将另一个序列的剩余元素依次输出即可。
    序列A表示为a1，a2，…，am，序列B表示为b1，b2，…，bn（m＜n）。
    若a1＜b1＜a2＜b2＜a3＜b3＜…＜am-1＜bm-1＜am＜bm，则需要2m+1次比较。
    若am＜b1，则需要依次比较a1与b1、a2与b1，a3与bl、…、am-1与b1、am，与b1，共
需要m次比较，这是归并时比较次数最少的情况。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2428022.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

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