初始有三个升序序列(3, 5)、(7, 9)、(6),若按从左至右的次序选择有序序列进行二路归并排序,则关键字之间的总比较次数是()。
A. 3 B. 4 C. 5 D. 6
要解决三个升序序列 (3...
用户登录可进行刷题及查看答案
要解决三个升序序列 (3,5)、(7,9)、(6) 的二路归并比较次数问题,需分步骤归并并计算每次归并的比较次数:
第一步:归并前两个序列 (3,5) 和 (7,9)
序列 1:[3,5],长度 m=2;序列 2:[7,9],长度 n=2。
归并过程:
比较 3 和 7,3 更小,取出 3,比较次数 +1。
比较 5 和 7,5 更小,取出 5,序列 1 空,剩余 7,9 直接接入,比较次数 +1。
总比较次数:1+1=2 次
归并后序列:[3,5,7,9]。
第二步:归并新序列 [3,5,7,9] 和 (6)
序列 1:[3,5,7,9],长度 m=4;序列 2:[6],长度 n=1。
比较 3 和 6,3 更小,取出 3,比较次数 +1。
比较 5 和 6,5 更小,取出 5,比较次数 +1。
比较 7 和 6,6 更小,取出 6,序列 2 空,剩余 7,9 直接接入,比较次数 +1。
总比较次数:1+1+1=3 次
总比较次数
两步归并的比较次数相加:2+3=5 次。
答案:C. 5
登录后提交答案
暂无评论,来抢沙发