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

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

軟件設(shè)計(jì)師案例分析每日一練試題（2025/1/4）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2025/1/4

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

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2025/1/4）

試題五
(以下試題五至試題七中任選一題解答)
閱讀以下說明和C語言函數(shù)，應(yīng)填入  (n)  處。
【說明】
在一個(gè)分布網(wǎng)絡(luò)中，資源(石油、天然氣、電力等)可從生產(chǎn)地送往其他地方。在傳輸過程中，資源會(huì)有損耗。例如，天然氣的氣壓會(huì)減少，電壓會(huì)降低。我們將需要輸送的資源信息稱為信號。在信號從信源地送往消耗地的過程中，僅能容忍一定范圍的信號衰減，稱為容忍值。分布網(wǎng)絡(luò)可表示為一個(gè)樹型結(jié)構(gòu)，如圖10-9所示。信號源是樹根，樹中的每個(gè)節(jié)點(diǎn)(除了根)表示一個(gè)可以放置放大器的子節(jié)點(diǎn)，其中某些節(jié)點(diǎn)同時(shí)也是信號消耗點(diǎn)，信號從一個(gè)節(jié)點(diǎn)流向其子節(jié)點(diǎn)。
每個(gè)節(jié)點(diǎn)有一個(gè)d值，表示從其父節(jié)點(diǎn)到該節(jié)點(diǎn)的信號衰減量。例如，在圖10-9中，節(jié)點(diǎn)w、p、q的d值分別為2、1、3，樹根節(jié)點(diǎn)表示信號源，其d值為0。
每個(gè)節(jié)點(diǎn)有一個(gè)M值，表示從該節(jié)點(diǎn)出發(fā)到其所有葉子的信號衰減量的最大值。顯然，葉子節(jié)點(diǎn)的M值為0。對于非葉子節(jié)點(diǎn)j，M(j)=max{M(k)+d(k)|k是j的孩子節(jié)點(diǎn)}。在此公式中，要計(jì)算節(jié)點(diǎn)的M值，必須先算出其所有子節(jié)點(diǎn)的M值。

在計(jì)算M值的過程中，對于某個(gè)節(jié)點(diǎn)i，其有一個(gè)子節(jié)點(diǎn)k滿足d(k)+M(k)大于容忍值，則應(yīng)在k處放置放大器，否則，從節(jié)點(diǎn)i到某葉子節(jié)點(diǎn)的信號衰減量會(huì)超過容忍值，使得到達(dá)該葉子節(jié)點(diǎn)時(shí)信號不可用，而在節(jié)點(diǎn)i處放置放大器并不能解決到達(dá)葉子節(jié)點(diǎn)的信號衰減問題。
例如，在圖10-9中，從節(jié)點(diǎn)p到其所有葉子節(jié)點(diǎn)的最大衰減值為4。若容忍值為3，則必須在s處放置信號放大器，這樣可使得節(jié)點(diǎn)p的M值為2。同樣，需要在節(jié)點(diǎn)小v處放置信號放大器，如圖10—10陰影節(jié)點(diǎn)所示。若在某節(jié)點(diǎn)放置了信號放大器，則從該節(jié)點(diǎn)輸出的信號與信號源輸出的信號等價(jià)。

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

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