1.  [说明]
    散列文件的存储单位称为桶(Bucket)。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回；否则沿指针到溢出桶中进行查找。
    例如，设散列函数为Hash(Key)=Key mod 7，记录的关键字序列为15，14，21，87，96，293，35，24，149，19，63，16，103，77，5，153，145，356，51，68，705，453，建立的散列文件内容如下图所示。
   
    为简化起见，散列文件的存储单位以内存单元表示。
    函数InsertToHashTable(int NewElemKey)的功能是：若新元素NewElemKey正确插入散列文件中，则返回值1；否则返回值0。
    采用的散列函数为Hash(NewElemKey)=NewElemKey%P，其中P设定基桶数目。
    函数中使用的预定义符号如下：
    #define NULLKEY -1  /*散列桶的空闲单元标识*/
    #define P 7    /*散列文件中基桶的数目*/
    #define ITEMS 3    /*基桶和溢出桶的容量*/
    typedef struct BucketNode {/*基桶和溢出桶的类型定义*/
    int KeyData [ITEMS];
    struct BucketNode *Link;
    } BUCKET;
    BUCKET Bucket [P];  /*基桶空间定义*/
    函数InsertToHashTable代码如下：
    int InsertToHashTable(int NewElemKey) {
    /*将元素NewElemKey插入散列桶中，若插入成功则返回0，否则返回-1*/
    /*设插入第一个元素前基桶的所有KeyData[]、Link域已分别初始化为NULLKEY、NULL*/
    int Index;  /*基桶编号*/
    int i, k;
    BUCKET *s, *front, *t;
    ______;
    for (i = 0; i ＜ ITEMS; i++)  /*在基桶查找空闲单元，若找到则将元素存入*/
    if (Bucket[Index]. KeyData[i] == NULLKEY) {
    Bucket[Index]. KeyData [i] = NewElemKey;
    break;
    }
    if (______) return 0;
    /*若基桶已满，则在溢出桶中查找空闲单元，若找不到则申请新的溢出桶*/
    ______；
    t = Bucket [Index]. Link;
    if (t != NULL) {  /*有溢出桶*/
    while (t !=NULL) {
    for (k=0; k＜ITEMS; k++)
    if (t→KeyData [k] == NULLKEY) {  /*在溢出桶链表中找到空闲单元*/
    t→KeyData [k] = NewElemKey;
    break;
    }  /*if*/
    front=t;
    if (______)t = t; Link;
    else break;
    } /*while*/
    }  /*if*/
    if (______) {  /*申请新溢出桶并将元素存入*/
    s = (BUCKET *) malloc (sizeof (BUCKET));
    if (!s) return -1;
    s→Link = NULL;
    for (k=0; k＜ITEMS; k++)
    s→KeyData [k] = NULLKEY;
    S→KeyData[0]=NewElemKey;
    ______;
    } /*if*/
    return 0;
    } /*InsertToHashTable*/

1.  [说明]
    在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树型结构，如图1所示。信号源是树根，树中的每个节点(除了根)表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子节点。
   
    每个节点有一个d值，表示从其父节点到该节点的信号衰减量。例如，在图1中，节点w、p、q的d值分别为2、1、3，树根节点表示信号源，其d值为0。
    每个节点有一个M值，表示从该节点出发到其所有叶子节点的信号衰减量的最大值。显然，叶子节点的M值为0。对于非叶子节点j，M(j)=max{M(k)+d(k)|k是j的子节点}。
    在此公式中，要计算节点的M值，必须先算出其所有子节点的M值。
    在计算M值的过程中，对于某个节点i，若其有一个子节点k满足d(k)+Mfk)大于容忍值，则应在k处放置放大器，否则，从节点i到某叶子节点的信号衰减量会超过容忍值，使得到达该叶子节点时信号不可用，而在节点i处放置放大器并不能解决到达叶子节点的信号衰减问题。例如，在图1中，从节点P到其所有叶子节点的最大衰减值为4。若容忍值为3，则必须在s处放置信号放大器，这样可使得节点p的M值为2。同样，需要在节点q、v处放置信号放大器，如图2阴影节点所示。若在某节点放置了信号放大器，则从该节点输出的信号与信号源输出的信号等价。
   
    函数placeBoosters(TreeNode *root)的功能是：对于给定树型分布网络中的各个节点，计算其信号衰减量的最大值，并确定应在树中的哪些节点放置信号放大器。
    全局变量Tolerance保存信号衰减容忍值。
    树的节点类型定义如下：
    typedef struct TreeNode {
    int id; /*当前节点的以别号*/
    int ChildNum;  /*当前节点的子节点数目*/
    int d;  /*父节点到当前节点的信号衰减值*/
    struct TreeNode **childptr;  /*向量，存放当前节点到其所有子节点的指针*/
    int M;  /*当前节点到其所有子节点的信号衰减值中的最大值*/
    bool boost; /*是否存当前节点放置信号放大器的标志*/
    } TreeNode;
    [C程序]
    void placeBooster (TreeNode *root)
    {  /*计算root所指节点处的衰减量，如果衰减量超出了容忍值，则放置放大器*/
    TreeNode *P;
    int i, degradation;
    if (______)
    {
    degradation=0; root→M=0;
    i=0;
    if (i＞=root→ChildNum)
    return;
    p=______;
    for(; i＜root→ChildNum && p; i++, p=______)
    {
    p→M=0;
    ______;
    if (p→d+p→M＞Tolerance)  /*在p所指节点中放置信号放大器*/
    {
    p→boost=true;
    P→M=0;
    }
    if(p→d+p→M＞degradation)
    degradation=p→d+p→M;
    }
    Root→M=______;
    }
    }