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

试卷预览

1 问答题 1分

对有向图进行拓扑排序的方法是：

（1）初始时拓扑序列为空；

（2）任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；

（3）重复（2），直到不存在入度为0的顶点为止（若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序）。

函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为v1，v2，…，vn，图G采用邻接表表示，其数据类型定义如下：

#define MAXVNUM 50/*最大顶点数*/

typedef struct ArcNode{/*表结点类型*/

int adjvex;/*邻接顶点编号*/

struct ArcNode*nextarc;/*指示下一个邻接顶点*/

}ArcNode;

typedef struct AdjList{/*头结点类型*/

char vdata;/*顶点的数据信息*/

ArcNode*firstarc;/*指向邻接表的第一个表结点*/

}AdjList;

typedef struct LinkedDigraph{/*图的类型*/

int n;/*图中顶点个数*/

AdjList Vhead[MAXVNUM];/*所有顶点的头结点数组*/

}LinkedDigraph;

例如，某有向图G如图4-1所示，其邻接表如图4-2所示。

图4-1有向图G

函数TopSort中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如下表所示：

【C代码】

int*TopSort(LinkedDigraph G){

ArcNode*p;/*临时指针，指示表结点*/

Queue Q;/*临时队列，保存入度为0的顶点编号*/

int k=0;/*临时变量，用作数组元素的下标*/

int j=0，w=0;/*临时变量，用作顶点编号*/

int*topOrder，*inDegree;

topOrder=(int*)malloc((G.n+1)*sizeof(int));/*存储拓扑序列中的顶点编号*/

inDegree=(int*)malloc((G.n+1)*sizeof(int));/*存储图G中各顶点的入度*/

if(!inDegree||!topOrder)return NULL;

（1）;/*构造一个空队列*/

for(j=1;j＜=G.n;j++){/*初始化*/

topOrder[j]=0;inDegree[j]=0;

}

for(j=1;j＜=G.n;j++)/*求图G中各顶点的入度*/

for(p=G.Vhead[j].firstarc;p;p=p->nextarc)

inDegree[p->adjvex]+=1;

for(j=1;j＜=G.n;j++)/*将图G中入度为0的顶点保存在队列中*/

if(0==inDegree[j])EnQueue(&Q，j);

while(!IsEmpty(Q)){

（2）;/*队头顶点出队列并用w保存该顶点的编号*/

topOrder[k++]=w;

/*将顶点w的所有邻接顶点的入度减1（模拟删除顶点w及从该顶点出发的弧的操作）*/

for(p=G.Vhead[w].firstarc;p;p=p->nextarc){

（3）-=1;

if(0==（4）)EnQueue(&Q，p->adjvex);

}/*for*/

free(inDegree);

if(（5）)

return NULL;

return topOrder;

}/*TopSort*/

【问题1】（9分）

根据以上说明和C代码，填充C代码中的空（1）～（5）。

【问题2】（2分）

对于图4-1所示的有向图G，写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈，写出函数TopSort执行后得到的拓扑序列。

【问题3】（4分）

设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是（6）。

若有向图采用邻接矩阵表示（例如，图4-1所示有向图的邻接矩阵如图4-3所示），且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时间复杂度是（7）。

查看答案 开始考试

正确答案：

本题解析：

【问题1】（9分）

（1）InitQueue(&Q)（1分）注：函数名与参数必须完全正确才可得分

（2）DeQueue(&Q，&w)（2分）注：函数名与参数必须完全正确才可得分

（3）inDegree[p->adjvex]及其等价形式（2分）

（4）inDegree[p->adjvex]及其等价形式（2分）

（5）k＜G.n或k!=G.n（2分）

【问题2】（2分）

队列方式：v1 v2 v5 v4 v3 v7 v6（或1 2 5 4 3 7 6）（1分）

栈方式：v1 v2 v5 v4 v7 v3 v6（或1 2 5 4 7 3 6）（1分）

【问题3】（4分）

（6）O(n+e)（2分）

（7）O（n2）（2分）

本题考查数据结构和算法中的拓扑排序算法。

【问题１】

拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程，并且该序列满足：若在有向图中从顶点Vi到Vj有一条路径，则在该线性序列中，顶点Vi必然在顶点Vj之前。

对AOE网进行拓扑排序的方法如下：

①在AOE网中选择一个入度为零（没有前驱）的顶点且输出它：

②从网中删除该顶点及其与该顶点有关的所有边；

③重复上述两步，直至网中不存在入度为零的顶点为止。

在拓扑排序过程中，需要将入度为0的顶点临时存储起来。函数中用一个队列暂存入度为0且没有进入拓扑序列的顶点。显然，空（1）处应填入InitQueue（&Q）。

进行拓扑排序之前，应先求出网中每个顶点的入度并存入数组inDegree[]中，从而将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减1”，一旦发现某个顶点的入度变为0，就将其编号压入堆栈。从而将选择入度为0的顶点操作转化为令队头所代表的顶点出队。

根据注释，空（2）处应填入DeQueue(&Q，&w)，实现队头元素出队列的处理。

题中图采用邻接表存储结构，当指针p指向Vi邻接表中的结点时，p->adjvex表示vi的一个邻接顶点，删除vi至顶点p->adjvex的弧的操作实现为顶点p->adjvex的入度减1，因此，空（3）处应填入inDegree[p->adjvex]，当顶点p->adjvex的入度为0时，需要将其加入队列，因此空(4）处也应填入inDegree[p->adjvex]。

空（5）处判断是否所有顶点都加入了拓扑序列，算法中变量k用于对加入序列的顶点计数，因此，空（5）处应填入“k＜G.n”或“k!=G.n"。

【问题2】

使用栈和队列的差别在于拓扑序列中顶点的排列次序可能不同。对于本题中的有向图，在使用队列的方式更下：

（1）开始时仅顶点V1的入度为0，因此顶点V1入队：

（2）队头顶点V1出队，并进入拓扑序列，然后删除从顶点V1出发的弧后，仅使顶点v2的入度为0，因此顶点v2入队：

（3）队头顶点v2出队，并进入拓扑序列，然后删除从顶点v2出发的弧后，仅使顶点v5的入度为0，因止顶点v5入队；

（4）队头顶点v5出队，并进入拓扑序列，然后删除从顶点v5出发的弧后，仅使顶点v4的入度为0，因此顶点v4入队；

（5）队头顶点v4出队，并进入拓扑序列，然后删除从顶点v4出发的弧后，仅使顶点v3和v7的入度为0，因此顶点v3和v7依次入队；

（6）队头顶点v3出队，并进入拓扑序列，然后删除从顶点v3出发的弧后，没有产生新的入度为0的顶点；

（7）队头顶点v7出队，并进入拓扑序列，然后删除从顶点v7出发的弧后，使顶点v6的入度为0，因此顶点v6入队；

（8）队头顶点v6出队，并进入拓扑序列，然后删除从顶点v6出发的弧后，没有产生新的入度为0的顶点，队列已空，因此结束拓扑排序过程，得到的拓扑序列为v1 v2 v5 v4 v3 v7 v6。

使用栈保存入度为0的顶点时，前4步都是一样的，因为每次仅有一个元素进栈，因此出栈序列与入栈序列一致。到第5步时，v3和v7依次入栈后，出栈时的次序为v7和v3，因此得到的拓扑序列为v1 v2 v5 v4 v7 v3 v6。

【问题3】

以邻接表为存储结构时，计算各顶点入度的时间复杂度为O(e)，建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中，（图中无环情况下）每个顶点进出队列各1次，入度减l的操作在while循环中共执行e次，所以总的时间复杂度为O(n+e)。

以邻接矩阵为存储结构时，计算各顶点入度时需要遍历整个矩阵，因此时间复杂度为O（n），建立零入度顶点队列的时间复杂度为O（n）。在拓扑排序过程中，（图中无环情况下）每个顶点进出队列各1次，实现入度减1操作时需遍历每个顶点的行向量1遍（时间复杂度为O(n))，所以总的时间复杂度为O(n2）。

2 问答题 1分

某软件公司现欲开发一款飞机飞行模拟系统，该系统主要模拟不同种类飞机的飞行特征与起飞特征。需要模拟的飞机种类及其特征如表5-1所示。

表5-1

为支持将来模拟更多种类的飞机，采用策略设计模式（Strategy）设计的类图如图5-1所示。

图5-1中，AirCraft为抽象类，描述了抽象的飞机，而类Helicopter、AirPlane、Fighter和Harrier分别描述具体的飞机种类，方法fly（　　）和takeOff（　　）分别表示不同飞机都具有飞行特征和起飞特征；类FlyBehavior与TakeOffBehavior为抽象类，分别用于表示抽象的飞行为与起飞行为；类SubSonicFly与SuperSonicFly分别描述亚音速飞行和超音速飞行的行为；类VerticalTakeOff与LongDistanceTakeOff分别描述垂直起飞与长距离起飞的行为。

【C++代码】

#include＜iostream>

using namespace std;

class FlyBehavior{

public:virtual void fly（　　）=0;

};

class SubSonicFly:public FlyBehavior{

public:void fly（　　）{cout＜＜"亚音速飞行！"＜＜endl;}

};

class SuperSonicFly:public FlyBehavior{

public:void fly（　　）{cout＜＜"超音速飞行！"＜＜endl;}

};

class TakeOffBehavior{

public:virtual void takeOff（　　）=0;

};

class VerticalTakeOff:public TakeOffBehavior{

public:void takeOff（　　）{cout＜＜"垂直起飞！"＜＜endl;}

};

class LongDistanceTakeOff:public TakeOffBehavior{

public:void takeOff（　　）{cout＜＜"长距离起飞！"＜＜endl;}

};

class AirCraft{

protected:

（1）;

（2）;

public:

void fly（　　）{（3）;}

void takeOff（　　）{（4）;};

};

class Helicopter:public AirCraft{

public:

Helicopter（　　）{

flyBehavior=new（5）;

takeOffBehavior=new（6）;

}

（7）{

if(!flyBehavior)delete flyBehavior;

if(!takeOffBehavior)delete takeOffBehavior;

}

};

//

其它代码省略

查看答案 开始考试

正确答案：

本题解析：

（1）FlyBehavior*flyBehavior（2分）

（2）TakeOffBehavior*takeOffBehavior（2分）

（3）flyBehavior->fly()（2分）

（4）takeOffBehavior->takeOff()（2分）

（5）SubSonicFly()（2分）

（6）VerticalTakeOff()（2分）

（7）~Helicopter()（3分）

注：空（1）与空（2）答案可互换

本题目考查了设计模式中的策略设计模式，实际上与2007年上半年考核内容相同。

从本题的叙述中可以看出，存在4种不同的飞机类型，但每种飞机类型的起飞特征和飞行特征并不完全相同，这就使得我们很难采用比较直接的方法来实现重用。例如，定义一个抽象的飞机类，实现飞机的起飞特征，然后4种飞机直接重用该特征。但是，我们可以观察到，尽管飞机的起飞特征和飞行特征有所不同，有一点可以肯定的是，每一种飞机都具备了飞行特征和起飞特征。因此，可以抽象出一个飞机类，其中含有飞行特征与起飞特征，但关于两个特征的实现要单独抽取出来，所以又形成了FlyBehavior类和TakeOffBehavior类分别表示抽象的飞行和起飞特征，而这两个类的子类则分别实现不同的起飞特征和飞行特征，最终转化为，在创建一个具体的飞机时，给其配上不同的起飞特征和飞行特征即可。

本题中的空（1）和空（2）应该填写成员变量，根据类图可以得知，此处应该表示的是飞行和起飞特征变量，在C++中可以采用指针来表示。空（3）和空（4）处需要实现飞行与起飞特征，但AirCraft是抽象的类，所以把实现代理给指针变量。Helicopter类需要指定由父类继承而来的成员变量的初始值，因为Helicopter的特征是垂直起飞和亚音速飞行，因此生成这两个特征的对象，分别赋值给flyBehavior和takeOffBehavior变量。

3 问答题 1分

某软件公司现欲开发一款飞机飞行模拟系统，该系统主要模拟不同种类飞机的飞行特征与起飞特征。需要模拟的飞机种类及其特征如表6-1所示。

表6-1

为支持将来模拟更多种类的飞机，采用策略设计模式（Strategy）设计的类图如图6-1所示。

图6-1中，AirCraft为抽象类，描述了抽象的飞机，而类Helicopter、AirPlane、Fighter和Harrier分别描述具体的飞机种类，方法fly（　　）和takeOff（　　）分别表示不同飞机都具有飞行特征和起飞特征类FlyBehavior与TakeOffBehavior为抽象类，分别用于表示抽象的飞行为与起飞行为；类SubSonicFly与SuperSonicFly分别描述亚音速飞行和超音速飞行的行为；类VerticalTakeOff与LongDistanceTakeOff分别描述垂直起飞与长距离起飞的行为。

【Java代码】

interface FlyBehavior{

public void fly（　　）;

};

class SubSonicFly implements FlyBehavior{

public void fly（　　）{System.out.println("亚音速飞行！");}

};

class SuperSonicFly implements FlyBehavior{

public void fly（　　）{System.out.println("超音速飞行！");}

};

interface TakeOffBehavior{

public void takeOff（　　）;

};

class VerticalTakeOff implements TakeOffBehavior{

public void takeOff（　　）{System.out.println("垂直起飞！");}

};

class LongDistanceTakeOff implements TakeOffBehavior{

public void takeOff（　　）{System.out.println("长距离起飞！");}

};

abstract class AirCraft{

protected（1）;

protected（2）;

public void fly（　　）{（3）;}

public void takeOff（　　）{（4）;};

};

class Helicopter（5）AirCraft{

public Helicopter（　　）{

flyBehavior=new（6）;

takeOffBehavior=new（7）;

}

};

//其它代码省略

查看答案 开始考试

正确答案：

本题解析：

（1）FlyBehavior flyBehavior（2分）

（2）TakeOffBehavior takeOffBehavior（2分）

（3）flyBehavior.fly()（2分）

（4）takeOffBehavior.takeOff()（2分）

（5）extends（3分）

（6）SubSonicFly()（2分）

（7）VerticalTakeOff()（2分）

注：空（1）与空（2）答案可互换

本题目考查了设计模式中的策略设计模式，实际上与2007年上半年Java题目的考核内容相同。

从本题的叙述中可以看出，存在四种不同的飞机类型，但每种飞机类型的起飞特征和飞行特征并不完全相同，这就使得我们很难采用比较直接的方法来实现重用。例如，定义一个抽象的飞机类，实现飞机的起飞特征，然后四种飞机直接重用该特征。但是，我们可以观察到，尽管飞机的起飞特征和飞行特征有所不同，有一点可以肯定的是，一种飞机都具备了飞行特征和起飞特征。因此，可以抽象出一个飞机类，其中含有飞行特征与起飞特征，但关于两个特征的实现要单独抽取出来，所以又形成了FIyBehavior类和TakeOffBehavior类，分别表示抽象的飞行特征和起飞特征，而这两个类的子类则分别现不同的起飞和飞行特征，最终转化为，在创建一个具体的飞机时，给其配上不同的起飞特征和飞行特征即可。

本题中的空（1）和空（2）应该填写成员变量，根据类图可以得知，此处应该表示的是飞行和起飞特征变量。空（3）和空（4）处需要实现飞行与起飞特征，但AirCraft是抽象的类，所以把实现代理给指针变量。Helicopter类需要指定由父类继承而来的成员变量的初始值，因为Helicopter的特征是垂直起飞和亚音速飞行，因此生成这两个特征的对象，分别赋值给flyBehavior和takeOffBchavior变量。

4 问答题 1分

某学校拟开发一套实验管理系统，对各课程的实验安排情况进行管理。

【需求分析】

一个实验室可进行多种类型不同的实验。由于实验室和实验员资源有限，需根据学生人数分批次安排实验室和实验员。一门课程可以为多个班级开设，每个班级每学期可以开设多门课程。一门课程的一种实验可以根据人数、实验室的可容纳人数和实验类型，分批次开设在多个实验室的不同时间段。一个实验室的一次实验可以分配多个实验员负责辅导实验，实验员给出学生的每次实验成绩。

（1）课程信息包括：课程编号、课程名称、实验学时、授课学期和开课的班级等信息；实验信息记录该课程的实验进度信息，包括：实验名、实验类型、学时、安排周次等信息，如表2-1所示。

（2）以课程为单位制定实验安排计划信息，包括：实验地点，实验时间、实验员等信息，实验计划如表2-2所示。

（3）由实验员给出每个学生每次实验的成绩，包括：实验名、学号、姓名、班级、实验成绩等信息，实验成绩如表2-3所示。

表2-3实验成绩

（4）学生的实验课程总成绩根据每次实验的成绩以及每次实验的难度来计算。

【概念模型设计】

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

图2-1实体联系图

【逻辑结构设计】

根据概念模型设计阶段完成的实体联系图，得出如下关系模式（不完整）：

课程（课程编号，课程名称，授课院系，实验学时）

班级（班级号，专业，所属系）

开课情况（（1），授课学期）

实验（（2），实验类型，难度，学时，安排周次）

实验计划（（3），实验时间，人数）

实验员（（4），级别）

实验室（实验室编号，地点，开放时间，可容纳人数，实验类型）

学生（（5），姓名，年龄，性别）

实验成绩（（6），实验成绩，评分实验员）

【问题1】（6分）

补充图2-1中的联系和联系的类型。

【问题2】（6分）

根据图2-1，将逻辑结构设计阶段生成的关系模式中的空（1）~（6）补充完整并用下划线指出这六个关系模式的主键。

【问题3】（3分）

如果需要记录课程的授课教师，新增加“授课教师”实体。请对图2-1进行修改，画出修改后的实体间联系和联系的类型。

查看答案 开始考试

正确答案：

本题解析：

【问题1】（6分）

注：联系的名称不做要求。

课程与班级之间的联系1分，联系的类型1分

班级与学生之间的联系1分，联系的类型0.5分

实验、实验员与学生之间的联系1分，联系的类型1分

实验、实验员与实验室之间的联系及类型0.5分

【问题2】（6分）

（1）课程编号，班级号

（2）实验编号，课程编号

（3）实验编号，批次号，安排学期，实验室编号，实验员编号

（4）实验员编号，实验员姓名

（5）学号，班级号

（6）实验编号，学号

注：每个空0.5分，每个主键0.5分。

【问题3】（3分）

授课教师、课程与班级之间的联系1.5分，联系的类型1.5分。

本题考查数据库概念结构设计及向逻辑结构转换的掌握。

此类题目要求考生认真阅读题目，根据题目的需求描述，给出实体间的联系。

【问题1】

根据题意，由“一门含实验的课程可以开设给多个班级，每个班级每学期可以开设多门含实验的课程”可知课程和班级之间的开设关系为m:n联系。由“一个实验室的一次实验可以分配多个实验员负责辅导实验”可知实验、实验室与实验员之间的安排关系为k:n:m联系。由“实验员给出学生的每次实验成绩”可知实验、学生与实验员之间的成绩关系为k:n:m联系。班级和学生之间的包含关系为1:n联系。

【问题2】

根据题意可知课程编号是课程的主键，班级号是班级的主键。从表2-1可知，开课情况是体现课程与班级间的m:n联系，因此开课情况关系模式应该包含课程编号和班级号，并共同作为主键。一门课程包含多次实验，实验与课程之间是m:1关系，因此，根据表2-1，实验关系模式应包含实验编号和课程编号，并且以实验编号为主键，以课程编号为外键。在制定试验计划时，每个班的每次实验可能按实验室被分成多个批次，每个批次的实验会有若干名实验员来辅导学生实验并打分。实验员关系模式应该记录实验员编号和实验员姓名，并以实验员编号为主键。实验室编号是实验室的主键。从表2-2可见，实验计划关系模式应记录实验编号、批次号和授课学期，并且共同作为主键。从表2-3可见，实验成绩关系模式记录每个学生的每次实验成绩，应包含学号和实验编号，并共同作为主键。

【问题3】

由于授课教师负责给若干个班级开设若干门课程，因此，课程、班级和授课教师之间的开设关系是k:n:m联系。

5 问答题 1分

某大型企业的数据中心为了集中管理、控制用户对数据的访问并支持大量的连接需求，欲构建数据管理中间件，其主要功能如下：

（1）数据管理员可通过中间件进行用户管理、操作管理和权限管理。用户管理维护用户信息，用户信息（用户名、密码）存储在用户表中；操作管理维护数据实体的标准操作及其所属的后端数据库信息，标准操作和后端数据库信息存放在操作表中；权限管理维护权限表，该表存储用户可执行的操作信息。

（2）中间件验证前端应用提供的用户信息。若验证不通过，返回非法用户信息；若验证通过，中间件将等待前端应用提交操作请求。

（3）前端应用提交操作请求后，中间件先对请求进行格式检查。如果格式不正确，返回格式错误信息；如果格式正确，则进行权限验证（验证用户是否有权执行请求的操作），若用户无权执行该操作，则返回权限不足信息，否则进行连接管理。

（4）连接管理连接相应的后台数据库并提交操作。连接管理先检查是否存在空闲的数据库连接，如果不存在，新建连接；如果存在，则重用连接。

（5）后端数据库执行操作并将结果传给中间件，中间件对收到的操作结果进行处理后，将其返回给前端应用。

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

【问题1】（3分）

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

【问题2】（3分）

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

【问题3】（6分）

给出图1-2中加工P的名称及其输入、输出流。

图1-1顶层数据流图

图1-2 0层数据流图

除加工P的输入与输出流外，图1-2还缺失了两条数据流，请给出这两条数据流的起点和终点。

注：名称使用说明中的词汇，起点和终点均使用图1-2中的符号或词汇。

【问题4】（3分）

在绘制数据流图时，需要注意加工的绘制。请给出三种在绘制加工的输入、输出时可能出现的错误。

查看答案 开始考试

正确答案：

本题解析：

【问题1】（3分，各1分）

E1：前端应用E2：数据管理员E3：后端数据库

【问题2】（3分，各1分）

D1：用户表D2：操作表D3：权限表

【问题3】（6分）

P的名称：操作结果处理（1分）

缺少的数据流：

【问题4】（3分）

在绘制数据流图时，可能出现的输入、输出错误：

只有输入而无输出或者黑洞（1分）

只有输出而无输入或者奇迹（1分）

输入的数据流无法通过加工产生输出流或者灰洞（1分）

输入的数据流与输出的数据流名称相同（1分）

注：总分3分，答对上述1个即可给1分，多答不多给分。

本题考查数据流图(DFD）的应用，是比较传统的题目，要求考生细心分析题目中所描述的内容。

DFD是一种便于用户理解、分析系统数据流程的图形工具。是系统逻辑模型的重要组成部分。

【问题1】

本问题考查顶层DFD。顶层DFD一般用来确定系统边界，将待开发系统看作一个加工，因此图中只有唯一的一个加工和一些外部实体，以及这两者之间的输入输出数据流。题目要求根据描述确定图中的外部实体。分析题目中的描述，并结合已经在顶层数据流图中给出的数据流进行分析。题目中有信息描述：数据管理员可通过中间件进行用户管理、操作管理和权限管理；前端应用提交操作请求；连接管理连接相应的后台数据库并提交操作。由此可知该中间件系统有数据管理员、前端应用和后端数据库三个外部实体。从图1-1中数据流和实体的对应关系可知，E1为前端应用，E2为数据管理员，E3为后端数据库。

【问题2】

本问题考查0层DFD中数据存储的确定。说明中描述：用户信息（用户名、密码）存储在用户表中；标准操作和后端数据库信息存放在操作表中；权限管理维护信息存放在权限表中。因此数据存储为用户表、操作表以及权限表。再根据图1-2可知D1的输入数据流从用户管理来，D2的输入数据流从操作管理来，D3的输入数据流从权限管理来，所以D1为用户表，D2为操作表，D3为权限表。

【问题3】

本问题考查0层DFD中缺失的加工和数据流。比较图1-1和图1-2，可知顶层DFD中的操作结果和处理后的操作结果没有在0层DFD中体现。再根据描述“后端数据库执行操作并将结果传给中间件，中间件对收到的操作结果进行处理后，将其返回给前端应用”可知，需要有操作结果处理，因此P为操作结果处理，其输入流为从后端数据库E3来的操作结果，输出结果为处理后的操作结果，并返回给前端应用E1。

考查完P及其输入输出流之后，对图1-2的内部数据流进行考查，以找出缺失的另外2条数据流。从图中可以看出D2和D3只有输入流没有输出流，这是常见DFD设计时的错误，所以首先考查D2和D3的输出流。描述中有“权限验证是验证用户是否有权执行请求的操作，若用户有权执行该操作，进行连接管理；连接管理连接相应的后台数据库并提交操作；权限表存储用户可执行的操作信息”。因此，权限验证有从权限表D3来的输入数据流。而要连接后端数据库，需要数据库信息，从权限验证的输出流中包含有数据库信息可知，权限验证需要获取到数据库信息，所以还需从操作表D2来的输入流。

【问题4】

本问题考查在绘制数据流图中加工绘制时的注意事项。绘制加工时可能出现的错误有：加工的输入、输出时可能出现只有输入而无输出、只有输出而无输入、输入的数据流无法通过加工产生输出流以及输入的数据流与输出的数据流名称相同等错误。

6 问答题 1分

某运输公司决定为新的售票机开发车票销售的控制软件。图3-1给出了售票机的面板示意图以及相关的控制部件。

售票机相关部件的作用如下所述：

（1）目的地键盘用来输入行程目的地的代码（例如，200表示总站）。

（2）乘客可以通过车票键盘选择车票种类（单程票、多次往返票和座席种类）。

（3）继续/取消键盘上的取消按钮用于取消购票过程，继续按钮允许乘客连续购买多张票。

（4）显示屏显示所有的系统输出和用户提示信息。

（5）插卡口接受MCard（现金卡），硬币口和纸币槽接受现金。

（6）打印机用于输出车票。

假设乘客总是支付恰好需要的金额而无需找零，售票机的维护工作（取回现金、放入空白车票等）由服务技术人员完成。

系统采用面向对象方法开发，使用UML进行建模。系统的顶层用例图和类图分别如图3-2和图3-3所示。

图3-3类图

【问题1】（5分）

根据说明中的描述，给出图3-2中A1和A2所对应的参与者，U1所对应的用例，以及（1）、（2）处所对应的关系。

【问题2】（7分）

根据说明中的描述，给出图3-3中缺少的C1~C4所对应的类名以及（3）～（6）处所对应的多重度。

【问题3】（3分）

图3-3中的类图设计采用了中介者（Mediator）设计模式，请说明该模式的内涵。

查看答案 开始考试

正确答案：

本题解析：

【问题1】（5分，各1分）A1：乘客A2：服务技术人员

U1：支付（1）＜＜include>>（2）＜＜include>>

【问题2】（7分）

C1：键盘（2分）

C2：目的地键盘（1分）

C3：车票键盘（1分）

C4：继续/取消键盘（1分）

（3）~（6）：1（各0.5分）

【问题3】（3分）

使用Mediator模式，可以使各个对象间的耦合松散（1分），只需关心和Mediator的关系，使多对多的关系变成了一对多的关系（1分），可以降低系统的复杂性，提高可修改扩展性(1分）。

本题考查面向对象开发相关知识，涉及UML用例图、类图以及类图设计时的设计模式。UML目前在面向对象软件开发中广泛使用，是面向对象软件开发考查的重要内容。

【问题1】

本问题考查用例图。用例图用于确定系统边界，识别与系统交互的参与者，通过判断参与者发起的用例，建立和参与者之间的关联，然后再确认用例之间的关系。

本题中对售票机的描述为“乘客可以通过车票键盘选择车票种类（单程票、多次往返票和座席种类）；售票机的维护工作（取回现金、放入空白车票等）由服务技术人员完成”。由此可知，图3-1中A1为乘客，A2为服务技术人员。

对购票用例，要选择目的地和车票类型、通过插卡口进行支付才可完成购票。因此U2为支付。

在考查用例之间的关系时，购票过程可以取消，也允许乘客连续购买多张票，因此，购票时可以包含多次选择目的地和车票类型、支付，即购票用例包含（关系＜＜include>>)选择目的地和车票类型以及支付。

【问题2】

本问题考查类图。类图设计的重点是类的抽象和继承关系以及多重度。售票机的面板由多个控制部件组成。根据说明这些控制部件有目的地键盘、车票键盘和继续／取消键盘、显示屏、卡驱动器、硬币／纸币槽、打印机。图3-3中只有前3个部件在图中没有给出，而要填如4个类。从图中己经抽象出的硬件组件，给出了抽象的思路，从而可以把键盘抽象出来。由C1与C2、C3、C4的继承关系中C1为基类，可知C1为键盘。由C2、C3和C4给出的方法名称可知，C2为目的地键盘获取目的地代码，C3为车票键盘选择产品类型，C4为继续／和取消动作。

本题中的重复度比较简单。从图3-1售票机的图示中可以看出，一个售票机只包含一个目的地键盘、一个车票键盘和一个继续／取消键盘，因此（3）～（6）均为1。

【问题３】

本问题考查设计模式。设计模式题目虽然比较难，但是本题题目中已经给出了所采用的设计模式为Mediator模式，只需说明设计模式的内涵即可，也比较容易。使用Mediator模式，可以使各个对象间的耦合松散，只需关心和Mediator的关系，使多对多的关系变成了一对多的关系，可以降低系统的复杂性，提高可修改扩展性。