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

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

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

(1) A.分治

B.動(dòng)態(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.肯定可以求得問題的一個(gè)最優(yōu)解

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

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

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

信管網(wǎng)參考答案：C、B、B、A

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

相關(guān)推薦：

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

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

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