20xx年軟件設(shè)計師下午試題試卷真題(編輯修改稿)
2024-09-27 06:51 本頁面
【文章內(nèi)容簡介】 rrowerDBLibrarySystem試題四(共 15 分)閱讀以下說明和圖，填補流程圖中的空缺，將解答填入答題紙的對應(yīng)欄內(nèi)。[說明]在一條農(nóng)村公路的一邊稀疏地分布著房子，其分布如圖 41 所示。某電信公司需要在 某些位置放置蜂窩電話基站，由于基站的覆蓋范圍是 6 公里，因此必須使得每棟房子到某 個基站的直線距離不超過 6 公里。為簡化問題，假設(shè)所有房子在同一直線上，并且基站沿 該直線放置。現(xiàn)采用貪心策略實現(xiàn)用盡可能少的基站覆蓋所有的房子。AB圖 41實現(xiàn)貪心算法的流程如圖 42 所示，請?zhí)畛淦渲锌瞻撞⒂嬎阍撍惴ǖ臅r間復(fù)雜度，其中：1．d[i](1≤ i ≤ N)表示第 i 個房子到公路 A 端的距離，N 表示房子的總數(shù)，房子的編號按照房子到公路 A 端的距離從小到大進行編號。2．s[k]表示第 k（k ≥1）個基站到公路 A 端的距離，算法結(jié)束后 k 的值為基站的總數(shù)。BeginNi = NEndY ( 2) amp。amp。d[j]–d [i]N圖 42該算法的時間復(fù)雜度為 （5） 。2007 年上半年 軟件設(shè)計師 下午試卷 第 8 頁 （共 14 頁） ( 2) d[j]–d [i]=12Yj = j + 1j = i + 1ij (3) －s[k ] = (4) －i = ji = 1 ( 1) －公 路d[1]d[2]d[N]圖 51每個節(jié)點有一個 d 值，表示從其父節(jié)點到該節(jié)點的信號衰減量。例如，在圖 51 中，節(jié)點 w、p、q 的 d 值分別為 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é)點的信號衰減問題。例如，在圖 51 中，從節(jié)點 p 到其所有葉子節(jié)點的最大衰減值為 4。若容忍值為 3，則 必須在 s 處放置信號放大器，這樣可使得節(jié)點 p 的 M 值為 2。同樣，需要在節(jié)點 q、v 處 放置信號放大器，如圖 52 陰影節(jié)點所示。若在某節(jié)點放置了信號放大器，則從該節(jié)點輸出的信號與信號源輸出的信號等價。試題五（共 15 分）閱讀以下說明和 C 語言函數(shù)，將應(yīng)填入 （n） 處的字句寫在答題紙的對應(yīng)欄內(nèi)。[說明]在一個分布網(wǎng)絡(luò)中，資源（石油、天然氣、電力等）可從生產(chǎn)地送往其他地方。在傳 輸過程中，資源會有損耗。例如，天然氣的氣壓會減少，電壓會降低。我們將需要輸送的 資源信息稱為信號。在信號從信源地送往消耗地的過程中，僅能容忍一定范圍的信號衰減， 稱為容忍值。分布網(wǎng)絡(luò)可表示為一個樹型結(jié)構(gòu)，如圖 51 所示。信號源是樹根，樹中的每 個節(jié)點（除了根）表示一個可以放置放大器的子節(jié)點，其中某些節(jié)點同時也是信號消耗點， 信號從一個節(jié)點流向其子節(jié)點。r13pq2221stu2yv2z21wxr13pq2221stu2yv2z21wx圖 522007 年上半年 軟件設(shè)計師 下午試卷 第 9 頁 （共 14 頁）從下列的 3 道試題（試題五至試題七）中任選 1 道解答。如果解答的試題數(shù)超過 1 道，則題號小的 1 道解答有效。函數(shù) placeBoosters(TreeNode *root)的功能是：對于給定樹型分布網(wǎng)絡(luò)中各個節(jié)點，計算其信號衰減量的最大值，并確定應(yīng)在樹中的哪些節(jié)點放置信號放大器。全局變量 Tolerance 保存信號衰減容忍值。樹的節(jié)點類型定義如下：typedef struct TreeNode{intintintid。ChildNum。d。/*當(dāng)前節(jié)點的識別號*//*當(dāng)前節(jié)點的子節(jié)點數(shù)目*//*父節(jié)點到當(dāng)前節(jié)點的信號衰減值*/**childptr。/*向量，存放當(dāng)前節(jié)點到其所有子節(jié)點的指針*//*當(dāng)前節(jié)點到其所有子節(jié)點的信號衰減值中的最大值*//*是否在當(dāng)前節(jié)點放置信號放大器的標(biāo)志*/structint M。TreeNodebool boost。}Tree
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1