軟件設(shè)計師案例分析當(dāng)天每日一練試題地址：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計師每日一練試題匯總：www.xomuzic.com/class/27/e4_1.html

軟件設(shè)計師案例分析每日一練試題（2024/8/9）在線測試：www.xomuzic.com/exam/ExamDayAL.aspx?t1=4&day=2024/8/9

點擊查看：更多軟件設(shè)計師習(xí)題與指導(dǎo)

軟件設(shè)計師案例分析每日一練試題內(nèi)容（2024/8/9）

試題五
(以下試題五至試題七中任選一題解答)
閱讀以下說明和C語言函數(shù)，應(yīng)填入  (n)  處。
【說明】
在一個分布網(wǎng)絡(luò)中，資源(石油、天然氣、電力等)可從生產(chǎn)地送往其他地方。在傳輸過程中，資源會有損耗。例如，天然氣的氣壓會減少，電壓會降低。我們將需要輸送的資源信息稱為信號。在信號從信源地送往消耗地的過程中，僅能容忍一定范圍的信號衰減，稱為容忍值。分布網(wǎng)絡(luò)可表示為一個樹型結(jié)構(gòu)，如圖10-9所示。信號源是樹根，樹中的每個節(jié)點(除了根)表示一個可以放置放大器的子節(jié)點，其中某些節(jié)點同時也是信號消耗點，信號從一個節(jié)點流向其子節(jié)點。
每個節(jié)點有一個d值，表示從其父節(jié)點到該節(jié)點的信號衰減量。例如，在圖10-9中，節(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é)點的信號衰減量會超過容忍值，使得到達(dá)該葉子節(jié)點時信號不可用，而在節(jié)點i處放置放大器并不能解決到達(dá)葉子節(jié)點的信號衰減問題。
例如，在圖10-9中，從節(jié)點p到其所有葉子節(jié)點的最大衰減值為4。若容忍值為3，則必須在s處放置信號放大器，這樣可使得節(jié)點p的M值為2。同樣，需要在節(jié)點小v處放置信號放大器，如圖10—10陰影節(jié)點所示。若在某節(jié)點放置了信號放大器，則從該節(jié)點輸出的信號與信號源輸出的信號等價。

函數(shù)placeBoosters(TreeNode*root)的功能是：對于給定樹型分布網(wǎng)絡(luò)中各個節(jié)點，計算其信號衰減量的最大值，并確定應(yīng)在樹中的哪些節(jié)點放置信號放大器。
全局變量Tolerance保存信號衰減容忍值。
樹的節(jié)點類型定義如下：
typedef struct TreeNode{
int id；                      /*當(dāng)前節(jié)點的識別號*/
int ChildNum；                /*當(dāng)前節(jié)點的子節(jié)點數(shù)目*/
int d;                       /*父節(jié)點到當(dāng)前節(jié)點的信號衰減值*/
struct TreeNode **childptr；  /*向量，存放當(dāng)前節(jié)點到其所有子節(jié)點的指針*/
int M；                       /*當(dāng)前節(jié)點到其所有子節(jié)點的信號衰減值中的最大值*/
bool boost；                  /*是否在當(dāng)前節(jié)點放置信號放大器的標(biāo)志*/
}TreeNode；
【C語言函數(shù)】
void placeBoosters(TreeNode *root)
{                               /*  計算root所指節(jié)點處的衰減量，如果衰減量超出了容忍值，則放置放大器*/
TreeNode *p；
int i，degradation；
if(  (1)  ){
degradation = 0；root-＞M = 0；
i = 0；
if  (i＞=root-＞ChildNum)
return；
p=  (2)  ；
for(;i＜root-＞ChildNum  &&  p； i++，p =  (3)  ){
p-＞M = 0；
(4)  ；
if  (p-＞d+p-＞M＞Tolerance)  {  /*在p所指節(jié)點中放置信號放大器*/
p-＞boost=true；
p-＞M = 0；
}
if  (p-＞d + p-＞M ＞ degradation)
degradation = p-＞d + p-＞M；
}
root-＞M =   (5)  ；
}
}

信管網(wǎng)cnitpm613520395848：
1. root -＞d == 0 2. root-＞ childptr 3. p-＞ childptr -＞ next 4. p-＞d ＝ p-＞d + degration 5.degration