1、计算机水平考试中级软件设计师 2014年上半年下午真题及答案解析(总分：90.00，做题时间：150 分钟)试题一(共 15分) 阅读下列说明和图，回答问题 1至问题 4，将解答填入答题纸的对应栏内。 说明 某巴士维修连锁公司欲开发巴士维修系统，以维护与维修相关的信息。该系统的主要功能如下： 1)记录巴士 ID和维修问题。巴士到车库进行维修，系统将巴士基本信息和 ID记录在巴士列表文件中，将待维修机械问题记录在维修记录文件中，并生成维修订单。 2)确定所需部件。根据维修订单确定维修所需部件，并在部件清单中进行标记。 3)完成维修。机械师根据维修记录文件中的待维修机械问题，完成对巴士的维修，登记
2、维修情况；将机械问题维修情况记录在维修记录文件中，将所用部件记录在部件清单中，并将所用部件清单发送给库存管理系统以对部件使用情况进行监控。巴士司机可查看己维修机械问题。 4)记录维修工时。将机械师提供的维修工时记录在人事档案中；将维修总结发送给主管进行绩效考核。 5)计算维修总成本。计算部件清单中实际所用部件、人事档案中所用维修工时的总成本；将维修工时和所用部件成本详细信息给会计进行计费。 现采用结构化方法对巴士维修系统进行分析与设计，获得如图 1-1所示的上下文数据流图和图 1-2所示的 0层数据流图。 （分数：15.00）(1).问题 1(5分) 使用说明中的词语，给出图 1-1中的实体
3、E1E5 的名称。（分数：3.75）_(2).问题 2(4分) 使用说明中的词语，给出图 1-2中的数据存储 D1D4 的名称。（分数：3.75）_(3).问题 3(3分) 说明图 1-2中所存在的问题。（分数：3.75）_(4).问题 4(3分) 根据说明和图中术语，采用补充数据流的方式，改正图 1-2中的问题。要求给出所补充数据流的名称、起点和终点。（分数：3.75）_试题二(共 15分)阅读下列说明和图，回答问题 1至问题 3，将解答填入答题纸的对应栏内。说明某家电销售电子商务公司拟开发一套信息管理系统，以方便对公司的员工、家电销售、家电厂商和客户等进行管理。需求分析(1)系统需要维护电
4、子商务公司的员工信息、客户信息、家电信息和家电厂商信息等。员工信息主要包括：工号、姓名、性别、岗位、身份证号、电话、住址，其中岗位包括部门经理和客服等。客户信息主要包括：客户 ID、姓名、身份证号、电话、住址、账户余额。家电信息主要包括：家电条码、家电名称、价格、出厂日期、所属厂商。家电厂商信息包括：厂商 ID、厂商名称、电话、法人代表信息、厂址。(2)电子商务公司根据销售情况，由部门经理向家电厂商订购各类家电。每个家电厂商只能由一名部门经理负责。(3)客户通过浏览电子商务公司网站查询家电信息，与客服沟通获得优惠后，在线购买。概念模型设计根据需求阶段收集的信息，设计的实体联系图(不完整)如图
5、2-1所示。（分数：15.00）(1).问题 1(6分) 补充图 2-1中的联系和联系的类型。（分数：5.00）_(2).问题 2(6分) 根据图 2-1，将逻辑结构设计阶段生成的关系模式中的空(1)(3)补充完整。用下划线指出“家电”、“家电厂商”和“购买”关系模式的主键。（分数：5.00）_(3).问题 3(3分) 电子商务公司的主营业务是销售各类家电，对账户有余额的客户，还可以联合第三方基金公司提供理财服务，为此设立客户经理岗位。客户通过电子商务公司的客户经理和基金公司的基金经理进行理财。每名客户只由一名客户经理和一名基金经理负责，客户经理和基金经理均可负责多名客户。请根据该要求，对图
6、2-1进行修改，画出修改后的实体间联系和联系的类型。（分数：5.00）_试题三(共 15分) 阅读下列说明和图，回答问题 1至问题 3，将解答填入答题纸的对应栏内。 说明 某高校图书馆欲建设一个图书馆管理系统，目前已经完成了需求分析阶段的工作。功能需求均使用用例进行描述，其中用例“借书(Check Out Books)”的详细描述如下。 参与者：读者(Patron)。 典型事件流： 1输入读者 ID； 2确认该读者能够借阅图书，并记录读者 ID； 3输入所要借阅的图书 ID； 4根据图书目录中的图书 ID确认该书可以借阅，计算归还时间，生成借阅记录； 5通知读者图书归还时间。重复步骤 35，直
7、到读者结束借阅图书。 备选事件流： 2a若读者不能借阅图书，说明读者违反了图书馆的借书制度(例如，没有支付借书费用等) 知读者不能借阅，并说明拒绝借阅的原因； 用例结束。4a.读者要借阅的书无法外借 知读者本书无法借阅； 到步骤 3。 说明：图书的归还时间与读者的身份有关。如果读者是教师，图书可以借阅一年；如果是学生，则只能借阅 3个月。读者 ID中包含读者身份信息。 现采用面向对象方法开发该系统，得到如图 3-1所示的系统类模型(部分)；以及如图 3-2所示的系统操作“check Out(book ID)(借书)”的通信图(或协作图)。 （分数：15.00）(1).问题 1(8分) 根据说明
8、中的描述，以及图 3-1和图 3-2，给出图 3-1中 C1C4 处所对应的类名(类名使用图 3-1和图 3-2中给出的英文词汇)。（分数：5.00）_(2).问题 2(4分) 根据说明中的描述，以及图 3-1和图 3-2，给出图 3-2中 M1M4 处所对应的方法名(方法名使用图 3-1和图 3-2中给出的英文词汇)。（分数：5.00）_(3).问题 3(3分) 用例“借书”的备选事件流 4a中，根据借书制度来判定读者能否借阅图书。若图书馆的借书制度会不断地扩充，并需要根据图书馆的实际运行情况来调整具体使用哪些制度。为满足这一要求，在原有类设计的基础上，可以来用何种设计模式?简要说明原因。（
9、分数：5.00）_试题四(共 15分) 阅读下列说明和 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏内。 说明 采用归并排序对 n个元素进行递增排序时，首先将 n个元素的数组分成各含 n2 个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。 下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下： arr：持排序数组 p，q，r：一个子数组的位置为从 p到 q，另一个子数组的位置为从 q+1到 r begin，end：待排序数组的起止位置 left，right：临时存放待合并的两个子数组 n1，n2：两个子数组的长度 k，
10、j，k：循环变量 mid：临时变量 C 代码 （分数：15.00）(1).问题 1(8分) 根据以上说明和 C代码，填充 C代码中的空(1)(4)。（分数：5.00）_(2).问题 2(5分) 根据题干说明和以上 C代码，算法采用了_(5)_算法设计策略。 分析时间复杂度时，列出其递归式为_(6)_，解得渐进时间复杂度为_(7)_(用 O符号表示)。空间复杂度为_(8)_(用 O符号表示)。（分数：5.00）_(3).问题 3(2分) 两个长度分别为 n1和 n2的已排好序的子数组进行归并，根据上述 C代码，则元素之间比较次数为_(9)_。（分数：5.00）_1.试题五(共 15分) 阅读下列
11、说明和 C+代码，将应填入_(n)_处的字句写在答题纸的对应栏内。 说明 某实验室欲建立一个实验室环境监测系统，能够显示实验室的温度、湿度以及洁净度等环境数据。当获取到最新的环境测量数据时，显示的环境数据能够更新。 现在采用观察者(Observer)模式来开发该系统。观察者模式的类图如图 5-1所示。 C+代码 （分数：15.00）_2.试题六(共 15分) 阅读下列说明和 Java代码，将应填入_(n)_处的字句写在答题纸的对应栏内。 说明 某实验室欲建立一个实验室环境监测系统，能够显示实验室的温度、湿度以及洁净度等环境数据。当获取到最新的环境测量数据时，显示的环境数据能够更新。 现在采用观
12、察者(Observer)模式来开发该系统。观察者模式的类图如图 6-1所示。 java代码 （分数：15.00）_计算机水平考试中级软件设计师 2014年上半年下午真题答案解析(总分：90.00，做题时间：150 分钟)试题一(共 15分) 阅读下列说明和图，回答问题 1至问题 4，将解答填入答题纸的对应栏内。 说明 某巴士维修连锁公司欲开发巴士维修系统，以维护与维修相关的信息。该系统的主要功能如下： 1)记录巴士 ID和维修问题。巴士到车库进行维修，系统将巴士基本信息和 ID记录在巴士列表文件中，将待维修机械问题记录在维修记录文件中，并生成维修订单。 2)确定所需部件。根据维修订单确定维修所
13、需部件，并在部件清单中进行标记。 3)完成维修。机械师根据维修记录文件中的待维修机械问题，完成对巴士的维修，登记维修情况；将机械问题维修情况记录在维修记录文件中，将所用部件记录在部件清单中，并将所用部件清单发送给库存管理系统以对部件使用情况进行监控。巴士司机可查看己维修机械问题。 4)记录维修工时。将机械师提供的维修工时记录在人事档案中；将维修总结发送给主管进行绩效考核。 5)计算维修总成本。计算部件清单中实际所用部件、人事档案中所用维修工时的总成本；将维修工时和所用部件成本详细信息给会计进行计费。 现采用结构化方法对巴士维修系统进行分析与设计，获得如图 1-1所示的上下文数据流图和图 1-2
14、所示的 0层数据流图。 （分数：15.00）(1).问题 1(5分) 使用说明中的词语，给出图 1-1中的实体 E1E5 的名称。（分数：3.75）_正确答案：( E1：巴士司机 E2：机械师 E3：会计 E4：主管 E5：库存管理系统)解析：试题一分析 本题考查的是 DFD的应用，属于比较传统的题目，考查点也与往年类似。 本问题考查的是顶层 DFD。顶层 DFD通常用来确定系统边界，其中只包含一个唯一的加工(即待开发的系统)、外部实体以及外部实体与系统之间的输入输出数据流。题目要求填充的正是外部实体。 从题干说明 1)没有明确说明由巴士到车库后由谁提供待维修问题，图 1-1中的 E1，考察说
15、明中 3)中最后一句说明“巴士司机可查看己维修机械问题”可以看出，从系统到巴士司机有输出数据流“己维修机械问题”，可知 El为巴土司机。从 2)中“机械师根据维修记录文件中的待维修机械问题，完成对巴士的维修，登记维修情况”；再看说明 4)中机械师提供维修工时，可以看出，从 E2到系统有输入数据流“维修工时”、输出数据流“待维修机械问题”，可知 E2为机械师，还将维修总结发送给主管，即系统到 E4有输出数据流“维系总结”，可知 E4为主管。从说明 5)将维修工时和所用部件成本详细信息给会计，从系统到 E3有输出数据流“维修工时和所用部件成本详细信息”，可知 E3为会计。说明 3)中将所用部件清单
16、发送给库存管理系统以对部件使用情况进行监控，及系统到 E5有输出数据流“所用部件清单”，可知 E5为库存管理系统。(2).问题 2(4分) 使用说明中的词语，给出图 1-2中的数据存储 D1D4 的名称。（分数：3.75）_正确答案：( D1：巴士列表文件 D2：维修记录文件 D3：部件清单 D4：人事档案)解析： 本问题考查 0层数据流图中的数据存储。系统中的主要功能与图 1-2中的处理一一对应，1)对应处理“记录巴士 ID和维修问题”，将巴士 ID记录在巴士列表文件中，可知 D1为巴士列表文件。说明 2)对应处理“确定所需部件”，将维修所需部件在部件清单中进行标记，可知以 D3为部件清单。
17、说明 1)中将待维修机械问题记录在维修记录文件中，可知 D2为维修记录文件。说明 4)对应处理“记录维修工时”，描述了将机械师提供的维修工时记录在人事档案中，可以判定 D4是人事档案。(3).问题 3(3分) 说明图 1-2中所存在的问题。（分数：3.75）_正确答案：( 图 1-2中处理 3只有输出数据流，没有输入数据流。D2 和 D3是黑洞，只有输入的数据流，没有输出的数据流。父图与子图不平衡，图 1-2中没有图 1-1中的数据流“维修情况”。)解析： 本问题考查 0层数据流图中的数据流。分析图 1-2，可以发现，处理 3只有输出数据流没有输入数据流，D2 和 D3只有输入数据流，而没有输
18、出流，造成黑洞。另外，对照图 1-2和图 1-1，发现图 1-1中从 E2输入的数据流维修工时维修情况，在图 1-2中只有维修工时，造成父图与子图不平衡。(4).问题 4(3分) 根据说明和图中术语，采用补充数据流的方式，改正图 1-2中的问题。要求给出所补充数据流的名称、起点和终点。（分数：3.75）_正确答案：( )解析： 针对问题 3分析图 1-2中存在的问题，题目要求以补充数据流的方式解决，进一步分析说明，说明 3)对应处理“完成维修”，机械师根据维修记录文件中的待维修机械问题完成对巴士的维修，可知处理完成维修需要从维修记录文件读取待维修问题，补充一条从 D2到处理 3的数据流“待维修
19、机械问题”。说明 5)对应处理“计算维修总成本”，需要计算部件清单中实际所用部件，补充从部件清单到计算总成本的数据流“实际所用部件”。说明 3)中机械师要登记维修情况，判定图 1-2中缺少了 E2到处理 3的数据流“维修情况”。 到此为止所有缺失的数据流都补齐了，也解决了问题 3中的平衡问题、处理只有输出数据流没有输入数据流的问题，D2 和 D3也既有输入数据流，又有输出数据流。试题二(共 15分)阅读下列说明和图，回答问题 1至问题 3，将解答填入答题纸的对应栏内。说明某家电销售电子商务公司拟开发一套信息管理系统，以方便对公司的员工、家电销售、家电厂商和客户等进行管理。需求分析(1)系统需要
20、维护电子商务公司的员工信息、客户信息、家电信息和家电厂商信息等。员工信息主要包括：工号、姓名、性别、岗位、身份证号、电话、住址，其中岗位包括部门经理和客服等。客户信息主要包括：客户 ID、姓名、身份证号、电话、住址、账户余额。家电信息主要包括：家电条码、家电名称、价格、出厂日期、所属厂商。家电厂商信息包括：厂商 ID、厂商名称、电话、法人代表信息、厂址。(2)电子商务公司根据销售情况，由部门经理向家电厂商订购各类家电。每个家电厂商只能由一名部门经理负责。(3)客户通过浏览电子商务公司网站查询家电信息，与客服沟通获得优惠后，在线购买。概念模型设计根据需求阶段收集的信息，设计的实体联系图(不完整)
21、如图 2-1所示。（分数：15.00）(1).问题 1(6分) 补充图 2-1中的联系和联系的类型。（分数：5.00）_正确答案：( )解析：试题二分析 本题考查数据库设计，属于比较传统的题目，考查点也与往年类似。 本问题考查数据库的概念结构设计，题目要求补充完整实体联系图中的联系和联系的类型。 根据题目的需求描述可知，一个家电厂商可以供应多台家电，而一台家电只能对应一个家电厂商，因此“家电厂商”和“家电”之间存在“供应”联系，联系的类型为一对多(1：*，或 1：m)。 根据题目的需求描述可知，“员工”和“部门经理”之间存在一个包含关系。 根据题目的需求描述可知，“客户”、“客服”和“家电”之
22、间存在“购买”联系，联系的类型为多对多对多(*：*：*，或 m：n：o)。(2).问题 2(6分) 根据图 2-1，将逻辑结构设计阶段生成的关系模式中的空(1)(3)补充完整。用下划线指出“家电”、“家电厂商”和“购买”关系模式的主键。（分数：5.00）_正确答案：( (1)厂商 ID (2)部门经理工号 或 经理工号 或 员工工号 (3)客户 ID、客服工号、家电条码 )解析： 本问题考查数据库的逻辑结构设计，题目要求补充完整各关系模式，并给出各关系模式的主键。 根据实体联系图和需求描述，“家电”和“家电厂商”存在多对一的关系，在家电关系中需要记录家电厂商的主键，也就是“厂商 ID”。所以，
23、对于“家电”关系模式，需补充属性“厂商 ID”。“家电条码”为“家电”关系的主键。 根据实体联系图和需求描述，“家电厂商”和“部门经理”之间存在多对一的关系，在家电厂商关系中需要记录部门经理的主键，也就是“部门经理工号”(或“经理工号”、或“员工工号”)。“厂商 ID”为“家电厂商”的主键。 根据实体联系图和需求描述，“客户”、“客服”和“家电”之间的多对多对多的“购买”联系。因为是多对多对多联系，所以“购买”联系需要单独作为一个关系，这个关系需要记录“客户”、“客服”和“家电”的主键。所以，对于“购买”关系模式，需补充属性“客户 ID”“客服工号”和“家电条码”。“订购单号”为“购买”的主键
24、。(3).问题 3(3分) 电子商务公司的主营业务是销售各类家电，对账户有余额的客户，还可以联合第三方基金公司提供理财服务，为此设立客户经理岗位。客户通过电子商务公司的客户经理和基金公司的基金经理进行理财。每名客户只由一名客户经理和一名基金经理负责，客户经理和基金经理均可负责多名客户。请根据该要求，对图 2-1进行修改，画出修改后的实体间联系和联系的类型。（分数：5.00）_正确答案：( )解析： 本问题考查数据库的概念结构设计，根据新增的需求增加实体联系图中的实体的联系和联系的类型。 根据问题描述，需要新增“客户经理”，包含于“员工”。 根据问题描述，客户只由一名客户经理和一名基金经理负责，
25、客户经理和基金经理均可负责多名客户，所以“客户”、“客户经理”和“基金经理”之间存在一个“理财”联系，联系的类型为多对 1对 1(*：1：1，或 m：1：1)。试题三(共 15分) 阅读下列说明和图，回答问题 1至问题 3，将解答填入答题纸的对应栏内。 说明 某高校图书馆欲建设一个图书馆管理系统，目前已经完成了需求分析阶段的工作。功能需求均使用用例进行描述，其中用例“借书(Check Out Books)”的详细描述如下。 参与者：读者(Patron)。 典型事件流： 1输入读者 ID； 2确认该读者能够借阅图书，并记录读者 ID； 3输入所要借阅的图书 ID； 4根据图书目录中的图书 ID确
26、认该书可以借阅，计算归还时间，生成借阅记录； 5通知读者图书归还时间。重复步骤 35，直到读者结束借阅图书。 备选事件流： 2a若读者不能借阅图书，说明读者违反了图书馆的借书制度(例如，没有支付借书费用等) 知读者不能借阅，并说明拒绝借阅的原因； 用例结束。4a.读者要借阅的书无法外借 知读者本书无法借阅； 到步骤 3。 说明：图书的归还时间与读者的身份有关。如果读者是教师，图书可以借阅一年；如果是学生，则只能借阅 3个月。读者 ID中包含读者身份信息。 现采用面向对象方法开发该系统，得到如图 3-1所示的系统类模型(部分)；以及如图 3-2所示的系统操作“check Out(book ID)
27、(借书)”的通信图(或协作图)。 （分数：15.00）(1).问题 1(8分) 根据说明中的描述，以及图 3-1和图 3-2，给出图 3-1中 C1C4 处所对应的类名(类名使用图 3-1和图 3-2中给出的英文词汇)。（分数：5.00）_正确答案：( C1： Patron C2： Book C3：Catalog C4： CheckoutSessionContro11er)解析：试题三分析 本题属于经典的考题，主要考查面向对象分析方法以及 UML类图和通信图的相关知识。问题 1 说明中给出了一个具体用例的详细描述，给出了其中的一个系统操作“checkoutbookID)(借书)”的通信图，需要
28、考生利用通信图中的信息来补充类图中缺失的部分。 通信图(communication diagram)强调收发消息的对象的结构组织，在早期的版本中也被称作协作图。通信图强调参加交互的对象的组织。产生一张通信图，首先要将参加交互的对象作为图的顶点，然后把连接这些对象的链表示为图的弧，最后用对象发送和接收的消息来修饰这些链。这就提供了在协作对象的结构组织的语境中观察控制流的一个清晰的可视化轨迹。 消息 checkOut(bookID)的接收者是类 CheckoutSessionController的对象，说明类CheckoutSessionController中应该包含这一方法，否则无法响应该条消息
29、。由图 3-1可知，C4 处所代表的类应该是 CheckoutSessionController。 消息 find(bookID)的接收者是类 Book，同理，由图 3-1可知，C2处对应的类应该是 Book。 根据用例描述，图书信息是包含在图书目录中，所以 C3处对应的类应该是Catalog，C1 处对应的就应该是 Patron。(2).问题 2(4分) 根据说明中的描述，以及图 3-1和图 3-2，给出图 3-2中 M1M4 处所对应的方法名(方法名使用图 3-1和图 3-2中给出的英文词汇)。（分数：5.00）_正确答案：( M1：getForCheckOut M2：isFaculty
30、M3：circulates M4：recordBookLoan)解析： 图 3-1填充完整之后，图 3-2的空缺就比较容易填写了。在通信图中，对象之间传递的消息就对应着接收对象中的方法。M1 对应的就是类 Catalog中的方法，由图 3-1可知，M1 对应的是getForCheckout。 M3 对应的应该是类 Book中的方法。由图 3-1可知，Book 中有 3个方法，find 和checkOut已经出现在通信图上了，所以 M3应该是 circulates。 M2 和 M4是类 Patron中的方法。Patron中有 2个方法。通信图中的消息是有序号的，这个序号表示了消息的时间顺序，也就
31、是说发送 M2的时间要早于消息 M4，因此必须区分类 Patron中两个方法使用的先后顺序。在用例描述中特别指出：图书的归还时间与读者的身份有关。计算还书及借书费用时，需先确定读者的身份，因此方法 isFaculty应该先被调用，所以 M2对应 isFaculty，M4 对应 recordBookLoan。(3).问题 3(3分) 用例“借书”的备选事件流 4a中，根据借书制度来判定读者能否借阅图书。若图书馆的借书制度会不断地扩充，并需要根据图书馆的实际运行情况来调整具体使用哪些制度。为满足这一要求，在原有类设计的基础上，可以来用何种设计模式?简要说明原因。（分数：5.00）_正确答案：( 解
32、答：策略模式。 策略模式定义了一系列算法，并将每个算法封装起来，而且使它们可以相互替换。策略模式让算法独立于使用它们的客户而变化。适用于需要在不同情况下使用不同的策略(算法)，或者策略还可能在未来用其他方式来实现。)解析： 本题在设计类时使用到了策略模式。 策略模式定义了一系列的算法，把它们一个个封装起来，并且使它们可以相互替换此模式使得算法可以独立于使用它们的客户而变化。策略模式的结构如下图所示。 试题四(共 15分) 阅读下列说明和 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏内。 说明 采用归并排序对 n个元素进行递增排序时，首先将 n个元素的数组分成各含 n2 个元素的两个
33、子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。 下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下： arr：持排序数组 p，q，r：一个子数组的位置为从 p到 q，另一个子数组的位置为从 q+1到 r begin，end：待排序数组的起止位置 left，right：临时存放待合并的两个子数组 n1，n2：两个子数组的长度 k，j，k：循环变量 mid：临时变量 C 代码 （分数：15.00）(1).问题 1(8分) 根据以上说明和 C代码，填充 C代码中的空(1)(4)。（分数：5.00）_正确答案：(1) kr 或 kr+1 (2)a
34、rrkrightj (3)beginend (4)mergeSort(arr，mid+1，end)解析：试题四分析 本题考查算法设计、分析和 C程序实现的知识，属于传统题目，考查点也与往年类似。归并排序是一种经典的排序算法，基本思想：把 n个元素构成的数组分成两个 n2 个元素构成的子数组，再进一步划分，一直到每个子数组仅包含 1个元素，此时再把两两有序的数组合并成更大的有序数组，一直到整个数组有序为止。 问题 1 本问题考查算法的实现。C 程序中有两个函数，merge 函数将两个有序数组合并成一个更大的有序数组。归并过程是首先将两个有序的子数组的元素分别放到 left和 right数组中，然
35、后依次比较这两个数组中的元素，从小到大把元素放到 arr数组的特定元素中。包含空格(1)的 for循环中，给出了将 left和 right元素放入 arr中，放入的位置是从 p到 r，因此，空格(1)填写kr。在比较 lefti和 rightj元素时，若 leftirightj，则应该把 rightj的值放入 arrk中，因此空格(2)填写 arrkrightj。mergeSort 函数进行数组的排序。若数组元素个数大于 1，则继续划分，因此空格(3)填写 beginend。将数组从 arrbegin到 arrend划分为 arrbegin到 arrmid和arrmid+1到 arrend两个
36、部分，因此空格(4)填写 mergeSort(arr，mid+1，end)。(2).问题 2(5分) 根据题干说明和以上 C代码，算法采用了_(5)_算法设计策略。 分析时间复杂度时，列出其递归式为_(6)_，解得渐进时间复杂度为_(7)_(用 O符号表示)。空间复杂度为_(8)_(用 O符号表示)。（分数：5.00）_正确答案：(5)分治 (6)T(n)2T(n2)+n 或 T(n)2T(n2)+f(n) (f(n)为线性函数) (7)O(nlgn) (8)O(n)解析： 本问题考查算法的设计策略和时间复杂度，归并排序算法是一个典型的分治算法。每次将一个规模为 n的问题变成两个规模为 n/2
37、的子问题，划分时直接从中间分开，因此划分采用 O(1)的时间，然后是递归求解两个子问题，根据 merge函数代码，合并的时间是线性时间 O(n)。因此递归式为 T(n)2T(n2)+f(n)，f(n)为线性函数。用主方法求解，得到时间复杂度为 O(nlgn)。由于在归并过程中，需要 left和 right两个辅助数组，其规模为待排序的数组长度，即 O(n)。(3).问题 3(2分) 两个长度分别为 n1和 n2的已排好序的子数组进行归并，根据上述 C代码，则元素之间比较次数为_(9)_。（分数：5.00）_正确答案：(9)n1+n2)解析： 本问题考查对算法的进一步分析。元素之间的比较次数就是
38、 merge函数的最后一个 for循环体执行的次数，由于 k从 p到 r，故循环体执行次数为 r-p+1次，即 n1+n2次。1.试题五(共 15分) 阅读下列说明和 C+代码，将应填入_(n)_处的字句写在答题纸的对应栏内。 说明 某实验室欲建立一个实验室环境监测系统，能够显示实验室的温度、湿度以及洁净度等环境数据。当获取到最新的环境测量数据时，显示的环境数据能够更新。 现在采用观察者(Observer)模式来开发该系统。观察者模式的类图如图 5-1所示。 C+代码 （分数：15.00）_正确答案：(1)Subject (2)(*it)-update(temperature，humidity
39、，cleanness) (3)notifyObservers() (4)measurementsChanged() (5)Observer (6)envData-registerObserver(this)解析：试题五分析 本题考察观察者(Observer)模式的概念及应用。 观察者模式定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。 Observer模式适用于： 当一个抽象模型有两个方面，其中一个方面依赖于另一个方面。将这两者封装在独立地对象中以使它们可以各自独立地改变和复用。 当对一个对象的改变需要同时改变其他对象，而不知道具体有多少
40、对象有待改变时。 当一个对象必须通知其他对象，而它又不能假定其他对象是谁，即：不希望这些对象是紧耦合的。 观察者模式的结构如下图所示，其中： 2.试题六(共 15分) 阅读下列说明和 Java代码，将应填入_(n)_处的字句写在答题纸的对应栏内。 说明 某实验室欲建立一个实验室环境监测系统，能够显示实验室的温度、湿度以及洁净度等环境数据。当获取到最新的环境测量数据时，显示的环境数据能够更新。 现在采用观察者(Observer)模式来开发该系统。观察者模式的类图如图 6-1所示。 java代码 （分数：15.00）_正确答案：(1) Subject (2)observer.update(temperature，humidity，cleanness) (3)notifyOb
