两个递增序列A和B 长度分别为m和n(m大于n 且m与 n 接近 ) ，将二者归井为一个长度为m+n 递增序列。当元素关系为（ ），归并过程中元素比较次数最少。
- 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 次比较，这是归并时比较次数最少情况。
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案