中级软件设计师2007上半年下午试题.pdf

微信公众号微信公众号“跨步软考跨步软考”中级软件设计师中级软件设计师2007上半年下午试题上半年下午试题试题一试题一阅读以下说明和图，回答问题阅读以下说明和图，回答问题1至问题至问题3。【说明】某房屋租赁公司欲建立一个房屋租赁服务系统，统一管理房主和租赁者的信息，从而快速地提供租赁服务。该系统具有以下功能：1登记房主信息。对于每名房主，系统需登记其姓名、住址和联系电话，并将这些信息写入房主信息文件。2登记房屋信息。所有在系统中登记的房屋都有一个唯一的识别号(对于新增加的房屋，系统会自动为其分配一个识别号)。除此之外，还需登记该房屋的地址、房型(如平房、带阳台的楼房、独立式住宅等)、最多能够容纳的房客数、租金及房屋状态(待租赁、已出租)。这些信息都保存在房屋信息文件中。一名房主可以在系统中登记多个待租赁的房屋。3登记租赁者信息。所有想通过该系统租赁房屋的租赁者，必须首先在系统中登记个人信息，包括：姓名、住址、电话号码、出生年月和性别。这些信息都保存在租赁者信息文件中。4租赁房屋。已经登记在系统中的租赁者，可以得到一份系统提供的待租赁房屋列表。一旦租赁者从中找到合适的房屋，就可以提出看房请求。系统会安排租赁者与房主见面。对于每次看房，系统会生成一条看房记录并将其写入看房记录文件中。5收取手续费。房主登记完房屋后，系统会生成一份费用单，房主根据费用单交纳相应的费用。6变更房屋状态。当租赁者与房主达成租房或退房协议后，房主向系统提交变更房屋状态的请求。系统将根据房主的请求，修改房屋信息文件。数据流图10-1和图10-2分别给出了该系统的顶层数据流图和0层数据流图。微信公众号微信公众号“跨步软考跨步软考”1、【问题1】使用说明中给出的词汇，将数据流图10-1中(1)(4)处的数据流补充完整。2、【问题2】使用说明中给出的词汇，将数据流图10-2中的(5)(8)补充完整。3、【问题3】数据流程图10-2中缺失了三条数据流，请指出这三条数据流的起点、终点和数据流名称。试题二试题二阅读下列说明，回答问题阅读下列说明，回答问题1至问题至问题3。【说明】某医院的门诊管理系统实现了为患者提供挂号、处方药品收费的功能。具体的需求及设计如下：1医院医师具有编号，姓名，科室，职称，出诊类型和出诊费用，其中出诊类型分为专家门诊和普通门诊，与医师职称无关；各个医师可以具有不同的出诊费用，与职称和出诊类型无关。2患者首先在门诊挂号处挂号，选择科室和医师，根据选择的医师缴纳挂号费(医师出诊费)。收银员为患者生成挂号单，如表10-1所示，其中，就诊类型为医师的出诊类型。表表10-1医院门诊挂号医院门诊挂号单单收银员：13011时间：2007年2月1日 08:58就诊号姓名科室医师就诊类型挂号费20070205015叶萌内科杨玉明专家门诊5元3患者在医师处就诊后，凭借挂号单和医师手写处方到门诊药房交费买药。收银员根据就诊号和医师处方中开列的药品信息，查询药品库(如表10-2所示)并生成门诊处方单(如表10-3所示)。微信公众号微信公众号“跨步软考跨步软考”表表10-2药品库药品库药品编码 药品名称 类型库存货架编号 单位规格单价12007牛蒡子中药51590B1401G炒0.034011090百部中药36950B1523G片0.0313表表10-3医院门诊处医院门诊处方单方单时间：2007年2月1日 10:31就诊号20070205015病人姓名叶萌医师姓名杨玉明金额总计0.65项目总计2收银员21081药品编码药品名称数量单位单价金额(元)12007牛蒡子10G0.03400.3411090百部10G0.03130.314由于药品价格会发生变化，因此，门诊管理系统必须记录处方单上药品的单价。根据需求阶段收集的信息，设计的实体联系图和关系模式(不完整)如下所示：1实体联系图2关系模式挂号单(就诊号，病患姓名，医师编号，时间，4)收银员(编号，姓名，级别)医师(编号，姓名，科室，职称，出诊类型，出诊费用)门诊处方(5，收银员，时间)处方明细(就诊号，6)药品库(药品编码，药品名称，7)4、【问题1】根据问题描述，填写图10-3实体联系图中(1)(4)处联系的类型。5、【问题2】图10-3中还缺少几个联系?请指出每个联系两端的实体名，格式如下。微信公众号微信公众号“跨步软考跨步软考”实体1：实体2例如，收银员与门诊处方之间存在联系，表示为：收银员：门诊处方或门诊处方：收银员6、【问题3】根据实体联系图10-3，填写挂号单、门诊处方、处方明细和药品库关系模式中的空(5)(8)处，并指出挂号单、门诊处方和处方明细关系模式的主键。试题三试题三阅读下列说明和图，回答问题阅读下列说明和图，回答问题1至问题至问题3。【说明】某图书管理系统的主要功能如下：1图书管理系统的资源目录中记录着所有可供读者借阅的资源，每项资源都有一个唯一的索引号。系统需登记每项资源的名称、出版时间和资源状态(可借阅或已借出)。2资源可以分为两类：图书和唱片。对于图书，系统还需登记作者和页数；对于唱片，还需登记演唱者和介质类型(CD或者磁带)。3读者信息保存在图书管理系统的读者信息数据库中，记录的信息包括：读者的识别码和读者姓名。系统为每个读者创建了一个借书记录文件，用来保存读者所借资源的相关信息。现采用面向对象方法开发该图书管理系统。识别类是面向对象分析的第一步。比较常用的识别类的方法是寻找问题描述中的名词，再根据相关规则从这些名词中删除不可能成为类的名词，最终得到构成该系统的类。表10-4给出了说明中出现的所有名词。表表10-4图书管理系统资源目录读者资源索引号系统名称出版时间资源状态图书唱片作者页数演唱者介质类型CD磁带读者信息读者信息数据库识别码姓名借书记录文件信息通过对表10-4中的名词进行分析，最终得到了图10-4所示的UML类图(类的说明如表10-5所示)。表表10-5类名说明LibrarySystem图书管理系统BorrowerDB保存读者信息的数据库CatalogItem资源目录中保存的每项资源Borrower读者BorrowerItems为每个读者创建的借书记录文件7、【问题1】表10-5所给出的类并不完整，根据说明和表10-4，将图10-4中的(a)(c)处补充完整。微信公众号微信公众号“跨步软考跨步软考”8、【问题2】根据【说明】中的描述，给出图10-4中的类CatalogItem以及(b)、(c)处所对应的类的关键属性(使用表10-4中给出的词汇)，其中，CamlogItem有4个关键属性；(b)、(c)处对应的类各有两个关键属性。9、【问题3】识别关联的多重度是面向对象建模过程中的一个重要步骤。根据说明中给出的描述，完成图10-4中的(1)(6)。试题四试题四阅读以下说明和图，填补流程图中的空缺。阅读以下说明和图，填补流程图中的空缺。10、【说明】在一条农村公路的一边稀疏地分布着房子，其分布如图10-5所示。某电信公司需要在某些位置放置蜂窝电话基站，由于基站的覆盖范围是6公里，因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化问题，假设所有房子在同一直线上，并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。微信公众号微信公众号“跨步软考跨步软考”实现贪心算法的流程如图10-6所示，请填充其中空白并计算该算法的时间复杂度，其中：1di(1iN)表示第i个房子到公路A端的距离，N表示房子的总数，房子的编号按照房子到公路A端的距离从小到大进行编号。2sk表示第k(k1)个基站到公路A端的距离，算法结束后k的值为基站的总数。该算法的时间复杂度为(5)。试题五试题五(以下试题五至试题七中任选一题解答以下试题五至试题七中任选一题解答)阅读以下说明和阅读以下说明和C语言函数，应填入语言函数，应填入(n)处。处。微信公众号微信公众号“跨步软考跨步软考”11、【说明】在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树型结构，如图10-9所示。信号源是树根，树中的每个节点(除了根)表示一个可以放置放大器的子节点，其中某些节点同时也是信号消耗点，信号从一个节点流向其子节点。每个节点有一个d值，表示从其父节点到该节点的信号衰减量。例如，在图10-9中，节点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处放置放大器并不能解决到达叶子节点的信号衰减问题。例如，在图10-9中，从节点p到其所有叶子节点的最大衰减值为4。若容忍值为3，则必须在s处放置信号放大器，这样可使得节点p的M值为2。同样，需要在节点小v处放置信号放大器，如图1010阴影节点所示。若在某节点放置了信号放大器，则从该节点输出的信号与信号源输出的信号等价。函数placeBoosters(TreeNode*root)的功能是：对于给定树型分布网络中各个节点，计算其信号衰减量的最大值，并确定应在树中的哪些节点放置信号放大器。全局变量Tolerance保存信号衰减容忍值。树的节点类型定义如下：typedef struct TreeNodeint 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(;iroot-ChildNum&p；i+，p=(3)p-M=0；(4)；if(p-d+p-MTolerance)/*在p所指节点中放置信号放大器*/p-boost=true；p-M=0；if(p-d+p-M degradation)degradation=p-d+p-M；root-M=(5)；试题六试题六阅读下列说明和阅读下列说明和C+代码，应填入代码，应填入(n)处。处。12、【说明】某游戏公司现欲开发一款面向儿童的模拟游戏，该游戏主要模拟现实世界中各种鸭子的发声特征、飞行特征和外观特征。游戏需要模拟的鸭子种类及其特征如表10-6所示：表表10-6微信公众号微信公众号“跨步软考跨步软考”为支持将来能够模拟更多种类鸭子的特征，采用策略设计模式(Strategy)设计的类图如图10-11所示：其中，Duck为抽象类，描述了抽象的鸭子，而类RubberDuck、MallardDuck、CottonDuck和RedHeadDuck分别描述具体的鸭子种类，方法fly()、quack()和display()分别表示不同种类的鸭子都具有飞行特征、发声特征和外观特征；类FlyBehavior与 QuackBehavior为抽象类，分别用于表示抽象的飞行行为与发声行为：类FlyNoWay与 FlyWithWings分别描述不能飞行的行为和用翅膀飞行的行为；类Quack、Squeak与 QuackNoWay分别描述发出“嘎嘎”声的行为、发出橡皮与空气摩擦声的行为与不发声的行为。请填补以下代码中的空缺。【C+代码】#includeiostreamusing namespace(1)；class FlyBehaviorpublic：(2)fly()=0；class QuackBehaviorpublic：(3)quack()=0；class FlyWithWings：public FlyBehaviorpublic：void fly()cout“使用翅膀飞行!”endl；微信公众号微信公众号“跨步软考跨步软考”；class FlyNoWay：public FlyBehaviorpublic：void fly()cout“不能飞行!”endl；class Quack：public QuackBehaviorpublic：void quack()cout“发出嘎嘎声!”endl；class Squeak：public QuackBehaviorpublic：void quack()cout“发出空气与橡皮摩擦声!”endl；class QuackNoWay：public QuackBehaviorpublic：void quack()cout“不能发声!”endl；class Duckprotected：FlyBehavior*(4)；QuackBehavior*(5)；public：void fly()(6)；void quack()(7)；)；virtual void display()=0；class RubberDuck：public Duckpublic：RubberDuck()flyBehavior=new(8)；quackBehaviornew(9)；RubberDuck()if(!flyBehavior)delete flyBehavior；if(!quackBehavior)delete quackBehavior；void display()/*此处省略显示橡皮鸭的代码*/；/其他代码省略试题七试题七阅读下列说明和阅读下列说明和Java代码，应填入代码，应填入(n)处。处。13、【说明】某游戏公司现欲开发一款面向儿童的模拟游戏，该游戏主要模拟现实世界中各种鸭子的发声特征、飞行特征和外观特征。游戏需要模拟的鸭子种类及其特征如表10-7所示：表表10-7微信公众号微信公众号“跨步软考跨步软考”为支持将来能够模拟更多种类鸭子的特征，采用策略设计模式(Strategy)设计的类图如图10-12所示：其中，Duck为抽象类，描述了抽象的鸭子，而类RubberDuck、MallardDuck、CottonDuck和 RedHeadDuck分别描述具体的鸭子种类，方法fly()、quack()和display()分别表示不同种类的鸭子都具有飞行特征、发声特征和外观特征；接口FlyBehavior与 QuackBehavior分别用于表示抽象的飞行行为与发声行为；类FlyNoWay与FlyWithWings分别描述不能飞行的行为和用翅膀飞行的行为；类Quack、Squeak与QuackNoWay分别描述发出“嘎嘎”声的行为、发出橡皮与空气摩擦声的行为与不发声的行为。请填补以下代码中的空缺。【Java代码】(1)FlyBehaviorpublic void fly()；(2)QuackBehaviorpublic void quack()；class FlyWithWings implements FlyBehaviorpublic void fly()System.out.println(“使用翅膀飞行!”)；class FlyNoWay implements FlyBehaviorpublic void fly()System.out.println(“不能飞行!”)；微信公众号微信公众号“跨步软考跨步软考”；class Quack implements QuackBehaviorpublic void quack()System.out.println(“发出嘎嘎声!”)；class Squeak implements QuackBehaviorpublic void quack()System.out.println(“发出空气与橡皮摩擦声!”)；class QuackNoWay implements QuackBehaviorpublic void quack()System.out.println(“不能发声!”)；abstract class DuckprotectedFlyBehavior(3)；protectedQuackBehavior(4)；public void fly()(5)；public void quack()(6)；public(7)void display()；class RubberDuck extends Duckpublic RubberDuck()flyBehaviornew(8)；quackBehaviornew(9)；public void display()/*此处省略显示橡皮鸭的代码*/；/其他代码省略答案:试题一试题一1、(1)费用单(2)待租赁房屋列表(3)看房请求(4)变更房屋状态请求2、(5)房主信息文件(6)租赁者信息文件(7)房屋信息文件(8)看房记录文件3、(1)起点：房主终点：变更房屋状态数据流名称：变更房屋状态请求(2)起点：租赁者终点：登记租赁者信息数据流名称：租赁者信息(3)起点：租赁者终点：安排租赁者看房数据流名称：看房请求解析 本题考查的是DFD的应用，属于比较传统的题目，考查点也与往年类似。问题1 考查的是顶层DFD。顶层DFD通常用来确定系统边界，其中只包含一个唯一的加工(即待开发的系统)、外部实体以及外部实体与系统之间的输入输出数据流。题目要求填充的正是数据流。细心的考生可能会发现，在0层DFD中，与“房主”相关的数据流有5条。其中的“费用单”是顶层DFD中没有出现过的，而且是系统输出给“房主”的。这条数据流恰好可以与第(1)空对应，因此(1)处缺失的数据流就是“费用单”。如果确定了(4)处的数据流，实际上问题3要求的一条数据流也就找到了。由于(4)处缺失的数据流是一条输入数据流，从说明中可以看出，只有功能6“当租赁者与房微信公众号微信公众号“跨步软考跨步软考”主达成租房或退房协议后，房主向系统提交变更房屋状态的请求”所描述的数据流没有在“房主”与系统之间体现出来。因此可以确定，(4)处缺失的数据流就是“变更房屋状态请求”。相应地，可以确定，在0层图中缺失的其中一条数据流也是它，其起点是“房主”，终点是“变更房屋状态”这个加工。类似地，通过比较两张DFD中与外部实体“租赁者”相关的数据流，可以发现：出现在0层图上的数据流“带租赁房屋列表”是顶层图上没有的，且与(2)处的数据流的方向一致。由此可以断定，(2)处的数据流就是“带租赁房屋列表”。而顶层图中的数据流“租赁者信息”却是0层图上没有的。这样就找到了0层图上缺失的第2条数据流：租赁者信息，它的起点是“租赁者”，终点是加工“登记租赁者信息”。再回到说明l，其中与“租赁者”相关的功能“一旦租赁者从中找到合适的房屋，就可以提出看房请求”并没有在图中体现出来。这样就能确定(3)处的数据流应该是“看房请求”。而0层图中也没有出现这条数据流。所以，0层图中缺失的第3条数据流就是“看房请求”，它的起点是“租赁者”，终点是加工“安排租赁者看房”。到此为止所有缺失的数据流都补齐了，0层图中的(5)(8)需要填的是数据存储。由说明可以确定，这个系统中的数据存储有房主信息文件(功能1)、房屋信息文件(功能2)、租赁者信息文件(功能3)、看房记录文件(功能4)。下面就可以根据相应的加工对号入座了。显然，(5)处的是房主信息文件：(6)处的是租赁者信息文件；(7)处的是房屋信息文件；(8)处的是看房记录文件。试题二试题二4、(1)1(2)*，或n，或m(3)*，或n，或m(4)*，或n，或m5、缺少的联系数：3挂号单：收银员挂号单：医师挂号单：门诊处方6、(5)收银员，或收银员编号(6)就诊号(7)药品编码，数量，单价(8)类型，库存，货架编号，单位，规格，单价挂号单主键：就诊号门诊处方主键：就诊号处方明细主键：就诊号、药品编码解析问题1分析本题主要是考数据库的概念结构设计。根据题目的需求描述和表10-3中的数据可知，一名医生可以开多张门诊处方，一张门诊处方由一名医生开出。所以对于医生实体与门诊处方实体之间的联系“开处方”，其联系的类型为一对多(1：n)。(1)空的答案为1，(2)空的答案为n。根据题目的需求描述和表10-3中的数据可知，一张门诊处方包含多种库存中的药品，一种库存中的药品也可以在多张门诊处方中。所以对于门诊处方实体与药品库存实体之间的联系“明细”，其联系的类型为多对多(m：n)。(3)空的答案为m，(4)空的答案为n。问题2分析根据题目的需求描述和表10-1中的数据可知，挂号单由收银员进行收费，因此挂号单实体与收银员实体之间存在联系。挂号单：收银员病人挂某个医师的号，将挂号信息记录在挂号单实体中，因此挂号单实体与医师实体之间存在联系。挂号单：医师根据题目的需求描述和表10-3中的数据可知，收银员根据挂号单和医师的手写处方生成门诊处方，所以挂号单实体与门诊处方实体之间存在联系。挂号单：门诊处方因此，缺少的联系数：3微信公众号微信公众号“跨步软考跨步软考”问题3分析本题主要考查数据库的逻辑结构设计。根据实体联系图和表10-1的数据，对于“挂号单”关系模式，由于挂号单与收银员实体有联系，需记录对应的收银员，因此，“挂号单”关系模式需补充属性(5)：收银员。根据实体联系图和表10-3的数据，由于门诊处方实体与挂号单实体有联系，因此，“门诊处方”关系模式需记录(6)：就诊号。并且，根据题意在门诊处方和挂号单之间存在的是1对1的联系，因此挂号单的主键可以作为门诊处方的主键。根据实体联系图和表10-2、表10-3的数据，由于广张门诊处方中包含多项药品信息，而一种药品也可以属于多张门诊处方，所以通过“处方明细”关系模式来表示这种多对多的联系。并且由于每种药品的具体信息已经在“药品库存”关系模式中记录，所以，“处方明细”关系模式主要记录的是门诊处方与药品的对应关系和处方所需药品的具体数量。并且，根据题目描述，由于药品价格会发生变化，门诊管理系统必须记录处方单上药品的当前单价。因此，“药品库存”关系模式补充属性(7)：堑显缠昱，数量，单价。其中就诊号和药品编号一起作为主键。“药品库存”关系模式主要记录药品的详细信息和库存信息，根据实体联系图和表 10-2的数据，“药品库存”关系模式需补充属性(8)：类型，库存，货架编号，单位，规格，单价。挂号单主键：就诊号门诊处方主键：就诊号处方明细主键：就诊号、药品编码试题三试题三7、(a)资源目录(b)图书(c)唱片注：(b)和(c)的答案可以互换8、CatalogItem的属性：索引号、名称、出版时间、资源状态图书的属性：作者、页数唱片的属性：演唱者、介质类型9、(1)1(2)0.*(3)1(4)0.*(5)1(6)1或者0.1解析本题主要考查面向对象分析中类图的设计，涉及到类的识别、属性的识别以及多重度的计算。问题1要求的是将所有的类找出来。由于说明中给出了识别类的规则，并给出了所有的候选类和一张不完整的类图，从而为我们提供了大量的提示信息。从类图可以看出，这里有一个继承结构，确实这两个类恰好是这个继承结构的子类。根据说明中提供信息，我们发现只有“资源”、“图书”和“唱片”这三者之间存在着继承结构所描述的“一般特殊”关系。因为“图书”和“唱片”都是图书管理系统中的资源，因此具有共性(索引号、名称、出版时间、资源状态)；而这两者又是两种完全不同的事物，所以有着各自特有的性质。同时，这三者又都在候选类集合中。所以可以断定(b)、(c)处要填的类就是“唱片”和“图书”。这里连这三个类的属性也可以完全确定了。类CatalogItem描述的是共性，所以它的属性是索引号、名称、出版时间、资源状态。由说明中第2条可以确定，“图书”的属性是作者和页数；“唱片”的属性是演唱者和介质类型。下面需要确定(a)处的类到底是什么?从说明中的第1条和表10-5可以看出，CatalogItem表示的是“资源目录保存的每项资源”，这是集合(资源目录)与其中的元素的概念。所以(a)处的类应该是“资源目录”一既然明确这里是集合的概念，(1)和(2)处的多重度也可以确定了。CatalogItem表示的是部分，所以(1)处应填1，(2)处应填1.*(0.*也可以)。类似的，BorrowerDB与Borrower之间也具有相似的关系。因为数据库中可以保存多个读者的信息。因此(3)处填1，(4)处填1.*(0.*也可以)。系统为每个读者都创建了借书记录文件，所以(5)处填1，(6)填1(0.1也可以)。试题四试题四10、(1)k=0(2)jN，或其等价形式微信公众号微信公众号“跨步软考跨步软考”(3)k=k+1，或其等价形式(4)di+6，或其等价形式(5)O(N)，或O(n)解析该问题可以建模为如图10-7所示，其中直线表示房子所在的直线，实心正方形表示房子。问题是要求如何在该直线上布局机站，使其能覆盖所有的房子，并且所用机站的数量要尽可能的少。这是一个通过进行一系列选择求最优解的问题。分析该问题，发现其具有最优子结构，并且具有贪心选择性质，故该问题可以用贪心算法来求解。算法思想：问题的规模为N。从第一个房子(最左端)开始布局机站，把第一个机站放置在该房子右方的6公里处，这时该机站会覆盖从第一个房子到其右方 12公里的直线的长度上的所有房子，假设覆盖了N1个房子。此时问题规模变成了N-N1。把第一个机站覆盖的房子去掉，再从N-N1中选择第一个(最左端)房子开始布局机站，将第二个机站放置在该房子右方的6公里处。依此布局，直到覆盖所有的房子。图10-8是问题解的模型，其中直线表示房子所在的直线，实心正方形表示房子，实心圆形表示机站，虚线圆以对应机站为圆心，直径为机站的覆盖范围，即对应机站的覆盖范围。算法中包含两个循环，但实际上只是遍历所有房子一次，故算法复杂度是O(N)。试题五试题五11、(1)root(2)root-childptr0，或其等价形式(3)root-childptri，p+，或其等价形式(4)placeBoosters(p)(5)degradation解析本题考查树结构的应用。根据题目中的说明，节点的M值表示从该节点出发到其所有叶子的信号衰减量的最大值。显然，叶子节点的M值为0。对于非叶子节点j，M(j)=maxM(k)+d(k)|k是j的孩子节点。在此公式中，要计算节点的M值，必须先算出其所有子节点的M值。因此，需要对树进行后序遍历。对树中节点的运算应针对非空节点，因此空(1)处应填入root。变量degradation用于计算节点的信号衰减量。节点中的ChildNum表示当前节点的孩子数目，因此若“iroot-ChildNum”，则root指向的节点是叶子。以下代码是对树进行后序遍历并计算节点的信号衰减量。p=(2)；微信公众号微信公众号“跨步软考跨步软考”for(;i root-ChildNum&p；i+，p=(3)p-M=0；(4)；if(p-d+p-MTolerance)/*在p所指节点中放置信号放大器*/p-boost=true；p-M=0；if(p-d+p-M degradation)degradation=p-d+p-M；root-M=(5)；分析以上代码可知，指针p用于指向子节点，其初始值应为第一个子节点“childptr0”的指针，因此空(2)处应填入“root-childptr0”，此后p依次指向下一个子节点，因此空(3)处填入“root-childpbtri”或“p+”。由于树结构是递归的，因此，可用递归方法计算所有子节点的信号衰减量。在设计思路上，应考虑节点为叶子时的情况(递归终止)以及从子节点返回父节点后需要处理的情况。对于当前的子节点(childptri)，显然需要通过递归调用去处理，因此空(4)处应填入“placeBoosters(p)”在计算M值的过程中，对于某个节点i，其有一个子节点k满足d(k)+M(k)大于容忍值(p-d+p-MTolerance)，则应在k处放置放大器(p-boosttrue)，否则，从节点i到某叶子节点的信号衰减量会超过容忍值，使得到达该叶子节点时信号不可用，而在节点i处放置放大器并不能解决到达叶子节点的信号衰减问题。当root所指节点的所有子节点的信号衰减量最大值求出来并按要求放置信号放大器后，就可以记录该节点的信号衰减量最大值了，因此空(5)处应填入“degradation”。试题六试题六12、(1)std(2)virtual void(3)virtual void(4)fiyBehavior(5)quackBehavior(6)flyBehavior-fly()(7)quackBehavior-quack()(8)FlyNoWay()(9)Squeak()解析C+标准的输出输入的命名空间为std，在本题的代码中使用了cout，因此必须使用标准的命名空间，空(1)处应该填写std；FlyWithWings和FlyNoWay类继承了 FlyBehavior，根据它们的成员函数fly的定义可知，fly函数的返回值为void，又因为 FlyBehavior中函数为纯虚拟函数，因此，空(2)处应该填写virtual void，空(3)处的原理和空(2)相同；Duck是各种鸭子种类的基类，而每一种鸭子都具有飞行特征和发声特征，这两种特征分别通过FlyBehavior 和QuackBehavior来实现，因此空(4)和(5)处应该为这两个类的对象或者指针(这两个类为纯虚类，因此只能采用指针形式)。每一种具体的鸭子种类的飞行特征和发声特征是不同的，因此，在每一种具体鸭子类的构造函数中需要指定其具有的飞行特征和发声特征，表10-6已经指出了RubberDuck的这两种特征分别为FlyNoWay 和 Squeak，所以，通过构造相应类的对象来实现该特征。试题七试题七13、(1)interface微信公众号微信公众号“跨步软考跨步软考”(2)interface(3)flyBehavior(4)quackBehavior(5)flyBehavior.fly()(6)quackBehavior.quack()(7)abstract(8)FlyNoWay()(9)Squeak()解析FlyBehavior与QuackBehavior分别表示抽象的飞行特征，它们仅仅规定了接口，因此空(1)和(2)应该填写interface；Duck是各种鸭子种类的基类，而每一种鸭子都具有飞行特征和发声特征，这两种特征分别通过FlyBehavior和QuackBehavior来实现，因此空(3)和(4)处应该为这两个类的对象引用，Duck的飞行动作和发声动作通过abstract与其飞行特征对象和发声特征对象相关，所以，直接调用这两个类的飞行和发声动作即可。因为每一种Duck的显示特征是不相同的，因此display方法应该为抽象的方法；每一种具体的鸭子种类的飞行特征和发声特征是不同的，因此，在每一种具体鸭子类的构造函数中需要指定其具有的飞行特征和发声特征。表10-7已经指出了RubberDuck的这两种特征分别为FlyNoWay和Squeak，所以，通过构造相应类的对象来实现该特征。