1、中级软件设计师 2013 年 11 月下午试题及答案解析(总分：90.00，做题时间：90 分钟)一、本试卷共六道题，试题一至试题四是必答，试(总题数：1，分数：15.00)说明 某大学欲开发一个基于 Web 的课程注册系统，该系统的主要功能如下： 1验证输入信息 (1)检查学生信息：检查学生输入的所有注册所需信息。如果信息不合法，返回学生信息不合法提示；如果合法，输出合法学生信息。 (2)检查学位考试结果：检查学生提供的学位考试结果。如果不合法，返回学位考试结果不合法提示；如果合法，检查该学生注册资格。 (3)检查学生注册资格：根据合法学生信息和合法学位考试结果，检查该学生对欲选课程的注册资
2、格。如果无资格，返回无注册资格提示；如果有注册资格，则输出注册学生信息(包含选课学生标识)和欲注册课程信息。 2处理注册申请 (1)存储注册信息：将注册学生信息记录在学生库。 (2)存储所注册课程：将选课学生标识与欲注册课程进行关联，然后存入课程库。 (3)发送注册通知：从学生库中读取注册学生信息，从课程库中读取所注册课程信息，给学生发送接受提示；给教务人员发送所注册课程信息和已注册学生信息。 现采用结构化方法对课程注册系统进行分析与设计，获得如图 1 所示的 0 层数据流图和图 2 所示的 1 层数据流图。 图 1 某课程注册系统 0 层数据流图（分数：15.00）(1).使用说明中的词语，
3、给出图 1 中的实体 E1 和 E2 的名称。（分数：3.75）_(2).使用说明中的词语，给出图 2 中的数据存储 D1 和 D2 的名称。（分数：3.75）_(3).根据说明和图中术语。补充图 2 中缺失的数据流及其起点和终点。（分数：3.75）_(4).根据补充完整的图 1 和图 2，说明上层的哪些数据流是由下层的哪些数据流组合而成。（分数：3.75）_二、试题二(总题数：1，分数：15.00)说明 某快递公司为了方便管理公司物品运送的各项业务活动，需要构建一个物品运送信息管理系统。 需求分析结果 (1)快递公司有多个分公司，分公司信息包括分公司编号、名称、经理、办公电话和地址。每个分公
4、司可以有多名员工处理分公司的日常业务，每名员工只能在一个分公司工作。每个分公司由一名经理负责管理分公司的业务和员工，系统需要记录每个经理的任职时间。 (2)员工信息包括员工号、姓名、岗位、薪资、手机号和家庭地址。其中，员工号唯一标识员工信息的每一个元组。岗位包括经理、调度员、业务员等。业务员根据客户提交的快件申请单进行快件受理事宜，一个业务员可以受理多个客户的快件申请，一个快件申请只能由一个业务员受理。调度员根据已受理的申请单安排快件的承运事宜，例如：执行承运的业务员、运达时间等。一个业务员可以执行调度员安排的多个快件的承运业务。 (3)客户信息包括客户号、单位名称、通信地址、所属省份、联系人
5、、联系电话、银行账号。其中，客户号唯一标识客户信息的每一个元组。当客户要寄快件时，先要提交快件申请单，申请号由系统自动生成。快件申请信息包括申请号、客户号、发件人、发件人电话、快件名称、运费、发出地、收件人、收件人电话、收件地址。其中，一个申请号对应唯一的一个快件申请，一个客户可以提交多个快件申请，但一个快件申请由唯一的一个客户提交。 概念模型设计 根据需求阶段收集的信息，设计的实体联系图(下图)和关系模式(不完整)如下： （分数：15.00）(1).根据问题描述，补充五个联系，完善题干图的实体联系图。联系名可用联系 1、联系 2、联系 3、联系 4 和联系 5 代替，联系的类型分为 1:1、
6、1:n 和 m:n(或 1:1、1:*和*:*)。（分数：5.00）_(2).(1)根据实体联系图，将关系模式中的空(a)(c)补充完整； (2)给出员工、申请单和安排承运关系模式的主键和外键。（分数：5.00）_(3).(1)客户关系的通信地址可以进一步分为邮编、省、市、街道，那么该属性是否属于简单属性，为什么?请用 100 字以内的文字说明。 (2)假设分公司需要增设一位经理的职位，那么分公司与经理之间的联系类型应修改为_，分公司的主键应修改为_。（分数：5.00）_三、试题三(总题数：1，分数：15.00)说明 某航空公司会员积分系统(CFrequentFlyer)的主要功能描述如下：
7、乘客只要办理该航空公司的会员卡，即可成为普卡会员(CBasic)。随着飞行里程数的积累，可以从普卡会员升级到银卡会员(CSilvet)或金卡会员(CCold)。非会员(CNonMember)不能累积里程数。 每年年末，系统根据会员在本年度累积的里程数对下一年会员等级进行调整。 普卡会员在一年内累积的里程数若满 25,000 英里但不足 50,000 英里，则自动升级为银卡会员；若累积的里程数在 50,000 英里以上，则自动升级为金卡会员。银卡会员在一年内累积的里程数若在 50,000 英里以上，则自动升级为金卡会员。 若一年内没有达到对应级别要求的里程数，则自动降低会员等级。金卡会员一年内累
8、积的里程数若不足25,000 英里，则自动降级为普卡会员；若累积的里程数达到 25,000 英里，但是不足 50,000 英里，则自动降级为银卡会员。银卡会员一年内累积的里程数若不足 25,000 英里，则自动降级为普卡会员。 采用面向对象方法对会员积分系统进行分析与设计，得到如图 1 所示的状态图和图 2 所示的类图。 图 1 某会员积分系统状态图（分数：15.00）(1).根据说明中的描述，给出图 1 中 S1S3 处所对应的状态以及 T1T3 处所对应的迁移的名称。（分数：5.00）_(2).根据说明中的描述，给出图 2 中 C1C4 所对应的类名(类名使用说明中给出的英文词汇)。（分数
9、：5.00）_(3).图 2 所示的类图中使用了哪种设计模式?在这种设计模式下，类 CFrequemFlver 必须具有的属性是什么?C1-C4 中的 travel 方法应具有什么功能? 本题考查面向对象分析中的类图、用例图。用例图描述了一组用例、参与者及他们之间的关系。包括以下几个部分：用例(Case)、参与者(Actor)。会员积分系统状态图就是一种用例图。用例视图中的参与者与系统外部的一个实体以某种方式参与了用例的执行过程；用例是一个叙述型文档，用来描述参与使用系统、完成某个事情时发生的顺序。（分数：5.00）_四、试题四(总题数：1，分数：15.00)说明 某工程计算中要完成多个矩阵相
10、乘(链乘)的计算任务。 两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算 A mn B np ，需要 mnp 次乘法运算。 矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵 A1 10100 ，A2 1005 ，A3 550 三个矩阵相乘为例，若按(A1A2)A3 计算，则需要进行 101005+10550=7500 次乘法运算；若按 A1(A2A3)计算，则需要进行 100550+1010050=75000 次乘法运算。可见不同的计算顺序对计算量有很大的影响。 矩阵链乘问题可描述为：给定 n 个矩
11、阵A1，A2，A n ，矩阵 A：的维数为 p i-l p i ，其中i=1，2，n。确定一种乘法顺序，使得这 n 个矩阵相乘时进行乘法的运算次数最少。 由于可能的计算顺序数量非常庞大，对较大的 n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若 A1A2An 的一个最优计算顺序从第 k 个矩阵处断开，即分为 A1A2Ak 和 Ak+1Ak+2An 两个子问题，则该最优解应该包含 A1A2Ak 的一个最优计算顺序和 Ak+1Ak+2An，的一个最优计算顺序。据此构造递归式， （分数：15.00）(1).根据以上说明和 C 代码，填充 C 代码中的空(1
12、)(4)。（分数：5.00）_(2).根据以上说明和 C 代码，该问题采用了_算法设计策略，时间复杂度为_(用 O 符号表示)。（分数：5.00）_(3).考虑实例 n=6，各个矩阵的维数：A1 为 510，A2 为 103，A3 为 312，A4 为 125，A5 为550，A6 为 506，即维数序列为 5，10，3，12，5，50，6。则根据上述 C 代码得到的一个最优计算顺序为_(用加括号方式表示计算顺序)，所需要的乘法运算次数为_。（分数：5.00）_五、从下列的 2 道试题(试题五和试题六)中任选(总题数：1，分数：15.00)说明 欲开发一个绘图软件，要求使用不同的绘图程序绘制不
13、同的图形。以绘制直线和圆形为例，对应的绘图程序如下表所示。 不同的绘图程序 DP1 DP2 绘制直线 draw_a_line(x1,y1,x2,y2) drawline(x1,x2,y1,y2) 绘制圆 draw_a_circle(x,y,r) drawcircle(x,y,r) 该绘图软件的扩展性要求，将不断扩充新的图形和新的绘图程序。为了避免出现类爆炸的情况，现采用桥接(Bridge)模式来实现上述要求，得到如下图所示的类图。 （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_六、试题六(总题数：1，分数：15.00)说明 欲开发一个绘
14、图软件，要求使用不同的绘图程序绘制不同的图形。以绘制直线和圆形为例，对应的绘图程序如下表所示。 不同的绘图程序 DP1 DP2 绘制直线 draw_a_line(x1,y1,x2,y2) drawline(x1,x2,y1,y2) 绘制圆 draw_a_circle(x,y,r) drawcircle(x,y,r) 该绘图软件的扩展性要求，将不断扩充新的图形和新的绘图程序。为了避免出现类爆炸的情况，现采用桥接(Bridge)模式来实现上述要求，得到如下图所示的类图。 （分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_中级软件设计师 2013
15、 年 11 月下午试题答案解析(总分：90.00，做题时间：90 分钟)一、本试卷共六道题，试题一至试题四是必答，试(总题数：1，分数：15.00)说明 某大学欲开发一个基于 Web 的课程注册系统，该系统的主要功能如下： 1验证输入信息 (1)检查学生信息：检查学生输入的所有注册所需信息。如果信息不合法，返回学生信息不合法提示；如果合法，输出合法学生信息。 (2)检查学位考试结果：检查学生提供的学位考试结果。如果不合法，返回学位考试结果不合法提示；如果合法，检查该学生注册资格。 (3)检查学生注册资格：根据合法学生信息和合法学位考试结果，检查该学生对欲选课程的注册资格。如果无资格，返回无注册
16、资格提示；如果有注册资格，则输出注册学生信息(包含选课学生标识)和欲注册课程信息。 2处理注册申请 (1)存储注册信息：将注册学生信息记录在学生库。 (2)存储所注册课程：将选课学生标识与欲注册课程进行关联，然后存入课程库。 (3)发送注册通知：从学生库中读取注册学生信息，从课程库中读取所注册课程信息，给学生发送接受提示；给教务人员发送所注册课程信息和已注册学生信息。 现采用结构化方法对课程注册系统进行分析与设计，获得如图 1 所示的 0 层数据流图和图 2 所示的 1 层数据流图。 图 1 某课程注册系统 0 层数据流图（分数：15.00）(1).使用说明中的词语，给出图 1 中的实体 E1
17、 和 E2 的名称。（分数：3.75）_正确答案：()解析：E1：学生 E2：教务人员 解析 该题以 Web 注册系统为载体来考核考生对数据流图知识点的掌握程度。从题目的问答形式上来看，和往年相似，要求补充外部实体、补充缺失数据流、找出外部存储。解答这类问题，有两个原则： (1)第一个原则是紧扣试题系统说明部分，数据流图与系统说明有着严格的对应关系，系统说明部分的每一句话都能对应到图中来，解题时可以一句一句的对照图来分析。 (2)第二个原则即数据的平衡原则，这一点在解题过程中也是至关重要的。数据平衡原则有两方面的含义，一方面是分层数据流图父子图之间的数据流平衡原则，另一方面是每张数据流图中输入
18、与输出数据流的平衡原则。 根据 0 层数据流图的课程注册系统可知：根据说明中向验证输入信息发送学位考试结果、学生信息、课程信息等可知 E1 为学生。同样，根据说明，经过处理注册申请向 E2 发送注册课程信息和已注册信息可知E2 为教务人员。(2).使用说明中的词语，给出图 2 中的数据存储 D1 和 D2 的名称。（分数：3.75）_正确答案：()解析：D1：学生库 D2：课程库解析 根据题目中说明，存储注册信息时，“将注册学生信息记录在学生库”，可知 D1 为学生库；存储注册课程时，关联后“存入课程库”，可 D2 为课程库。(3).根据说明和图中术语。补充图 2 中缺失的数据流及其起点和终点
19、。（分数：3.75）_正确答案：()解析：数据流 起点 终点 学生信息不合法 提示 1.1 或检查学生 信息 E1 或学生 无注册资格提示 1.3 或检查学生 注册资格 E1 或学生 学位考试结果不 合法提示 1.2 或检查学位 考试结果 E1 或学生 接受提示 2.3 或发送注册 通知 E1 或学生 解析 对应图 1 中的处理 1 验证输入信息的输出数据流“不合法提示”，不难发现，在题干图 1 中，处理 I.1 缺少了到实体学生的输出数据流“学生信息不合法提示”；处理 1.2 缺少了到实体学生的输出数据流“无注册资格提示”；处理 1.3 缺少了到实体学生的输出数据流“学位考试结果不合法提示”
20、。再查题干图 1 中处理 2，其输出数据流有三条，而题干图 2 中对题干图 1 中处理中，只包含了“所注册课程信息”和“已注册学生信息”两条数据流，缺失了“接受提示”。(4).根据补充完整的图 1 和图 2，说明上层的哪些数据流是由下层的哪些数据流组合而成。（分数：3.75）_正确答案：()解析：题干图 1 中不合法提示分解为题干图 2 中的三条数据流的组合：学生信息不合法提示、无注册资格提示、学位考试结果不合法提示。 题干图 1 中注册学生信息对应题干图 2 中注册学生信息和选课学生标识。 解析 本问题考查数据流的分解与组合。题干图 2 中对于说明中的功能出现了“学生信息不合法提示”、“无注
21、册资格提示”和“学位考试结果不合法提示”三条数据流，说明题干图 1 中的数据流“不合法提示”是由这三条数据流组合而成。题干图 1 中注册学生信息在题干图 2 中进一步分出注册学生信息和选课学生标识，即题干图 1 中注册学生信息是注册学生信息和选课学生标识的并集。二、试题二(总题数：1，分数：15.00)说明 某快递公司为了方便管理公司物品运送的各项业务活动，需要构建一个物品运送信息管理系统。 需求分析结果 (1)快递公司有多个分公司，分公司信息包括分公司编号、名称、经理、办公电话和地址。每个分公司可以有多名员工处理分公司的日常业务，每名员工只能在一个分公司工作。每个分公司由一名经理负责管理分公
22、司的业务和员工，系统需要记录每个经理的任职时间。 (2)员工信息包括员工号、姓名、岗位、薪资、手机号和家庭地址。其中，员工号唯一标识员工信息的每一个元组。岗位包括经理、调度员、业务员等。业务员根据客户提交的快件申请单进行快件受理事宜，一个业务员可以受理多个客户的快件申请，一个快件申请只能由一个业务员受理。调度员根据已受理的申请单安排快件的承运事宜，例如：执行承运的业务员、运达时间等。一个业务员可以执行调度员安排的多个快件的承运业务。 (3)客户信息包括客户号、单位名称、通信地址、所属省份、联系人、联系电话、银行账号。其中，客户号唯一标识客户信息的每一个元组。当客户要寄快件时，先要提交快件申请单
23、，申请号由系统自动生成。快件申请信息包括申请号、客户号、发件人、发件人电话、快件名称、运费、发出地、收件人、收件人电话、收件地址。其中，一个申请号对应唯一的一个快件申请，一个客户可以提交多个快件申请，但一个快件申请由唯一的一个客户提交。 概念模型设计 根据需求阶段收集的信息，设计的实体联系图(下图)和关系模式(不完整)如下： （分数：15.00）(1).根据问题描述，补充五个联系，完善题干图的实体联系图。联系名可用联系 1、联系 2、联系 3、联系 4 和联系 5 代替，联系的类型分为 1:1、1:n 和 m:n(或 1:1、1:*和*:*)。（分数：5.00）_正确答案：()解析：(2).(
24、1)根据实体联系图，将关系模式中的空(a)(c)补充完整； (2)给出员工、申请单和安排承运关系模式的主键和外键。（分数：5.00）_正确答案：()解析：(1)：(a)分公司编号 (b)申请号，客户号 (c)申请号，业务号 (2)： 关系模式 主键 外键 员工 员工号 分公司编号 申请单 申请号 客户号，业务员 安排乘运 申请号 业务员，调度员 解析 逻辑结构设计中，分公司信息包括分公司编号、名称、经理、办公电话和地址。每个分公司可以有多名员工处理分公司的日常业务，故主键为员工号；外键为分公司编号。 业务员根据客户提交的快件申请单进行快件受理事宣，一个业务员可以受理多个客户的快件申请，一个快件
25、申请只能由一个业务员受理，故主键为申请号，外键为客户号、业务员；调度员根据已受理的申请单安排快件的承运事宜，例如：执行承运的业务员、运达时间等。一个业务员可以执行调度员安排的多个快件的承运业务。故主键为申请号，外键为业务员、调度员。(3).(1)客户关系的通信地址可以进一步分为邮编、省、市、街道，那么该属性是否属于简单属性，为什么?请用 100 字以内的文字说明。 (2)假设分公司需要增设一位经理的职位，那么分公司与经理之间的联系类型应修改为_，分公司的主键应修改为_。（分数：5.00）_正确答案：()解析：(1)该属性不属于简单属性。因为简单属性是原子的、不可再分的，复合属性是可以细分为更小
26、的部分。客户关系的通信地址可以进一步分为邮编、省、市、街道，该属性属于复合属性。 (2)(d)1:n； (e)分公司编号，经理 解析 (1)简单属性是原子的、不可再分的，复合属性是可以细分为更小的部分。根据题意，客户关系的通信地址可以进一步分为邮编、省、市、街道，该属性属于复杂属性。 (2)分公司需要增设一位经理的职位，分公司可以有多位经理，所以分公司与经理之间的联系类型应该修改为 1:n，分公司主键应修改为分公司编号，经理。三、试题三(总题数：1，分数：15.00)说明 某航空公司会员积分系统(CFrequentFlyer)的主要功能描述如下： 乘客只要办理该航空公司的会员卡，即可成为普卡会
27、员(CBasic)。随着飞行里程数的积累，可以从普卡会员升级到银卡会员(CSilvet)或金卡会员(CCold)。非会员(CNonMember)不能累积里程数。 每年年末，系统根据会员在本年度累积的里程数对下一年会员等级进行调整。 普卡会员在一年内累积的里程数若满 25,000 英里但不足 50,000 英里，则自动升级为银卡会员；若累积的里程数在 50,000 英里以上，则自动升级为金卡会员。银卡会员在一年内累积的里程数若在 50,000 英里以上，则自动升级为金卡会员。 若一年内没有达到对应级别要求的里程数，则自动降低会员等级。金卡会员一年内累积的里程数若不足25,000 英里，则自动降级
28、为普卡会员；若累积的里程数达到 25,000 英里，但是不足 50,000 英里，则自动降级为银卡会员。银卡会员一年内累积的里程数若不足 25,000 英里，则自动降级为普卡会员。 采用面向对象方法对会员积分系统进行分析与设计，得到如图 1 所示的状态图和图 2 所示的类图。 图 1 某会员积分系统状态图（分数：15.00）(1).根据说明中的描述，给出图 1 中 S1S3 处所对应的状态以及 T1T3 处所对应的迁移的名称。（分数：5.00）_正确答案：()解析：S1：普卡会员 S2：银卡会员 S3：金卡会员 T1：25000=里程数5000C T2：里程数=50000 T3：里程数=500
29、00 解析 图中要求填充 S1、S2、S3 这三个状态以及它们之间的变迁关系。本题中会员有三种状态：普卡、金卡和银卡。普卡会员在一年内累积的里程数若满 25,000 英里但不足 50,000 英里，则自动升级为银卡会员；若累积的里程数在 50,000 英里以上，则自动升级为金卡会员。银卡会员在一年内累积的里程数若在 50,000 英里以上，则自动升级为金卡会员；所以，S1 为普卡会员、S2 为银卡会员、S3 为金卡会员。同样根据上述分析可知，T1、T2 就是 S2 和 S3 之间的转换原则，T3 是 S1-S2 的转换原则。(2).根据说明中的描述，给出图 2 中 C1C4 所对应的类名(类名
30、使用说明中给出的英文词汇)。（分数：5.00）_正确答案：()解析：C1：CNonMember C2：CBasic C3；CSilver C4：CGold 解析 本问题考查类图。考查类图的层次结构和多重度。图中更有 4 个非常明显的继承结构，即 C1C4 继承 CLevel，根据说明可知代表了四类不同的会员模式。(3).图 2 所示的类图中使用了哪种设计模式?在这种设计模式下，类 CFrequemFlver 必须具有的属性是什么?C1-C4 中的 travel 方法应具有什么功能? 本题考查面向对象分析中的类图、用例图。用例图描述了一组用例、参与者及他们之间的关系。包括以下几个部分：用例(Ca
31、se)、参与者(Actor)。会员积分系统状态图就是一种用例图。用例视图中的参与者与系统外部的一个实体以某种方式参与了用例的执行过程；用例是一个叙述型文档，用来描述参与使用系统、完成某个事情时发生的顺序。（分数：5.00）_正确答案：()解析：使用了 State 模式(状态模式)。 类 CFrequentFlyer 必须具有的属性：CLevel 的对象。 Travel 方法的功能：计算飞行里程数，根据里程数判断是否需要调整会员级别(跳转到不同的状态)。 状态模式的组成如下： 环境类(Context)：定义客户感兴趣的接口。维护一个 ConcreteState 子类的实例，这个实例定义当前状态。
32、 抽象状态类(State)：定义一个接口以封装与 Context 的一个特定状态相关的行为。 具体状态类(ConcreteState)：每一子类实现一个与 Context 的一个状态相关的行为。 系统类图中的类 CFrequentFlyer 对应上图中的环境类，因此类 CFrequentFlyer 应该有一个 CLevel 类的对象。 Travel 方法的功能：计算飞行里程数，根据里程数判断是否需要调整会员级别(跳转到不同的状态)。 解析 状态模式允许对象在内部状态变化时，变更其行为，并且修改其类。状态模式的类图如下： 四、试题四(总题数：1，分数：15.00)说明 某工程计算中要完成多个矩阵
33、相乘(链乘)的计算任务。 两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算 A mn B np ，需要 mnp 次乘法运算。 矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵 A1 10100 ，A2 1005 ，A3 550 三个矩阵相乘为例，若按(A1A2)A3 计算，则需要进行 101005+10550=7500 次乘法运算；若按 A1(A2A3)计算，则需要进行 100550+1010050=75000 次乘法运算。可见不同的计算顺序对计算量有很大的影响。 矩阵链乘问题可描述为：给定 n 个
34、矩阵A1，A2，A n ，矩阵 A：的维数为 p i-l p i ，其中i=1，2，n。确定一种乘法顺序，使得这 n 个矩阵相乘时进行乘法的运算次数最少。 由于可能的计算顺序数量非常庞大，对较大的 n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若 A1A2An 的一个最优计算顺序从第 k 个矩阵处断开，即分为 A1A2Ak 和 Ak+1Ak+2An 两个子问题，则该最优解应该包含 A1A2Ak 的一个最优计算顺序和 Ak+1Ak+2An，的一个最优计算顺序。据此构造递归式， （分数：15.00）(1).根据以上说明和 C 代码，填充 C 代码中的空(
35、1)(4)。（分数：5.00）_正确答案：()解析：in-P(2)j=i+P(3)constik+constk+1j+seqi*seqk+1*seqj+1(4)tempTraee=k； 解析 本题考查矩阵连乘最优调度问题，是一种动态规划算法。 上述算法中，第一个循环是给 n 个 costii附赋初值 0；第二个循环是个外循环，其循环变量 P 是矩阵连乘的规模，(p=1 时)先计算出所有规模为 2 的 costi，i+1，(p=2)再计算出所有规模为 3 的costi，i+2，最后计算出来的即为我们所求的 cost1，n-1，所以(1)填 in-p；第三个循环是内循环，其循环变量 i 表示矩阵连
36、乘的起始位置，即从 1，1+1，i，1+i，一直算到 n-1，n，所以(2)填 j=i+P；第四个循环用于计算 mincosti，j(ikj)；所以(3)填 costik+costk+1j+seqi*seqk+1*seqj+1；而(4)用于追踪取得最小花费代价的 k 值，即 tempTrace=k；而每一项的计算可在 O(1)时间里完成。(2).根据以上说明和 C 代码，该问题采用了_算法设计策略，时间复杂度为_(用 O 符号表示)。（分数：5.00）_正确答案：()解析：动态规划 O(n 3 ) 解析 求 min(iKj)要做 1 次比较；(k=i，i+1，i+1-1 而 j=i+l)，而第
37、 3 行的循环要做 n-1 次，故该循环执行完毕要做 l(n-1)次比较。第 2 的循环 1 从 1 做到 n-1，故该外循环执行完毕要做 O(n 3 )比较。此即该算法的时间复杂度。(3).考虑实例 n=6，各个矩阵的维数：A1 为 510，A2 为 103，A3 为 312，A4 为 125，A5 为550，A6 为 506，即维数序列为 5，10，3，12，5，50，6。则根据上述 C 代码得到的一个最优计算顺序为_(用加括号方式表示计算顺序)，所需要的乘法运算次数为_。（分数：5.00）_正确答案：()解析：(A1A2)(A3A4)(A5A6) 2010解析 启发式的思路是先把维度最大
38、的消掉，如 A5A6相乘之后，维度 50 就没有了，所以考虑这两个矩阵先相乘；然后是 A3A4 相乘之后，维度 12 就没有了，所以考虑这两个矩阵相乘；接着，A1A2 相乘之后，维度 10 就没有了，所以考虑这两个矩阵相乘这样可以确定相乘的顺序(A1A2)(A3A4)(A5A6)，需要的计算开销分别是5506=1500，3125=180.5103=150.356=90,536=90，把上述值相加，即1500+180+150+90+90=2010。五、从下列的 2 道试题(试题五和试题六)中任选(总题数：1，分数：15.00)说明 欲开发一个绘图软件，要求使用不同的绘图程序绘制不同的图形。以绘制
39、直线和圆形为例，对应的绘图程序如下表所示。 不同的绘图程序 DP1 DP2 绘制直线 draw_a_line(x1,y1,x2,ydrawline(x1,x2,y1,y2) 2) 绘制圆 draw_a_circle(x,y,r) drawcircle(x,y,r) 该绘图软件的扩展性要求，将不断扩充新的图形和新的绘图程序。为了避免出现类爆炸的情况，现采用桥接(Bridge)模式来实现上述要求，得到如下图所示的类图。 （分数：15.00）填空项 1:_ （正确答案：*unknown）填空项 1:_ （正确答案：*unknown）填空项 1:_ （正确答案：*unknown）填空项 1:_ （正确
40、答案：*unknown）填空项 1:_ （正确答案：*unknown）填空项 1:_ （正确答案：*unknown）解析：Shape(dp).六、试题六(总题数：1，分数：15.00)说明 欲开发一个绘图软件，要求使用不同的绘图程序绘制不同的图形。以绘制直线和圆形为例，对应的绘图程序如下表所示。 不同的绘图程序 DP1 DP2 绘制直线 draw_a_line(x1,y1,x2,y2) drawline(x1,x2,y1,y2) 绘 dr dr制圆 aw_a_circle(x,y,r) awcircle(x,y,r) 该绘图软件的扩展性要求，将不断扩充新的图形和新的绘图程序。为了避免出现类爆炸的情况，现采用桥接(Bridge)模式来实现上述要求，得到如下图所示的类图。 （分数：15.
