外部排序¶
约 476 个字 26 张图片 预计阅读时间 2 分钟
时间匆忙，参考这里。
例题¶
例题
解答
T.正如课上所讲的，以斐波那契数分割runs的方法，可以使得最后的Passes数目最少。
解答
T.由于只有一个磁带机，寻道时间会变长。
解答
F.K不能越大越好
解答
T.需要2k个input buffers和2个output buffer。
解答
B。根据公式:
\[
\text{Number of Passes} = 1 + \lceil\log_K {N/M}\rceil = 1 + \lceil\log_2 {2^8 * 10^8/2^{27}}\rceil = 1 + 8 = 9
\]
解答
B。根据构建哈夫曼树的原则，不断合并最小的两个节点。
解答
B。最后得到的两个序列为:
\[
\begin{matrix}
25 & 34 & 56 & 74\\
11 & 21 & 29 & 38 & 53 & 80
\end{matrix}
\]
解答
D。我们把内存分为6个buffer，包括4个input buffer和2个output buffer，每个buffer可以存放两个数据，依次记为B1, B2, B3, B4, B5, B6。
-
读取数据到B1和B2
B1 B2 B3 B4 B5 B6 1,3 2,4 - - - - -
读取数据到B3，再将B1和B2中的数据merge到B5
B1 B2 B3 B4 B5 B6 3 4 5,7 - 1,2 - -
读取数据到B4，同时输出B5数据，再将B1和B2中的数据merge到B6
B1 B2 B3 B4 B5 B6 - - 5,7 6,15 -- 3,4 -
读取数据到B1，同时输出B6数据，再将B3和B4中的数据merge到B5
B1 B2 B3 B4 B5 B6 8,9 - 7 15 5,6 - -
读取数据到B2，同时输出B5数据，再将B1和B3中的数据merge到B6
B1 B2 B3 B4 B5 B6 9 20,25 - 15 - 7,8 -
读取数据到B3，同时输出B6数据，再将B2和B4中的数据merge到B5
B1 B2 B3 B4 B5 B6 - 20,25 12 15 9,10 -
D 选项强错误在没有等10,12读入完毕再merge。
解答
C。 最后的结果为:
\[
\begin{matrix}
9 & 12 & 17 & 25 & 75 & 88 & 91\\
22 & 35 & 41 & 58 & 96 \\
15
\end{matrix}
\]