1、软件水平考试（中级）软件设计师下午（应用技术）试题模拟试卷 38及答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 阅读以下某建账软件的技术说明和数据流图，根据要求回答问题 1问题 6。 说明 某商业银行已有一套基于客户机 /服务器 (C/S)模式的储蓄系统 X和一套建账软件 Y。建账软件 Y主要用于将储蓄所手工处理的原始数据转换为系统 X所需的数据格式。该建账软件具有以下功能。 (1)分户账录入：手工办理业务时建立的每个分户账数据均由初录员和复录员分别录入，以确保数据的正确性。 (2)初录 /复录比对：将初 录员和复录员录入的数据进行一一比较，并标记两套数据是否一致。 (3)数据
2、确认：当上述两套数据完全一致后，将其中任一套作为最终进入系统 X的原始数据。 (4)汇总核对和打印：对经过确认的数据进行汇总，并和会计账目中的相关数据进行核对，以确保数据的整体正确性，并打印输出经过确认的数据，为以后核查可能的错误提供依据。该建账软件需要打印的分户账清单样式如表 3-8所示。(5)数据转换：将经过确认的数据转换为储蓄系统 X需要的中间格式数据。 (6)数据清除：为加快初录和复录的处理速度，在数据确认之后，可以有选择地清除初录 员和复录员录入的数据。 该软件的数据流图如图 3-17图 3-19所示，图中部分数据流数据文件的格式如下。 初录分户账 =储蓄所号 +账号 +户名 +开户
3、日 +开户金额 +当前余额 +性质 复录分户账 =储蓄所号 +账号 +户名 +开户日 +开户金额 +当前余额 +性质 会计账目 =储蓄所号 +总户数 +总余额 操作结果 =初录操作结果 +比对操作结果 +复录操作结果 1 不考虑数据确认处理 (加工 2)，请指出图 3-17图 3-19数据流图中可能存在的错误。 2 请使用 说明 中的词汇，给出数据确认处理所需的数据流，在图 3-19建账软件第1层数据流图中的全部可选起点。 3 请使用 说明 中数据字典条目定义形式，将以下 (1)和 (2)空缺处的内容填写完整。 初录数据 =(1) 复录数据 =(2) 4 请使用 说明 中数据字典条目定义形式，
4、给出图 3-18中的 “手工分户账 ”数据流和图 3-19中的 “初录分户账 ”和 “复录分户账 ”的关系。 5 加工 1(录入比对处理 )除能够检查出初录数据和复录数据不一致之外，还应检测的错误有 (3)。 A显示器无法显示 B输入的无效字符 C输入数据的格式 D输入 数据的界限 E打印机卡纸 F重复录入同一账户 G输入的半个汉字 H汇总数据与会计账目不符 6 打印分户账清单 (表 3-8)时，必须以 “(4)”作为关键字进行排序才能满足系统需求。 A储蓄所 B账号 C开户日 D户名 E其他分户账数据 F总户数和总余额 7 阅读下列说明，根据要求回答问题 1问题 3。 说明 某地区举行篮球比
5、赛，需要开发一个比赛信息管理系统来记录比赛的相关信息。 需求分析结果 1登记参赛 球队的信息。记录球队的名称、代表地区、成立时间等信息。系统记录球队的每个队员的姓名、年龄、身高、体重等信息。每个球队有一个教练负责管理球队，一个教练仅负责一个球队。系统记录教练的姓名、年龄等信息。 2安排球队的训练信息。比赛组织者为球队提供了若干个场地，供球队进行适应性训练。系统记录现有的场地信息，包括：场地名称、场地规模、位置等信息。系统可为每个球队安排不同的训练场地，如表 3-9所示。系统记录训练场地安排的信息。3安排比赛。该赛事聘请有专职裁判，每场比赛只安排一个裁判。系统记录裁判的姓名、年龄、级别 等信息。
6、系统按照一定的规则，首先分组，然后根据球队、场地和裁判情况，安排比赛 (每场比赛的对阵双方分别称为甲队和乙队 )。记录参赛球队、比赛时间、比分、场地名称等信息，如表 3-10所示。4所有球员、教练和裁判可能出现重名情况。 概念模型设计 根据需求阶段收集的信息，设计的实体联系图和关系模式 (不完整 )如下。 1实体联系图 (图 3-20) 2关系模式 教练 (教练编号，姓名，年龄 ) 队员 (队员编号，姓名，年龄，身高，体重， (a) 球队(球队名称，代表地区，成立时间， (b) 场地 (场地名称，场地规模， 位置 ) 训练记录( (c) ) 裁判 (裁判编号，姓名，年龄，级别 ) 比赛记录 (
7、 (d) ) 7 根据问题描述，补充 4个联系，完善图 3-20的实体联系图。 8 根据你的实体联系图，完成关系模式，并给出训练记录和比赛记录关系模式的主键和外键。 9 如果考虑记录一些特别资深的热心球迷的情况，每个热心球迷可能支持多个球队。热心球迷的基本信息包括：姓名、住址和喜欢的俱乐部等。根据这一要求修改图 3-20的实体联系图，给出修改后的关系模式。 10 阅读以下技术说明，根据要求回答问题 1问题 4。 说明 某 汽车停车场欲建立一个信息系统，已经调查到的需求如下。 1在停车场的入口和出口分别安装一个自动栏杆、一台停车卡打印机、一台读卡器和一个车辆通过传感器等，其示意图见如图 3-21
8、所示。 2当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡。当驾驶员拿走停车卡后，系统命令栏杆自动抬起；汽车通过入口后，入口处的传感器通知系统发出命令，栏杆自动放下。 3在停车场内分布着若干个付款机器。驾驶员将在入口处获取的停车卡插入付款机器，并缴纳停车费。付清停车费之后，将获得一张出场卡，用于离开停车场。 4当汽车到达 出口时，驾驶员将出场卡插入出口处的读卡器。如果这张卡是有效的，系统命令栏杆自动抬起；汽车通过出口后，出口传感器通知系统发出命令，栏杆自动放下。若这张卡是无效的，系统不发出栏杆抬起命令而发出告警信号。 5系统自动记录停车场内空闲的停车位的数量。若停车场当前没有车位，系统
9、将在入口处显示 “车位已满 ”信息。这时，停车卡打印机将不再出卡，只允许场内汽车出场。 根据上述描述，采用面向对象方法对其进行分析与设计，得到如表 3-11所示的类 /用例 /状态列表，如图 3-22所示的用例图，如图 3-23所示的初始类图以及如图 3-24所示的描述入口自动栏杆行为的 UML状态图。10 根据说明中的描述，使用表 3-11给出的用例名称，给出图 3-22中 U1、 U2和U3所对应的用例。 11 根据说明中的描述，使用表 3-11给出的类的名称，给出图 3-23中的 A D所对应的类。 12 根据说明中的描述，使用表 3-11给出的状态名称，给出图 3-24中 S1 S4所
10、对应的状态。 13 简要解释图 3-22中用例 U1和 U3之间的 extend关系的内涵。 14 阅读下列算法说明和流程图，根据要求回答问题 1问题 3。 说明 某机器上需要 处理 n个作业 job1， job2， ， jobn，其中： (1)每个作业 jobi(1in)的编号为i， jobi有一个收益值 Pi和最后期限值 di； (2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍； (3)job1 jobn的收益值呈非递增顺序排列，即 p1p2pn ； (4)如果作业 jobi在其期限之内完成，则获得
11、收益pi；如果在其期限之后完成，则没有收益。 为获得较高的收益，采用贪心策略 求解在期限之内完成的作业序列。图 3-25是基于贪心策略求解该问题的流程图。 (1)整型数组 J有 n个存储单元，变量 k表示在期限之内完成的作业数， J1k存储所有能够在期限内完成的作业编号，数组 J1k)里的作业按其最后期限非递减排序，即 dJ1dJk 。 (2)为了便于在数组 J中加入作业，增加一个虚拟作业job0，并令 d0=0， J0=0。 (3)算法大致思想是：先将作业 job1的编号 1放入J1，然后，依次对每个作业 jobi(2in)进行判定，看其能否插入到数组 J中。若能，则将其编号插入到数组 J的
12、适当位置，并保证 J中作业按其最后期限非递减排列；否则不插入。 jobi能插入数组 J的充要条件是： jobi和数组 J中已有作业均能在其期限之内完成。 (4)流程图中的主要变量说明如下。 i：循环控制变量，表示作业的编号； k：表示在期限内完成的作业数； r：若 jobi能插入数组 J，则其在数组J中的位置为 r+1； q：循环控制变量，用于移动数组 J中的元素。14 请将图 3-25中的 (1) (3)空缺处的内容填写完整。 15 假设有 6个作业 job1， job2， ， job6； 完成作业的收益数组 p=(p1,p2,p3,p4,p5,p6)=(90,80,50,30,20,10)
13、； 每个作业的处理期限数组 d=(d1,d2,d3,d4,d5,d6)=(1,2,1,3,4,3)。 请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列 (4) (按作业处理的顺序给出 )，得到的总收益为 (5)。 16 对于本试题的作业处理问题，用图 3-25的贪心算法能否求得最高收益 ? (6)。(能或不能 ) 用贪心算法 求解任意给定问题时，是否一定能得到最优解 ? (7)。 (能或不能 ) 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 17 阅读以下函数说明、图和 C程序代码，将
14、 C程序段中 (1) (6)空缺处的语句填写完整。 说明 散列文件的存储单位称为桶 (BUCKET)。假如一个桶能存放 m个记录，当桶中已有 m个同义词 (散列函数值相同 )的记录时，存放第 m+1个同义词会发生 “溢出 ”。此时需要将第 m+1个同义词存放到另一个称为 “溢出桶 ”的桶中。 相对地，称存放前 m个同义词的桶为 “基桶 ”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。 例如，设散列函数为 Hash(Key)=Key mod7，记录的关键字序列为 15， 14， 21， 87， 96， 293， 35，
15、 24， 149， 19， 63， 16， 103， 77， 5，153， 145， 356， 51， 68， 705， 453，建立的散列文件内容如图 2-27所示。 为简化起见，散列文件的存储单位以内存单元表示。 函数 InsertToHashTable(int NewElemKey)的功能是：若新元素NewElemKey正确插入散列文件中，则返回值 0；否则返回值 -1。 采用的散列函数为 Hash(NewElemKey)=NewElemKey%P，其中 P设定基桶的数目。 函数中使用的预定义符号如下。 18 阅读以下技术说明及 C+代码，将 C+程序中 (1) (5)空缺处的语句填写完
16、整。 说明 在一公文处理系统中，开发者定义了一个公文类 OfficeDoc，其中定义了公文具有的属性和处理公文的相应方法。当公文件中内容或状态发生变化时，关注此OfficeDoc类对象的相应的 DocExplorer对象都要更新其自身的状态。一个OfficeDoc对象能够关联一组 DocExplorer对象。当 OfficeDoc对象的内容或状态发生变化时，所有与之相关联的 DocExplorer对象都将得到通知，这种应用被称为Observer(观察者 )模式。以下代码采用 C+语言实现，能够正确编译通过。 C+代码 19 阅读以下技术说明及 Java代码，将 Java程序中 (1) (5)空
17、缺处的语句填写完整。 说明 在一公文处理系统中，开发者定义了一个公文类 OfficeDoc，其中定义了公文具有的属性和处理公文的相应方法。当公文件的内容或状态发生变化时，关注此 OfficeDoc类对象的相应的 DocExplorer对象都要更新其自身的状态。一个OfficeDoc对象能够关联一组 DocExplorer对象。当 OfficeDoc对象的内容或状态发生变化时，所有与之相关联的 DocExplorer对象都将得到通知，这种应用被称为Observer(观察者 )模式。以下代码采用 Java语言实现，能够正确编译通过。 Java代码 软件水平考试（中级）软件设计师下午（应用技术）试
18、题模拟试卷 38答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 这是一道要求考生掌握分层数据流图输入 /输出平衡原则的分析题。本题的解答思路如下。 每个加工必须既有输入数据流，又有输出数据流。但一个加工的输入数据流不要与输出数据流同名。在整套数据流图中，每个数据存储必须既有读的数据流，也有写的数据流。但在某张子图中，可能只有读没有写，或者是只有写而没有读。 在数据流图 (DFD)中，加工处理是对输入数据进行相关处理并生成输出数据的过程，因此，对于 DFD中的每个加工处理至少 要有一个输入数据流和一个输出数据流。根据这一原则仔细检查图 3-17图 3-19可知，在建账
19、软件第 0层数据流图 (见图 3-18)中，数据确认处理 (加工 2)和数据清除处理 (加工 6)只有输出数据流而没有输入数据，这是图 3-18中存在的错误之处。由于题目中已说明 “不考虑数据确认处理 (加工 2)”，因此，本试题的正确答案是 “在建账软件第 0层数据流图 (图 3-18)中，数据清除处理 (加工 6)没有输入数据流 ”。 2 【正确答案】 这也是一道要求考生掌握分层数据流图输入 /输出平衡原则的综合分析题。本题的解答思路如下。 在本试题说明中关于 “数据确认 ”功能的描述 “数据确认：当上述两套数据 (即初录员和复录员录入的数据 )完全一致后，将其中任一套作为最终进入系统 X
20、的原始数据 ”中， “进入系统 X”其对应于建账软件第 0层数据流图 (见图 3-18)中 “数据确认 ”处理。由此可知，在图 3-19建账软件第 1层数据流图中，无论是 “初录数据 ”数据存储还是 “复录数据 ”数据存储都可作为 “数据确认 ”处理的数据源。 3 【正确答案】 由题干中给出的关键信息 “分户账录入：手工办理业务时建立的每个分户账数据均由初录员和复录员分别录入 ” 和 “初录 /复 录比对：将初录员和复录员录入的数据进行一一比较，并标记两套数据是否一致 ”可知，初录员录入的“初录数据 ”中应包含 “初录分户账 ”和 “一致性标志 ”，而复录员录入的 “复录数据 ”中应包含 “复
21、录分户账 ”和 “一致性标志 ”。然后将它们表达成 说明 中数据字典条目定义形式如下。 初录数据 =初录分户账 +一致性标志 (或初录数据 =手工分户账 +一致性标志 ) 复录数据 =复录分户账 +一致性标志 (或复录数据 =手工分户账 +一致性标志 ) 4 【正确答案】 这是一道要求考生掌握分层数据流图中父图与子图平衡原则的综合分析题。本题的 解答思路如下。 任何一个数据流子图必须与它上一层父图的某个加工相对应，即父图中某加工的输入 /输出数据流必须与它的子图的输入 /输出数据流在数量和名字上相同。但如果父图中的数据流是由子图中的几个数据流合并而成，即子图中组成这些数据流的数据项全体正好是父
22、图中的这一个数据流，这种情况下也认为是平衡的。 在建账软件第 0层数据流图 (见图 3-18)中， “手工分户账 ”数据流是 “1录入比对 ”处理的输入数据流，而 “1录入比对 ”处理包含了建账软件第 1层数据流图 (见图 3-19)中的 “1.1初录 ”处理、 “1.2复录 ”处理 和 “1.3比对 ”处理。在图 3-19中， “1.1初录 ”处理的输入数据流是 “初录分户账 ”， “1.2复录 ”处理的输入数据流是 “复录分户账 ”，因此， “手工分户账 ”数据流包含了 “初录分户账 ”和 “复录分户账 ”，将其表达成本试题 说明 所示例的数据字典条目定义形式如下。 手工分户账 =初录分户
23、账 +复录分户账 5 【正确答案】 由 问题 3要点解析可知，建账软件第 0层数据流图 (见图 3-18)中“1录入比对 ”处理包含了第 1层数据流图 (图 3-19)中的 “1.1初录 ”、 “1.2复录 ”和 “1.3比对 ”这 3个处理。结合题干给出的关键信息 “初录 /复录比对：将初录员和复录员录入的数据进行一一比较，并标记两套数据是否一致 ”和常识可知，加工 1(录入比对处理 )除能够检查出初录数据和复录数据不一致之外，还应检测的错误有 输入的无效字符 (如在 “账号 ”数据项中输入了小数点、 $和 等其他字符 )、 输入数据的格式 (如 “账号 ”数据项规定每 4位数字后加一位半角
24、空格字符等 )、 输入数据的界限 (例如 “开户日 ”的数值是否超过了当前日期等 )、 输入的半个汉字 (在某些运行环境中 (或输入法 )中可能存在这种情况 )和 (初录员 /复录员 )重复录入同一账户等。 由题干给出的关键信息 “汇总核对和打印：对经过确认的数据进行汇总，并和会计账目中的相关数据进行核对 ” 可知，检查汇总数据和会计账目是否相符是在图 3-18中处理 “3汇总核对 ”所完成的功能；数据打印是在图 3-18中处理 “4打印清单 ”所完成的功能。同时根据常识可知， “1录入比对 ”处理通常未涉及检查 “显示器无 法显示 ”和 “打印机卡纸 ”等硬件故障的功能。 6 【正确答案】
25、仔细阅读分户账清单样式表 (见表 3-8)可知，表中数据是按照 “储蓄所 ”这一数据字段进行分组的，每一分组中均通过 “共 XXXX户，总余额YYYYYYY.YY元 ”格式给出了储蓄所的统计数据。这就要求在数据查询 /打印操作中，至少要按照 “储蓄所 ”这一数据字段进行排序才能实现。在实际应用中，在软件实现时也可以按照 “账号 ”和 “开户日 ”等数据字段进行排序，但从表 3-8数据格式中无法确定是否需要这些排序工作。 7 【正确答案】 本题考查读者对数据库概念结构设计 及向逻辑结构转换的掌握情况。此类题目要求认真阅读题目对现实问题的描述，经过分类、聚集、概括等方法，从中确定实体及其联系。题目
26、已经给出了 4个实体，需要根据需求描述，给出实体间的联系。 由 “每个球队有一个教练负责管理球队，一个教练仅负责一个球队。 ”知球队与教练间为 1:1联系；球队与队员之间应为 1:N联系；多个球队使用多个训练场地，球队与场地之间为 M:N联系；比赛是球队、场地与裁判之间的联系，一个球队会与同组的其他多个队之间比赛，有多个场地和裁决，一位裁判会对多场比赛判罚，一个场地会有多场比赛，涉及多个球队和裁判 ，因此球队、场地与裁判之间的比赛关系为 M:N:P联系。补充完整的实体联系图如图 3-29所示。8 【正确答案】 根据补充后的 E-R图，球队与球员之间的 1:N联系应通过将 1端实体 (球员 )的
27、主码 (球队名称 )加入到 N端实体 (球员 )对应的关系中来表达。这类联系也可通过独立的一个关系来表达，如球队 -球员 (球队名称，队员编号 )，这样会对查询增加多余的连接操作，因此一般不采用这种方法。 同样，球队与教练之间的 1:1联系也应通过将一方的主码增加到另一方实体对应的关系中，来表达联系。 训练和比赛为多对多联 系，只能独立成一个关系模式，取该联系相关联的各实体的码及联系自有的属性构成。如比分和分组应该是比赛的属性，再加上球队、裁判、场地的码，即构成 “比赛记录 ”的关系模式。比赛记录关系模式的主键可以是“场地名称，比赛时间 ”，也可以是 “裁判，比赛时间 ”，或者是 “甲队，比赛
28、时间 ”，再或者是 “乙队，比赛时间 ”。其外键是 “甲队，乙队，场地名称，裁判 ”。 同理，训练是球队和场地的多对多联系，训练开始时间和结束时间为训练的属性，加上球队的码和场地的码，构成 “训练记录 ”关系模式。训练记录关系模式的主键可以是 “球队，开始时间 ”，也可以是 “场地名称，开始时间 ”，或者是 “球队，结束时间 ”，再或者是 “场地名称，结束时间 ”。其外键是 “球队名称，场地名称 ”。 9 【正确答案】 球迷与球队之间为多对多联系，需新增球迷实体和球迷与球队之间的支持联系，如图 3-30所示。 新增的关系模式如下。 热心球迷 (球迷编号，姓名，住址，俱乐部 ) 支持球队 (球迷
29、编号，球队 ) 10 【正确答案】 表 3-11中给出了 Car entry、 Car exit、 Report Statistics、 Car entry when full等 4个用例。在这 4个用例中 ，两个用例表示汽车进入停车场，一个用例表示汽车退出停车场，另一个用例表示记录停车场相关信息。经分析得出，前 3个用例的参与者都是驾驶员，因此 U1、 U2和 U3对应进入和退出停车场。 U1和 U3之间存在扩展关系，而用例之间的延伸关系用于对被用户看作是可选系统行为的用例的一部分建模。通过这种方式，可以把可选行为从必需的行为中分离出来。 Car entry when full和 Car e
30、ntry之间就可以使用 extend关系进行建模。 11 【正确答案】 在 UML类图中，类与类之间的 5种关系从弱到强依次为：依赖(Dependency)，关联 (Association)，聚合 (Aggregation)，组合 (Composition)和继承(Inheritance)。因此依赖关系最弱，继承表示类与类之间关系最强。依赖(Dependency)关系是类与类之间的连接，并且依赖总是单向的，其标准 UML图形表示为 表示其相联的两个类之间存在关联关系，用于描述两个概念上位于相同级别的类的实例之间存在的某种语义上的联系。聚合关系是关联关系的一种特例，代表两个类之间的整体 /局部关
31、系，其标准 UML图形表示为表示其相联的两个类之间存在继承关 系。子类继承父类的行为与含义，子类还可以增加或者覆盖父类的行为。子类可以出现在父类出现的任何位置。 依题意可以判断 Barrier、 EntryBarrier和 ExitBarrier之间存在继承关系，而在图 3-23类图中 所表示的继承关系的部分只有一处，因此这 3个类分别对应于图 3-23中的类 B、类 C和类 D，而剩下的类 A只有选择类 CarPark了。 12 【正确答案】 在图 3-24状态图中， Idle表示有空闲车位， Disable表示没有空闲车位，因此在其之间存在双向的状态迁移，即状态图上的状态 S1为 Idle
32、状态。当停车场存在空闲车位时，汽车请求进入停车场，根据说明描述 “当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡 ”，可知在该动作正对应于状态图上的 S1和状态 S2之间的迁移，因此，状态 S2表示的含义应该是按下按钮后状态，此时，驾驶员等待打印停车卡，所以状态 S2为 Await Ticket Take。同理可分析出状态 S3和状态 S4。 13 【正确答案】 在用例的执行过程中，可能会在不同的流程分支中选择执行，也可能会出现异常行为。此时，可以将异常行为或可选分支抽象成一个单独的扩展用例，它与主用例之间形成 “扩展 (extend)”关系。 14 【正确答案】 这是一道考查贪心算
33、法的流程图分析的试题。 (1)空缺处表示第 2个作业到第 n个作业的主循环的条件判断，由于 i是循环控制变量，因此 (1)空缺处所填写的内容是 i =h。 注意到题干中给出的关键信息 “J1k)存储所有能够在期限内完成的作业编号，数组 J1k里的作业按其最后期限非递减排序，即”。换言之，数组 J中的作业 Ji(1ik)是在其期限之前完成的作业，且 。由图 3-25给出的算法流程图可知，主循环内嵌套了两个循环，第 1个循环判断当前考虑的作 业 i应该插入到 J中的什么位置，用循环控制变量 r表示当前考虑的 J中的作业。使用虚拟作业 J0，允许作业较方便地插入到第 1个位置。为了保证 J中的作业期
34、限按升序排序，作业 Jr若比作业 i的期限大，则循环控制变量 r要自减，因此 (2)空缺处所填写的内容是 dJr di。 dJr与 r的关系只有两种： dJr r，表示还可能在 J1与 Jr之间插入作业“dJr=r，表示不可以在 J1 Jr之间插入作业 i。 dJr r的情况不会存在，因为 J中若有 r个作业，那么最后一个作业 的期限不可能小于 r。当作业 i大于等于作业 Jr的期限时，此时找到了作业 i插入的位置，即 r+1。第 2个循环的作用是将作业 Jr+1Jk 依次往后移动，此处用插入排序算法的思想。最后把作业 i插入到 Jr+1处，因此 (3)空缺处所填写的内容是 Jr+1=i(或
35、Jq+1=i)。 15 【正确答案】 这是一道考查贪心算法实例应用的分析题。 6个作业 job1，job2， ， job6的收益已经按降序排列，根据图 3-25的算法流程，将作业 1， 2， 4和 5放入数组 J中，并得到总收益为 220，具体分析过程见表 3-13。16 【正确答案】 这是一道判断贪心算法是否能求得最优解的应用分析题。对于本试题的作业处理问题，用图 3-25的贪心算法策略，能求得最优解 (即能求得最高收益 )。但不是所有的问题都能通过贪心策略来求得最优解，一个典型的例子是 01背包问题。例如，有 3件物品，背包可容纳 50磅重的东西，每件物品的详细信息如表 3-14所示，问如
36、何装包使得其价值最大 ? 如果按贪心策略求解该问题，优先选择单位价值最大的物品，则先选择物品 R，然后选择物品 S。由于此时背包容量还剩下 50-10-20=20，不足以容纳物品 T， 故总价值为 60+100=160美元。但若选择物品 S和物品 T，容量总和为 20+30，小于等于总容量 50，得到总价值为 100+120=220美元，会得到更优解。此时用贪心策略不能得到最优解。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 17 【正确答案】 这是一道要求读者掌握如何在散列文件中插入一个新的数据元
37、素的编程题。本题的解答思路如下。 在散列文件中插入一个新的数据元素的基本思路是，首先将要插入的元素代入到散列函数中， 从而计算出该元素的散列地址。然后按照散列地址，在基桶中查找空闲单元，若找到，则将元素插入，若基桶已满，则在溢出桶中查找空闲单元。若溢出桶中也查找不到，则申请新的溢出桶，然后将元素存入。 在散列文件中查找一个元素的基本思路是，查找指定元素记录时，首先在基桶中查找，若找到，则成功返回，否则沿指针到溢出桶中进行查找。 在本试题中，将元素存储在预先设定的基桶或根据需要申请的溢出桶中，只要基桶中有空闲单元，就将新元素 NewElemkey插入在基桶中，若基桶中无空闲单元，则看是否存在溢出
38、桶，若存在，则在溢出桶中查找空闲 单元，若不存在溢出桶或溢出桶中无空闲单元，则申请一个溢出桶并存入新元素。 在基桶查找空闲单元时，使用的桶号为 Index，由此可知 (1)空缺处所填写的内容是 “Index=NewElemKey%P”，或“Index=Hash(NewElemKey)”等其他等价形式。 一旦在基桶中找到空闲单元，即“Bucket1ndex.keyDatai=NULLKEY”(0i ITEMS)，则可将元素 NewElemkey放入 BucketIndex.keyDatai，至此元素已经插入散列桶中，函数可返回，因此 (2)空缺处所填写的内容是 “i ITEMS”。反之， 若在基
39、桶中没有找到空闲单元，则需查找溢出桶。 “t=BucketIndex.Link”，指针 t首先指向桶号 Index的第一个溢出桶。以下的代码完成在溢出桶中查找空闲单元的功能。 由于每个溢出桶都可以存储 ITEMS个元素，因此在溢出桶中查找空闲单元与在基桶中的查找过程相同，代码如下。 若在指针 t指向的溢出桶中找到空闲单元则插入元素，否则，由 “t=t- Link”得到下一个溢出桶的指针，因此 “k ITEMS”可作为是否在当前溢出桶中找到空闲单元的判定条 件。显然，在桶号 Index的基桶和其所有溢出桶都已满的情况下， t的值为空指针。此时才需要申请新的溢出桶并建立链接关系，因此在上面查找溢出
40、桶中空闲单元时，进行指针 t的后移 “t=t- Link前应先用 front记录 t的值，以便于后面建立链接关系。所以 (3)空缺处应给 front置初值，即所填写的内容是 “front=BucketIndex”，或 “front=Bucket+Index”等其他等价形式。 (4)空缺处用于判断该溢出桶是否已满，即所填写的内容是 “k=ITEMS(或 k =ITEMS)”。如果该溢出 桶已满，则继续查找下一个溢出桶，直到查找到空闲单元为止。 若所有溢出桶都不存在空闲单元 (即 t=NULL)，则申请新的溢出桶，并将新的溢出桶的首地址保存在原有的最后一个溢出桶的 Link域中 (即 front-
41、 Link=s)。因此 (5)空缺处所填写的内容是 “t=NULL”， (6)空缺处用于建立新申请溢出桶的链接关系 “front-Link=s”。 18 【正确答案】 Observer(观察者 )模式的设计意图是：定义对象间的一种一对多的依赖关系，以便当一个对象的状态发生改变时，所有依赖于它的对象都得到 通知并被自动更新。首先， DocExplorer需要知道 OfficeDoc是一个类，但由于OfficeDoc定义在 DocExplorer之后，因此需要在 DocExplorer类的定义前加上 class OfficeDoc的声明，即 (1)空缺处所填写的内容是： class OfficeD
42、oc。 (2)空缺处可根据程序最后的构造函数的实现知道，应该填写 OfficeDoc。在观察者模式中，不同的观察者更新自身的方法不同，因此 (3)空缺处应填写 virtual，而且程序最后的 “=0”也表明是一个纯虚拟函数。 由 (4)空缺处所在行的程序注释说明可知，所有与 OfficeDoc相关联的对象更新自身状态，因此需要使用 update函数。但 update函数的参数是一个 OfficeDoc类的对象，所以参数应该为 this。 (5)空缺处所在行语句的功能是，将 OfficeDoc类的对象和 DocExplorer类的对象相关联，关联的函数是 OfficeDoc中的 attach方法
43、，其参数是一个 DocExplorer对象，使用 this能够表示当前的对象，因此该空缺处应填写 attach(this)。 19 【正确答案】 Observer(观察者 )模式的设计意图是：定义对象间的一种一对多的依赖关系，以便当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。 (1)空缺处观察者对象更新自身的状态，更新的数据应该来自被观察者对象，所以此处应该为一 Subject，因此 (1)空缺处所填写的内容是： Subject subject。同理， (5)空缺处与 (1)空缺处所填写的内容是相同的。 notifyObservers方法通知所有的观察者对象更新自身的状态，因此 (2)空缺处应该返回所有的观察者对象，调用方法 Observers()即可获得。 (3)空缺处对每个观察者对象更新状态，所以应该调用 update方法， update方法需要此被观察者对象作为参数，所以使用 this宋获取对象自身。 DocExplorer是一个观察者，因此需要实现接口 Observer，即 (4)空缺处所填写的内容是： Observer。
