参考答案:
详细解析:
阅读以下说明和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 阴影节点所示。若在某节点放置了信号放大器,则从该节点输出的信号与信号源输出的信号等价。
函数placeBoosters(TreeNode *root)的功能是:对于给定树型分布网络中各个节点,计算其信号衰减量的最大值,并确定应在树中的哪些节点放置信号放大器。
全局变量Tolerance保存信号衰减容忍值。
树的节点类型定义如下:
[C语言函数]
参考答案:
详细解析: