2018年下半年（下午）《软件设计师》真题

试卷预览

1 问答题 1分

某航空公司的会员积分系统将其会员划分为:普卡(Basic)、银卡(Silver)和金卡(Gold)

三个等级。非会员(Non Member)可以申请成为普卡会员。会员的等级根据其一年内累积的里程数进行调整。描述会员等级调整的状态图如图6-1所示。现采用状态(State)模式

实现上述场景，得到如图6-2所示的类图。

查看答案 开始考试

正确答案：

本题解析：

（1）abstract double travel(int miles,FrequentFlyer context)

（2）context.setState(new CSilver())

（3）context.setState(new CGold())

（4）context.setState(new CSilver())

（5）context.setState(new CBasic())

由代码可知，（1）空缺少一个抽象方法，根据下面的子类可以发现，子类都有double travel(int miles,FrequentFlyer context)方法，是从该抽象类中继承而来，因此（1）空应该补充这个方法，并加上abstract修饰。

（2）（3）（4）（5）可以从状态图中根据相关状态推断出来。

首先，（2）（3）属于普卡会员CBasic，从状态图和代码可以看到，当里程>=25000且＜5000时，会员等级应该从普卡会员CBasic升级到银卡会员CSilver，根据后面已有的代码，可以推断表示升级到银卡会员CSilver的表示方式为context.setState(new CSilver())；同理对于（3）空，在普卡会员CBasic状态，里程>=50000时，应该升级为金卡会员CGold，此时升级金卡CGold的表示方式为context.setState(new CGold())，以此类推，（4）（5）分别对应金卡会员CGold状态下，不同条件，降低的不同等级。因此（4）为降级为银卡会员CSilver，（5）为降级为普卡会员CBasic，对应的表示方式分别为context.setState(new CSilver())和context.setState(new CBasic())。

2 问答题 1分

【问题1】（8分）

根据题干说明，填充C代码中的空（1）-（4）。

【问题2】（4分）

根据题干说明和C代码，算法采用的设计策略为（5）。

算法的时间复杂度为（6）,（用O表示）。

【问题3】(3分〉

给定字符序列ACCGGUAGU，根据上述算法求得最大字符对数为（7）。

查看答案 开始考试

正确答案：

本题解析：

【问题1】

（1）max=C[i][j-1]

（2）t=i

（3）isMatch(B[t],B[j])，或isMatch(B[t],B[j])==1，或与其等价的形式

（4）C[1][n]

【问题2】

采用的算法策略：动态规划法

时间复杂度：O(n3)

【问题3】

最大字符对数：2

本题考查的是用动态规划法，以非递归方式实现。

根据题干，配对要求：

（1）满足四种组合之一；

（2）配对的2个字符间距至少有4个字符；

（3）若字符已配对，则其他配对不再考虑，也就是说1个字符不能配对2次，比如ACCCCUCCCCA，只有1组配对AU，U不能再与后面的A形成第2组配对；

（4）不交叉，2组配对字符位置能交叉，比如ACCCCCUUUUG，只有1组配对AU，CG与AU有交叉不能形成配对。

【问题1】

对于问题1代码填空，主要根据题干描述和代码上下文进行推导。

根据代码上下文可知，在整段代码中，缺少对变量max和t赋初值，这两个初值的赋值，应该填在空（1）和空（2）中，一般t作为循环变量，在for中进行赋值。

代码中有三层嵌套for循环。

其中第一层for循环，变量为k，取值范围从5到n-1，从题干描述，我们可以看到对于整个比较过程，要求字符对的位置相差大于4，因此此处的k值是字符对下标的差值；

第二层for循环，变量为i，取值范围从1到n-k，从题干描述，我们可以得出i是字符对较小的下标；

第三层for循环，变量为t，取值范围需要赋初值，并且t＜=j-4（此处有异议，与题干描述中的>4有不符，但不影响本题解题过程），从题干描述和递归式可以看到，t是中间字符下标，用来划分子问题的，并且从递归式我们可以得出，t的最小值应该从i开始，因此空（2）为t=i；

在第二层for循环内部，有j=i+k，根据代码和题干描述，可以得出j是字符对较大的下标，根据i和k的取值，可以看到j的取值范围为从6到n-1，对于空（1）作为max的初始赋值，又根据递归式，可以看到max应该在C[i][j-1]和C[i][t-1]+1+C[t+1][j-1]之间取最大值，在代码中可以看到if会判断max与C[i][t-1]+1+C[t+1][j-1]之间的大小，因此，max之前的赋值应该为C[i][j-1]，才能对二者进行比较，也就是说空（1）应该为max=C[i][j-1]。

空（3）在if判断中作为判断条件，根据递归式的条件和代码上下文，此处缺少字符匹配的判断，题干描述字符下标从1开始，因此，在比较过程中，实际比较的应该为B[t]和B[j]位置的字符，空（3）应该填写isMatch(B[t],B[j)，或isMatch(B[t],B[j])==1，或与其等价的形式。

空（4）作为整个函数的返回值，因此空（4）应该为C[1][n]为最终结果。

【问题2】

本题采取的是动态规划的策略，代码为三层嵌套循环时间复杂度为k*i*t，由于k的取值范围是6~n-1，i的取值范围是1~n-5，t的取值范围是1~n-5，都是与n的取值相关，因此本题的时间复杂度为O(n3)。

【问题3】

对于本题最大字符匹配对数，根据题干描述或代码推导，可以看到，字符序列ACCGGUAGU的最大匹配情况为，(b1,b6)，(b1,b9)或(b2,b8)，(b3,b8)，这两种情况的最大匹配对数都为2，因此本题答案（7）空为2。

3 问答题 1分

某集团公司拥有多个分公司，为了方便集团公司对分公司各项业务活动进行有效管理，集团公司决定构建一个信息系统以满足公司的业务管理需求。

【需求分析】

1.分公司关系需要记录的信息包括分公司编号、名称、经理、联系地址和电话。分公司编号唯一标识分公司信息中的每一个元组。每个分公司只有一名经理，负责该分公司的管理工作。每个分公司设立仅为本分公司服务的多个业务部门，如研发部、财务部、采购部、销售部等。

2.部门关系需要记录的信息包括部门号、部门名称、主管号、电话和分公司编号。部门号唯一标识部门信息中的每一个元组。每个部门只有一名主管，负责部门的管理工作。每个部门有多名员工，每名员工只能隶属于一个部门。

3.员工关系需要记录的信息包括员工号、姓名、隶属部门、岗位、电话和基本工资。其中，员工号唯一标识员工信息中的每一个元组。岗位包括：经理、主管、研发员、业务员等。

【概念模型设计】

根据需求阶段收集的信息，设计的实体联系图和关系模式(不完整)如图2-1所示:

【关系模式设计】

分公司（分公司编号，名称，（a），联系地址，电话）

部门（部门号，部门名称，（b），电话）

员工（员工号，姓名（c），电话，基本工资）

【问题1】（4分）

根据问题描述，补充4个联系，完善图2-1的实体联系图。联系名可用联系1、联系2、联系3和联系4代替，联系的类型为1:1、1:n和m:n（或1:1、1:*和*:*）。

【问题2】（5分）

根据题意，将关系模式中的空(a)-(c)补充完整。

【问题3】（4分）

给出“部门”和“员工”关系模式的主键和外键。

【问题4】（2分）

假设集团公司要求系统能记录部门历任主管的任职时间和任职年限，那么是否需要在数据库设计时增设一个实体？为什么？

查看答案 开始考试

正确答案：

本题解析：

【问题1】

联系1：分公司：经理，1:1

联系2：分公司：部门，1:*

联系3：部门：主管，1:1

联系4：部门：员工，1:*

【问题2】

（a）经理工号

（b）分公司编号，主管号

（c）隶属部门，岗位

【问题3】

部门

主键：部门号；外键：分公司编号，主管号

员工

主键：员工号；外键：隶属部门

【问题4】

不需要增加新的实体，对于任职情况，可以将任职时间和任职年限放入联系的属性即可，将部门与主管的联系单独形成关系模式，任职（部门号，主管工号，任职时间，任职年限）。

【问题1-3】

根据题干描述，可以找到对应答案。

“分公司关系需要记录的信息包括分公司编号、名称、经理、联系地址和电话。”（a）需要补充经理工号；

“部门关系需要记录的信息包括部门号、部门名称、主管号、电话和分公司编号。部门号唯一标识部门信息中的每一个元组。”（b）需要补充分公司编号和主管号，且部门号唯一标识元组，为部门关系主键，其中分公司编号、主管号分别是分公司关系和员工关系的主键，所以在部门关系中为外键；

同理，“员工关系需要记录的信息包括员工号、姓名、隶属部门、岗位、电话和基本工资。其中，员工号唯一标识员工信息中的每一个元组。”可知（c）空需补充隶属部门和岗位，其中员工号为主键，隶属部门为外键。

【问题4】

不需要增加新的实体，对于任职情况，可以将任职时间和任职年限放入联系的属性即可，将部门与主管的联系单独形成关系模式，任职（部门号，主管工号，任职时间，任职年限）。

4 问答题 1分

某房产中介连锁企业欲开发一个基于Web的房屋中介信息系统，以有效管理房源和客户，提高成交率。该系统的主要功能是：

1.房源采集与管理。系统自动采集外部网站的潜在房源信息，保存为潜在房源。由经纪人联系确认的潜在房源变为房源，并添加出售/出租房源的客户。由经纪人或客户登记的出售/出租房源，系统将其保存为房源。房源信息包括基本情况、配套设施、交易类型、委托方式、业主等。经纪人可以对房源进行更新等管理操作。

2.客户管理。求租/求购客户进行注册、更新，推送客户需求给经纪人，或由经纪人对求租/求购客户进行登记、更新。客户信息包括身份证号、姓名、手机号、需求情况、委托方式等。

3.房源推荐。根据客户的需求情况（求购/求租需求情况以及出售/出租房源信息），向已登录的客户推荐房源。

4.交易管理。经纪人对租售客户双方进行交易信息管理，包括订单提交和取消，设置收取中介费比例。财务人员收取中介费之后，表示该订单已完成，系统更新订单状态和房源状态，向客户和经纪人发送交易反馈。

5.信息查询。客户根据自身查询需求查询房屋供需信息。

现采用结构化方法对房屋中介信息系统进行分析与设计，获得如图1-1所示的上下文数据流图和图1-2所示的0层数据流图。

【问题1】（4分）

使用说明中的词语，给出图1-1中的实体E1-E4的名称。

【问题2】（4分）

使用说明中的词语，给出图1-2中的数据存储D1-D4的名称。

【问题3】（3分）

根据说明和图中术语，补充图1-2中缺失的数据流及其起点和终点。

【问题4】（4分）

根据说明中术语，给出图1-1中数据流“客户信息”、“房源信息”的组成。

查看答案 开始考试

正确答案：

本题解析：

【问题1】

E1：客户；E2：经纪人；E3：财务人员；E4：外部网站

【问题2】

D1：客户记录；D2：潜在房源记录；D3：房源记录；D4：订单记录

【问题3】

缺失数据流如下：

1、交易反馈：起点-P4交易管理，终点-E2

2、客户需求：起点-D1，终点-P3房源推荐

3、房源状态：起点-P4交易管理，终点-D3

4、检索潜在房源：起点-D2，终点-P1房源采集与管理

【问题4】

客户信息=身份证号+姓名+手机号+需求情况+委托方式。

房源信息=基本情况+配套设施+交易类型+委托方式+业主等。

【问题1】

题干说明中，自动采集潜在房源信息，并且无反馈信息的为外界网站，即1-1中的E4；

只有经纪人可以确认潜在房源，因此E2为经纪人；

系统只向客户推送推荐房源，因此E1为客户；

财务管理人员收取中介费用，因此E3为财务人员；

综上，E1：客户；E2：经纪人；E3：财务人员；E4：外部网站。

【问题2】

对于新增潜在房源，保存为潜在房源，即D2为潜在房源记录；

对于新增房源保存为房源，即D3为房源记录；

对于新增客户应该保存为客户信息，因此D1为客户记录或客户信息表；

对于订单检索的对象应该为订单记录，即D4为订单记录。

【问题3】

由顶层图和0层图的父子平衡可知，图1-2遗漏P4→E2，交易反馈；

由题干描述可知，对于P4交易管理，“系统更新订单状态和房源状态”，此时需要更新房源记录，此处缺少数据流P4→D3；

由题干描述可知，对于P3房源推荐，“根据客户的需求情况（求购/求租需求情况以及出售/出租房源信息），向已登录的客户推荐房源。”，此处缺少数据流，D1→P3。

由题干描述可知，对于房源采集与管理“系统自动采集外部网站的潜在房源信息，保存为潜在房源。由经纪人联系确认的潜在房源变为房源，并添加出售/出租房源的客户。”可知加工房源采集与管理P1从潜在房源D2读取数据进行确认，此处缺少数据流D2→P1。

【问题4】

“房源信息包括基本情况、配套设施、交易类型、委托方式、业主等”“客户信息包括身份证号、姓名、手机号、需求情况、委托方式等。”根据题干说明列出数据项即可。

5 问答题 1分

某航空公司的会员积分系统将其会员划分为:普卡（Basic）、银卡（Silver）和金卡（Gold）三个等级。非会员（Non Member）可以申请成为普卡会员。会员的等级根据其一年内累积的里程数进行调整。描述会员等级调整的状态图如图5-1所示。现采用状态(State)模式实现上述场景，得到如图5-2所示的类图。

查看答案 开始考试

正确答案：

本题解析：

（1）virtual double travel(int miles,FrequentFlyer*context)=0

（2）context->setState(context→silver)

（3）context->setState(context→gold)

（4）context->setState(context→silver)

（5）context->setState(context→basic)

由代码可知，（1）空缺少一个抽象方法，根据下面的子类可以发现，子类都有double travel(int miles,FrequentFlyer context)方法，是从该抽象类中继承而来，因此（1）空应该补充这个方法，并加上abstract修饰，即（1）virtual double travel(int miles,FrequentFlyer*context)=0。

（2）（3）（4）（5）可以从状态图中根据相关状态推断出来。

首先，（2）（3）属于普卡会员CBasic，从状态图和代码可以看到，当里程>=25000且＜5000时，会员等级应该从普卡会员CBasic升级到银卡会员CSilver，根据后面已有的代码，可以推断表示升级到银卡会员CSilver的表示方式为：

context->setState(context->silver)；同理对于（3）空，在普卡会员CBasic状态，里程>=50000时，应该升级为金卡会员CGold，此时升级金卡CGold的表示方式为context->setState(ncontext->silver)，以此类推，（4）（5）分别对应金卡会员CGold状态下，不同条件，降低的不同等级。因此（4）为降级为银卡会员CSilver，（5）为降级为普卡会员CBasic，对应的表示方式分别为context->setState(context->silver)和context->setState(context->basic)。

注：

本题空（3）条件代码有异议，参照题干逻辑，此处缺失向金卡会员的变迁。因此可填写context->setState(context->gold)。

6 问答题 1分

社交网络平台（SNS）的主要功能之一是建立在线群组，群组中的成员之间可以互相分享或挖掘兴趣和活动。每个群组包含标题、管理员以及成员列表等信息。

社交网络平台的用户可以自行选择加入某个群组。每个群组拥有一个主页，群组内的所有成员都可以查看主页上的内容。如果在群组的主页上发布或更新了信息，群组中的成员会自动接收到发布或更新后的信息。

用户可以加入一个群组也可以退出这个群组。用户退出群组后，不会再接收到该群组发布或更新的任何信息。

现采用面向对象方法对上述需求进行分析与设计，得到如表3-1所示的类列表和如图3-1所示的类图。

【问题1】（6分）

根据说明中的描述，给出图3-1中C1~C3所对应的类名。

【问题2】(6分)

图3-1中采用了哪一种设计模式？说明该模式的意图及其适用场合。

【问题3】(3分)

现在对上述社交网络平台提出了新的需求：一个群体可以作为另外一个群体中的成员，例如群体A加入群体B。那么，群体A中的所有成员就自动成为群体B中的成员。

若要实现这个新需求，需要对图3-1进行哪些修改?（以文字方式描述）

查看答案 开始考试

正确答案：

本题解析：

【问题1】

C1：SNSGroup；C2：SNSUser；C3：SNSAdmin。

（其中C2、C3可以互换）

【问题2】

采用的设计模式：观察者模式

意图：定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并自动更新。

适用场合：

（1）当一个抽象模型有两个方面，其中一个方面依赖于另一个方面，将这两者封装在独立的对象中以使它们可以各自独立地改变和复用。

（2）当对一个对象的改变需要同时改变其他对象，而不知道具体有多少对象有待改变时。

（3）当一个对象必须通知其他对象，而它又不能假定其他对象是谁，即不希望这些对象是紧耦合的。

【问题3】

（1）在SNSSubject和SNSObserver之间增加继承关系，SNSObserver为基类，SNSSubject为派生类。

（2）为类SNSGroup增加自关联（自己到自己的关联关系）。

【问题1】

本题补充类名，来源是表3-1所给出的类名。根据图示，对于SNSSubje是抽象的被观察者，具体被观察的对象应该是在主页发布消息的群组，即C1是SNSGroup；SNSObserver是抽象的观察者，具体的观察者应该是关注主页的群组成员或群组管理员，即C2是SNSUser；C3是SNSAdmin，且二者可以互换。

【问题2】

根据图示可知本题所用的是观察者模式。观察者模式是行为型设计模式。

意图：定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并自动更新。

适用场合：

（1）当一个抽象模型有两个方面，其中一个方面依赖于另一个方面，将这两者封装在独立的对象中以使它们可以各自独立地改变和复用。

（2）当对一个对象的改变需要同时改变其他对象，而不知道具体有多少对象有待改变时。

（3）当一个对象必须通知其他对象，而它又不能假定其他对象是谁，即不希望这些对象是紧耦合的。

【问题3】

对于新需求：一个群体可以作为另外一个群体中的成员，例如群体A加入群体B。那么，群体A中的所有成员就自动成为群体B中的成员。即群组是可以嵌套的，针对这个需求：

（1）在SNSSubject和SNSObserver之间增加继承关系，SNSObserver为基类，SNSSubject为派生类。

（2）为类SNSGroup增加自关联（自己到自己的关联关系）。