设有5个初始归并段,每个归并段有20个记录,采用5路平衡归并排序,若采用败者树最小的方法,总的比较次数是( )。

admin2018-09-11  47

问题 设有5个初始归并段,每个归并段有20个记录,采用5路平衡归并排序,若采用败者树最小的方法,总的比较次数是(    )。

选项 A、20
B、300
C、396
D、500

答案B

解析 采用败者树时,5一路归并意味着败者树的外结点有5个,败者树的高度h为log25向上取整,结果为3。每次在参加比较的记录中选择一个关键字最小的纪录,比较次数不超过h,总共100个记录,需要的比较次数不超过1 00×3=300次,故选B。
转载请注明原文地址:https://jikaoti.com/ti/Q4fjFFFM
0

最新回复(0)