数据结构第十章作业

第一题

假设一次I/O的物理块大小为150，每次可对750个记录进行内部排序，那么对含有150000个记录的磁盘文件进行4-路平衡归并排序时，共需进行多少次I/O?

解:

共200个归并段，$\lceil \log_{4}{200} \rceil = 4$ 趟归并。I/O次数为内部排序得到归并段加上归并所需的I/O。$T=1000\times 2 + 4 \times 1000 \times 2 = 10000$

试从空树开始，画出按以下次序向3阶B-树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后B-树的状态。

解：

$$ \text{I/O次数}=((4+7)\times3+(9+12+18+23+31)\times 2 + 47 \times 1)=266 $$