試題五（共15分）

閱讀以下說明和C語言函數(shù)，將應(yīng)填入  （n）  處的字句寫在答題紙的對應(yīng)欄內(nèi)。

[說明]

在一個分布網(wǎng)絡(luò)中，資源（石油、天然氣、電力等）可從生產(chǎn)地送往其他地方。在傳輸過程中，資源會有損耗。例如，天然氣的氣壓會減少，電壓會降低。我們將需要輸送的資源信息稱為信號。在信號從信源地送往消耗地的過程中，僅能容忍一定范圍的信號衰減，稱為容忍值。分布網(wǎng)絡(luò)可表示為一個樹型結(jié)構(gòu)，如圖 5-1 所示。信號源是樹根，樹中的每個節(jié)點（除了根）表示一個可以放置放大器的子節(jié)點，其中某些節(jié)點同時也是信號消耗點，信號從一個節(jié)點流向其子節(jié)點。

每個節(jié)點有一個 d 值，表示從其父節(jié)點到該節(jié)點的信號衰減量。例如，在圖5-1 中，節(jié)點w、p、q的d值分別為2、1、3，樹根節(jié)點表示信號源，其d值為0。

每個節(jié)點有一個M值，表示從該節(jié)點出發(fā)到其所有葉子的信號衰減量的最大值。顯然，葉子節(jié)點的M值為0。對于非葉子節(jié)點j，M(j)=max{M(k)+d(k)|k是j的孩子節(jié)點}。在此公式中，要計算節(jié)點的M值，必須先算出其所有子節(jié)點的M值。

在計算 M 值的過程中，對于某個節(jié)點 i，其有一個子節(jié)點 k 滿足 d(k)+M(k)大于容忍值，則應(yīng)在 k 處放置放大器，否則，從節(jié)點 i 到某葉子節(jié)點的信號衰減量會超過容忍值，使得到達該葉子節(jié)點時信號不可用，而在節(jié)點 i 處放置放大器并不能解決到達葉子節(jié)點的信號衰減問題。

例如，在圖5-1中，從節(jié)點p到其所有葉子節(jié)點的最大衰減值為4。若容忍值為3，則必須在 s 處放置信號放大器，這樣可使得節(jié)點 p 的 M 值為 2。同樣，需要在節(jié)點 q、v 處放置信號放大器，如圖 5-2 陰影節(jié)點所示。若在某節(jié)點放置了信號放大器，則從該節(jié)點輸出的信號與信號源輸出的信號等價。

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10]  [11]  [12]  [13]