北京大学信息学院2007年秋季学期《数据结构与算法A(实验班)》课程作业
张铭编写并发布 mzhang@ 第9次作业，11月28日（周三）课前提交，电子稿提交时间11月28日10：00之前提交。

9.1 假设一个记录长64个字节，一个块长1024个字节(因此每个块有16个记录)，工作内存是2MB(还有用于I/O 缓冲区、程序变量等的其他存储空间)。

使用置换选择和多路归并，其中归并算法只允许扫描两遍。

预计能得到的文件最长为多少？请解释你是怎样得到这个结果的。

9.2 为了满足信息隐藏原理，请扩充类LoserTree ，实现下列共享函数
int LeftChild(int i); // 返回内部结点 i 的左孩子
int RightChild(int i); // 返回内部结点 i 的右孩子
int Paren(int i); // 返回内部结点 i 的父结点；
void SetLeftChild(int i, int left) // 设置内部结点 i 的左孩子
void SetRightChild(int i, int right); // 设置内部结点 i 的右孩子
void SetParen(int i, int par) // 设置内部结点 i 的父结点；
9.2 用最先匹配法求解箱子装载问题
在箱子装载问题中，有若干个容量为 c 的箱子和 n 个待装载入箱子中的物品。

物品i 需占s[i]个单元（0<s[i]≤c ）。

所谓成功装载（feasible packing ），是指能把所有物品都装入箱子而不溢出，而最优装载（optimal packing ）则是指使用了最少箱子的成功装载。

箱子装载问题是NP 复杂问题。

因此可用近似的算法求解。

在箱子装载问题中，该算法可得到一个接近于最少箱子个数的解。

可以采用最先匹配法（First Fit, FF ）求近似解：物品按1，2，⋯，n 的顺序装入箱子，假设箱子从左至右排列，每一物品 i 首先放入可盛载它的最左箱子。

下图给出了在n = 8，c = 10，s[1] = 8，s [2] = 6，s[3] = 5，s[4] = 3的条件下，利用最大赢者树进行最先匹配的过程。

B[1]
B[2]
B[3]B[4]B[5]B[6]B[7]
L[1]L[2]L[3]L[4]L[5]L[6]L[7]L[8]
请编写利用最大赢者树编写采用最先匹配策略的算法。

分析对算法的时间代价。