2017下半年软件设计师考试真题及答案

【问题1】（9分）

根据说明中的描述，给出图3-1中C1~C9所对应的类名。 C1:Object C2:User C3:Student C4:Faculty C5:Staff C6:Publication C7:ConfPaper C8:JournalArticle C9:TechReport

【问题1】（4分）

根据说明中的描述，给出图3-1中类C6~C9的属性。 C6:题目，作者，出版年份 C7:会议名称，召开时间，召开地点 C8:期刊名称，出版月份，期号，主办单位

C9:ID

【问题3】 （2分）

图3-1中包含了哪种设计模式？实现的是该系统的哪个功能？ 观察者模式，实现：引用他人学术出版物发送电子邮件通知该用户。

试题四

阅读下列说明和C代码，回答问题1至问题 2，将解答写在答题纸的对应栏内。 【说明】

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

假设图G存在一个从顶点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 #include #define MAX 100

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

in t ;

in t visited[MAX]; int k;

/*初始化x数组贺visited数组*/ for （i=0:i

x[i]=0; visited [i]=0; ｝

/*访问起始顶点*/ k=0 （ ）； x[0]=0 K=k+1

/*访问其他顶点*/ while（k>=0）｛

x[k]=x[k]+1; while（x[k]>

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

break； ｝else｛

x[k] = x[k] +1 ｝ ｝

if（x[k]

for （k=0;k

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

prinf（〝%d--〝,x[0] ; return；

｝else if x[k]

（ ） k=k+1;

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

x[k]=0； visited x[k]=0； （ ）； ｝ ｝ ｝

【问题1】（10分）

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

1、visited[0] = 1 2、visited[x[k]] == 0 3、c[x[0]][x[k]] 4、visited[x[k]] = 1 5、k = k - 1 【问题2】（5分）

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