2007上半年軟件設計師下午試題[7]
摘要：試題四(共15分)閱讀以下說明和圖，填補流程圖中的空缺，將解答填入答題紙的對應欄內。[說明]在一條農村公路的一邊稀疏地分布著房子，其分布如圖4-1所示。某電信公司需要在某些位置放置蜂窩電話基站，由于基站的覆蓋范圍是6公里，因此必須使得每棟房子到某個基站的直線距離不超過6公里。為簡化問題，假設所有房子在同一直
試題四(共15分)
閱讀以下說明和圖，填補流程圖中的空缺，將解答填入答題紙的對應欄內。
[說明]
在一條農村公路的一邊稀疏地分布著房子，其分布如圖 4-1 所示。某電信公司需要在某些位置放置蜂窩電話基站，由于基站的覆蓋范圍是6公里，因此必須使得每棟房子到某個基站的直線距離不超過6公里。為簡化問題，假設所有房子在同一直線上，并且基站沿該直線放置。現采用貪心策略實現用盡可能少的基站覆蓋所有的房子。
實現貪心算法的流程如圖4-2所示，請填充其中空白并計算該算法的時間復雜度，其中：
1．d[i](1≤ i ≤ N)表示第i個房子到公路A端的距離，N 表示房子的總數，房子的編號按照房子到公路A 端的距離從小到大進行編號。
2．s[k]表示第k（k ≥1）個基站到公路A 端的距離，算法結束后k的值為基站的總數。
該算法的時間復雜度為 （5） 。
溫馨提示：因考試政策、內容不斷變化與調整，本網站提供的以上信息僅供參考，如有異議，請考生以權威部門公布的內容為準！
備考學習
一鍵領取新人專享大禮包
備考學習
2025下半年軟考各科真題免費下載
備考學習
信息系統項目管理師報考指南視頻課程
備考資料
2026上半年軟考各科備考資料匯總
歷年真題
軟考各科歷年真題在線答題練習
每日一練
備考2026年軟考不慌，每日一練陪伴你
報考指導
軟考報考指南（全流程詳細指導）
延伸閱讀
軟考備考資料免費領取
去領取
距離考試還有
天
- 0
- 8
- 0
專注在線職業教育25年
APP 
微信群 
掃描二維碼
掃描二維碼
