精品文档
该算法的时间复杂度为 (5)。 这道题您没有回答 答案:(1)k=0
(2)j＜＝N，或其等价形式 (3)k=k+1，或其等价形式 (4)d[i]+6，或其等价形式 (5)O(N)，或O(n) [分析]
该问题可以建模为如图10-7所示，其中直线表示房子所在的直线，实心正方形表示房子。问题是要求如何在该直线上布局机站，使其能覆盖所有的房子，并且所用机站的数量要尽可能的少。这是一个通过进行一系列选择求最优解的问题。
分析该问题，发现其具有最优子结构，并且具有贪心选择性质，故该问题可以用贪心算法来求解。算法思想：问题的规模为N。从第一个房子(最左端)开始布局机站，把第一个机站放置在该房子右方的6公里处，这时该机站会覆盖从第一个房子到其右方 12公里的直线的长度上的所有房子，假设覆盖了N1个房子。此时问题规模变成了N-N1。把第一个机站覆盖的房子去掉，再从N-N1中选择第一个(最左端)房子开始布局机站，将第二个机站放置在该房子右方的6公里处。依此布局，直到覆盖所有的房子。
图10-8是问题解的模型，其中直线表示房子所在的直线，实心正方形表示房子，实心圆形表示机站，虚线圆以对应机站为圆心，直径为机站的覆盖范围，即对应机站的覆盖范围。
精品文档
精品文档
算法中包含两个循环，但实际上只是遍历所有房子一次，故算法复杂度是O(N)。 试题五
(以下试题五至试题七中任选一题解答)
阅读以下说明和C语言函数，应填入 (n)处。 11. 【说明】
在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树型结构，如图10-9所示。信号源是树根，树中的每个节点(除了根)表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子节点。
每个节点有一个d值，表示从其父节点到该节点的信号衰减量。例如，在图10-9中，节点w、p、q的d值分别为2、1、3，树根节点表示信号源，其d值为0。
每个节点有一个M值，表示从该节点出发到其所有叶子的信号衰减量的最大值。显然，叶子节点的M值为0。对于非叶子节点j，M(j)=max{M(k)+d(k)|k是j的孩子节点}。在此公式中，要计算节点的M值，必须先算出其所有子节点的M值。
在计算M值的过程中，对于某个节点i，其有一个子节点k满足d(k)+M(k)大于容忍值，则应在k处放置放大器，否则，从节点i到某叶子节点的信号衰减量会超过容忍值，使得到达该叶子节点时信号不可用，而在节点i处放置放大器并不能解决到达叶子节点的信号衰减问题。
例如，在图10-9中，从节点p到其所有叶子节点的最大衰减值为4。若容忍值为3，则必须在s处放置信号放大器，这样可使得节点p的M值为2。同样，需要在节点小v处放置信号放大器，如图10—10阴影节点所示。若在某节点放置了信号放大器，则从该节点输出的信号与信号源输出的信号等价。
精品文档
精品文档
函数placeBoosters(TreeNode*root)的功能是：对于给定树型分布网络中各个节点，计算其信号衰减量的最大值，并确定应在树中的哪些节点放置信号放大器。 全局变量Tolerance保存信号衰减容忍值。 树的节点类型定义如下：
typedef struct TreeNode{
int id； /*当前节点的识别号*/
int ChildNum； /*当前节点的子节点数目*/ int d; /*父节点到当前节点的信号衰减值*/
struct TreeNode **childptr； /*向量，存放当前节点到其所有子节点的指针*/ int M； /*当前节点到其所有子节点的信号衰减值中的最大值*/ bool boost； /*是否在当前节点放置信号放大器的标志*/ }TreeNode； 【C语言函数】
void placeBoosters(TreeNode *root)
{ /* 计算root所指节点处的衰减量，如果衰减量超出了容忍值，则放置放大器*/ TreeNode *p；
int i，degradation；
if( (1)){ degradation = 0；root-＞M = 0； i = 0；
if (i＞=root-＞ChildNum) return； p= (2)；
for(;i＜root-＞ChildNum && p； i++，p = (3)){ p-＞M = 0； (4)；
if (p-＞d+p-＞M＞Tolerance) { /*在p所指节点中放置信号放大器*/ p-＞boost=true； p-＞M = 0；
}
if (p-＞d + p-＞M ＞ degradation) degradation = p-＞d + p-＞M； }
root-＞M = (5)； } 精品文档
精品文档
}
这道题您没有回答 答案:(1)root
(2)root-＞childptr[0]，或其等价形式
(3)root-＞childptr[i]，p++，或其等价形式 (4)placeBoosters(p)
(5)degradation [分析]
本题考查树结构的应用。
根据题目中的说明，节点的M值表示从该节点出发到其所有叶子的信号衰减量的最大值。显然，叶子节点的M值为0。对于非叶子节点j，M(j)=max{M(k)+d(k)| k是j的孩子节点}。在此公式中，要计算节点的M值，必须先算出其所有子节点的M值。因此，需要对树进行后序遍历。
对树中节点的运算应针对非空节点，因此空(1)处应填入root。变量degradation用于计算节点的信号衰减量。节点中的ChildNum表示当前节点的孩子数目，因此若“i＞＝root-＞
ChildNum”，则root指向的节点是叶子。以下代码是对树进行后序遍历并计算节点的信号衰减量。 p= (2)；
for(;i ＜ root-＞ChildNum && p； i++，p = (3)){ p-＞M = 0； (4)；
if (p-＞d+p-＞M＞Tolerance) { /*在p所指节点中放置信号放大器*/ p-＞boost = true； p-＞M = 0；
}
if (p-＞d + p-＞M ＞ degradation) degradation = p-＞d + p-＞M； }
root-＞M= (5)；
}
分析以上代码可知，指针p用于指向子节点，其初始值应为第一个子节点“childptr[0]”的指针，因此空(2)处应填入“root-＞childptr[0]”，此后p依次指向下一个子节点，因此空(3)处填入“root-＞childpbtr[i]”或“p++”。
由于树结构是递归的，因此，可用递归方法计算所有子节点的信号衰减量。在设计思路上，应考虑节点为叶子时的情况(递归终止)以及从子节点返回父节点后需要处理的情况。对于当前的子节点(childptr[i])，显然需要通过递归调用去处理，因此空(4)处应填入“placeBoosters(p)” 在计算M值的过程中，对于某个节点i，其有一个子节点k满足d(k)+M(k)大于容忍值(p-＞d+p-＞M＞Tolerance)，则应在k处放置放大器(p-＞boost＝true)，否则，从节点i到某叶子节点的信号衰减量会超过容忍值，使得到达该叶子节点时信号不可用，而在节点i处放置放大器并不能解决到达叶子节点的信号衰减问题。
当root所指节点的所有子节点的信号衰减量最大值求出来并按要求放置信号放大器后，就可以记录该节点的信号衰减量最大值了，因此空(5)处应填入“degradation”。 试题六
阅读下列说明和C++代码，应填入 (n)处。 精品文档
