两个递增序列A和B 的长度分别为m和n(m大于n 且m与 n 接近 ) ,将

最全题库2022-08-02  52

问题 两个递增序列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

解析 两个递增序列 A 、B 进行归并时,从序列的第一个元素开始,分别从这两个序列中取一个元素并进行比较,将较小者输出,然后从较小者所在序列取下一个元素再进行比较,循环往复,直到某个序列的全部元素已经输出,再将另一个序列的剩余元素依次输出即可。若 am  大于 b1   ,则需要依次比较  a1  与 b1  , a2  与 b1  , a3  与 b1  , am-1与 b1, am与 b1  共需要 m 次比较,这是归并时比较次数最少的情况。
转载请注明原文地址:https://tihaiku.com/congyezige/2408397.html

最新回复(0)