设外存上有120个初始归并段，进行12路归并时，为实现最佳归

[单选题]

设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段个数是 ____。

查看正确选项

分部求导

设n0,n12,n补,分别为度为零，十二和要补充的结点，则有：

n0=120+n补(根据哈夫曼树构成，度为零的结点全是初始提供的结点）；

n0=12*(n12)-(n12)+1;（根据完全十二叉树构成）；

即n12=（119+n补）/11，且n12为整数，则n补最小为2。

发表于 2021-08-30 20:58:06 回复(0)

cc扣扣

发表于 2023-02-06 15:38:00 回复(0)

Mapple

在一般情况下，对于 k–路平衡归并来说，若 (m-1)MOD(k-1)=0，则不需要增加虚段；否则需附加 k-(m-1)MOD(k-1)-1 个虚段。

发表于 2020-12-02 15:48:32 回复(1)

牛客563546967号

12路哈夫曼树

发表于 2020-11-23 12:12:29 回复(0)

提交观点

问题信息

2019 Java工程师

上传者：小小

难度：

4条回答 15收藏 4574浏览

扫一扫，把题目装进口袋