1、计算机水平考试中级软件设计师 2009 年上半年下午真题及答案解析(总分：105.00，做题时间：150 分钟)试题一（共 15 分） 阅读下列说明，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。 【说明】 假设某大型商业企业由商品配送中心和连锁超市组成，其中商品配送中心包括采购、财务、配送等部门。为实现高效管理，设计了商品配送中心信息管理系统，其主要功能描述如下： 1. 系统接收由连锁超市提出的供货请求，并将其记录到供货请求记录文件。 2. 在接到供货请求后，从商品库存记录文件中进行商品库存信息查询。如果库存满足供货请求，则给配送处理发送配送通知；否则，向采购部门发出缺货通知。 3.
2、 配送处理接到配送通知后，查询供货请求记录文件，更新商品库存记录文件，并向配送部门发送配送单，在配送货品的同时记录配送信息至商品配送记录文件。 4. 采购部门接到缺货通知后，与供货商洽谈，进行商品采购处理，合格商品入库，并记录采购清单至采购清单记录文件、向配送处理发出配送通知，同时通知财务部门给供货商支付货款。 该系统采用结构化方法进行开发，得到待修改的数据流图（如图 1-1 所示）。 （分数：15.00）(1).【问题 1】（8 分） 使用【说明】中的词语，给出图 1-1 中外部实体 E1 至 E4 的名称和数据存储 D1 至 D4 的名称。 （分数：7.50）填空项 1:_(2).【问题
3、2】（7 分） 图 1-1 中存在四处错误数据流，请指出各自的起点和终点；若将上述四条错误数据流删除，为保证数据流图的正确性，应补充三条数据流，请给出所补充数据流的起点和终点。（起点和终点请采用数据流图 1-1 中的符号或名称） （分数：7.50）填空项 1:_试题二（15 分 ） 阅读下列说明，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。 【说明 】 某集团公司拥有多个大型连锁商场，公司需要构建一个数据库系统以方便管理其业务运作活动。 【需求分析结果】 1. 商场需要记录的信息包括商场编号（编号唯一），商场名称，地址和联系电话。某商场信息如表 2-1 所示。 2. 每个商场包含有不
4、同的部门，部门需要记录的信息包括部门编号（集团公司分配），部门名称，位置分布和联系电话。某商场的部门信息如下图所示。 3. 每个部门雇用多名员工处理日常事务，每名员工只能隶属于一个部门（新进员工在培训期不隶属于任何部门）。员工需要记录的信息包括员工编号（集团公司分配），姓名，岗位，电话号码和工资。员工信息如下图所示。 4. 每个部门的员工中有一名是经理，每个经理只能管理一个部门，系统需要记录每个经理的任职时间。 【概念模型设计 】 根据需求阶段收集的信息，设计的实体联系图和关系模式（不完整）如下： （分数：15.00）(1).【问题 1】 （6 分 ） 根据问题描述，补充四个联系，完善图 2-
5、1 的实体联系图。联系名可用联系 1、联系 2、联系 3 和联系 4 代替，联系的类型分为 1:1、1:n 和 m:n。 （分数：5.00）填空项 1:_(2).【问题 2】 （6 分） 根据实体联系图，将关系模式中的空（a）（c）补充完整，并分别给出部门、员工和经理关系模式的主键和外键。 （分数：5.00）填空项 1:_(3).【问题 3】 （3 分） 为了使商场有紧急事务时能联系到轮休的员工，要求每位员工必须且只能登记一位紧急联系人的姓名和联系电话，不同的员工可以登记相同的紧急联系人。则在图 2-1 中还需添加的实体是 1，该实体和图 2-1 中的员工存在 2 联系（填写联系类型）。给出该
6、实体的关系模式。 （分数：5.00）填空项 1:_试题三 （共 15 分） 阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。 【说明 】 某银行计划开发一个自动存提款机模拟系统（ATM System）。系统通过读卡器（CardReader）读取 ATM 卡；系统与客户（Customer）的交互由客户控制台（CustomerConsole）实现；银行操作员（Operator）可控制系统的启动（System Startup）和停止（System Shutdown）；系统通过网络和银行系统（Bank）实现通信。 当读卡器判断用户已将 ATM 卡插入后，创建会话（Session
7、）。会话开始后，读卡器进行读卡，并要求客户输入个人验证码（PIN）。系统将卡号和个人验证码信息送到银行系统进行验证。验证通过后，客户可从菜单选择如下事务（Transaction）： 1. 从 ATM 卡账户取款（Withdraw）； 2. 向 ATM 卡账户存款（Deposit）； 3. 进行转账（Transfer）； 4. 查询（Inquire）ATM 卡账户信息。 一次会话可以包含多个事务，每个事务处理也会将卡号和个人验证码信息送到银行系统进行验证。若个人验证码错误，则转个人验证码错误处理（Invalid PIN Process）。每个事务完成后，客户可选择继续上述事务或退卡。选择退卡时，
8、系统弹出 ATM 卡，会话结束。 系统采用面向对象方法开发，使用 UML 进行建模。系统的顶层用例图如图 3-1 所示，一次会话的序列图（不考虑验证）如图 3-2 所示。消息名称参见表 3-1。 （分数：15.00）(1).【问题 1】（7 分） 根据【说明 】中的描述，给出图 3-1 中 A1 和 A2 所对应的参与者，U1 至 U3 所对应的用例，以及该图中空 1 所对应的关系。（U1 至 U3 的可选用例包括：Session、Transaction、Insert Card、Invalid PIN Process 和 Transfer） （分数：5.00）填空项 1:_(2).【问题 2】
9、（6 分 ） 根据【说明 】中的描述，使用表 3-1 中的英文名称，给出图 3-2 中 69对应的消息。 （分数：5.00）填空项 1:_(3).【问题 3】（2 分 ） 解释图 3-1 中用例 U3 和用例 Withdraw、Deposit 等四个用例之间的关系及其内涵。（分数：5.00）填空项 1:_试题四 （共 15 分 ） 阅读下列说明，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。 【说明】 现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。 现设计一
10、个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其它各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其它各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。 （分数：15.00）(1).【问题 1】（12 分） 本题采用 Floyd-Warshall 算法求解任意两个顶点之间的最短路径。 已知图 G 的顶点集合为 V= 1,2,.,n ，W= Wijn*n 为权重矩阵。设 d (k)ij=为从顶点 i 到顶点 j 的一条最短路径的权重。当 k = 0
11、时，不存在中间顶点，因此 d(0)ij=wij 当 k 0 时，该最短路径上所有的中间顶点均属于集合 1,2, ., k若中间顶点包括顶点 k ，则 d(k)ij=d(k-1)ik+d(k-1)kj 若中间顶点不包括顶点 k ，则 d(k-1)ij=d(k-1)ij 于是得到如下递归式。 （分数：7.50）填空项 1:_(2).【问题 2】（3 分） 【问题】中伪代码的时间复杂度为 1（用 符号表示）。 （分数：7.50）填空项 1:_1.试题五（共 15 分） 阅读下列说明和 C 函数代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍
12、历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数 InOrder()借助栈实现二叉树的非递归中序遍历运算。 设二叉树采用二叉链表存储，结点类型定义如下： typedef struct BtNode ElemType data; /*结点的数据域，ElemType 的具体定义省略*/ struct BtNode *lchild,*rchild; /*结点的左、右孩子指针域*/ BtNode, *BTree; 在函数 InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点 的单向链表（简称链栈），其结点类型定义如下： typedef struct StN
13、ode /*链栈的结点类型*/ BTree elem; /*栈中的元素是指向二叉链表结点的指针*/ struct StNode *link; StNode; 假设从栈顶到栈底的元素为 en、en-1、e1，则不含头结点的链栈示意图如图 5-1 所示。 （分数：15.00）填空项 1:_2.试题六（共 15 分） 阅读下列说明和 C+代码，将应填入 （n） 处的字句写在答题纸的对应栏内。【说明】 现欲实现一个图像浏览系统，要求该系统能够显示 BMP、JPEG 和 GIF 三种格式的文件，并且能够在 Windows 和 Linux 两种操作系统上运行。系统首先将 BMP、JPEG 和 GIF 三种
14、格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如下图所示。 （分数：15.00）填空项 1:_3.试题七 （共 15 分 ） 阅读下列说明和 Java 代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】 现欲实现一个图像浏览系统，要求该系统能够显示 BMP、JPEG 和 GIF 三种格式的文件，并且能够在 Windows 和 Linux 两种操作系统上运行。系统首先将 BMP、JPEG 和 GIF 三种格式的文件解析为像素矩阵，然后将
15、像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如图 7-1 所示。 （分数：15.00）填空项 1:_计算机水平考试中级软件设计师 2009 年上半年下午真题答案解析(总分：105.00，做题时间：150 分钟)试题一（共 15 分） 阅读下列说明，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。 【说明】 假设某大型商业企业由商品配送中心和连锁超市组成，其中商品配送中心包括采购、财务、配送等部门。为实现高效管理，设计了商品配送中心信息管理系统，其主要功能描述如下： 1.
16、系统接收由连锁超市提出的供货请求，并将其记录到供货请求记录文件。 2. 在接到供货请求后，从商品库存记录文件中进行商品库存信息查询。如果库存满足供货请求，则给配送处理发送配送通知；否则，向采购部门发出缺货通知。 3. 配送处理接到配送通知后，查询供货请求记录文件，更新商品库存记录文件，并向配送部门发送配送单，在配送货品的同时记录配送信息至商品配送记录文件。 4. 采购部门接到缺货通知后，与供货商洽谈，进行商品采购处理，合格商品入库，并记录采购清单至采购清单记录文件、向配送处理发出配送通知，同时通知财务部门给供货商支付货款。 该系统采用结构化方法进行开发，得到待修改的数据流图（如图 1-1 所示
17、）。 （分数：15.00）(1).【问题 1】（8 分） 使用【说明】中的词语，给出图 1-1 中外部实体 E1 至 E4 的名称和数据存储 D1 至 D4 的名称。 （分数：7.50）填空项 1:_ （正确答案： ）解析： (2).【问题 2】（7 分） 图 1-1 中存在四处错误数据流，请指出各自的起点和终点；若将上述四条错误数据流删除，为保证数据流图的正确性，应补充三条数据流，请给出所补充数据流的起点和终点。（起点和终点请采用数据流图 1-1 中的符号或名称） （分数：7.50）填空项 1:_ （正确答案： ）解析： 试题二（15 分 ） 阅读下列说明，回答问题 1 至问题 3，将解答填
18、入答题纸的对应栏内。 【说明 】 某集团公司拥有多个大型连锁商场，公司需要构建一个数据库系统以方便管理其业务运作活动。 【需求分析结果】 1. 商场需要记录的信息包括商场编号（编号唯一），商场名称，地址和联系电话。某商场信息如表 2-1 所示。 2. 每个商场包含有不同的部门，部门需要记录的信息包括部门编号（集团公司分配），部门名称，位置分布和联系电话。某商场的部门信息如下图所示。 3. 每个部门雇用多名员工处理日常事务，每名员工只能隶属于一个部门（新进员工在培训期不隶属于任何部门）。员工需要记录的信息包括员工编号（集团公司分配），姓名，岗位，电话号码和工资。员工信息如下图所示。 4. 每个部
19、门的员工中有一名是经理，每个经理只能管理一个部门，系统需要记录每个经理的任职时间。 【概念模型设计 】 根据需求阶段收集的信息，设计的实体联系图和关系模式（不完整）如下： （分数：15.00）(1).【问题 1】 （6 分 ） 根据问题描述，补充四个联系，完善图 2-1 的实体联系图。联系名可用联系 1、联系 2、联系 3 和联系 4 代替，联系的类型分为 1:1、1:n 和 m:n。 （分数：5.00）填空项 1:_ （正确答案： ）解析： (2).【问题 2】 （6 分） 根据实体联系图，将关系模式中的空（a）（c）补充完整，并分别给出部门、员工和经理关系模式的主键和外键。 （分数：5.0
20、0）填空项 1:_ （正确答案： ）解析： (3).【问题 3】 （3 分） 为了使商场有紧急事务时能联系到轮休的员工，要求每位员工必须且只能登记一位紧急联系人的姓名和联系电话，不同的员工可以登记相同的紧急联系人。则在图 2-1 中还需添加的实体是 1，该实体和图 2-1 中的员工存在 2 联系（填写联系类型）。给出该实体的关系模式。 （分数：5.00）填空项 1:_ （正确答案： ）解析： 试题三 （共 15 分） 阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。 【说明 】 某银行计划开发一个自动存提款机模拟系统（ATM System）。系统通过读卡器（CardRe
21、ader）读取 ATM 卡；系统与客户（Customer）的交互由客户控制台（CustomerConsole）实现；银行操作员（Operator）可控制系统的启动（System Startup）和停止（System Shutdown）；系统通过网络和银行系统（Bank）实现通信。 当读卡器判断用户已将 ATM 卡插入后，创建会话（Session）。会话开始后，读卡器进行读卡，并要求客户输入个人验证码（PIN）。系统将卡号和个人验证码信息送到银行系统进行验证。验证通过后，客户可从菜单选择如下事务（Transaction）： 1. 从 ATM 卡账户取款（Withdraw）； 2. 向 ATM 卡
22、账户存款（Deposit）； 3. 进行转账（Transfer）； 4. 查询（Inquire）ATM 卡账户信息。 一次会话可以包含多个事务，每个事务处理也会将卡号和个人验证码信息送到银行系统进行验证。若个人验证码错误，则转个人验证码错误处理（Invalid PIN Process）。每个事务完成后，客户可选择继续上述事务或退卡。选择退卡时，系统弹出 ATM 卡，会话结束。 系统采用面向对象方法开发，使用 UML 进行建模。系统的顶层用例图如图 3-1 所示，一次会话的序列图（不考虑验证）如图 3-2 所示。消息名称参见表 3-1。 （分数：15.00）(1).【问题 1】（7 分） 根据【
23、说明 】中的描述，给出图 3-1 中 A1 和 A2 所对应的参与者，U1 至 U3 所对应的用例，以及该图中空 1 所对应的关系。（U1 至 U3 的可选用例包括：Session、Transaction、Insert Card、Invalid PIN Process 和 Transfer） （分数：5.00）填空项 1:_ （正确答案： ）解析： (2).【问题 2】（6 分 ） 根据【说明 】中的描述，使用表 3-1 中的英文名称，给出图 3-2 中 69对应的消息。 （分数：5.00）填空项 1:_ （正确答案： ）解析： (3).【问题 3】（2 分 ） 解释图 3-1 中用例 U3
24、和用例 Withdraw、Deposit 等四个用例之间的关系及其内涵。（分数：5.00）填空项 1:_ （正确答案： ）解析： 试题四 （共 15 分 ） 阅读下列说明，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。 【说明】 现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。 现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其它各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径，即需要计算任意两个顶点之间
25、的最短路径；然后对每个顶点，计算其它各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。 （分数：15.00）(1).【问题 1】（12 分） 本题采用 Floyd-Warshall 算法求解任意两个顶点之间的最短路径。 已知图 G 的顶点集合为 V= 1,2,.,n ，W= Wijn*n 为权重矩阵。设 d (k)ij=为从顶点 i 到顶点 j 的一条最短路径的权重。当 k = 0 时，不存在中间顶点，因此 d(0)ij=wij 当 k 0 时，该最短路径上所有的中间顶点均属于集合 1,2, ., k若中间顶点包括顶点 k ，则 d(k)ij=d(k-1)
26、ik+d(k-1)kj 若中间顶点不包括顶点 k ，则 d(k-1)ij=d(k-1)ij 于是得到如下递归式。 （分数：7.50）填空项 1:_ （正确答案： ）解析：(2).【问题 2】（3 分） 【问题】中伪代码的时间复杂度为 1（用 符号表示）。 （分数：7.50）填空项 1:_ （正确答案： ）解析： 1.试题五（共 15 分） 阅读下列说明和 C 函数代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数 InOrder()借助栈实现二叉树的非递归中序遍历运算
27、。 设二叉树采用二叉链表存储，结点类型定义如下： typedef struct BtNode ElemType data; /*结点的数据域，ElemType 的具体定义省略*/ struct BtNode *lchild,*rchild; /*结点的左、右孩子指针域*/ BtNode, *BTree; 在函数 InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点 的单向链表（简称链栈），其结点类型定义如下： typedef struct StNode /*链栈的结点类型*/ BTree elem; /*栈中的元素是指向二叉链表结点的指针*/ struct StNode
28、 *link; StNode; 假设从栈顶到栈底的元素为 en、en-1、e1，则不含头结点的链栈示意图如图 5-1 所示。 （分数：15.00）填空项 1:_ （正确答案： ）解析： 2.试题六（共 15 分） 阅读下列说明和 C+代码，将应填入 （n） 处的字句写在答题纸的对应栏内。【说明】 现欲实现一个图像浏览系统，要求该系统能够显示 BMP、JPEG 和 GIF 三种格式的文件，并且能够在 Windows 和 Linux 两种操作系统上运行。系统首先将 BMP、JPEG 和 GIF 三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作
29、系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如下图所示。 （分数：15.00）填空项 1:_ （正确答案： ）解析：3.试题七 （共 15 分 ） 阅读下列说明和 Java 代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】 现欲实现一个图像浏览系统，要求该系统能够显示 BMP、JPEG 和 GIF 三种格式的文件，并且能够在 Windows 和 Linux 两种操作系统上运行。系统首先将 BMP、JPEG 和 GIF 三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如图 7-1 所示。 （分数：15.00）填空项 1:_ （正确答案： ）解析：
