阅读下列说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
    已知某企业的采购审批是分级进行的，即根据采购金额的不同由不同层次的主管人员来审批，主任可以审批5万元以下（不包括5万元）的采购单，副董事长可以审批5万元至10万元（不包括10万元）的采购单，董事长可以审批10万元至50万元（不包括50万元）的采购单，50万元及以上的采购单就需要开会讨论决定。
    采用责任链设计模式（Chain of Responsibility）对上述过程进行设计后得到的类图如图6-1所示。

【C++代码】

阅读以下说明和C代码，将应填入  （n）  处的字句写在答题纸的对应栏内。
【说明】
    在一个简化的绘图程序中，支持的图形种类有点（point）和圆（circle），在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形（shape），并定义了类型shape_t、point_t和circle_t分别表示基本图形、点和圆，并且点和圆具有基本图形的所有特征。

【C代码】
 
【运行结果】
    P（2，3）
      （5）  
    Circle destoryed!
    Point destoryed!

阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】
　　某机器上需要处理n个作业job1， job2， …， jobn，其中：
　　（1） 每个作业jobi（1≤i≤n）的编号为i，jobi有一个收益值p[i]和最后期限值d[i]；
　　（2） 机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；
　　（3） job1～jobn的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；
　　（4） 如果作业jobi在其期限之内完成，则获得收益p[i]；如果在其期限之后完成，则没有收益。
　　为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4-1是基于贪心策略求解该问题的流程图。
　　（1） 整型数组J[]有n个存储单元，变量k表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤ … ≤d[J[k]]。
　　（2） 为了方便于在数组J中加入作业，增加一个虚拟作业job0，并令d[0] = 0，J[0] = 0。
　　（3） 算法大致思想：先将作业job1的编号1放入J[1]，然后，依次对每个作业jobi （2≤i≤n）进行判定，看其能否插入到数组J中，若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列，否则不插入。
　　jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。
　　（4） 流程图中的主要变量说明如下： 
　　i：循环控制变量，表示作业的编号；
　　k：表示在期限内完成的作业数；
　　r：若jobi能插入数组J，则其在数组J中的位置为r+1；
　　q：循环控制变量，用于移动数组J中的元素。
 

【问题 1】（9分）

　　请填充图4-1中的空缺（1）、（2）和（3）处。
【问题 2】（4分）
　　假设有6个作业job1， job2， …， job6；
　　完成作业的收益数组p=（p[1]，p[2]，p[3]，p[4]，p[5]，p[6]） = （90，80，50，30，20，10）； 
　　每个作业的处理期限数组d=（d[1]，d[2]，d[3]，d[4]，d[5]，d[6]） = （1，2，1，3，4，3）。
　　请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列   （4）   （按作业处理的顺序给出），得到的总收益为   （5）   。
【问题 3】（2分）
　　对于本题的作业处理问题，用图4-1的贪心算法策略，能否求得最高收益？   （6）   。用贪心算法求解任意给定问题时，是否一定能得到最优解？   （7）   。

阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。
【说明】
　　已知某唱片播放器不仅可以播放唱片，而且可以连接电脑并把电脑中的歌曲刻录到唱片上（同步歌曲）。连接电脑的过程中还可自动完成充电。
　　关于唱片，还有以下描述信息：
　　1．每首歌曲的描述信息包括：歌曲的名字、谱写这首歌曲的艺术家以及演奏这首歌曲的艺术家。只有两首歌曲的这三部分信息完全相同时，才认为它们是同一首歌曲。艺术家可能是一名歌手或一支由2名或2名以上的歌手所组成的乐队。一名歌手可以不属于任何乐队，也可以属于一个或多个乐队。
　　2．每张唱片由多条音轨构成；一条音轨中只包含一首歌曲或为空，一首歌曲可分布在多条音轨上；同一首歌曲在一张唱片中最多只能出现一次。
　　3. 每条音轨都有一个开始位置和持续时间。一张唱片上音轨的次序是非常重要的，因此对于任意一条音轨，播放器需要准确地知道，它的下一条音轨和上一条音轨是什么（如果存在的话）。
　　根据上述描述，采用面向对象方法对其进行分析与设计，得到了如表3-1所示的类列表、如图3-1所示的初始类图以及如图3-2所示的描述播放器行为的UML状态图。
 

【问题 1】（3分）

　　根据说明中的描述，使用表3-1给出的类的名称，给出图3-1中的A~F所对应的类。
【问题 2】（6分）
　　根据说明中的描述，给出图3-1中（1）~（6）处的多重度。
【问题 3】（4分）
　　图3-1中缺少了一条关联，请指出这条关联两端所对应的类以及每一端的多重度。
 

【问题 4】（2分）
　　根据图3-2所示的播放器行为UML状态图，给出从“关闭”状态到“播放”状态所经过的最短事件序列（假设电池一开始就是有电的）。

（共15分）
　　阅读以下说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。
【说明】
　　某高校欲开发一个成绩管理系统，记录并管理所有选修课程的学生的平时成绩和考试成绩，其主要功能描述如下：
　　1. 每门课程都有3到6个单元构成，每个单元结束后会进行一次测试，其成绩作为这门课程的平时成绩。课程结束后进行期末考试，其成绩作为这门课程的考试成绩。
　　2. 学生的平时成绩和考试成绩均由每门课程的主讲教师上传给成绩管理系统。
　　3. 在记录学生成绩之前，系统需要验证这些成绩是否有效。首先，根据学生信息文件来确认该学生是否选修这门课程，若没有，那么这些成绩是无效的；如果他的确选修了这门课程，再根据课程信息文件和课程单元信息文件来验证平时成绩是否与这门课程所包含的单元相对应，如果是，那么这些成绩是有效的，否则无效。
　　4. 对于有效成绩，系统将其保存在课程成绩文件中。对于无效成绩，系统会单独将其保存在无效成绩文件中，并将详细情况提交给教务处。在教务处没有给出具体处理意见之前，系统不会处理这些成绩。
　　5. 若一门课程的所有有效的平时成绩和考试成绩都已经被系统记录，系统会发送课程完成通知给教务处，告知该门课程的成绩已经齐全。教务处根据需要，请求系统生成相应的成绩列表，用来提交考试委员会审查。
　　6. 在生成成绩列表之前，系统会生成一份成绩报告给主讲教师，以便核对是否存在错误。主讲教师须将核对之后的成绩报告返还系统。
　　7. 根据主讲教师核对后的成绩报告，系统生成相应的成绩列表，递交考试委员会进行审查。考试委员会在审查之后，上交一份成绩审查结果给系统。对于所有通过审查的成绩，系统将会生成最终的成绩单，并通知每个选课学生。
现采用结构化方法对这个系统进行分析与设计，得到如图1-1所示的顶层数据流图和图1-2所示的0层数据流图。

【问题 1】（4分）

　　使用说明中的词语，给出图1-1中的外部实体E1~E4的名称。
【问题 2】（3分）
　　使用说明中的词语，给出图1-2中的数据存储D1~D5的名称。
【问题 3】（6分）
　　数据流图1-2缺少了三条数据流，根据说明及数据流图1-1提供的信息，分别指出这三条数据流的起点和终点。
 

【问题 4】（2分）
　　数据流图是在系统分析与总体设计阶段宏观地描述系统功能需求的重要图形化工具，程序流程图也是软件开发过程中比较常用的图形化工具。简要说明程序流程图的适用场合与作用。

阅读下列说明和Java代码，将应填入  （n）  处的字句写在答题纸的对应栏内。 
[说明]
　　某游戏公司现欲开发一款面向儿童的模拟游戏，该游戏主要模拟现实世界中各种鸭子的发声特征、飞行特征和外观特征。游戏需要模拟的鸭子种类及其特征如表7-1所示：

　　为支持将来能够模拟更多种类鸭子的特征，采用策略设计模式(Strategy)设计的类图如图7-1所示：

　　其中，Duck为抽象类，描述了抽象的鸭子，而类RubberDuck、 MallardDuck、 CottonDuck和RedHeadDuck分别描述具体的鸭子种类，方法fly()、quack()和display()分别表示不同种类的鸭子都具有飞行特征、发声特征和外观特征；接口FlyBehavior与QuackBehavior分别用于表示抽象的飞行行为与发声行为；类FlyNoWay与FlyWithWings分别描述不能飞行的行为和用翅膀飞行的行为；类Quack、Squeak与QuackNoWay分别描述发出“嘎嘎”声的行为、发出橡皮与空气摩擦声的行为与不发声的行为。请填补以下代码中的空缺。
　　 

[Java代码]  

阅读下列说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
[说明]
　　某游戏公司现欲开发一款面向儿童的模拟游戏，该游戏主要模拟现实世界中各种鸭子的发声特征、飞行特征和外观特征。游戏需要模拟的鸭子种类及其特征如表6-1所示：

　　为支持将来能够模拟更多种类鸭子的特征，采用策略设计模式(Strategy)设计的类图如图6-1所示：

　　其中，Duck为抽象类，描述了抽象的鸭子，而类RubberDuck、 MallardDuck、 CottonDuck和RedHeadDuck分别描述具体的鸭子种类，方法fly()、quack()和display()分别表示不同种类的鸭子都具有飞行特征、发声特征和外观特征；类FlyBehavior与QuackBehavior为抽象类，分别用于表示抽象的飞行行为与发声行为；类FlyNoWay与 FlyWithWings分别描述不能飞行的行为和用翅膀飞行的行为；类Quack、Squeak与QuackNoWay分别描述发出“嘎嘎”声的行为、发出橡皮与空气摩擦声的行为与不发声的行为。请填补以下代码中的空缺。

[C++代码]

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

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

　　函数placeBoosters(TreeNode  *root)的功能是：对于给定树型分布网络中各个节点，计算其信号衰减量的最大值，并确定应在树中的哪些节点放置信号放大器。
　　全局变量Tolerance保存信号衰减容忍值。
　　树的节点类型定义如下：
　　 
　　

[C语言函数]

阅读以下说明和图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
[说明]
　　在一条农村公路的一边稀疏地分布着房子，其分布如图 4-1 所示。某电信公司需要在某些位置放置蜂窝电话基站，由于基站的覆盖范围是6公里，因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化问题，假设所有房子在同一直线上，并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。

　　实现贪心算法的流程如图4-2所示，请填充其中空白并计算该算法的时间复杂度，其中：
　　1．d[i](1≤ i ≤ N)表示第i个房子到公路A端的距离，N 表示房子的总数，房子的编号按照房子到公路A 端的距离从小到大进行编号。
　　2．s[k]表示第k（k ≥1）个基站到公路A 端的距离，算法结束后k的值为基站的总数。 

　　该算法的时间复杂度为 （5）。

阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。
[说明]
　　某图书管理系统的主要功能如下：
　　1．图书管理系统的资源目录中记录着所有可供读者借阅的资源，每项资源都有一个唯一的索引号。系统需登记每项资源的名称、出版时间和资源状态（可借阅或已借出）。
　　2．资源可以分为两类：图书和唱片。对于图书，系统还需登记作者和页数；对于唱片，还需登记演唱者和介质类型（CD 或者磁带）。
　　3．读者信息保存在图书管理系统的读者信息数据库中，记录的信息包括：读者的识别码和读者姓名。系统为每个读者创建了一个借书记录文件，用来保存读者所借资源的相关信息。
　　现采用面向对象方法开发该图书管理系统。识别类是面向对象分析的第一步。比较常用的识别类的方法是寻找问题描述中的名词，再根据相关规则从这些名词中删除不可能成为类的名词，最终得到构成该系统的类。表3-1给出了[说明]中出现的所有名词。

　　通过对表3-1中的名词进行分析，最终得到了图 3-1 所示的UML类图（类的说明如表3-2所示）。

[问题1]（3分）

　　表3-2所给出的类并不完整，根据[说明]和表3-1，将图3-1中的（a）~（c）处补充完整。
[问题2]（6分）
　　根据[说明]中的描述，给出图3-1中的类CatalogItem以及（b）、（c）处所对应的类的关键属性（使用表3-1中给出的词汇），其中，CatalogItem有4个关键属性；（b）、（c）处对应的类各有2个关键属性。
[问题3]（6分）
　　识别关联的多重度是面向对象建模过程中的一个重要步骤。根据[说明]中给出的描述，完成图3-1中的(1)~(6)。