信管网案例分析

为帮助广大软考中级软件设计师考生更好备考，信管网特整理汇总了软件设计师部分下午考试真题、答案及解析供考生查阅，并提供免费在线模拟答题、历年真题免费下载等服务，了解软件设计师更多备考信息请关注信管网。

相关推荐：

点击查看/下载：软件设计师历年真题汇总

点击查看：软件设计师在线培训课程 丨 免费试听课程

免费练习：软件设计师考试题库(模拟试题、章节练习、每日一练)

阅读以下说明和图，填补流程图中的空缺。

【说明】

在一条农村公路的一边稀疏地分布着房子，其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站，由于基站的覆盖范围是6公里，因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化问题，假设所有房子在同一直线上，并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。

实现贪心算法的流程如图10-6所示，请填充其中空白并计算该算法的时间复杂度，其中：

1.d[i](1≤i≤n)表示第i个房子到公路a端的距离，n表示房子的总数，房子的编号按照房子到公路a端的距离从小到大进行编号。

2.s[k]表示第k(k≥1)个基站到公路a端的距离，算法结束后k的值为基站的总数。

该算法的时间复杂度为 (5) 。

信管网参考答案：

答案∶(1)k=0

(2)j<=N，或其等价形式

(3)k=k+1，或其等价形式

(4)d[i]+6，或其等价形式

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

查看解析：www.cnitpm.com/st/2455317292.html