試題五（共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]  [9]  [10]  [11]  [12]  [13]