首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C语言函数,应填入(n)处。 【说明】 在一个分布网络中,资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中,资源会有损耗。例如,天然气的气压会减少,电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗
阅读以下说明和C语言函数,应填入(n)处。 【说明】 在一个分布网络中,资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中,资源会有损耗。例如,天然气的气压会减少,电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗
admin
2008-08-01
97
问题
阅读以下说明和C语言函数,应填入(n)处。
【说明】
在一个分布网络中,资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中,资源会有损耗。例如,天然气的气压会减少,电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中,仅能容忍一定范围的信号衰减,称为容忍值。分布网络可表示为一个树型结构,如图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
”或“p++”。
由于树结构是递归的,因此,可用递归方法计算所有子节点的信号衰减量。在设计思路上,应考虑节点为叶子时的情况(递归终止)以及从子节点返回父节点后需要处理的情况。对于当前的子节点(childptr
),显然需要通过递归调用去处理,因此空(4)处应填入“placeBoosters(p)”
在计算M值的过程中,对于某个节点i,其有一个子节点k满足d(k)+M(k)大于容忍值(p->d+p->M>Tolerance),则应在k处放置放大器(p->boost=true),否则,从节点i到某叶子节点的信号衰减量会超过容忍值,使得到达该叶子节点时信号不可用,而在节点i处放置放大器并不能解决到达叶子节点的信号衰减问题。
当root所指节点的所有子节点的信号衰减量最大值求出来并按要求放置信号放大器后,就可以记录该节点的信号衰减量最大值了,因此空(5)处应填入“degradation”。
转载请注明原文地址:https://kaotiyun.com/show/ZfDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
高速缓存cache与主存间采用全相联地址映像方式,高速缓存的容量为4MB,分为4块,每块1MB,主存容量为256MB。若主存读写时间为30ns,高速缓存的读写时间为3ns,平均读写时间为3.27ns,则该高速缓存的命中率为(3)%。若地址变换表如下所示,
阅读下列流程图:当用判定覆盖法进行测试时,至少需要设计(44)个测试用例。
设有职工EMP(职工号,姓名,性别,部门号,职务,进单位时间,电话),职务JOB(职务,月薪)和部门DEPT(部门号,部门名称,部门电话,负责人)实体集。一个职务可以由多个职工担任,但一个职工只能担任一个职务,并属于一个部门,部门负责人是一个职工。下图所示
假设在程序控制流图中有14条边、10个节点,则控制流程图的环路复杂性V(G)等于______。A.12B.8C.6D.4
对需求说明书评测的内容包括______。①系统定义的目标是否与用户的要求一致②被开发项目的数据流与数据结构是否足够、确定③与所有其他系统交互的重要接口是否都已经描述④主要功能是否已包含在规定的软件范围之内,是否都已充分说明
模块设计中,某模块根据输入的控制信息从文件中读一个记录或者向文件中写一个记录,则其内聚类型为______。
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(37)
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(36)
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(35)
完成下列命令行,对网络接口进行地址初始化配置。firewall(config)#ipaddressinside(1)(2)firewall(config)#ipaddressoutside(3)(4)管道命令的作用是允许数据流从
随机试题
小儿洋地黄中毒最常见的表现是
下列关于代议制的说法不正确的有()
Sometimesyou’llhearpeoplesaythatyoucan’tloveothersuntilyouloveyourself.Sometimesyou’llhearpeoplesaythatyou
男性患者,42岁,发现大腿肿块生长迅速,予以切除。肿物直径6cm,质韧,灰白色,镜下见肿瘤细胞排列成羽毛状结构,细胞间有多量的胶原纤维,核分裂较少,免疫组化Vimentin阳性,SMA、CD68、EMA阴性。有关此病的预后,错误的是
很少造成感染,但毒力强,一旦造成感染病情凶险,死亡率高产褥感染最常见的细菌为
下列收入中,属于民间非营利组织收入的有()。
贯彻“以人为本”的教育理念首先应做到()。
社会救济和弱势人口的救助属于政府的()。
研究发现,中年之后开始学习演奏乐器,可以在很短时间内就令听力显著改善。此外,聆听和演奏乐曲需要调动多个大脑系统协作,这也有助于帮助因衰老和疾病受损的大脑恢复和保持功能。因此,学习演奏乐器可以预防衰老。以下哪项如果为真,最能支持这一论证?
操作系统将CPU的时间资源划分成极短的时间片,轮流分配给各终端用户,使用户单独分享CPU的时间片,有“独占计算机”的感觉,这种操作系统称为
最新回复
(
0
)