中级软件设计师填空集试卷（中级软件设计师）_14.docVIP

试卷第 PAGE 1 页共 NUMPAGES 4 页 中级软件设计师填空集试卷（中级软件设计师） 姓名:_____________ 年级:____________ 学号:______________ 题型 选择题 填空题 解答题 判断题 计算题 附加题 总分 得分 评卷人 得分 1、[说明]在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树型结构，如图4-1所示。信号源是树根，树中的每个节点(除了根)表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子节点。每个节点有一个d值，表示从其父节点到该节点的信号衰减量。例如，在图4-1中，节点w、p、q的d值分别为2、1、3，树根节点表示信号源，其d值为0。每个节点有一个M值，表示从该节点出发到其所有叶子的信号衰减量的最大值。显然，叶子节点的M值为0。对于非叶子j，M(j)=maxM(k)+d(k)|k是j孩子节点，在此公式中，要计算节点的M值，必须先算出其所有子节点的M值。在计算M值的过程中，对于某个节点i，其有一个子节点k满足d(k)+M(k)大于容忍值，则应在k处放置放大器，否则，从节点i到某叶子节点的信号衰减量会超过容忍值，使得到达该叶子节点时信号不可用，而在节点i处放置放大器并不能解决到达叶子节点的信号衰减问题。例如，在图4-1中，从节点p到其所有叶子节点的最大衰减值为4。若容忍值为3，则必须在s处放置信号放大器，这样可使得节点p的M值为2。同样，需要在节点q、v处放置信号放大器，如图4-2阴影节点所示。若在某节点放置了信号放大器，则从该节点输出的信号源输出的信号等价。函数placeBoosters(TreeNode*root)的功能是：对于给定树型分布网络中各个节点，计算其信号衰减量的最大值，并确定应在树中的哪些节点放置信号放大器。全局变量Tolerance保存信号衰减容忍值。树的节点类型定义如下：typedef struc tTreeNodeint id; /*当前节点的识别号*/int ChildNum; /*当前节点的子节点数目*/int d; /*父节点到当前节点的信号衰减值*/struct TreeNode **childptr; /*向量，存放当前节点到其所有子节点的指针*/int M; /*当前节点到其所有子节点的信号衰减值中的最大值*/bool boost; /*是否在当前节点放置信号放大器的标志*/TreeNode;[C语言函数]void placeBooster(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 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）处填（ ）。 2、[说明]在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树型结构，如图4-1所示。信号源是树根，树中的每个节点(除了根)表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子节点。每个节点有一个d值，表示从其父节点到该节点的信号衰减量。例如，在图4-1中，节点w、p、q的d值分别为2、1、3，树根节点表示信号源，其d值为0。每个节点有一个M值，表示从该节点出发到其所有叶子的信号衰减量的最大值。显然，叶子节点的M值为0。对于非叶子j，M(j)=maxM(k)+d(k)|k是j孩子节点，在此公式中，要计算节点的M值，必须先算出其所有子节点的M值。在计算M值的过程中，对于某个节点i，其有一个子节点k满足d(k)+M(k)大于容忍值，则应在k处放置放大器，否则，从节点i到某叶子节点的信号衰减量会超过容忍值，使得到达该叶