在一條筆直公路的一邊有許多房子，現(xiàn)要安裝消防栓，每個消防栓的覆蓋范圍遠大于房子的面積，如下圖所示?，F(xiàn)求解能覆蓋所有房子的最少消防栓數(shù)和安裝方案(問題求解過程中，可將房子和消防栓均視為直線上的點)。

該問題求解算法的基本思路為：從左端的第一棟房子開始，在其右側m米處安裝一個消防栓，去掉被該消防栓覆蓋的所有房子。在剩余的房子中重復上述操作，直到所有房子被覆蓋。算法采用的設計策略為( 1 )；對應的時間復雜度為( 2 )。

假設公路起點A的坐標為0，消防栓的覆蓋范圍(半徑)為20米，10棟房子的坐標為(10，20,，30，35，60，80，160，210，260，300)，單位為米。根據上述算法，共需要安裝( 3 )個消防栓。以下關于該求解算法的敘述中，正確的是( 4 )。

(1) A.分治

B.動態(tài)規(guī)劃

C.貪心

D.回溯

(2)A.Θ(lgn)

B.Θ(n)

C.Θ(nlgn)

D.Θ(n2)

(3) A.4

B.5

C.6

D.7

(4)A.肯定可以求得問題的一個最優(yōu)解

B.可以求得問題的所有最優(yōu)解

C.對有些實例，可能得不到最優(yōu)解

D.只能得到近似最優(yōu)解

信管網參考答案：C、B、B、A

查看解析：www.xomuzic.com/st/407522687.html

相關推薦：

點擊查看/下載：軟件設計師歷年真題匯總

點擊查看：軟件設計師在線培訓課程 丨 免費試聽課程

免費練習：軟件設計師考試題庫(模擬試題、章節(jié)練習、每日一練)