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

试卷预览

1 问答题 1分

一个无向连通图G点上的哈密尔顿（Hamilton）回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。一种求解无向图上哈密尔顿回路算法的基本思想如下：

假设图G存在一个从顶点V0出发的哈密尔顿回路V0——V1——V2——V3——...——Vn-1——V0。算法从顶点V0出发，访问该顶点的一个未被访问的邻接顶点V1，接着从顶点V1出发，访问V1一个未被访问的邻接顶点V2，…；对顶点Vi，重复进行以下操作：访问Vi的一个未被访问的邻接接点Vi+1；若Vi的所有邻接顶点均已被访问，则返回到顶点Vi-1，考虑Vi-1的下一个未被访问的邻接顶点，仍记为Vi；直到找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。

【C代码】

下面是算法的C语言实现。

（1）常量和变量说明

n:图G中的顶点数

c[][]:图G的邻接矩阵

k:统计变量，当期已经访问的定点数为k+1

x［k］:第k个访问的顶点编号，从0开始

visited［x［k］］：第k个顶点的访问标志，0表示未访问，1表示已访问

（2）C程序

#include＜stido.h>

#include＜stidb.h>

#define MAX 100

void Hamilton（int n,int x［MAX],int c[MAX][MAX]）｛

int i;

int visited[MAX];

int k;

/*初始化x数组和visited数组*/

for（i=0:i＜n;i++）｛

x[i]=0;

visited[i]=0;

｝

/*访问起始顶点*/

k=0

（1）；

x[0]=0;

k=k+1;

/*访问其他顶点*/

while（k>=0）｛

x[k]=x[k]+1;

while（x[k]＜n）｛

if（（2）&&c[x[k-1]][x[k]]==1）｛/*邻接顶点x[k]未被访问过*/

break；

｝else｛

x[k]=x[k]+1

｝

｝

if（x[k]＜n&&k==n-1&&（3）)｛/*找到一条哈密尔顿回路*/

for（k=0;k＜n;k++）｛

printf（〝%d--〝,x[k]);/*输出哈密尔顿回路*/

｝

printf（〝%d\n〝,x[0]);

return；

｝else if(x[k]＜n&&k＜n-1）｛/*设置当前顶点的访问标志，继续下一个顶点*/

（4）

k=k+1;

｝else｛/*没有未被访问过的邻接顶点，回退到上一个顶点*/

x[k]=0；

visited[x[k]]=0；

（5）；

｝

｝

｝

【问题1】（10分）

根据题干说明。填充C代码中的空（1）~（5）。

【问题2】（5分）

根据题干说明和C代码，算法采用的设计策略为（6），该方法在遍历图的顶点时，采用的是（7）方法（深度优先或广度优先）。

查看答案 开始考试

正确答案：

本题解析：

【问题1】

1、visited[0]=1

2、visited[x[k]]==0

3、c[x[k]][0]==1

4、visited[x[k]]=1

5、k=k-1

【问题2】

6、回溯法

7、深度优先

哈密顿图是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路，含有图中所有顶点的路径称作哈密顿路径。

回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

算法题历来都被认为是比较难的题，一个程序开发人员都不喜欢看别人的代码。但是要得分也不是太难。

问题2比较容易得分，而且第二空就是个二选一的填空。只要了解到回溯法的相关原理，基本可以得满分。对于问题1就需要花一些心思，去读懂题干和代码，但是这里的第1空和第5空也是比较容易发挖出来的空。第一空是初始化第一个结点，第五空是此路不通，得回走，所以得退回。

2 问答题 1分

某图像预览程序要求能够查看BMP、JPEG和GIF三种格式的文件，且能够在Windows和Linux两种操作系统上运行。程序需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，现采用桥接（Bridge）模式进行设计，得到如图6-1所示的类图。

图6-1

【Java代码】

import java.util.*;

class Matrix{//各种格式的文件最终都被转化为像素矩阵

//此处代码省略

};

abstract class Implementor{

public（1）;//显示像素矩阵m

};

class WinImp extends Implementor{

public void doPaint(Matrix m){//调用Windows系统的绘制函数绘制像素矩阵

}

};

class LinuxImp extends Implementor{

public void doPaint(Matrix m){//调用Linux系统的绘制函数绘制像素矩阵

}

};

abstract class Image{

public void setImp(Implementor imp){this.imp=imp;}

public abstract void parseFile(String fileName);

protected Implementor imp;

};

class BMPImage extends Image{

//此处代码省略

};

class GIFImage extends Image{

public void parseFile(String fileName){

//此处解析BMP文件并获得一个像素矩阵对象m

（2）;//显示像素矩阵m

}

};

class JPEGImage extends Image{

//此处代码省略

}；

class Main{

public static void main(String[]args){

//在Linux操作系统上查看demo.gif图像文件

Image image=（3）;

Implementor imageImp=（4）;

（5）;

Image.parseFile("demo.gif");

}

}

查看答案 开始考试

正确答案：

本题解析：

1.abstract void doPaint(Matrix m)

2.imp.doPaint(m)

3.new GIFImage()

4.new LinuxImp()

5.image.setImp(imageImp)

第一空是显示像素矩阵m

从类图来看Implementor是WinImp和LinuxImp两子类的父类。那就需要从子类中去找共同的方法，然后把它们抽象出来。

共同的方法为:void doPaint(Matrix m);抽象就成了abstract void doPaint(Matrix m)；此处别忘了abstract关键字。是抽象方法。

第二空是显示像素矩阵m

在Image的类和其子类中，要显示像素矩阵，可以使用调用Implementor类的方法doPaint，而Image类中定义了对象imp。

即调用的方法为：imp.doPaint(m)

第三空是构造出Gif图像的对象new GIFImage()

第四空是要在Linux操作系统上查看，需要一个LinuxImp的对象.new LinuxImp()

第五空是把imageImp对象传递，以便能够查看Gif图像文件，image.setImp(imageImp)

3 问答题 1分

M公司为了便于开展和管理各项业务活动，提高公司的知名度和影响力，拟构建一个基于网络的会议策划系统。

【需求分析结果】

该系统的部分功能及初步需求分析的结果如下：

（1）M公司旗下有业务部、策划部和其他部门。部门信息包括部门号、部门名、主管、联系电话和邮箱号；每个部门只有一名主管，只负责管理本部门的工作，且主管参照员工关系的员工号；一个部门有多名员工，每名员工属于且仅属于一个部门。

（2）员工信息包括员工号、姓名、职位、联系方式和薪资。职位包括主管、业务员、策划员等。业务员负责受理用户申请，设置受理标志。一名业务员可以受理多个用户申请，但一个用户申请只能由一名业务员受理。

（3）用户信息包括用户号、用户名、银行账号、电话、联系地址。用户号唯一标识用户信息中的每一个元组。

（4）用户申请信息包括申请号、用户号、会议日期、天数、参会人数、地点、预算和受理标志。申请号唯一标识用户申请信息中的每一个元组，且一个用户可以提交多个申请，但一个用户申请只对应一个用户号。

（5）策划部主管为已受理的用户申请制定会议策划任务。策划任务包括申请号、任务明细和要求完成时间。申请号唯一标识策划任务的每一个元组。一个策划任务只对应一个己受理的用户申请，但一个策划任务可由多名策划员参与执行，且一名策划员可以参与执行多项策划任务。

【概念模型设计】

根据需求阶段收集的信息，设计的实体联系图（不完整）如图2-1所示。

图2-1

【关系模型设计】

部门（部门号，部门名，部门主管，联系电话，邮箱号）

员工（员工号，姓名，（a），联系方式，薪资）

用户（用户名，（b），电话，联系地址）

用户申请（申请号，用户号，会议日期，天数，参会人数，地点，受理标志，（c））

策划任务（申请号，任务明细，（d））

执行（申请号，策划员，实际完成时间，用户评价）

【问题1】（5分）

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

【问题2】（4分）

根据题意，将关系模式中的空（a）~（d）补充完整，并填入答题纸对应的位置上。

【问题3】（4分）

给出“用户申请”和“策划任务”关系模式的主键和外键。

【问题4】（2分）

请问“执行”关系模式的主键为全码的说法正确吗？为什么？

查看答案 开始考试

正确答案：

本题解析：

【问题1】

1.联系1：部门和员工，1:n

2.联系2：业务员和用户申请，1:n

3.联系3：用户和用户申请，1:n

4.联系4：策划员和策划任务，n:m

5.联系5：策划任务和用户申请，1:1

或（联系5：部门和主管，1:1）

【问题2】

a.职位，部门号

b.用户号，银行账号

c.预算费用，业务员（员工号）

d.要求完成时间，主管号

【问题3】

用户申请：主键：申请号外键：用户号，业务员

策划任务：主键：申请号外键：申请号，主管号

【问题4】

不正确

All-key关系模型的所有属性组成该关系模式的候选码，称为全码。即所有属性当作一个码。若关系中只有一个候选码，且这个候选码中包含全部属性，则该候选码为全码。

实际完成时间和用户评价为非主属性。

【问题1】

问题1需要找出5个联系：

部门与员工之间：一个部门有多名员工，每名员工属于且仅属于一个部门。是1对多的联系。

业务员和用户申请之间：一名业务员可以受理多个用户申请，但一个用户申请只能由一名业务员受理。是1对多的联系。

用户和用户申请之间：申请号唯一标识用户申请信息中的每一个元组，且一个用户可以提交多个申请，但一个用户申请只对应一个用户号。是1对多的联系。

策划员和策划任务之间：一个策划任务可由多名策划员参与执行，且一名策划员可以参与执行多项策划任务。是多对多的联系。

策划任务和用户申请之间：一个策划任务只对应一个已受理的用户申请。是1对1的联系。

【问题2】

找出关系模式中的属性。

明显的题干中有的，这里不作分析。

着重分析一下，1对多的联系，联系是可以合并到多的一端。多对多的联系，此时联系必须单独成一个关系模式来描述它们之间的联系。此时填空的时间，就不要把关系给丢失了。

【问题3】

问题3要求找关系模式的主键和外键。主键是指一个或多个属性的组合，能够唯一标识元组的。即记录。此题中关系都比较简单，一个属性即可以唯一标识。

外键是指另一个表的主键，是用来与其他表建立联系的属性。所以用户申请模式中外键有两个。

用户申请：主键：申请号外键：用户号，业务员

策划任务：主键：申请号外键：申请号，主管号

【问题4】

说明见参考答案。

4 问答题 1分

某公司拟开发一个共享单车系统，采用北斗定位系统进行单车定位，提供针对用户的APP以及微信小程序、基于Web的管理与监控系统。该共享单车系统的主要功能如下。

1）用户注册登录。用户在APP端输入手机号并获取验证码后进行注册，将用户信息进行存储。用户登录后显示用户所在位置周围的单车。

2）使用单车。

①扫码/手动开锁。通过扫描二维码或手动输入编码获取开锁密码，系统发送开锁指令进行开锁，系统修改单车状态，新建单车行程。

②骑行单车。单车定时上传位置，更新行程。

③锁车结账。用户停止使用或手动锁车并结束行程后，系统根据已设置好的计费规则及使用时间自动结算，更新本次骑行的费用并显示给用户，用户确认支付后，记录行程的支付状态。系统还将重置单车的开锁密码和单车状态。

3）辅助管理。

①查询。用户可以查看行程列表和行程详细信息。

②报修。用户上报所在位置或单车位置以及单车故障信息并进行记录。

4）管理与监控。

①单车管理及计费规则设置。商家对单车基础信息、状态等进行管理，对计费规则进行设置并存储。

②单车监控。对单车、故障、行程等进行查询统计。

③用户管理。管理用户信用与状态信息，对用户进行查询统计。

现采用结构化方法对共享单车系统进行分析与设计，获得如图1-1所示的上下文数据流图和图1-2所示的0层数据流图。

图1-1上下文数据流图

图1-2 0层数据流图

【问题1】（3分）

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

【问题2】（5分）

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

【问题3】（5分）

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

【问题4】（2分）

根据说明中术语，说明“使用单车”可以分解为哪些子加工？

查看答案 开始考试

正确答案：

本题解析：

【问题1】

E1：用户

E2：商家

E3：单车

【问题2】

D1：用户信息存储

D2：单车信息表

D3：单车行程信息表

D4：计费规则存储

D5：单车故障信息记录

【问题3】

1.起点：p3终点：E1数据流名称：开锁密码

2.起点：p3终点：E1数据流名称：费用

3.起点：p3终点：E3数据流名称：开锁指令

4.起点：D3终点：p7数据流名称：行程

5.起点：p3终点：D2数据流名称：单车状态

或（起点：P3终点：D3数据流名称：支付状态）

（起点：D4，终点：P3，计费规则）

【问题4】

扫码/手动开锁，更新行程，锁车结账

（或扫码/手动开锁，更新行程，锁车，计算费用，重置开锁密码，用户确认支付）

【问题1】

问题1要求找图1-1所示的上下文数据流图中的实体名称：

结合题干，和数据流名称找出对应的实体名称。

E1与共享单车系统，有着个人信息，等数据流名称，其中明显有一个用户位置，和确认支付的数据流，从第2点使用单车，锁车结账一条中，明显提到用户的操作。

E2的实体名称，是由其与共享单车系统有数据流名称为计价规则，由第4点管理与监控，题干直接说明“商家对单车基础信息、状态等进行管理，对计费规则进行设置并存”。

E3的实体名称，从第2点使用单车上，能查找出所有的数据流名称。

然后验证所有的数据流，是否都是从对应的实体之间的关系，确保答案的正确。

所以E1为用户，E2为商家，E3为单车

【问题2】

问题2要求找出存储名称，这个应该不用作解析，就是找出可以存储的记录、表、文件等，只是考生可能纠结的地方是写这个名称的时候，到底要写什么，才最符合标准答案的问题。一个原则，名称从题干查找，尽量不要自己命名，题干说明是用户信息，那就是用户信息，顶多写成，用户信息记录，或用户信息表。

【问题3】

查找缺失的数据流，有两条原则经常使用到，父图和子图平衡原则，数据守恒原则。另外一个要紧靠题干。需要耐心和细心。

参考答案中1，2，3是从父图和子图平衡原则中找出来的，父图中有的数据流，在子图中却没有，就是缺失。4，5是数据守恒结合题干查找出来的。

【问题4】

问题4是要求分解加工。

在第4点题干描述中，明显的有三个加工，即扫码/手动开锁，更新行程，锁车结账。

5 问答题 1分

某图像预览程序要求能够查看BMP、JPEG和GIF三种格式的文件，且能够在Windows和Linux两种操作系统上运行。程序需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，现采用桥接（Bridge）模式进行设计，得到如图5-1所示的类图。

图5-1

【C++代码】

#include＜iostream>

#include＜string>

using namespace std;

class Matrix{//各种格式的文件最终都被转化为像素矩阵

//此处代码省略

};

class Implementor{

public:

（1）;//显示像素矩阵m

};

class WinImp:public Implementor{

public:

void doPaint(Matrix m){/*调用Windows系统的绘制函数绘制像素矩阵*/}

};

class LinuxImp:public Implementor{

public:

void doPaint(Matrix m){/*调用Linux系统的绘制函数绘制像素矩阵*/}

};

class Image{

public:

void setImp(Implementor*imp){this->imp=imp;}

virtual viod parseFile(string fileName)=0;

protected:

Implementor*imp;

};

class BMPImage:public Image{

//此处省略代码

};

class GIFImage:public Image{

public:

void parseFile(string fileName){

//此处解析GIF文件并获得一个像素矩阵对象m

（2）;显示像素矩阵m

}

};

class JPEGImage:public Image{

//此处代码省略

};

int main（　　）{

//在Linux操作系统上查看demo.gif图像文件

Image*image=（3）;

Implementor*imageImp=（4）;

（5）;

image->parseFile("demo.gif");

return 0;

}

查看答案 开始考试

正确答案：

本题解析：

（1）virtual void doPaint(Matrix m)=0

（2）imp->doPaint(m)

（3）new GIFImage()

（4）new LinuxImp()

（5）image->setImp(imageImp)

第一空是显示像素矩阵m

从类图来看Implementor是WinImp和LinuxImp两子类的父类。那就需要从子类中去找共同的方法，然后把它们抽象出来。

共同的方法为：void doPaint(Matrix m)；抽象就成了virtual void doPaint(Matrix m)=0。

第二空是显示像素矩阵m

在Image的类和其子类中，要显示像素矩阵，可以使用调用Implementor类的方法doPaint，而Image类中定义了对象imp。

即调用的方法为：imp->doPaint(m)

第三空是构造出Gif图像的对象new GIFImage()

第四空是要在Linux操作系统上查看，需要一个LinuxImp的对象，new LinuxImp()

第五空是把imageImp对象传递，以便能够查看Gif图像文件，image->setImp(imageImp)

6 问答题 1分

某大学拟开发一个用于管理学术出版物（Publication）的数字图书馆系统，用户可以从该系统查询或下载已发表的学术出版物。系统的主要功能如下：

1.登录系统。系统的用户（User）仅限于该大学的学生（Student）、教师（Faculty）和其他工作人员（Staff）。在访问系统之前，用户必须使用其校园账户和密码登录系统。

2.查询某位作者（Author）的所有出版物。系统中保存了会议文章（Conf Paper）、期刊文章（JournalArticle）和校内技术报告（TechReport）等学术出版物的信息，如题目、作者以及出版年份等。除此之外，系统还存储了不同类型出版物的一些特有信息：

（1）对于会议文章，系统还记录了会议名称、召开时间以及召开地点；

（2）对于期刊文章，系统还记录了期刊名称、出版月份、期号以及主办单位；

（3）对于校内技术报告，系统记录了由学校分配的唯一ID。

3.查询指定会议集（Proceedings）或某个期刊特定期（Edition）的所有文章。会议集包含了发表在该会议（在某个特定时间段、特定地点召开）上的所有文章。期刊的每一期在特定时间发行，其中包含若干篇文章。

4.下载出版物。系统记录每个出版物被下载的次数。

5.查询引用了某篇出版物的所有出版物。在学术出版物中引用他人或早期的文献作为相关工作或背景资料是很常见的现象。用户也可以在系统中为某篇出版物注册引用通知，若有新的出版物引用了该出版物，系统将发送电子邮件通知该用户。

现在采用面向对象方法对该系统进行开发，得到系统的初始设计类图如图3-1所示。

图3-1初始设计类图

【问题1】（9分）

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

【问题2】（4分）

根据说明中的描述，给出图3-1中类C6~C9的属性。

【问题3】（2分）

图3-1中包含了哪种设计模式？实现的是该系统的哪个功能？

查看答案 开始考试

正确答案：

本题解析：

【问题1】

C1：Person

C2：User

C3：Student

C4：Faculty

C5：Staff

C6：Publication

C7：ConfPaper

C8：JournalArticle

C9：TechReport

注：C3/C4/C5可互换。

【问题2】

C6：题目，作者，出版年份

C7：会议名称，召开时间，召开地点

C8：期刊名称，出版月份，期号，主办单位

C9：ID

【问题3】

观察者模式，实现：引用他人学术出版物发送电子邮件通知该用户。

试题解析：

此题，应当属于最简单的类图题了。只是出题者，有一个小小的疏忽，少了个类名，根据下面的子类抽象，可以填写Person或人。

此题，应当属于最简单的类图题了。只是出题者，有一个小小的疏忽，少了个类名，根据下面的子类抽象，可以填写Person或人。

【问题1】

问题1找类名：直接从类图看，C2有三个子类，而C6也同样有三个子类。这个明显的破绽，为我们解题提供了捷径。阅读题干找出有三个从属关系的事物来：系统的用户（User）仅限于该大学的学生（Student）、教师（Faculty）和其他工作人员（Staff）；查询某位作者（Author）的所有出版物。系统中保存了会议文章（ConfPaper）、期刊文章（JournalArticle）和校内技术报告（TechReport）等学术出版物的信息。

这个关系找到了，然后结合类图来看。用户（User），出版物（Publication）要判别出是C2和C6。其他后面的空就容易了。

C2和Author（作者）有共同的父类。说明只有用户（User）可以与其在同一个级别上。而Author（作者）和C6之间有一个written by 1对多的关系，说明C6就是出版物（Publication），因为作者可以有多个出版物。所以可以确定C2为User，C6为Publication。

然后要填写C3，C4，C5就是学生（Student）、教师（Faculty）和其他工作人员（Staff），这个次序可以随意。

填写C7，C8，C9就是会议文章（ConfPaper）、期刊文章（JournalArticle）和校内技术报告（TechReport）这个次序也可随意。只是这个位置的次序决定了问题2的内容排列次序。填英文。

唯一的遗憾是从题干中找不出作者（Author）和用户(User)的父类是什么，是人（Person）？只能让人想像了。

【问题2】

问题2的答案，全在题干第2点的陈述中。

此处不作解析。

【问题3】

题干第5查询引用了某篇出版物的所有出版物。在学术出版物中引用他人或早期的文献作为相关工作或背景资料是很常见的现象。用户也可以在系统中为某篇出版物注册引用通知，若有新的出版物引用了该出版物，系统将发送电子邮件通知该用户。这个说明加上类图中有一个类名为Observer。可以断定为观察者模式，实现的功能即是第5点的陈述。