假设有12个初始归并段,其长度分别为85,68,62,9,18,60,20,3,6,8,44,30;现要进行4路外部归并排序,试画出表示归并过程的最佳归并树,并计算树的带权路径长度WPL。

admin2013-12-31  30

问题 假设有12个初始归并段,其长度分别为85,68,62,9,18,60,20,3,6,8,44,30;现要进行4路外部归并排序,试画出表示归并过程的最佳归并树,并计算树的带权路径长度WPL。

选项

答案应加4-(12-1)mod(4-1)-1=1个虚段。   WPL=(3+6+8)×3+(9+18+20+30+44+60+62)×2+(68+85)×1=690

解析
转载请注明原文地址:https://kaotiyun.com/show/2vxi777K
0

最新回复(0)