问题
单项选择题
设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并排序，若采用败者树最小的方法，总的比较次数是______。
A．20
B．300
C．396
D．500
答案
参考答案：B
解析： 采用败者树时，5-路归并意味着败者树的外结点有5个，败者树的高度h为log25向上取整，结果为3。每次在参加比较的记录中选择一个关键字最小的纪录，比较次数不超过h，总共100个记录，需要的比较次数不超过100×3=300次，故选B。