试题四(共15 分)

阅读以下说明和图，填补流程图中的空缺，将解答填入答题纸的对应栏内。

[说明]

在一条农村公路的一边稀疏地分布着房子，其分布如图 4-1 所示。某电信公司需要在某些位置放置蜂窝电话基站，由于基站的覆盖范围是 6 公里，因此必须使得每栋房子到某个基站的直线距离不超过 6 公里。为简化问题，假设所有房子在同一直线上，并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。

实现贪心算法的流程如图 4-2 所示，请填充其中空白并计算该算法的时间复杂度，其中：

1．d[i](1≤i≤N)表示第 i 个房子到公路 A 端的距离，N 表示房子的总数，房子的编号按照房子到公路 A 端的距离从小到大进行编号。

2．s[k]表示第 k（k ≥1）个基站到公路 A 端的距离，算法结束后 k 的值为基站的总数。

该算法的时间复杂度为　（5）　。

从下列３道试题（试题五至试题七）中任选一道解答。

　如果解答的试题数超过1道，则题号小的1道解答有效

试题五（共15 分）

阅读以下说明和 C 语言函数，将应填入　（n）　处的字句写在答题纸的对应栏内。

[说明]

在一个分布网络中，资源（石油、天然气、电力等）可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树型结构，如图 5-1 所示。信号源是树根，树中的每个节点（除了根）表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子节点。

每个节点有一个 d 值，表示从其父节点到该节点的信号衰减量。例如，在图 5-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)+M(k)大于容忍值，则应在 k 处放置放大器，否则，从节点 i 到某叶子节点的信号衰减量会超过容忍值，使得到达该叶子节点时信号不可用，而在节点 i 处放置放大器并不能解决到达叶子节点的信号衰减问题。

例如，在图 5-1 中，从节点 p 到其所有叶子节点的最大衰减值为 4。若容忍值为 3，则必须在 s 处放置信号放大器，这样可使得节点 p 的 M 值为 2。同样，需要在节点 q、v 处放置信号放大器，如图 5-2 阴影节点所示。若在某节点放置了信号放大器，则从该节点输出的信号与信号源输出的信号等价。

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]