為幫助廣大軟考中級(jí)軟件設(shè)計(jì)師考生更好備考，信管網(wǎng)特整理匯總了軟件設(shè)計(jì)師部分下午考試真題、答案及解析供考生查閱，并提供免費(fèi)在線模擬答題、歷年真題免費(fèi)下載等服務(wù)，了解軟件設(shè)計(jì)師更多備考信息請(qǐng)關(guān)注信管網(wǎng)。

相關(guān)推薦：

點(diǎn)擊查看/下載：軟件設(shè)計(jì)師歷年真題匯總

點(diǎn)擊查看：軟件設(shè)計(jì)師在線培訓(xùn)課程 丨 免費(fèi)試聽課程

免費(fèi)練習(xí)：軟件設(shè)計(jì)師考試題庫(kù)(模擬試題、章節(jié)練習(xí)、每日一練)

閱讀以下說(shuō)明和圖，填補(bǔ)流程圖中的空缺。

【說(shuō)明】

在一條農(nóng)村公路的一邊稀疏地分布著房子，其分布如圖10-5所示。某電信公司需要在某些位置放置蜂窩電話基站，由于基站的覆蓋范圍是6公里，因此必須使得每棟房子到某個(gè)基站的直線距離不超過(guò)6公里。為簡(jiǎn)化問(wèn)題，假設(shè)所有房子在同一直線上，并且基站沿該直線放置?，F(xiàn)采用貪心策略實(shí)現(xiàn)用盡可能少的基站覆蓋所有的房子。

實(shí)現(xiàn)貪心算法的流程如圖10-6所示，請(qǐng)?zhí)畛淦渲锌瞻撞⒂?jì)算該算法的時(shí)間復(fù)雜度，其中：

1.d[i](1≤i≤n)表示第i個(gè)房子到公路a端的距離，n表示房子的總數(shù)，房子的編號(hào)按照房子到公路a端的距離從小到大進(jìn)行編號(hào)。

2.s[k]表示第k(k≥1)個(gè)基站到公路a端的距離，算法結(jié)束后k的值為基站的總數(shù)。

該算法的時(shí)間復(fù)雜度為 (5) 。

信管網(wǎng)參考答案：

答案∶(1)k=0

(2)j<=N，或其等價(jià)形式

(3)k=k+1，或其等價(jià)形式

(4)d[i]+6，或其等價(jià)形式

(5)O(N)，或O(n)

查看解析：m.pokkc.com/st/2455317292.html