试题四（共15 分) 阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。 【说明】 某

试题三（共 15 分）

阅读下列说明和 UML 图，回答问题 1 至问题4，将解答填入答题纸的对应栏内。

【说明】

某企业为了方便员工用餐，为餐厅开发了一个订餐系统（COS：Cafeteria Orderin

System），企业员工可通过企业内联网使用该系统。

企业的任何员工都可以查看菜单和今日特价。

系统的顾客是注册到系统的员工，可以订餐（如果未登录，需先登录）、注册工资支

付、预约规律的订餐，在特殊情况下可以覆盖预订。

餐厅员工是特殊顾客，可以进行备餐、生成付费请求和请求送餐，其中对于注册工资

支付的顾客生成付费请求并发送给工资系统。

菜单管理员是餐厅特定员工，可以管理菜单。

送餐员可以打印送餐说明，记录送餐信息（如送餐时间）以及记录收费（对于没有注

册工资支付的顾客，由送餐员收取现金后记录）。

顾客订餐过程如下：

1. 顾客请求查看菜单；

2. 系统显示菜单和今日特价；

3. 顾客选菜；

4. 系统显示订单和价格；

5. 顾客确认订单；

6. 系统显示可送餐时间；

7. 顾客指定送餐时间、地点和支付方式；

8. 系统确认接受订单，然后发送 Email 给顾客以确认订餐，同时发送相关订餐信息通

知给餐厅员工。

系统采用面向对象方法开发，使用 UML 进行建模。系统的顶层用例图和一次订餐的活动图初稿分别如图 3-1和图 3-2 所示。

【问题 1】（2 分）

根据【说明】中的描述，给出图 3-1中 A1 和 A2所对应的参与者。

【问题 2】（8 分）

根据【说明】中的描述，给出图 3-1中缺少的四个用例及其所对应的参与者。

【问题 3】（4 分）

根据【说明】中的描述，给出图 3-2中（1）～（4）处对应的活动名称或图形符号。

【问题 4】（1 分）

指出图 3-1 中员工和顾客之间是什么关系，并解释该关系的内涵。

试题二（15 分）

阅读下列说明，回答问题 1 至问题 4，将解答填入答题纸的对应栏内。

【说明】

某汽车维修站拟开发一套小型汽车维修管理系统，对车辆的维修情况进行管理。

1．对于新客户及车辆，汽车维修管理系统首先登记客户信息，包括：客户编号、客户名称、客户性质（个人、单位） 、折扣率、联系人、联系电话等信息；还要记录客户的车辆信息，包括：车牌号、车型、颜色等信息。一个客户至少有一台车。客户及车辆信息如表 2-1 所示。

2．记录维修车辆的故障信息。包括：维修类型（普通、加急） 、作业分类（大、中、小修） 、结算方式（自付、三包、索赔）等信息。维修厂的员工分为：维修员和业务员。车辆维修首先委托给业务员。业务员对车辆进行检查和故障分析后，与客户磋商，确定故障现象，生成维修委托书。如表 2-2 所示。

3．维修车间根据维修委托书和车辆的故障现象，在已有的维修项目中选择并确定一个或多个具体维修项目，安排相关的维修工及工时，生成维修派工单。维修派工单如表 2-3所示。

4．客户车辆在车间修理完毕后，根据维修项目单价和维修派工单中的工时计算车辆此次维修的总费用，记录在委托书中。 根据需求阶段收集的信息，设计的实体联系图（图 2-1）和关系模式（不完整）如下所

示。图 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 分）

根据问题描述，写出客户、委托书和派工单这三个关系的主键。

●试题二

对文法G[S]：S→a|∧|(T)；T→T，S｜S；回答问题1～问题3。

【问题1】

对文法G进行改写，然后对每个非终结符写出不带回溯的递归子程序。

【问题2】

经改写后的文法是否是LL (1) 的?指出它的预测分析表中 (1) ～ (3) 处的内容。

【问题3】

说明输入串(a，a)是否为G的句子。

试题三（共15 分）

阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。

【说明】

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

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

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

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

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

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

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

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

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

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

【问题1】（5 分）

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

【问题2】（7 分）

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

【问题3】（3 分）

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

●试题三

有下列关于运动会管理系统的ER图，如图10所示。图中矩形表示实体，圆表示属性，双圆表示关键字属性，菱形表示实体之间的关系。假定已通过下列SQL语言建立了基本表。

CREATE TABLE ATHLETE

(ANO CHAR (6) NOT NULL，

ANAME CHAR (20) ，

ASEX CHAR (1) ，

ATEAM CHAR (20) )；

CREATE TABLE ITEM

(INO CHAR (6) NOT NULL，

INAME CHAR (20) ，

ITIME CHAR (12) ，

IPLACE CHAR (20) ；

CREATE TABLE GAMES

(ANO CHAR (6) NOT NULL，

INO CHAR (6) NOT NULL，

SCORRE CHAR (10) )；

为了答题的方便，图中的实体和属性同时给出了中英文两种文字，回答问题时只需写出英文名即可。

【E-R图】

图10 E-R图

【问题】

填充下列SQL程序1～4中的 (1) ～ (7) ，使它们分别完成相应的功能：

程序1：统计参加比赛时男运动员人数。

SELECT (1)

FROM ATHLETE

WHERE ASEX=′M′；

程序2：查100872号运动员参加的所有项目及其比赛时间和地点。

SELECT ITEM，INO，IN A ME，ITIME，IPLACE

FROM GAMES，ITEM

WHERE (2) ；

AND (3) ；

程序3：查参加100035项目的所有运动员名单。

SELECT ANO，ANAME，ATEAM

FROM ATHLETE

WHERE (4) ；

(SELECT (4) (5)

FROM GAMES

WHERE GAMES.ANO=ATHLETE.ANO AND INO='100035')；

程序4：建立运动员成绩视图。

(6) ATHLETE-SCORE

AS SELECT ATHLETE，ANO，ANAME，ATEAM，INAME，SCORE

FORM (7) WHERE ATHLETE.ANO=GAMES.ANO AND GAMES.INO=ITEM.INO；

●试题一

阅读下列说明和数据流图，回答问题1～问题3。

【说明】

某医院收费系统的主要功能是收取病人门诊的各项费用。系统的收费功能分为3个方面：病历收费、挂号收费和根据处方单内容收取检查或药物费用。

1.病人初次来该医院看病，首先购买病历，记录病人基本情况。

2.病人看病前要挂号。根据病人的病历和门诊部门(内科、外科等)，系统提供相应的挂号单和处方单，并收取费用。

3.病人根据处方单进行进一步检查或取药前需交纳各项费用。系统首先根据病人基本情况检查处方单中病历号是否正确，记录合格的处方单，并提供收据。

4.所有收费都必须依据定价表中的定价来计算，且所有收费都必须写入收费记录中。

医院收费系统的顶层图如图2所示；医院收费系统的第O层DFD图如图3所示。其中，加工1的细化图如图4所示，加工2的细化图如图5所示。

假定顶层图是正确的，"定价表"文件已由其他系统生成。

【数据流图】

图2医院收费系统的顶层图

图3医院收费系统的0层图

图4医院收费系统的加工1子图

图5医院收费系统的加工2子图

【问题1】

指出哪张图的哪些文件可以不必画出。

【问题2】

数据流图4中缺少2条数据流，请直接在图中添加。

【问题3】

数据流图5中缺少4条数据流，请直接在图中添加。

●试题六

【说明】

下面是一个Applet程序，其功能是在绘图区域中通过鼠标的移动来绘制直线，并且有清除绘图区域按钮，用来清除已经绘制的图像。

程序运行结果如图5所示。

图5

import javA．awt.*;

import javA．applet.*;

/*

<applet code=ex6_7.class width=800 height=400>

</applet>

*/

public class ex6_7 extends Applet{

private Button btn;

private boolean bDraw, bClear;

private int upX, upY,downX, downY;

public void init(){

setLayout(null);

bClear = false;

bDraw = false;

btn = new Button("clear");

btn.reshape(250, 150, 70, 30);

add(btn);

}

public void paint(Graphics g){

if(bClear){

g.clearRect(0, 0, getSize().width, getSize().height);

(1) ;

}

if(bDraw){

g.drawLine( (2) );

bDraw = false;

}

}

public void update(Graphics g){

(3) ;

}

public boolean mouseDown(Event event, int x, int y){

downX = x;

downY = y;

return true;

}

public boolean mouseUp(Event event, int x, int y){

upX = x;

upY = y;

(4) ;

repaint();

return true;

}

public boolean action(Event event, Object object){

if ( (5) ){

bClear = true;

repaint();

}

return true;

}

}

ex6_7.html

<HTML>

<HEAD>

<TITLE> ex6_7 </TITLE>

</HEAD>

<BODY>

<applet code=" ex6_7.class" width=800 height=400 >

</applet>

</BODY>

</HTML>

●试题七

【说明】

下面是一个Applet程序，其功能是从3~100之间（包括3和100）每隔0.5秒显示一个新的数字，如果数字为素数，则显示为灰色，其他为绿色。

程序运行结果如图4所示。

import java.awt.*;

import java.applet.Applet;

/*

<applet code=ex2_7.class width=800 height=400>

</applet>

*/

图 4

public class ex2_7 extends Applet {

public Color color2_7 = Color.black;

private int n2_7 = 3;

public myPrime thPrime2_7;

public void init() {

thPrime2_7 = new myPrime(this);

thPrime2_7.start();

}

public void paint(Graphics g) {

g.setColor(color2_7);

g.drawstring((1) ,50, 50);

}

public int getInt(){

return n2_7;

}

public void setInt(int i){

n2_7=i;

}

}

class myPrime extends Thread {

ex2_7 obj2_7;

myPrime (ex2_7 o) {

this.obj2_7 = o;

}

public boolean isPrime(int n) {

boolean bPrime = true;

int i=2;

if(（2）)

return false;

while(i<n-1&&bPrime){

if (（3）)

bPrime = false;

i++;

}

return bPrime;

}

public void run() {

int i;

for (i = 3;（4）; i++) {

if (isPrime(i))

obj2_7.color2_7 = Color.gray;

else

obj2_7.color2_7 = Color.green;

（5）;

obj2_7.repaint();

try {

sleep(500);

} catch (InterruptedException ie) {

}

}

}

}

ex2_7.html

<HTML>

<HEAD>

<TITLE>ex2_7</TITLE>

</HEAD>

<BODY>

<applet code="ex2_7.class" width=800 height=400 >

</applet>

</BODY>

</HTML>

阅读以下预备知识、函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

【预备知识】

①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a，b，c，d}及其权值2、7、4、5，可构造如图3所示的最优二叉树和相应的结构数组Ht(数组元素Ht［0］不用)(见表5)。

图3最优二叉树

表5 结构数组Ht

结构数组Ht的类型定义如下：

define MAXLEAFNUM 20

struct node{

char ch;/*当前结点表示的字符，对于非叶子结点，此域不用*/

int weight;/*当前结点的权值*/

int parent;/*当前结点的父结点的下标，为0时表示无父结点*/

int lchild,rchild;

/*当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点*/

}Ht［2*MAXLEAFNUM］;

②用′0′或′1′标识最优二叉树中分支的规则是：从一个结点进入其左(右)孩子结点，就用′0′(′1′)标识该分支(示例如图3所示)。

③若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由′0′、′1′组成的一个序列，称此序列为该叶子结点的前缀编码。例如图3所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。

【函数5．1说明】

函数void LeafCode(int root,int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参n为叶子结点个数。

在构造过程中 ，将Ht［p］．weight域用作被遍历结点的遍历状态标志。

【函数5．1】

char**Hc；

void LeafCode(int root,int n)

{/*为最优二叉树中的n个叶子结点构造前缀编码，root是树的根结点下标*/

int i,p=root,cdlen=0;char code［20］;

Hc=(char**)malloc((n+1)*sizeof(char*));/*申请字符指针数组*/

for(i=1;i＜=p;++i)

Ht［i］．weight=0;/*遍历最优二叉树时用作被遍历结点的状态标志*/

while(p){/*以非递归方法遍历最优二叉树，求树中每个叶子结点的编码*/

if(Ht［p］．weight==0){/*向左*/

Ht［p］．weight=1;

if (Ht［p］．lchild !=0) { p=Ht［p］．lchild; code［cdlen++］=′0′;}

else if (Ht［p］．rchild==0) {/*若是叶子结 点，则保存其前缀编码*/

Hc［p］=(char*)malloc((cdlen+1)*sizeof(char));

(1) ;strcpy(He［p］，code);

}

}

else if (Ht［p］．weight==1){/*向右*/

Ht［p］．weight=2;

if(Ht［p］．rchild !=0){p=Ht［p］．rchild;code［cdlen++］=′1′;}

}

else{/*Ht［p］．weight==2,回退*/

Ht［p］．weight=0;

p= (2) ; (3) ;/*退回父结点*/

}

}/*while结束*/

}

【函数5．2说明】

函数void Decode(char*buff,int root)的功能是：将前缀编码序列翻译成叶子结点的字符序列并输出。其中形参root为最优二叉树的根结点下标;形参buff指向前缀编码序列。

【函数5．2】

void Decode(char*buff,int root)

{ int pre=root,p;

while(*buff!=′＼0′){

p=root;

while(p!=0){/*存在下标为p的结点*/

pre=p;

if( (4) )p=Ht［p］．lchild;/*进入左子树*/

else p=Ht［p］．rchild;/*进入右子树*/

buff++;/*指向前缀编码序列的下一个字符*/

｝

(5) ;

printf(″%c″,Ht［pre］．ch);

}

}

【问题 1】（8 分）

用回溯法求解此 0-1 背包问题，请填充下面伪代码中（1）～（4）处空缺。

回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND( v,w,k,W )函数，其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。

下面给出 0-1背包问题的回溯算法伪代码。

函数参数说明如下:

W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。

变量说明如下：

cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。