2. 考研
  3. 假设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并排序，若采用败者树的方法，总的排序码比较次数不超过( )。

假设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并排序，若采用败者树的方法，总的排序码比较次数不超过( )。

admin2019-07-18  52
问题 假设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并排序，若采用败者树的方法，总的排序码比较次数不超过(    )。
选项 A、20
B、300
C、396
D、500
答案B
解析 假设采用k路平衡归并排序算法，则败者树的高度为[log2k]+1。且在每次调整后，找下一个具有最小排序码记录时，最多做[log2k]次排序码比较。由题意可知，总共有100个记录，所以总的比较次数不超过100×[log25]=300。
    注意：采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k无关。
转载请注明原文地址:https://www.kaotiyun.com/show/xxCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)