2. 计算机
  3. 阅读下列说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信

阅读下列说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信

admin2018-07-23  77
问题 阅读下列说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。
    【说明】
    在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树形结构，如题图4-1所示。信号源是树根，树中的每个节点(除了根)表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子节点。

    每个节点有一个d值，表示从其父节点到该节点的信号衰减量。例如，在题图4-1中，节点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处放置放大器并不能解决到达叶子节点的信号衰减问题。例如，在题图4-1中，从节点p到其所有叶子节点的最大衰减值为4。若容忍值为3，则必须在s处放置信号放大器，这样可使得节点p的M值为2。同样，需要在节点q、v处放置信号放大器，如题图4-2阴影节点所示。若在某节点放置了信号放大器，则从该节点输出的信号与信号源输出的信号等价。

    函数placeBoosters(TreeNode*root)的功能是：对于给定树形分布网络中各个节点，计算其信号衰减量的最大值，并确定应在树中的哪些节点放置信号放大器。
    全局变量Tolerance保存信号衰减容忍值。树的节点类型定义如下：
    typedef  struct  TreeNode  {
    int id；／*当前节点的识别号*／
    int ChildNum；／*当前节点的子节点数目*／
    int d；／*父节点到当前节点的信号衰减值*／
    struct TreeNode*★childptr；／*向量，存放当前节点到其所有子节点的指针*／
    int M;／*当前节点到其所有子节点的信号衰减值中的最大值*／
    bool boost；／*是否在当前节点放置信号放大器的标志*／
  } TreeNode；
  【C语言函数】
  Void placeBoosters(TreeN0de  *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] (4)placeBoosters(p) (5)degradation
解析 本题考查数据结构中树的基本操作。题目说明部分对树的结构以及程序的目的有比较明确的说明。本程序的功能是在合适的位置安放信号放大器。通过对题目说明部分的分析可以得知放置信号放大器的原则是判断当前节点的d+M是否大于容忍值。若大于，则在i处设信号放大器。例如，对于节点s，d[s]=2，M[s]=2，d[s]+M[s]=4，此时容忍值为3，则d[s]+M[s1]＞3，需要在此放置一个信号放大器。但在题目中，节点的M值是未提供的，所以程序应完成两个操作，第一个是求出节点的M值，第二个是确定当前节点是否需要加信号放大器。
    下面进行具体的代码分析。
    空(1)处是一个判断条件，当条件成立时，才能进入程序主体。这一空非常容易，在对树进行操作的过程中，只有当前节点不为空节点时才有必要进行相应的操作，所以此处应填入root。
    通过对程序主体进行分析可知，指针p用于指向子节点，其初始值应为第一个子节点childptr[0]的指针，因此空(2)处应填入root-＞childptr[0]，此后P依次指向下一个子节点。因此空(3)处应填入root-＞childptr。
    空(4)处是关键的一步，由于“要计算节点的M值，必须先算出其所有子节点的M值”，所以需要用到递归，利用递归来计算子节点的M值，故此处填入placeBoosters(p)。
    空(5)处非常容易，是将已求得的M值存入当前节点的root-＞M中，由于程序中计算出来的M记录在degradation中，所以此处填入degradation。
转载请注明原文地址:https://kaotiyun.com/show/pKDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)