1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 37及答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 阅读以下某图书管理系统的技术说明和数据流图，根据要求回答问题 1问题4。 说明 某图书管理系统的主要功能是图书管理和信息查询。对于初次借书的读者，系统自动生成读者号，并与读者基本信息 (姓名、单位和地址等 )一起写入读者文件。 该系统的图书管理功能主要分为购入新书、读者借书、读者还书及图书注销 4个方面。 (1)购入新书时需要为该书编制入库单。入库单内容包括图书分类目录号、书名、作者、 价格、数量和购书日期，将这些信息写入图书目录文件并修改文件中的库存总量 (表示到目
2、前为止，购入此种图书的数量 )。 (2)读者借书时需填写借书单。借书单内容包括读者号和所借图书分类目录号。系统首先检查该读者号是否有效，若无效，则拒绝借书；若有效，则进一步检查该读者已借图书是否超过最大限制数 (假设每位读者能同时借阅的书不超过 10本 )，若已达到最大限制数，则拒绝借书；否则允许借书，同时将图书分类目录号、读者号和借阅日期等信息写入借书文件中。 (3)读者还书时需填写还书单。系统根据读者号和图书分类目录号，从借书文件中 读出与该图书相关的借阅记录，标明还书日期，再写回到借书文件中，若图书逾期，则处以相应的罚款。 (4)注销图书时，需填写注销单并修改图书目录文件中的库存总量。
3、系统的信息查询功能主要包括读者信息查询和图书信息查询。其中，读者信息查询可得到读者的基本信息及读者借阅图书的情况；图书信息查询可得到图书基本信息和图书的借出情况。 该图书管理系统的顶层数据流图，如图 2-21所示；该图书管理系统的第 0层 DFD图，如图 2-22所示；其中加工2的细化图，如图 2-23所示。 1 请用 100字以内的文字简要说明逻辑数据流 图 (Logical Data Flow Diagram)和物理数据流图 (Physical Data Flow Diagram)之间的主要差别。 2 该图书管理系统的第 0层 DFD图 (见图 2-22)有两条数据流是错误的，请指出改正后
4、这两条数据流的起点、终点和数据流名称。 3 加工 2的细化图 (见图 2-23)中缺少 3条数据流，请指出这 3条数据流的起点、终点和数据流名称。 4 请根据系统功能描述数据流图，并使用 说明 中的词汇，将以下数据字典条目中(1) (5)空缺处的内容填写完整。 查询请求信息 =查询读者请求信息 |查询图书请求信息 读者情况 =读者号 +姓名 +所在单位 +借书情况 管理工作请求单 =(1) 入库单 =(2) 借书单： (3) 还书单 =(4) 非法请求信息 =(5) 5 阅读以下某人才信息交流网数据库设计的技术说明和图，根据要求回答问题 1问题 5。 说明 某市人才交流中心为促进当地人力资源的
5、合理配置，加强当地企业与人才的沟通，拟建立人才信息交流网。 需求分析结果 1每个前来登记的个人需填写人才入库登记表，如表 2-17所示 ，并出示相关证件，经工作人员审核后录入个人信息。2每个前来登记的企业需填写企业信息登记表，如表 2-18所示，并出示相关证明及复印件，经工作人员核实后录入企业信息。 3个人和企业的基本信息只需在第一次登记时填写，个人编号和企业编号由系统自动生成。个人和企业的基本信息由计算机长期存储，以后个人只需提供个人编号和求职意向信息，企业只需提供企业编号和岗位需求信息。 4个人的求职意向信息和企业的岗位需求信息在两个工作日内由工作人员录入数据库并发布。 概念模型设计 根据
6、需求阶段收集的信息，设 计人才、岗位和企业的实体联系图如图 2-24所示 (不完整 )。逻辑结构设计 1将概念模型设计的实体联系图转换为以下关系模式 人才 (个人编号，姓名，性别，出生日期，身份证号，毕业院校，专业，学历，证书名称，证书编号，联系电话，电子邮件，个人简历及特长 ) 企业 (企业编号，企业名称，联系人，联系电话，地址，企业网址，电子邮件，企业简介 ) 求职意向 ( (2) ) 岗位需求( (3) ) 2由于一个人可能持有多个证书，因此对 “人才 ”关系模式进行优化，得到如下两个新的关系模式 人才 ( (4) ) 证书 ( (5) ) 根据上述的设计过程，回答以下问题。 5 在 (
7、1)空缺处填入所需的实体、联系及其属性，完成概念模型设计。 6 在 (2) (5)空缺处填入对应关系的属性，完成逻辑结构设计。 (参见本题 附 ) 7 对于 问题 2所完成的各实体关系模式，以下画线指出其主键和外键。 8 如果允许企业通过互联网修改本企业的基本信息，应对数据库的设计做哪些修改 ?请用 200字以内的文字叙述实现方案。 附 关系模式的标记规则如下： 关系名 (属性名 1，属性名 2， ，属性名 n) 其中： 若该属性 仅为主键属性时，则该属性名下画实下画线； 若该属性仅为外键属性时，则该属性名下画虚下画线； 若该属性既是主键属性，又是外键属性时，则在该属性名下画实下画线和虚下画线
8、； 若该属性既不是主键属性，又不是外键属性时，则在该属性名下不做标记。 9 阅读以下某门禁控制系统的技术说明，根据要求回答问题 1问题 3。 说明 门禁系统是楼宇安防系统的重要组成部分，也是大厦智能化管理的体现。其工作过程是，如果在入口处的读卡器上刷卡，锁控器 (LockController)接收读卡器(FingerReader)的读卡信息并进一步识别，如果为有效卡，则触发控制电控锁 (Lock)的继电器，让持卡人通过。锁控器还会将这些读卡及进出事件存储起来，并将相关事件记录传送给上位机。每个锁控器管理 1 4个门，每 5 8个锁控器接入 1条RS-485总线，并转换成 RS-232方式与管理
9、主机的串行口。对锁控器进行相关设置后，允许它脱机独立对门禁点进行控制，管理主机或通信线路故障都不会影响它的正常运行。在普通场合通常会设置 1个出门按钮，允许已进入的人员按动此按钮以打开电控锁；而对于一些重要场合通常会在门的内外安装两个读卡器，进出 门时都需按预设方式进行刷卡。 门禁系统中的每个电控锁都有一个唯一的编号。锁的状态有两种： “已锁住 ”和 “未锁住 ”。在管理主机上可以设置每把锁的安全级别及用户的开锁权限。只有当用户的开锁权限大于或等于锁的安全级别并且锁处于 “已锁住 ”状态时，才能将锁打开。用户的感应卡信息、开锁权限及锁的安全级别都保存在管理主机的数据库中。表 2-19给出了门禁
10、系统主要组成部件的作用。软件开发公司 A承担了该门禁控制系统的开发任务，其开发小组采用根据问题领域的模型建立系统结构的面向对象方法完成该系统的设计，系统中的类及类之间的关系用 UML类图表示。 9 如图 2-25所示是门禁控制系统的一个不完整类图，根据题干说明中给出的术语，请给出类 Lock的主要属性。 10 序列图是场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动，即显示了一组对象和由这组对象发送和接收的消息。如图 2-26所示是用户成功开锁的序列图。依据上述说明中给出的词语，将图 2-26中的 (1) (5)空缺处补充完整。 11 在系统的需求分析阶段，可以使用用例对系统需求建模
11、。用例可以使用 UML的用例图来表示。请分别用 100字以内的文字解释 UML用例图中扩展用 例和抽象用例的内涵。 12 阅读以下算法说明，根据要求回答问题 1问题 3。 说明 快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的 3个步骤如下。 1分解：选择一个枢轴 (pivot)元素划分数组。将数组 Apr划分为两个子数组(可能为空 )Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1中的每个元素，小于Aq+1r中的每个元素。 q的值在划分过程中计算。 2递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。 3合并：快速排序在原地排序，故无需合并操
12、作。 12 下面是快速排序的伪代码，请将空缺处 (1) (3)的内容填写完整。伪代码中的主要变量说明如下。 A：待排序数组 p,r：数组元素下标，从 p到 r q：划分的位置 x：枢轴元素 i：整型变量，用于描述数组下标。下标小于或等于 i的元素的值，小于或等于枢轴元素的值 j：循环控制变量，表示数组元素下标 13 (1)假设要排序包含 n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度 (用 O记号 )。最佳情况 为 (4)，平均情况为 (5)，最坏情况为 (6)。 (2)假设要排序的 n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况 ? (7)。 (最佳、平均、
13、最坏 ) 14 (1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素。下面是随机化快速排序划分的伪代码 利用原有的快速排序的划分操作，请填充其中的空缺处。其中， RANDOM(i,j)表示随机取 i到 j之间的一个数，包括 i和 j。 (2)随机化快速排序是否 能够消除最坏情况的发生 ? (10)。 (是或否 ) 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 15 请认真阅读以下函数说明、图及 C程序，将
14、程序段中 (1) (7)空缺处的语句填写完整。 说明 一般的树结构常采用孩子 兄弟表示法表示，即用二叉链表做树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如，如图 1-15(a)所示树的孩子 兄弟表示如图 1-15(b)所示。 函数 LevelTraverse()的功能是对给定树进行层序遍历。例如，对如图 1-15所示的树进行层序遍历时，节点的访问次序为 D B A E F P C。 对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如表 1-11所示。 Bool、 Status类型定义如下： 树的二叉链表节点定义如下： C函数程序 16 请阅读
15、以下技术说明、类图及 C+代码，根据要求将 (1) (7)空缺处的内容填写完整。 说明 已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器面板如图 1-16所示。该遥控器共有 4个按钮，编号分别是 0至 3，按钮 0和 2能够遥控打开电器 1和电器 2，按钮 1和 3则能遥控关闭电器 1和电器 2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如图 1-17所示。 在图 1-17中，类RomoteController的方法 onPressButton(int b
16、utton)表示当遥控器按键按下时调用的方法，参数为按键的编号； Command接口中 on和 off方法分别用于控制电器的开与关； Light中 turnLight (int degree)方法用于调整电灯灯光的强弱，参数 degree值为 0时表示关灯，值为 100时表示开灯并且将灯光亮度调整到最大； TV中setChannel(int channel)方法表示设置电视播放的频道，参数 channel 值为 0时表示关闭电视，为 1时表示开机并将频道切换为第 1频道。 C+代码 本试题应用命令模式能够有效让类 (5)和类 (6)、类 (7)之间的耦合性降至最小。 17 请阅读以下技术说明、
17、类图及 Java代码，根据要求将 (1) (7)空缺处的内容填写完整。 1. 说明 已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器面板如图 1-18所示。该遥控器共有 4个按钮，编号分别是 0至 3，按钮 0和 2能够遥控打开电器 1和电器 2，按钮 1和 3则能遥控关闭电器 1和电器 2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如图 1-19所示。 在图 1-19中，类RomoteController的方法 onPressButton(int but
18、ton)表 示当遥控器按键按下时调用的方法，参数为按键的编号； Command接口中 on和 off方法分别用于控制电器的开与关； Light中 turnLight (int degree)方法用于调整电灯灯光的强弱，参数 degree值为 0时表示关灯，值为 100时表示开灯并且将灯光亮度调整到最大； TV中setChannel(int channel)方法表示设置电视播放的频道，参数 channel 值为 0时表示关闭电视，为 1时表示开机并将频道切换为第 1频道。 Java代码 本试题应用命令模式能够有效让类 (5)和类 (6)、类 (7)之间的耦合性降至最小。 软件水平考试（中级）软件
19、设计师下午（应用技术）试题模拟试卷 37答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 这是一道要求读者掌握逻辑数据流图和物理数据流图区别点的简答题。本题所涉及的知识点如下。 数据流图是系统分析阶段用于描述系统逻辑模型的图形描述工具，解决信息系统 “做什么 ”的问题。它可分为逻辑数据流图和物理数据流图。 逻辑数据流图强调参与者所做的事情，可以帮助设计者决定需要哪些系统资源、为了运行系统用户必须执行的活动、在系统安装之后 如何保护和控制这些系统等内容。逻辑数据流图说明应该具有哪些加工和数据存储，而不关心这些加工和数据存储是如何实现的。 物理数据流图关注的是系统中的物理
20、实体，以及一些具体的文档、报告和其他输入 /输出数据。它通常用做系统构造和实现的技术性蓝图。在物理数据流图中需要说明加工和数据存储是如何实现的。 2 【正确答案】 这是一道要求读者掌握 DFD父图与子图的平衡原则和输入 /输出平衡原则的综合分析题。本题的解答思路如下。 根据 DFD父图与子图的平衡原则和输入 /输出平衡原则，通过比对图 2-21和图2-22中所有输入数据流和输出数据流可知，如图 2-22所示中与加工 “1处理管理请求 ”相关的两条输入数据流和两条输出数据流都是正确的。其中，如图 2-21所示中数据流 “非法请求信息 ”在如图 2-22所示中包含了 “非法管理工作请求单 ”和 “
21、非法查询请求信息 ”两条子数据流。 由题干给出的关键信息 “对于初次借书的读者，系统自动生成读者号，并与读者基本信息 (姓名、单位和地址等 )一起写入读者文件 ”可知，加工 “3登记读者信息 ”将有一条 “读者情况 ”数据流输出到数据存储 “读者文件 ”，即加工 3是用来登记读者信息，应该将登记的读者信 息写入读者文件，因此，在如图 2-22所示中这一 “写入 ”的箭头方向画反了。这条改正后数据流的起点是 “3 登记读者信息 ”，终点是 “读者文件 ”，数据流名称是 “读者情况 ”。其中，该数据流名称应综合考虑题干中关键信息 “系统自动生成读者号，并与读者基本信息一起写入读者文件 ”，并从如图
22、 2-22所示中数据流 “读者信息 ”、 “读者情况 ”中得到启发。 由题干给出的关键信息 “系统首先检查该读者号是否有效，若无效，则拒绝借书；若有效 ” 和 “系统的信息查询功能主要包括读者信息查询和图书信息查询。其中读者信息查询可得到读者的 基本信息及读者借阅图书的情况 ” ，并结合加工 2的细化图 (见图 2-23)中加工 “2.1读者信息查询 ”与数据存储 “读者文件 ”之间数据流的箭头方向可知，加工 “2处理查询请求 ”应该从数据存储 “读者文件 ”中读出读者的信息，因此在如图 2-22所示中这一 “查询 ”的箭头画反了。这条改正后的数据流的起点是 “读者文件 ”，终点是 “2处理查
23、询请求 ”，数据流名称是 “读者情况 ”。其中，该数据流名称可从图 2-22所示中加工 “2处理查询请求 ”的输出数据流 “读者情况 ”中得到启发。 3 【正确答案】 这也是一道要求读者从题干说明信息中识 别数据流，以及掌握局部数据存储的隐蔽性原则的综合分析题。本题的解答思路如下。 根据 DFD父图与子图的平衡原则和输入 /输出平衡原则，通过比对图 2-22和图2-23中所有输入 /输出数据流可知，如图 2-22所示中数据流 “查询请求信息 ”在如图2-23所示中包含了 “查询读者请求信息 ”和 “查询图书请求信息 ”两条子数据流；如图2-22所示中数据流 “非法查询请求信息 ”在如图 2-2
24、3所示中包含了 “非法查询读者请求信息 ”和 “非法查询图书请求信息 ”两条子数据流。 由题干给出的说明信息可知，读者基本信息存储在读者文 件中，而读者借阅图书的信息存储在借书文件中。再由题干给出的关键信息 “读者信息查询可以得到读者的基本信息及读者借阅图书的情况 ”，并结合 问题 2的分析过程可知，在如图 2-23所示中加工 “2.1读者信息查询 ”应从数据存储 “借书文件 ”中获取该读者借阅图书的情况。因此在如图 2-23所示中补充的一条数据流起点是 “借书文件 ”，终点是 “2.1读者信息查询 ”，数据流名称是 “读者借阅图书情况 ”。 同理，由题干给出的说明信息可知，读者借阅图书的信息
25、存储在借书文件中，而图书的基本信息存储在图书目录文件中。再由题干给出的关 键信息 “图书信息查询可以得到图书基本信息和图书的借出情况 ”可知，在如图 2-23所示中加工 “2.2图书信息查询 ”应从数据存储 “图书目录文件 ”中获取所查询图书的基本信息，从数据存储 “借书文件 ”中获取所查询图书的借出情况。因此在如图 2-23所示中补充的一条数据流起点是 “图书目录文件 ”，终点是 “2.2图书信息查询 ”，数据流名称是 “图书基本信息 ”；另一条数据流起点是 “借书文件 ”，终点是 “2.2图书信息查询 ”，数据流名称是 “图书借出情况 ”。 4 【正确答案】 这是一道要求读者根据具体应用环
26、境编写数据字典条目的综合分析题。本题的解答思路如下。 由题干给出的关键信息 “入库单内容包括图书分类目录号、书名、作者、价格、数量和购书日期 ”，并结合试题中给出的数据字典条目示例 “读者情况 =读者号+姓名 +所在单位 +借书情况 ”的编写风格，可得到 “入库单 ”的数据字典条目如下。 入库单 =分类目录号 +书名 +作者 +价格 +数量 +购书日期 同理，由题干给出的关键信息 “借书单内容包括读者号和所借图书分类目录号 ”和 “假设每位读者能同时借阅的书不超过 10本 ”可知，每位读者一次可借阅多本图书 (即 1： n的关系 )，每次借阅时需向系统提 交 “读者号 ”和 “所借图书分类目录
27、号 ”，因此可得到 “借书单 ”的数据字典条目如下。 借书单 =读者号 +所借图书分类目录号 同理，由题干给出的关键信息 “读者还书时需填写还书单。系统根据读者号和图书分类目录号，从借书文件中读出与该图书相关的借阅记录 ” ，并结合常识“每位读者一次可归还多本图书 (即 1： n的关系 )”等信息，可得到 “借书单 ”的数据字典条目如下。 还书单 =读者号 +所还图书分类目录号 由题干给出的关键信息 “该系统的图书管理功能主要分为购入新书、读者借书、读者还书及图书注销 4个方面 ”，以及题干中关于 “入库单 ”、 “借书单 ”、 “还书单 ”和 “注销单 ”的描述信息可知，每一项管理工作都需要
28、填写相应的单据。结合试题中给出的示例 “查询请求信息 =查询读者请求信息 |查询图书请求信息 ，可得到“管理工作请求单 ”的数据字典条目如下。 管理工作请求单 =入库单 |借书单 |还书单 |注销单 由 问题 2、 问题 3的分析过程可知，如图 2-21所示中数据流 “非法请求信息 ”在如图 2-22所示中包含 了 “非法管理工作请求单 ”和 “非法查询请求信息 ”两条子数据流，而数据流 “非法查询请求信息 ”在如图 2-23所示中又包含了 “非法查询读者请求信息 ”和 “非法查询图书请求信息 ”两条子数据流，因此 “非法请求信息 ”的数据字典条目如下。 非法请求信息 =非法管理工作请求单 |
29、非法查询请求信息 或非法请求信息 =非法管理工作请求单 |非法查询读者请求信息 |非法查询图书请求信息 5 【正确答案】 这是一道要求读者掌握数据库概念模型设计的综合分析题。本题的解答思路如下。 根据题干中给出的关键信息 “根据需求阶段收集的 信息，设计人才、岗位和企业的实体联系图 ”可知，应建立人才、岗位和企业 3个实体之间的联系。可见， (1)空缺处还缺少了一个 “岗位 ”实体。 题干在 “逻辑结构设计 ”中已给出了 “人才 (个人编号，姓名，性别，出生日期，身份证号，毕业院校，专业，学历，证书名称，证书编号，联系电话，电子邮件，个人简历及特长 )”、 “企业 (企业编号，企业名称，联系人
30、，联系电话，地址，企业网址，电子邮件，企业简介 )”、“求职意向 ( (2) )”和 “岗位需求 ( (3) )”4个关系模式，结合常识可知，人才与岗位之间是 “求职意向 ”联系，企业与岗位之 间是 “岗位需求 ”联系。 同理，结合常识可知， “人才 ”、 “岗位 ”实体之间是多对多 (m： n)的联系。从试题中给出的人才入库登记表 (表 2-17)中，扣除 “逻辑结构设计 ”关系模式 “人才 ”的相关属性后，可得到剩余的属性有 “登记日期 ”、 “职位名称 ”和 “最低薪水 ”。因此与联系 “求职意向 ”相关的属性有 “登记日期 ”和 “最低薪水 ”。 由常识可知， “企业 ”与 “岗位 ”
31、实体之间也是多对多(m： n)的联系。从试题中给出的企业信息登记表 (表 2-18)中，扣除 “逻辑结构设计 ”关系模式 “企业 ”的相关属性后，可得到剩余的属性有 “登记日期 ”、 “职位 (名称 )”、“专业 ”、 “学历 ”、 “薪水 ”和 “备注 ”。因此，与联系 “岗位需求 ”相关的属性有 “登记日期 ”、 “专业 ”、 “学历 ”、 “薪水 ”和 “备注 ”。 结合以上分析结果，整理可得完整的人才、岗位和企业的实体联系图如图 2-28所示。 另外说明一点， “需求 ”是人才、岗位和企业 3个实体之间的联系，而事实上只有人才被聘用之后三者之间才产生联系。根据题干所给出的信息，主要解决
32、的是人才的求职和企业的岗位需求之间的问题，而人才与企业之间没有直接的联系。 6 【正确答案】 这是一道要求读者掌握数据库逻辑结构设计的综合分析 题。本题的解答思路如下。 逻辑结构设计是建立在概念结构设计的基础上的，按照 E-R图向关系模式的转换方法，将实体和联系分别转换为关系模式。本题中已给出了实体对应的关系模式，其中 “岗位 ”实体没有属性，应归并到联系中。结合 问题 1的分析结果可知，求职意向的关系模式如下。 求职意向 (个人编号，岗位名称，最低薪水，登记日期 ) 同理，结合 问题 1的分析结果可知，岗位需求的关系模式如下。 岗位需求 (企业编号，岗位名称，专业，学历，薪水，备注，登记日期
33、 ) 本试题还要求对 “人才 ”关系模式进行 模式分解，以达到实体分离的优化目的 (即规范化 )。分解后 “人才 ”新关系模式可以减少 “证书编号 ”这一属性，而 “证书 ”新增关系模式的属性有 “证书名称 ”和 “证书编号 ”。这两个新的关系模式如下。 人才 (个人编号，姓名，性别，出生日期，身份证号，毕业院校，专业，学历，证书名称，联系电话，电子邮件，个人简历及特长 ) 证书 (证书名称，证书编号 ) 7 【正确答案】 这是一道要求读者根据题目给定的关系模式，以及属性间的函数依赖关系和关系模式的语义，并结合 E-R图向关系模式的转换方法来确定各关系模式主键和外键的综 合分析题。本试题的解答
34、思路如下。 (1)由题干中给出的关键信息 “一个人可能持有多个证书 ”可知，在证书关系模式中，证书名称可以决定证书关系模式中的全属性，因此证书关系模式的主键如下。 证书 (证书名称，证书编号 ) (2)由题干中给出的关键信息 “个人和企业的基本信息只需在第一次登记时填写，个人编号和企业编号由系统自动生成 以后个人只需提供个人编号和求职意向信息，企业只需提供企业编号和岗位需求信息 ”可知，个人编号可以决定人才关系模式中的全属性。同时考虑到 “证书名称 ”是证书关系模式的主键，因此 “证书名称 ”应为人才关 系模式的外键。最后可得人才关系模式的主键、外键如下。 人才 (个人编号，姓名，性别，出生日
35、期，身份证号，毕业院校，专业，学历，证书名称，联系电话，电子邮件，个人简历及特长 ) (3)同理，由于企业编号可以决定企业关系模式中的全属性，因此企业关系模式的主键如下。 企业 (企业编号，企业名称，联系人，联系电话，地址，企业网址，电子邮件，企业简介 ) (4)由 问题 1的分析结果可知， “人才 ”与 “岗位 ”实体之间是多对多 (m： n)的联系，个人编号多值决定岗位，如果仅用 “个人编号 ”作为求职意向关系模式的主键，则无法唯一区分求 职意向关系中的每一个元组 (记录 )。如果用 “个人编号 ”、 “岗位名称 ”作为主键，则可以唯一区分求职意向关系中的每一个元组。同时考虑到 “个人编号
36、 ”是人才关系模式的主键，因此 “个人编号 ”也是求职意向关系模式的外键。最后可得，求职意向关系模式的主键、外键如下。 求职意向 ( ，最低薪水，登记日期 ) (5)同理，“企业 ”与 “岗位 ”实体之间是多对多 (m： n)的联系，企业编号多值决定岗位，需要用“企业编号 ”、 “岗位名称 ”作为主键，才可唯一区分岗位需求关系中的每一个元组。同时考虑到 “企业编号 ”是企业关系模式的主键，则 “企业编号 ”也是岗位需求关系模式的外键。最后可得，岗位需求关系模式的主键、外键如下。 岗位需求( ，专业，学历，薪水，备注，登记日期 ) 8 【正确答案】 这是一道要求读者针对新应用进行数据表扩充的综合
37、分析题。本题的解答思路如下。 如果允许企业通过互联网修改本企业的基本信息，则应建立企业的登录信息表。该表中包含用户名和密码，用来记录企业的用户名和密码。接着将对本企业的基本信息的修改权限赋予相关的用户名。企业工作人员可以通过输入用户名和密码，经过服务器将其与登录信息表中记录的该企业的用户名和密码进行验证后，合法 用户才有权限修改企业的信息。 9 【正确答案】 这是一道要求读者掌握如何从问题域中抽象出类的属性的综合分析题。本题的解答思路如下。 首先要仔细理解题目中的信息，从这些信息牛获知该感应门禁系统主要部件有锁控器 (LockController)、读卡感应器 (FingerReader)、电
38、控锁 (Lock)和主机管理软件 (Win-Pak Software)。将关键信息转化成如图 2-29所示的系统体系结构。 在面向对象系统建模过程中，通常用概念模型来详细描述系统的问题域。类图用于描述系统的结构化设计，即用来表 示概念模型，表达了类、接口及它们之间的静态结构和关系。它最基本的元素是类或接口。通常，在类图上包含泛化 (Generalization)、实例(Realization)、关联 (Association)、聚集 (Aggregation)、组装 (Composition)、依赖(Dependency)等关系。 对系统的静态设计视图建模时，通常以对系统的词汇建模、对简单协作
39、建模、对逻辑数据库模式建模这 3种方式之一使用类图。其中，对系统的词汇建模需划分哪些抽象是考虑中的系统的一部分，哪此抽象是处于系统的边界之外，即用类 图详细描述这些抽象和它们的职责。而对简单协作建模中，协作是一些共同工作的类，接口和其他元素的群体，该群体提供的一此合作行为强于所有这些元素的行为之和。在很多领域中要在关系数据库或面向对象数据库中存储永久信息，可以用类图对这些数据库的模式进行建模。 在图 2-25类图中，已经完成了面向对象分析中的认定类，读者所要完成的工作是定义类的内部信息。类Lock是本系统中的一个关键类，题目与它的属性相关的描述有 “门禁系统中的每个电控锁都有一个唯一的编号 ”
40、、 “锁的状态有两种 ”、 “在管理主机上可以设置每把锁的安全级别 ”、 “锁处于 已锁住 状态时，才能将锁打开 ”等。从这些信息中提炼出说明类 Lock关键属性及特性的答案，即 “锁的编号 ”、 “锁的状态 ”和 “锁的安全级别 ”。 10 【正确答案】 这是一道要求读者掌握 UML建模中序列图知识点的分析题。本题的解答思路如下。 系统的动态行为常采用 UML序列图表示，它展现了一组对象和由这组对象收发的消息，用于按时间顺序对控制流建模。要注意它强调的是时间和顺序。 图 2-26所表达的序列图有两个特征：一是它有对象生命线；二是它有控制焦点。对象生命线是一条垂直的虚线，表示一个对象的生命跨度
41、。控 制焦点是一个瘦高的矩形，表示一个对象执行一个动作所经历的时间段。矩形的顶部表示动作的开始，底部表示动作的结束。在序列图顶部水平方向画出的是参与交换的对象。 看懂序列图之后，接着根据问题要点，查找题目中与用户开锁相关的信息。对这些关键信息进行归纳整理的结果如下：用户开锁时，只需将感应卡靠近读卡器。读卡器获取信息后将发送一个中断事件给锁控器，锁控器从读卡器读取用户卡的 ID号并将该 ID号信息发送到管理主机，管理主机根据数据库中存储的信息来判断用户是否具有开锁权限，若有且锁当前处于 “已锁住 ”状态，则将锁打开；否则 系统报警。 通过以上分析，可以得出用户开锁的激发事件是：用户感应卡靠近读卡
42、器。 由于序列图是按照时间顺序组织对象之间交互活动，因此需要将这些活动按照时间顺序进行排序，并记录下参与每个活动的对象。根据以上分析结果结合图 2-26已给出的信息，可以得出用户开锁涉及的活动事件如表 2-20所示。11 【正确答案】 这是一道要求读者掌握 UML用例图中扩展用例和抽象用例的内涵的简答题。本试题所涉及的知识点如下。 由某个更复杂的用例提取出来的事件序列所构成的用例称为扩展用例，它可以简化原有用例并扩展其功 能。 若从几个执行相同功能步骤的用例中，将公共步骤提取成独立的用例，那么这个提取出来的用例就称为抽象用例。它代表某种形式的 “复用 ”，可以降低用例之间的冗余。 12 【正确
43、答案】 这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进，其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分，即 PARTITION 操作：根据枢轴元素的值，把一个较大的数组分成两个较小的子数组，一个子数组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。划分时，以最后一个元素为枢轴元素，从左到右依次访问数组的每一个元素，判断其与
44、枢轴元素的大小关系，并进行元素的交换，如图 2-30所示。 在问题 1所给出的伪代码中，当 for循环结束后， Api中的值应小于等于枢轴元素值 x，而 Ai+1r-1中的值应大于枢轴元素值 x。此时 Ai+1是第一个比 Ar大的元素， 因此 Ar与 Ai+1进行交换，得到划分后的两个子数组。 PARTITION操作返回枢轴元素的位置，因此返回值为 i+l。 13 【正确答案】 这是一道考查快速排序算法时间复杂度的分析题。当每次能作均匀划分时，算法为最佳情况，此时时间复杂度可以通过计算递归式T(n)=2T(n/2)+O(n)，得到时间复杂度为 O(nlogn)。当每次为极端不均匀划分时，即长度
45、为 n的数组划分后一个子数组为 n-1，一个为 0，算法为最坏情况，此时时间复杂度可以通过计算递归式 T(n)=T(n-1)+O(n)，得到时间复杂度为 O(n2)。 对于平均情况的分析较为复杂，假设数组每次划分为 9/10： 1/10，此时时间复杂度可以通过计算递归式 T(n)=T(9/10)+T(1/10)+O(n)，得到时间复杂度为 O(nlogn)，因此在平均情况下快速排序仍然有较好的性能，时间复杂度为 O(nlogn)。 当所有的 n个元素具有相同的值时，可以认为数组已经有序，此时每次都划分为长度为 n-1和 0的两个子数组，属于最坏情况。 14 【正确答案】 由于随机化的快速排序的
46、划分调用了传统的快速排序算法的PARTITION操作，而传统的划分每 次以数组的最后一个元素作为枢轴元素，因此随机化的划分操作中每次先随机获得一个元素，将其与最后一个元素交换。随机化的快速排序消除了输入数据的不同排列对算法性能的影响，降低了极端不均匀划分的概率，但不能保证不会导致最坏情况的发生。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 15 【正确答案】 这是一道要求读者掌握树结构的存储及遍历运算的程序分析题。本试题的解答思路如下。 队列可以保证访问节点时按照层次和自左至右的顺 序。借助队列结构
47、对树进行层序遍历时，每个节点都进出队列一次，节点出队列时进行访问。其过程是，首先令树根节点入队，若是森林 (树根之间互为兄弟 )，接着则令其余树的根节点入队，然后在队列非空的情况下，队头节点出队，访问该节点同时令其孩子节点入队。以此类推，直到队列为空。 在试题所给出的 C函数程序 中，代码 “InitQueue( tempQ)； (1) ； ”完成初始化队列并令根节点入队列的功能，因此 (1)空缺处所填写的内容是 “EnQueue( tempQ, root)”。 采用二叉树存储树结构时， 其右分支表示兄弟关系，因此队头节点出队时，应沿右分支将队头节点的所有孩子依次加入队列。 (2)空缺处所在的
48、 while循环完成处理第一棵树的兄弟节点的功能，因此， (2)空缺处所填写的内容是“brotherptr=brotherptr- nextbrother”。至此，就完成了第一层节点的处理。 (3)空缺处用于判断队列是否为空，即应填入 “!IsEmpty(tempQ)”或其他等价形式。 使用队列或栈结构存储元素以实现某种运算的基本特点是，当队列非空时，应令队头元素出队列。因此 (4)空缺处所填写的内容 是 “DeQueue( tempQ， ptr)”。 若一个节点不存在孩子，则其 firstchild指针域为空，也无须令其孩子节点入队列。因此， (5)空缺处所填写的内容是 “!ptr- fir
49、stchild”或其他等价形式。反之，若一个节点有孩子，则应首先令其第一个孩子节点入队列，然后通过右分支链使其他孩子节点入队列。因此， (6)空缺处所填写的内容是 “EnQueue( tempQ， ptr-firstchild)”， (7)空缺处所填写的内容是 “brotherptr=brotherptr- nextbrother”。 16 【正确答案】 考查设计模式中的 Command(命令 )模式的案例分析题。Command(命令 )模式的设计意图是：将一个请求封装为一个对象，从而使用户可用不同的请求对客户进行参数化；对请求排队或记录请求日志，以及支持可撤销的操作。其中一种应用场合就是抽象出待执行的动作以参数化某种对象，可用过程语言中的回调 (callback)函数表达这种参数化机制。 Comma
