软件设计师历年试题 1 车辆 (1) 故障 委托书 (2) (3) 维修项目 派工 (4) 客户 业务员 图2-1 实体联系图
员工 维修工 【逻辑结构设计】
客户( (5) ，折扣率，联系人，联系电话) 车辆(车牌号，客户编号，车型，颜色，车辆类别)
委托书( (6) ，维修类型，作业分类，结算方式，进厂时间，
预计完工时间，登记日期，故障描述，总费用)
维修项目(维修项目编号，维修项目，单价)
派工单( (7) ，工时)
员工( (8) ，工种，员工类型，级别)
【问题1】（4分）
根据问题描述，填写图2-1中(1)～(4)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用1 : 1，1 : n 或 1 : *，m : n 或 * : *表示。
【问题2】（4分）
补充图2-1中的联系并指明其联系类型。联系名可为：联系1，联系2，?。 【问题3】（4分）
根据图2-1和说明，将逻辑结构设计阶段生成的关系模式中的空(5)～(8)补充完整。 【问题4】（3分）
根据问题描述，写出客户、委托书和派工单这三个关系的主键。 试题三（共15分）
阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。 【说明】
已知某唱片播放器不仅可以播放唱片，而且可以连接电脑并把电脑中的歌曲刻录到唱片上（同步歌曲）。连接电脑的过程中还可自动完成充电。
关于唱片，还有以下描述信息：
1．每首歌曲的描述信息包括：歌曲的名字、谱写这首歌曲的艺术家以及演奏这首歌曲的艺术家。只有两首歌曲的这三部分信息完全相同时，才认为它们是同一首歌曲。艺术家可能是一名歌手或一支由2名或2名以上的歌手所组成的乐队。一名歌手可以不属于任何乐队，也可以属于一个或多个乐队。
2．每张唱片由多条音轨构成；一条音轨中只包含一首歌曲或为空，一首歌曲可分布在多条音轨上；同一首歌曲在一张唱片中最多只能出现一次。
3. 每条音轨都有一个开始位置和持续时间。一张唱片上音轨的次序是非常重要的，因此对于任意一条音轨，播放器需要准确地知道，它的下一条音轨和上一条音轨是什么（如果存在的话）。
根据上述描述，采用面向对象方法对其进行分析与设计，得到了如表3-1所示的类列表、如图3-1所示的初始类图以及如图3-2所示的描述播放器行为的UML状态图。
表3-1 类列表
30
软件设计师考试历年真题 第59页 共 31 页 软件设计师历年试题 名 说 明 Artist 艺术家 Song 歌曲 Band 乐队 Musician 歌手 Track 音轨 Album 唱片 编写 1 0..* A 1 演奏 0..* B (3) (4) C D (1) (2) E (5) (6)
F 图3-1 初始类图 图3-2 播放器行为UML状态图
【问题1】（3分）
根据说明中的描述，使用表3-1给出的类的名称，给出图3-1中的A~F所对应的类。 【问题2】（6分）
根据说明中的描述，给出图3-1中（1）~（6）处的多重度。 【问题3】（4分）
图3-1中缺少了一条关联，请指出这条关联两端所对应的类以及每一端的多重度。
类 多重度 【问题4】（2分）
软件设计师考试历年真题 第61页 共 32 页 31
软件设计师历年试题 3-2所示的播放器行为UML状态图，给出从“关闭”状态到“播放”状态所经过的最短事件
序列（假设电池一开始就是有电的）。 试题四(共15分)
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。 【说明】
某机器上需要处理n个作业job1, job2, ?, jobn，其中：
(1) 每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值p[i]和最后期限值d[i]；
(2) 机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；
(3) job1～jobn的收益值呈非递增顺序排列，即p[1]≥p[2]≥?≥p[n]；
(4) 如果作业jobi在其期限之内完成，则获得收益p[i]；如果在其期限之后完成，则没有收益。 为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4-1是基于贪心策略求解该问题的流程图。
(1) 整型数组J[]有n个存储单元，变量k表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤ ? ≤d[J[k]]。
(2) 为了方便于在数组J中加入作业，增加一个虚拟作业job0，并令d[0] = 0， J[0] = 0。
(3) 算法大致思想：先将作业job1的编号1放入J[1]，然后，依次对每个作业jobi (2≤i≤n)进行判定，看其能否插入到数组J中，若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列，否则不插入。
jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。 (4) 流程图中的主要变量说明如下：
i：循环控制变量，表示作业的编号； k：表示在期限内完成的作业数；
r：若jobi能插入数组J，则其在数组J中的位置为r+1； q：循环控制变量，用于移动数组J中的元素。
32
软件设计师考试历年真题 第63页 共 33 页 软件设计师历年试题
图4-1 贪心策略流程图
【问题1】（9分）
请填充图4-1中的空缺(1)、(2)和(3)处。 【问题2】(4分)
假设有6个作业job1, job2, ?, job6；
完成作业的收益数组p=(p[1],p[2],p[3],p[4],p[5],p[6]) = (90,80,50,30,20,10)； 每个作业的处理期限数组d=(d[1],d[2],d[3],d[4],d[5],d[6]) = (1,2,1,3,4,3)。
请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列 (4) （按作业处理的顺序给出），得到的总收益为 (5) 。 【问题3】(2分)
对于本题的作业处理问题，用图4-1的贪心算法策略，能否求得最高收益？ (6) 。用贪心算法求解任意给定问题时，是否一定能得到最优解？ (7) 。 试题五（共15分）
阅读以下说明和C代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】
在一个简化的绘图程序中，支持的图形种类有点(point)和圆(circle)，在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形(shape)，并定义了类型shape_t、point_t和circle_t分别表示基本图形、点和圆，并且点和圆具有基本图形的所有特征。 [C代码]
typedef enum { point,circle } shape_type; /* 程序中的两种图形：点和圆 */ typedef struct { /* 基本的图形类型 */
shape_type type; void (*destroy)(); void (*draw)();
/* 图形种类标识：点或者圆 */ /* 销毁图形操作的函数指针 */
/* 绘制图形操作的函数指针 */
} shape_t;
typedef struct { shape_t common; int x; int y; } point_t; /* 定义点类型，x、y为点坐标 */ void destroyPoint(point_t* this) { free(this); printf(\ /* 销毁点对象 */ void drawPoint(point_t* this) { printf(\ /* 绘制点对象 */ shape_t* createPoint(va_list* ap) { /* 创建点对象，并设置其属性 */
point_t* p_point;
if( (p_point = (point_t*)malloc(sizeof(point_t))) == NULL ) return NULL; p_point->common.type = point; p_point->common.destroy = destroyPoint; p_point->common.draw = drawPoint;
p_point->x = va_arg(*ap, int); /* 设置点的横坐标 */ p_point->y = va_arg(*ap, int); /* 设置点的纵坐标 */
33
软件设计师考试历年真题 第65页 共 34 页 软件设计师历年试题 return (shape_t*)p_point; /* 返回点对象指针 */ }
typedef struct { /* 定义圆类型 */
shape_t common;
point_t *center; /* 圆心点 */
int radius; /* 圆半径 */ } circle_t;
void destroyCircle(circle_t* this){
free( （1） ); free(this); printf(\
}
void drawCircle(circle_t* this) { printf(\
（2） .draw( this->center ); /* 绘制圆心 */ printf(\
}
shape_t* createCircle(va_list* ap) { /* 创建一个圆，并设置其属性 */ circle_t* p_circle;
if( (p_circle = (circle_t*)malloc(sizeof(circle_t))) == NULL ) return NULL; p_circle->common.type = circle; p_circle->common.destroy = destroyCircle; p_circle->common.draw = drawCircle;
（3） = createPoint(ap); /* 设置圆心 */ p_circle->radius = va_arg(*ap, int); /* 设置圆半径 */ return p_circle; }
shape_t* createShape(shape_type st, ...) { /* 创建某一种具体的图形 */ va_list ap; /* 可变参数列表 */ shape_t* p_shape = NULL; （4） (ap, st);
if( st == point ) p_shape = createPoint( &ap); /* 创建点对象 */ if( st == circle ) p_shape = createCircle(&ap); /* 创建圆对象 */ va_end(ap); return p_shape; } int main( ) { int i; /* 循环控制变量，用于循环计数 */ shape_t* shapes[2]; /* 图形指针数组，存储图形的地址 */
shapes[0] = createShape( point, 2, 3); /* 横坐标为2，纵坐标为3 */ shapes[1] = createShape( circle, 20, 40, 10); /* 圆心坐标(20,40)，半径为10 */ for(i=0; i<2; i++) { shapes[i]->draw(shapes[i]); printf(\ } /* 绘制数组中图形 */ for( i = 1; i >= 0; i-- ) shapes[i]->destroy(shapes[i]); /* 销毁数组中图形 */
return 0;
}
[运行结果] P(2,3)
软件设计师考试历年真题 第67页 共 35 页34
软件设计师考试 - 历年真题及答(2007年-2012)年 - 图文
