全国计算机技术与软件专业技术资格（水平）考试
2007年下半年  软件设计师  下午试卷
（考试时间  14:00～16:30 共150分钟）
请按下述要求正确填写答题纸
1.在答题纸的指定位置填写你所在的省、自治区、直辖市、计划单列市的名称。
2.在答题纸的指定位置填写准考证号、出生年月日和姓名。
3.答题纸上除填写上述内容外只能写解答。
4.本试卷共7道题，试题一至试题四是必答题，试题五至试题七选答1道。每题15分，满分75分。
5.解答时字迹务必清楚，字迹不清时，将不评分。
6.仿照下面例题，将解答写在答题纸的对应栏内。
例题
2007年下半年全国计算机技术与软件专业技术资格（水平）考试日期是（1）月（2）日。
因为正确的解答是“11月3日”，故在答题纸的对应栏内写上“11”和“3”（参看下表）。
例题
解答栏
（1）
11
（2）
3

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

试题二（15分）
阅读下列说明，回答问题1至问题4，将解答填入答题纸的对应栏内。
【说明】
某汽车维修站拟开发一套小型汽车维修管理系统，对车辆的维修情况进行管理。
    1．对于新客户及车辆，汽车维修管理系统首先登记客户信息，包括：客户编号、客户名称、客户性质（个人、单位）、折扣率、联系人、等信息；还要记录客户的车辆信息，包括：车牌号、车型、颜等信息。一个客户至少有一台车。客户及车辆信息如表2-1所示。
表2-1 客户及车辆信息
客户编号
GS0051
客户名称
××公司
客户性质
单位
折扣率
95%
联系人
杨浩东
82638779
车牌号
颜
车型
车辆类别
**0765
白
帕萨特
微型车
2．记录维修车辆的故障信息。包括：维修类型（普通、加急）、作业分类（大、中、小修）、结算方式（自付、三包、索赔）等信息。维修厂的员工分为：维修员和业务员。车辆维修首先委托给业务员。业务员对车辆进行检查和故障分析后，与客户磋商，确定故障现象，生成维修委托书。如表2-2所示。
表2-2  维修委托书
No.20070702003                                                    登记日期：2007-07-02
车牌号
**0765
客户编号
GS0051
维修类型
普通
作业分类
中修
结算方式
自付
进厂时间
20070702 11:09
业务员
张小江
业务员编号
012
预计完工时间
故障描述
车头损坏，水箱漏水
3．维修车间根据维修委托书和车辆的故障现象，在已有的维修项目中选择并确定一个或多个具体维修项目，安排相关的维修工及工时，生成维修派工单。维修派工单如表2-3所示。
表2-3 维修派工单
No.20070702003   
维修项目编号
维修项目
工时
维修员编号
维修员工种
012
    维修车头
5.00
012
机修
012
维修车头
2.00
023
漆工
015
水箱焊接补漏
1.00
006
焊工
017
更换车灯
1.00
012
机修
4．客户车辆在车间修理完毕后，根据维修项目单价和维修派工单中的工时计算车辆此次维修的总费用，记录在委托书中。
根据需求阶段收集的信息，设计的实体联系图（图2-1）和关系模式（不完整）如下所示。图2-1中业务员和维修工是员工的子实体。
【概念结构设计】
图2-1 实体联系图
【逻辑结构设计】
客户(      (5)        ，折扣率，联系人，)
车辆(车牌号，客户编号，车型，颜，车辆类别)
委托书(      (6)        ，维修类型，作业分类，结算方式，进厂时间，
预计完工时间，登记日期，故障描述，总费用)
维修项目(维修项目编号，维修项目，单价)
        派工单(    (7)     ，工时)
        员工(    (8)     ，工种，员工类型，级别)
【问题1】（4分）
根据问题描述，填写图2-1中(1)～(4)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用1 : 1，1 : n 或 1 : *，m : n 或 * : *表示。
【问题2】（4分）
补充图2-1中的联系并指明其联系类型。联系名可为：联系1，联系2，…。
【问题3】（4分）
根据图2-1和说明，将逻辑结构设计阶段生成的关系模式中的空(5)～(8)补充完整。
【问题4】（3分）
根据问题描述，写出客户、委托书和派工单这三个关系的主键。

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