[计算机类试卷]软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷43及答案与解析.doc

1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 43及答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 阅读以下某网上作业提交与管理系统的技术说明，根据要求回答问题 1问题3。 说明 某学校建立了一个网上作业提交与管理系统，基本功能描述如下。 (1)账号和密码。任课老师用账号和密码登录系统后，提交所有选修学生的名单。系统自动为每个选修学生创建登录系统的账号和密码。 (2)作业提交。选修学生使用账号和密码登录系统后，可以向系统申请所选课程的作业。系统首先检查 学生的当前状态，如果该选修学生还没有做过作业，则从数据库服务器申请一份作业。若申请成功，则显示需要完成的作业。学生

2、需在线完成作业，单击 提交 按钮上交作业。 (3)在线批阅。系统自动在线批改作业，显示作业成绩，并将该成绩记录在作业成绩统计文件中。 1 在系统的需求分析阶段，使用用例对系统需求建模。表 1-8和表 1-9分别给出了其中用例 “创建选修学生账号和密码 ”、用例 “作业申请 ”的概要描述。 请使用 说明 中的词汇，将表 1-8和表 1-9中的 (1) (10)空缺处的内容填写完整。 2 如果将数据库服 务器 (记为 DB)作为一个外部实体，那么在绘制该网上作业提交与管理系统的数据流图时，还应有哪些外部实体和数据存储 ? 3 该网上作业提交与管理系统的顶层数据流图中，相关数据流的部分信息如表 1-

3、10所示。请使用 说明 中的词汇，结合 问题 2的解答，将表 1-10中的 (11) (24)空缺处的内容填写完整。 4 阅读以下关于项目工作管理系统的数据库设计说明，根据要求回答问题 1问题4。 说明 某软件开发公司，决定结合自身工作的需求开发设计本公司的项目工作管理系统，由郭工程师承担数据库的设计工作。公司项目管 理的需求分析如下。 1组织机构。该公司有多个部门，每个部门有多个职员、多个办公室，每个办公室有一部电话。当部门变更时更换新的部门代码。职员辞职后，若再次被聘用仍使用辞职前的代码。被聘用职员担任某职务，职务用职务代码来标识。职务分为：工程师、高级工程师、经理助理、经理等。职员的工资

4、根据等级区分，共分为 S、A、 B、 C、 D 5个等级。一个职务对应某个等级，一个等级对应多个职务。职员月工资等于职员月工作时间 (小时 )乘以小时工资。职员的人事变动及职位变更 (升级、降级 )在月初进行。 2项目管理。项目用项目代码标识， 使用过的项目代码不能重复使用。一个部门可承担多个项目，但一个项目仅由一个部门承担。一个项目有一名项目主管和多个职员；一个职员可参加多个项目。项目代码由系统自动生成，一旦项目建立，项目名、部门代码及起始年月日不能再变更。 3项目的工作管理流程为：项目工作计划输入 (初始计划 ) 工作业绩输入 业绩生成 (每月一次 ) 计划修正 (每月一次 )。 项目工作

5、计划输入。项目主管使用如图 1-9所示的计划输入界面，输入项目代码、职员代码、职员参加某个项目的月工作时间 (计划 )。图中空白区域为可输入项。 工作业绩输入。输入职员 每天参加各个项目的工作时间。如图 1-10所示为工作业绩输入界面，图中空白区域为可输入项。其中，出勤时间由考勤系统管理，指定项目代码的顺序可以不同，并且一天可以输入多个项目代码，但同一个项目代码不能重复输入。 业绩生成。月底汇总职员的当月工作业绩，生成月工作业绩表。 计划修正。项目主管根据项目进度修改以后的工作计划。 郭工程师根据公司的项目需求将数据库关系模式设计如下： 部门 (部门代码，部门名，起始年月，终止年月，办公室，办

6、公电话 )； 职务 (职务代码，职务名 )； 等级 (等级代码，等级名，年月，小时工资 )； 职员 (职员代码，职员名，部门代码，职务代码，任职时间 )； 项目 (项目代码，项目名，部门代码，起始年月日，结束年月日，项目主管 )； 工作计划 (项目代码，职员代码，年月，工作时间 )。 4 请使用 “关系模式标记规则 ”(见本题附内容，全书同 )，给出 “部门 ”、 “等级 ”、 “项目 ”和 “工作计划 ”关系模式的主键和外键。 5 请将以下关系模式中的 (1)和 (2)空缺处填入属性名称 (要求使用题干说明中已有的属性名称 )。 (1)郭工程师设计的关系模式不能管理职务和等级之间的关系，可以

7、通过修改 “职务 ”关系模式来实现 。修改后的关系模式为： 职务 (1) (2)为了管理公司职员参加各项目每天的工作业绩，需设计工作业绩关系模式为： 工作业绩 (2) 6 郭工程师设计的 “部门 ”关系模式中存在什么问题 ?请用 100字以内的文字简要说明理由。为了解决这个问题可将关系模式分解，请给出分解后的关系模式 (分解后的关系模式的关系名可依次取 “部门 _A”、 “部门 _B”、 ) 。 7 假定月工作业绩关系模式为：月工作业绩 (职员代码，年月，工作时间 )，请将以下 “查询职员代码、职员名、年月、月工资 ”SQL语句中 (3) (5)空缺处的内容填写完整。 SELECT (3) F

8、ROM (4) WHERE (5) 附 关系模式的标记规则如下： 关系名 (属性名 1，属性名 2， ，属性名 n) 其中： 若该属性仅为主键属性时，则该属性名下画实下画线； 若该属性仅为外键属性时，则该属性名下画虚下画线； 若该属性既是主键属性，又是外键属性时，则在该属性名下画实下画线和虚下画线； 若该属性既不是主键属性，又不是外键属性时，则在该属性名下不做标记。 8 阅读以下某前台销售子系统的技术说明和 UML图，根据要求回答问题 1问题4。 说明 某超市管理系统的前台销售子系统以最基本的方式处理销售业务。系统的功能需求如下： 记录每种商品的编号、单价和现有数量； 为顾客选购的商品计价、收

9、费，并打印清单； 帮助商家找出哪种商品将脱销，从而及时补充货源； 随时按上级系统的要求报告当前的款货数量、增减商品的种类或修改商品定价； 交接班时结算货款数目和商品数目。 每台收款机可以处理任何数目的销售事件，但一个销 售事件只能由一台收款机处理。每个销售事件从收款机响应收款人员的指令开始，先向商品发送检索请求消息来查找将被出售的商品。如果该商品的数量少于下限，则向供货员发送缺货登记消息。每名供货员可以提供一种或多种商品，同一品牌的商品只能由一位供货员来提供。接着收款机发送计价和入账消息请求售出操作，再由销售事件发送记账消息给相应的账册，并控制流程返回收款机等待下一次销售操作。每本销售账册可以

10、记录任何数目的销售事件，但一个销售事件只能由一本销售账册记录。 该销售子系统采用面向对象方法开发，系统中的类及类之间的关系用 UML类图表示，图 1-11是该系统类图中的一部分；系统的动态行为采用 UML序列图表示，图 1-12是销售事件部分的序列图。 8 根据题干的 说明 及图 1-11、图 1-12的相关信息，类商品除了售出和缺货登记操作之外，还应具有哪些主要操作 ? (请使用 说明 中给出的词语回答问题 ) 9 请将图 1-11中类商品、类特价商品和类计量商品 3者之间的联系补充完整。 10 识别关联的多重度是面向对象建模过程中的一个重要步骤。请根据说明中给出的描述，将图 1-11中 (

11、1) (8)空缺处的内容填写完整。 11 请 使用 说明 中给出的词语，将销售事件序列图中的 (A) (D)空缺处的内容填写完整。 12 阅读以下算法说明和问题模型图，根据要求回答问题 1、问题 2。 说明 某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点 AP(Access Poin)。假设每个无线 AP覆盖范围的半径是 6米，因此必须使得每台笔记本电脑上的无线网卡到某个无线 AP的直线距离不超过 6米。为了简化问题，假设所有无线网卡在同一直线上，并且无线 AP沿该直线放置。该问题可以建模为如图 1-13所示，其中直线表示无线网卡所在的直线，实心正方形表 示无线网卡。现采用贪心策略实

12、现用尽可能少的无线 AP覆盖所有的无线网卡。 实现贪心算法的流程如图 1-14所示。其中， di(1iN)表示第 i张无线网卡到通道A端的距离， N表示无线网卡的总数，无线网卡的编号按照无线网卡到通道 A端的距离从小到大进行编号： sk表示第 k(k1)个无线 AP到通道 A端的距离。算法结束后 k的值为无线 AP的总数。12 请填补图 1-14流程图中 (1) (4)空缺处的内容。 13 该贪心算法的时间复杂度为 (5)。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 14 阅读以下说明和 C函数，

13、将 (1) (5)空缺处的字句填写完整。 说明 计算机在处理算术表达式时，首先将其转换为后缀表达式。例如，表达式 “46+5*120-37)”的后缀表达式形式为 “46 5 120 37-*+”。 计算后缀表达式时，从左至右扫描后缀表达式：若遇到运算对象，则压入栈中；遇到运算符，则从栈中弹出相关运算对象进行计算，并将运算结果压入栈中。重复以上过程，直到后缀表达式扫描结束。例如，后缀表达式 “46 5 120 37-*+”的计算过程如下： a依次将 46、 5、 120、 37压入栈中； b遇到 “-”，取出 37、 120，计算 120-37=83，将其压入栈中； c遇到 “*”，取出 83、

14、 5，计算 583=415，将其压入栈中； d遇到 “+”，取出 415、 46，计算46+415=461，将其压入栈中； e表达式结束，则计算过程完成。 函数computing(char expr,int*result)的功能是基于栈计算后缀形式的表达式 (以串形式存入字符数组 expr)的值，并通过参数 result返回该值。函数的 返回值为 -1/0，分别表示表达式有 /无错误。假设表达式中仅包含数字、空格和算术运算符号，其中所有项均以空格分隔，且运算符仅包含加 (“+”)、减 (“-”)、乘 (“*”)、除 (“ ”)。 函数computing中所用栈的基本操作的函数原型说明如下。 v

15、oid InitStack(STACK*s)：初始化栈。 void Push(STACK*s,int e)：将一个整数压栈，栈中元素数目增 1。 void Pop(STACK*s)：栈顶元素出栈，栈中元素数目减 1。 int Top(STACK s)： 返回非空栈的栈顶元素值，栈中元素数目不变。 int IsEmpty(STACKs)：若 s是空栈，则返回 1；否则返回 0。 C函数 15 请认真阅读以下关于某传输系统的技术说明、状态转换图及 C+代码，根据要求回答问题 1问题 2。 说明 传输门是传输系统中的重要装置。传输门具有Open(打开 )、 Closed(关闭 )、 Opening(

16、正在打开 )、 StayOpen(保持打开 )和 Closing(正在关闭 )5种状态。触发状态的转换事件有 click、 complete和 timeout3种。事件与其相应的 状态转换如图 7-15所示。 下面的 C+代码 1与 C+代码 2分别用两种不同的设计思路对传输门进行状态模拟，请填补代码段中的空缺语句。 C+代码 1 15 请将以上 C+代码 1与 C+代码 2程序段中的 (1) (7)空缺处的语句填写完整。 16 请用 150字以内的文字简要说明 C+代码 1、 C+代码 2这两种对传输门进行状态模拟的设计思路的区别之处。 17 请仔细阅读以下关于某传输系统的技术说明、状态转换

17、图及 Java程序，根据要求回答问题 1问题 2。 说明 传输门是 传输系统中的重要装置。传输门具有Open(打开 )、 Closed(关闭 )、 Opening(正在打开 )、 StayOpen(保持打开 )和 Closing(正在关闭 )5种状态。触发状态的转换事件有 click、 complete和 timeout3种。事件与其相应的状态转换如图 7-16所示。 下面的 Java代码 1与 Java代码 2分别用两种不同的设计思路对传输门进行状态模拟，请填补代码段中的空缺语句。 Java代码117 请将以上 Java代码 1与 Java代码 2程序段中， (1) (7)空缺处的语 句填写

18、完整。 18 请用 150字以内的文字简要说明 Java代码 1、 Java代码 2这两种对传输门进行状态模拟的设计思路的区别之处。 软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 43答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 这是一道要求读者掌握用例获取方法的综合分析题。本题的解答思路如下。 由题干中给出的关键信息 “账号和密码：任课老师用账号和密码登录系统后，提交所有选修学生的名单。系统自动为每个选修学生创建登录系统的账号和密码 ”，并结合表 1-8中给 出的信息可知，用例 “创建选修学生账号和密码 ”是在任课老师登录系统并提交选修学生名单之后

19、触发产生的，因此该用例的触发器是 “提交选修学生名单 ”。在该用例中输入角色 (Actor)主要是 “任课老师 ”，输入信息有 “账号和密码 ”和 “所有选修学生名单 ”，而输出角色 “任课老师 ”将接收 “登录成功或失败通知 ”等系统输出信息，输出角色 “每个选修学生 ”将接收到 “登录账号和密码 ”和 “登录账号和密码激活通知 ”等输出信息。完整的 “创建选修学生账号和密码 ”用例描述表如表 1-12所示。 同理，由题干中关键信息 “作业提交：学生使用账号和密码 登录系统后，可以向系统申请所选课程的作业。系统首先检查学生的当前状态，如果该学生还没有做过作业，则从数据库服务器申请一份作业。若

20、申请成功，则显示需要完成的作业 ”，并结合表 1-9中给出的信息可知，用例 “作业申请 ”是在选修学生向系统提交 “申请作业请求 ”时触发产生的，因此该用例的触发器是 “申请作业请求 ”。该用例的主要输入角色是 “选修学生 ”，其输入信息有 “账号和密码 ”和 “申请所选课程的作业 ”。 在用例 “作业申请 ”中输出角色有两个，即 “选修学生 ”和 “数据库服务器 ”。其中，“选修学生 ”角色将接收系统输出的 “登录成功或 失败通知 ”、 “当前状态信息 ”、 “(作业 )申请成功或失败通知 ”及 “需要完成的作业 ”等信息。 “数据库服务器 ”角色将接收到系统输出的 “申请一份作业 ”信息。

21、 将以上分析结果进行整理，完整的用例 “作业申请 ”描述表如表 1-13所示。 2 【正确答案】 这是一道要求读者掌握数据流图中外部实体识别的综合分析题。本题的解答思路如下。 外部实体是指存在于软件系统之外的人员或组织。它指出系统所需数据的来源地 (即信源 )和系统所输出数据的归宿地 (即信宿 )。 根据 说明 中提供的信息，并结合 问题 1的分析过 程可知， “选修学生 ”和 “任课老师 ”向 “网上作业提交与管理系统 ”提供了最原始的输入数据，并从系统中获取相应的输出数据。因此可以确定 “选修学生 ”、 “任课老师 ”是数据流图中除数据库服务器 (记为 DB)之外的两个外部实体。 数据存储

22、用来表示暂时保存数据的地方，每个数据存储都有一个名字。由题干给出的关键信息 “在线批阅：系统自动在线批改作业，显示作业成绩，并将该成绩记录在作业成绩统计文件中 ”可知， “作业成绩统计文件 ”是一个数据存储。 3 【正确答案】 这是一道要求读者掌握数据流图中数据流识别的综合分析题。本题的 解答思路如下。 根据 说明 中提供的信息，并结合 问题 1、 问题 2的分析过程可知，外部实体 “选修学生 ”和 “任课老师 ”各自向 “网上作业提交与管理系统 ”提交登录的 “账号和密码 ”，因此 (11)、 (12)空缺处所填写的数据流起点分别是 “选修学生 ”和 “任课老师 ”。 由于 “任课老师 ”登

23、录 “网上作业提交与管理系统 ”后向系统提交的数据流是 “所有选修学生名单 ”，因此 (13)空缺处所填写的数据流名称是 “所有选修学生名单 ”。 由于数据流 “作业申请 ”是由 “选修学生 ”登录系统后向该系统提交的，因此 (14)空缺处所填写的数据 流起点是 “选修学生 ”。 由题干中关键信息 “如果该学生还没有做过作业，则从数据库服务器申请一份作业 ”可知，由 “网上作业提交与管理系统 ”产生的数据流 “作业申请 ”将送往外部实体 “数据库服务器 ”，因此 (15)空缺处所填写的数据流终点是 “数据库服务器 ”。 由题干中关键信息 “若申请成功，则显示需要完成的作业 ”可知，由 “网上作

24、业提交与管理系统 ”产生的数据流 “需完成的作业 ”将送给外部实体 “选修学生 ”，因此 (18)空缺处所填写的数据流终点是“选修学生 ”。 由题干中关键信息 “学生需在线完成作业，单击 提交 按钮上交作业 ”可知，数据流 “提交的作业 ”是由 “选修学生 ”在线完成后向 “网上作业提交与管理系统 ”提交的，因此 (19)空缺处所填写的数据流起点是 “选修学生 ”， (20)空缺处所填写的数据流终点是 “网上作业提交与管理系统 ”。 由题干中关键信息 “在线批阅 并将该成绩记录在作业成绩统计文件中 ”可知，由 “网上作业提交与管理系统 ”产生的数据流 “作业成绩 ”也将送往数据存储 “作业成绩

25、统计文件 ”，因此 (23)空缺处所填写的数据流名称是 “作业成绩 ”， (24)空缺处所填写的数据流起点是 “网上作业提交与管理系统 ”。 由题干中关键信息 “在线批阅 ：系统自动在线批改作业，显示作业成绩 ” 可知，数据流 “作业成绩 ”是由 “网上作业提交与管理系统 ”向外部实体 “选修学生 ”提供的，而非 “任课老师 ”向 “选修学生 ”提供 “作业成绩 ”，因此 (21)空缺处所填写的数据流起点是 “网上作业提交与管理系统 ”， (22)空缺处所填写的数据流终点是 “选修学生 ”。 由题干中关键信息 “如果该学生还没有做过作业，则从数据库服务器申请一份作业。若申请成功，则显示需要完成

26、的作业 ”间接可知，外部实体 “数据库服务器 ”将产生一条数据流 “所申请的作业 ”送至 “网上作业提交与管理系统 ”，因此 (16)空 缺处所填写的数据流名称是 “所申请的作业 ”， (17)空缺处所填写的数据流起点是 “数据库服务器 ”。 将以上分析结果进行整理，完整的顶层数据流图中数据流描述信息如表 1-14所示。4 【正确答案】 这是一道要求读者根据题目给定的关系模式，以及属性间的函数依赖关系和给定的关系实例，并结合 E-R图向关系模式的转换方法来确定各关系模式主键和外键的综合分析题。本试题的解答思路如下。 设 K为 R(U,F)中的属性的组合，若 KU ，且对于 K的任何一个真子集

27、K，都有 K不能决定 U，则 K为R的候选码 (候选关键字 )，若有 多个候选码，则选一个作为主码 (主键 )。 部门关系模式的主键和外键。 由题干中给出的关键信息 “该公司有多个部门，每个部门有多个职员、多个办公室 ”可知，部门代码多值决定办公室，如果仅用 (部门代码 )作为主键，则无法唯一区分 部门关系中的每一个元组 (记录 )。如果用 (部门代码，办公室 )作为主键，则可以唯一区分部门关系中的每一个元组，因此，部门关系模式的主键如下。 部门 (部门代码，部门名，起始年月，终止年月，办公室，办公电话 ) 等级关系模式的主键和外键。 由题干中给出的关键信息 “一个职务对应某个等级，一个等级对

28、应多个职务 ”， “职员月工资等于职员月工作时间 (小时 )乘以小时工资 ”， “职员的人事变动及职位变更 (升级、降级 )在月初进行 ”可知，如果仅用 “等级代码 ”作为主键，则无法唯一区分等级关系中的每一个元组，这是因为对于同一个等级在不同的 时期小时工资值不一定一样。例如，等级 1在 2007年 6月小时工资为 10元，可能到 2007年 10月小时工资为 15元。可见用 (等级代码，年月 )作为主键，可以唯一区分等级关系中的每一个元组。因此等级关系模式的主键如下。 等级 (等级代码，等级名，年月，小时工资 ) 项目关系模式的主键和外键。 由题干中给出的关键信息 “项目用项目代码标识，使

29、用过的项目代码不能重复使用 ”可知，项目代码可以决定项目关系中的全属性，因此，项目关系模式的主键是 “项目代码 ”。在项目关系模式中，由于部门代码是部门关系的主键，因此 “部门代码 ”应为项目 关系模式的外键。同时考虑到项目主管应该来自职员，所以 “项目主管 ”也是项目关系模式的外键。最后可得项目关系模式的主键、外键如下。 项目 (项目代码，项目名， ，起始年月日，结束年月日， ) 工作计划关系模式的主键和外键。 由题干中给出的关键信息 “一个项目有一名项目主管和多个职员；一个职员可参加多个项目 ”， “项目代码由系统自动生成，一旦项目建立，项目名、部门代码及起始年月日不能再变更 ”可知，在工

30、作计划关系中，由于一个项目有多个职员参加，因此仅用 “项目代码 ”作为主键，则无法唯一确定关系中的每一个元组。又由于工作计 划是按月给职员安排的，因此工作计划关系的主键是 (项目代码，职员代码，年月 )。最后可得工作计划关系模式的主键、外键如下。 工作计划 (项目带代码，职员带代码，年月，工作时间 ) 5 【正确答案】 郭工程师所设计的关系模式不能管理职务和等级之间的关系，为此可以在 “职务 ”关系模式中增加属性 “等级代码 ”来实现，修改后的关系模式如下。 职务 (职务代码，职务名，等级代码 ) 为了管理公司职员参加各项目每天的工作业绩，需设计工作业绩的关系模式。根据图 1-10所给出的工作

31、业绩输入界面实例分析，可得工作业绩关系模式 如下。 工作业绩 (项目代码，职员代码，年月日，工作时间 ) 6 【正确答案】 郭工程师设计的 “部门 ”关系模式中存在的主要问题是数据冗余，因为部门关系模式属于 2范式 (或 2NF)。 “部门 ”关系模式的基本函数依赖集 F1为： F1=部门代码 ( 部门名，起始年月，终止年月 )，部门代码 办公室，办公室 办公电话 ) 例如，假设某个部门有 10个办公室，部门代码、部门名、起始年月、终止年月就要被重复 10次。为了解决这个问题可将关系模式分解，分解后的关系模式如下。 部门 _A(部门代码，部门名，起始 年月，终止年月 ) 部门 _B(部门代码，

32、办公室，办公电话 ) 7 【正确答案】 假定月工作业绩关系模式为：月工作业绩 (职员代码，年月，工作时间 )，那么 “查询职员代码、职员名、年月、月工资 ”的 SQL语句如下。8 【正确答案】 由题干给出的关键信息 “ 记录每种商品的编号、单价和现有数量 ”和 “如果该商品的数量少于下限，则向供货员发送缺货登记消息 ”可知，类商品有 5个属性，即编号、名称、单价、数量和下限。 由题干中关键信息 “ 帮助商家找出哪种商品将脱销，从而及时补充货源 ”、 “接着收款机发送计价和入账 消息请求售出操作 ” 和 “ 先向商品发送检索请求消息来查找将被出售的商品 ” 可知，类商品有 3个操作，即检索、补充

33、和售出。 由题干中关键信息 “ 随时按上级系统的要求报告当前的款货数量、增减商品的种类或修改商品定价 ”可知，类商品还具有两个操作，即种类增删和价格更新。 9 【正确答案】 在 UML类图中， “ ”表示其相连的两个类之间存在泛化 (generalization)关系。这种关系描述了一般事物与该事物中特殊种类之间的关系，子用例是父用例的一种特殊形式，子用例继承了父用例所有的结构、行为和关系，还 可以增加或者覆盖父用例的行为。子用例可以出现在父用例出现的任何位置。 在图 1-11类图中，类特价商品和类计量商品是类商品的子类，它们将继承类商品的所有属性和操作，并且又有自己特殊的属性和操作。因此这

34、3者之间的联系是泛化关系，如图 1-20所示。 10 【正确答案】 由题干描述中给出的关键信息 “每台收款机可以处理任何数目的销售事件 ” 和常识可知，每个超市有多台收款机，每个销售事件可能与 1种或多种商品发生联系，商品可以到任何一台收款机付款，因此收款机与商品之间存在多对多 (m:n)的关系，即 (1)、 (2)空缺 处所填写的内容均是 “1*” 。 由题干中关键信息“每名供货员可以提供一种或多种商品，同一品牌的商品只能由一位供货员来提供 ”可知，商品与供货员之间存在多对一 (m:1)的关系，因此 (3)空缺处所填写的内容是“1*” ， (4)空缺处所填写的内容是 “1”。 由题干中关键信

35、息 “每台收款机可以处理任何数目的销售事件，但一个销售事件只能由一台收款机处理 ”可知，收款机与销售事件之间存在一对多 (1:n)的关系，因此 (5)空缺处所填写的内容是 “1”， (6)空缺处所填写的内容是 “1*” 。 由题干中关键信息 “每本销售账册可以记录 任何数目的销售事件，但一个销售事件只能由一本销售账册记录 ”可知，账册与销售事件之间存在一对多 (1:n)的关系，因此 (7)空缺处所填写的内容是 “1”， (8)空缺处所填写的内容是 “1*” 。 较完整的前台销售子系统类图如图 1-21所示。11 【正确答案】 由题干中给出的关键信息 “每个销售事件从收款机响应收款人员的指令开始

36、，先向商品发送检索请求消息来查找将被出售的商品 ” 可知，收款机将向商品对象发送 “检索 ”这一触发消息，因此 (A)空缺处所填写的内容是 “检索 ”。 由题干中关键信息 “接着收款机发送计 价和入账消息请求售出操作，再由销售事件发送记账消息给相应的账册 ” 可知，收款机将向销售事件发送 “计价 ”、 “入账 ”触发消息，其中， “入账 ”消息将被销售事件转变为 “记账 ”消息送给账册对象，因此 (B)空缺处所填写的内容是 “计价 ”， (C)空缺处所填写的内容是 “记账 ”。 由题干中关键信息 “再由销售事件发送记账消息给相应的账册，并控制流程返回收款机等待下一次销售操作 ”可知，记账操作完

37、成时即可表示本次销售事件入账操作结束，账册对象将发送 “入账 ”结束消息给收款机，以触发收款机等待下一次销售操作，因此 (D)空缺处所填 写的内容是 “入账 ”。 12 【正确答案】 本试题的题干说明中已将无线网卡分布问题建模 (如图 1-13所示 )。其中，直线表示无线网卡所在的直线，实心正方形表示无线网卡。而要求解的问题是要求如何在该直线上布局无线 AP，使其能覆盖所有的无线网卡，并且所用无线 AP的数量要尽可能的少。这是一个通过进行一系列选择求最优解的问题。 分析该问题，发现其具有最优子结构，并且具有贪心选择性质，故该问题可以用贪心算法来求解。贪心算法思想是：问题的规模为 N，从第 1个

38、无线网卡 (最左端 )开始布局无线 AP，把第 1个无线 AP放置在该无线网 卡右方的 6米处，此时该无线AP会覆盖从第 1个无线网卡到该无线网卡右方直线长度为 12米的所有无线网卡，假设覆盖了 N1个无线网卡。此时问题规模变成了 N-N1，接着把第 1个无线 AP覆盖的无线网卡去掉，再从 N-N1中选择第 1个 (最左端 )无线网卡开始布局无线 AP，将第 2个无线 AP放置在该无线网卡右方的 6米处。依此布局，直到覆盖所有的无线网卡。 图 1-22是问题解的模型。其中，直线表示无线网卡所在的直线，实心正方形表示无线网卡，实心圆形表示无线 AP，虚线圆以对应无线 AP为圆心，直径为无线 AP

39、的覆盖范围，即对应无线 AP的 覆盖范围 (12米 )。 实现贪心算法的流程见题干的图 1-14。由于 “算法结束后 k的值为无线 AP的总数 ”，因此在算法开始处需要对变量 k赋初值，即 (1)空缺处所填写的内容是 “k=0”。 该贪心算法中， N表示无线网卡的总数，且无线网卡的编号按照无线网卡到通道 A端的距离从小到大进行编号， di(1iN)表示第 i个无线网卡到通道 A端的距离。当判断第 i个无线网卡未超过无线网卡总数 N，而求解下一个无线网卡 (即第 i+1个无线网卡，或第 j个无线网卡 )所归属的无线 AP时，也需要判断第 j个无线网卡是否超过无线网卡总数 N，以 及第 j个无线网

40、卡与第 i个无线网卡之间的距离是否超过 12米，因此 (2)空缺处所在的判断条件是 “j =N dj-di =12”，即该空缺处所填写的内容是 “j =N”或其等价形式。 若第 j个无线网卡未超过无线网卡总数 N，且第 j个无线网卡与第 i个无线网卡之间的距离未超过 12米，则可以求解再下一个无线网卡 (即第 i+2个无线网卡，或第 j+1个无线网卡 )所归属的无线 AP。反之，则需要记录无线 AP的总数 k，即 (3)空缺处所填写的内容是 “k=k+1”或其等价形式；以及记录第 k(k1)个无线 AP到通道 A端的距离，即 (4)空缺处所填写的内容是 “di+6”或其等价形式。 当求解完第

41、k个无线AP(覆盖了 N1个无线网卡 )的布局后，需要把第 k个无线 AP覆盖的无线网卡去掉，再从 N-N1中选择第 1个 (最左端 )无线网卡开始布局第 k+1个无线 AP。依此不断求解，直到覆盖所有的无线网卡。 13 【正确答案】 虽然该贪心算法中包含两个循环，但实际上只是遍历所有无线网卡一次，因此算法复杂度是 O(N)。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 14 【正确答案】 是一道考查栈结构在后缀表达式求值过程中应用的分析题。利用栈计算后缀表达式时，从左至右扫描后缀表达式：若遇到运算

42、对象，则压入栈中；遇到运算符，则从栈中弹出对应数目的运算对象进行计算，并将运算结果压入栈中。重复以上过程，直到后缀表达式扫描结束，最后栈顶就是表达式的计算结果。 根据题干中的说明，由于后缀表达式以字符串方式存储且以空格分隔符号 (数值、算符 )，因此遇到空格字符时，指向表达式中字符的指针 ptr应增加 1指向后续字符，因此， (1)空缺处应填入 “ptr+”或其等价形式。下面以字符串 “375”为例说明将一个数字串转换为数值的过程。 数值 375=(010+3)10+7)10+5 (1)取得数字字符“3”(ASCII码值为 51，字符 0的 ASCII码值为 48)。 (2)取得数字字符 “7

43、” (ASCII码值为 55)。 (3)取得数字字符 “5” (ASCII码值为 53)。 以下程序代码用于将一个数字字符串转换为对应的整数存入 tnum，显然， tnum的初始值应为 0。 因此， (2)空缺处应填入 “0”。对于 (3)空缺所在表达式的功能是：将数字字符转换为数值，因此 (3)空缺处填入 “*ptr-48”。 (4)空缺处用于将转换所得的数值 tnum压入栈顶，根据题目中 Push的原型“void Push(STACK*s， int e)”，调用时第一个实际参数是 STACK类型变量的地址，第二个实际参数是一个整数，因此， (4)空缺处填入 “ s,tnum”。 由于函数c

44、omputing(char expr,int*result)通过参数 result 返回该表达式的值，因此需要将存在栈顶的运算结果赋值给 result指向的整型变量，即 (5)空缺处填入 “*result”。 本试题目还考查了参数传递知识，读者可通过上 机实践加强基本概念的理解，以及 C程序设计能力的培养。 15 【正确答案】 这是一道要求读者掌握状态转换图的程序设计与实现的综合题。本试题的解答思路如下。 根据 (1)空缺处所在的程序段给出的注释信息 “发生 crick事件时进行状态转换 ”可知， (1)空缺处所在的方法为 click，表示当发生 crick事件时应该发生什么状态转换。找出传输

45、门响应事件与其状态转换图 (见图 7-15)与 crick事件相关的内容，并特别注意箭头所指的方向。由于发生 click事件前的状态 CLOSED、 CLOSING分别跳转到状态 OPENING，因此 (1)空缺处所填写的内容是“state=CLOSEDstate=CLOSING”。 同理，由图 7-15所示中的状态转换关系可知，发生 click事件前的状态OPENING、 STAYOPEN分别跳转到状态 CLOSING，即 (2)空缺处所填写的内容是“state=OPENINGstate=STAYOPEN”；发生 click事件前的状态 OPEN跳转到状态 STAYOPEN，即 (3)空缺处

46、所填写的内容是 “state=OPEN”。 仔细阅读 C+代码 2程序段，由语句 private DoorState state=CLOSED；可知，类Door的 state成员变量用于记录类 Door所处的状态，而 state变量的类型为Doorstate*。由语句 “virtual void click() ”、 “virtual void complete() ”和 “virtual void timeout() ”可知， Doorstate中分别具有 click、 timeout和 complete方法用来响应对应的事件。根据 (4)空缺处所在程序段 “void Door click(

47、)”可得， (4)空缺处所填写的内容是 “state- click()”。 同理，根据 (5)空缺处所在程序段 “void Door timeout()”可得， (5)空缺处所填写的内容是 “state- timeout()”；根据 (6)空缺处所在程序段 “void Door complete()”可得， (6)空缺处所填写的内容是 “state- complete()”。 根据 (7)空缺处所在程序段给出的注释信息 “定义一个基本的 Closed状态 ”和语句“void DoorClosed click()”可知， (7)空缺处所填写 的内容与传输门当前状态为CLOSED且发生 Click

48、事件时状态的迁移有关。结合如图 7-16所示中的状态转换关系可知，在 Click事件下 CLOSED状态将迁移到 OPENING，因此 (7)空缺处应该将传输门的状态设置为 OPENING。由于 Doorstate变量存储了当前其存储的传输门的实例，因此可直接调用其方法 setState设置状态。同时考虑到传输门的状态采用类的实例变量表示，故 (7)空缺处所填写的内容为 “door- setState(door-OPENING)”。 16 【正确答案】 C+代码 1和 C+代码 2区别是， C+代码 2将状态间的转换规则封装到具体的类中，当状态转换图的转换规则发生变化时，只需更改部分对应类中的状态迁移规则，易于维护、移植。由于 C+代码 1中的迁移规则散落在程序中，因此维护起来较为困难。 17 【正确答案】 这是一道要求读者掌握状态转换图的程序设计与实现的综合题。本试题的解答思路如下。 根据 (1)空缺处所在的程序段给出的注释信息 “发生 click事件时进行状态转换 ”可知， (1)空缺处所在的方法为 click，表示当发生 click事件时应该发生什么状态转换 。找出传输门响应事件与其状态转换图 (见图 7-16)与 click事件相关的内容，并特别注意箭头所指的方向。由于发生 click事件前的状态 CLOSED、 CLOSING分别跳转到状态 OPENI