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

试题二（共15 分）

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

【说明】

某服装销售公司拟开发一套服装采购管理系统，以便对服装采购和库存进行管理。

【需求分析】

(1)采购系统需要维护服装信息及服装在仓库中的存放情况。服装信息主要包括：

服装编码、服装描述、服装类型、销售价格、尺码和面料，其中，服装类型为销售分类，服装按销售分类编码。仓库信息包括：仓库编码、仓库位置、仓库容量和库管员。系统记录库管员的库管员编码、姓名和级别。一个库管员可以管理多个仓库，每个仓库有一名库管员。一个仓库中可以存放多类服装，一类服装可能存放在多个仓库中。

(2)当库管员发现有一类或者多类服装缺货时，需要生成采购订单。一个采购订单可以包含多类服装。每类服装可由多个不同的供应商供应，但具有相同的服装编码。采购订单主要记录订单编码、订货日期和应到货日期，并详细记录所采购的每类服装的数量、采购价格和对应的多个供应商。

(3)系统需记录每类服装的各个供应商信息和供应情况。供应商信息包括：供应商编码、供应商名称、地址、企业法人和联系电话。供应情况记录供应商所供应服装的服装类型和服装质量等级。一个供应商可以供应多类服装，一类服装可由多个供应商供应。库管员根据入库时的服装质量情况，设定或修改每个供应商所供应的每类服装的服装质量等级，作为后续采购服装时，选择供应商的参考标准。

【概念模型设计】

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

【逻辑结构设计】

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

库管员（库管员编码，姓名，级别）

仓库信息( (1) ，仓库位置，仓库容量）

服装（服装编码，服装描述，服装类型，尺码，面料，销售价格）

供应商（供应商编码，供应商名称，地址，联系电话，企业法人）

供应情况( (2) ，服装质量等级）

采购订单( (3) )

采购订单明细(____(4) )

【问题1】（6 分）

根据需求分析的描述，补充图 2.1 中的联系和联系的类型。

【问题2】（6 分）

根据补充完整的图2-1，将逻辑结构设计阶段生成的关系模式中的空(1)～(4)补充完整，并给出其主键（用下划线指出）。

【问题3】（3 分）

如果库管员定期需要轮流对所有仓库中的服装质量进行抽查，对每个仓库中的每一类被抽查服装需要记录一条抽查结果，并且需要记录抽查的时间和负责抽查的库管员。请根据该要求，对图2-1 进行修改，画出修改后的实体间联系和联系的类型。

试题七（共 15 分）

阅读以下说明和C程序，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明】

现有 n（n < 1000）节火车车厢，顺序编号为 1,2,3,...,n，按编号连续依次从 A方向的铁轨驶入，从 B 方向铁轨驶出，一旦车厢进入车站（Station）就不能再回到 A方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如图 7-1所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。

下面的 C 程序判断能否从 B 方向驶出预先指定的车厢序列，程序中使用了栈类

STACK,关于栈基本操作的函数原型说明如下：

void InitStack(STACK *s)：初始化栈。

void Push(STACK *s,int e): 将一个整数压栈，栈中元素数目增 1。

void Pop(STACK *s)：栈顶元素出栈，栈中元素数目减 1。

int Top(STACK s)：返回非空栈的栈顶元素值，栈中元素数目不变。

int IsEmpty(STACK s)：若是空栈则返回 1，否则返回 0。

【C 程序】

include<stdio.h>

/*此处为栈类型及其基本操作的定义，省略*/

int main( ){

STACK station;

int state[1000];

int n; /*车厢数*/

int begin, i, j, maxNo; /*maxNo 为 A端正待入栈的车厢编号*/

printf("请输入车厢数： ");

scanf("%d",&n);

printf("请输入需要判断的车厢编号序列（以空格分隔） ： ");

if (n < 1) return -1;

for (i = 0; i<n; i++) /* 读入需要驶出的车厢编号序列,存入数组 state[] */

scanf("%d",&state[i]);

（1） ; /*初始化栈*/

maxNo = 1;

for(i = 0; i < n; ){/*检查输出序列中的每个车厢号 state[i]是否能从栈中获取*/

if ( （2） ){/*当栈不为空时*/

if (state[i] == Top(station)){ /*栈顶车厢号等于被检查车厢号*/

printf("%d ",Top(station));

Pop(&station); i++;

}

else

if ( （3） ){

printf("error\n");

return 1;

}

else {

begin = （4） ;

for(j = begin+1; j<=state[i]; j++) {

Push(&station, j);

}

}

}

else { /*当栈为空时*/

begin = maxNo;

for(j = begin; j<=state[i]; j++){

Push(&station, j);

}

maxNo = （5） ;

}

}

printf("OK");

return 0;

}

●试题二

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

【说明】

算法2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如下所示：

文件提示信息

(1+2)

abc)缺少对应左括号：第2行，第4列

((def)gx)缺少对应左括号：第3行，第10列

(((h)

ij)(k

(1ml)缺少对应右括号：第5行，第4列;第4行 ，第1列

在算法2-1中，stack为一整数栈。算法中各函数的说明见表4。

【算法2-1】

将栈stack置空，置EOF 为false

ch＜-nextch();

while(not EOF)

k＜-kind(CH);

if(k== (1) )

push( (2) );push( (3) );

elseif(k== (4) )

if(not empty())

pop();pop()；

else

显示错误信息(缺少对应左括号或右括号);

显示行号row;显示列号col;

endif

endif

ch＜-nextch();

endwhile

if(not empty())

显示错误信息(缺少对应左括号或右括号);

while(not empty())

row＜-pop();col＜-pop();

显示行号row;显示列号co1;

endwhile

endif

为了识别更多种类的括号，对算法2-1加以改进后得到算法2-2。算法2-2能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(char ch)的参数及其对应的返回值见表5。

【算法2-2】

将栈stack置空，置EOF为false

ch＜-nextch();

while(not EOF)

k＜-kind(ch);

if(k＞0)

if(判断条件1)

push( (5) );push( (6) );push( (7) )；

elseif(判断条件2and判断条件3)

pop();pop();pop();

else

显示错误信息(缺少对应左括号或右括号)；

显示行号row;显示列号col;

endif

endif

ch＜-nextch();

endwhile

if(not empty())

显示错误信息(缺少对应左括号或右括号);

while(not empty())

pop();rowpop();colpop();

显示行号row;显示列号col;

endwhile

endif

【问题1】

请将【算法2-1】和【算法2-2】中 (1) ~ (7) 处补充完整。

【问题2】

请从下面的选项中选择相应的判断逻辑填补【算法2-2】中的"判断条件1"至"判断条件3"。注意，若"判断条件2"的逻辑判断结果为假，就无需对"判断条件3"进行判断。

(a)字符是括号

(b)字符是左括号

(c)字符是右括号

(d)栈空

(e)栈不空

(f)栈顶元素表示的是与当前字符匹配的左括号

(g)栈顶元素表示的是与当前字符匹配的右括号

●试题六

【说明】

下面是一个Applet程序，其功能是建立一个图形用户界面的窗口，包括一个文本显示区和一个按钮，点击按钮，可以在文本区已有的文本基础上追加显示10条"Welcome to China"信息，并且文本区由滚动条控制文本的上下滚动。

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

import javax.swing.*;

import javA．awt.*;

import javA．awt.event.*;

/*

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

</applet>

图4

*/

public class ex5_6 extends JApplet {

JButton jb = new JButton("Add Text");

JTextPane jtp = new JTextPane();

public void init() {

jb.addActionListener(new ActionListener() {

public void actionPerformed(ActionEvent e){

for(int i = 1; i < 10; i++)

(1) + "Welcome to China!＼n");

}

});

Container cp = (2) ;

cp.add(new JScrollPane(jtp));

cp.add( (3) );

}

public static void main(String［］ args) {

ex5_6 obj5_6=new ex5_6();

String str = obj5_6.getClass().toString();

if(str.indexOf("class") !=-1)

str = str.substring (6) ;

JFrame. frm = new JFrame(str);

frm.addWindowListener(new (4) {

public void windowClosing(WindowEvent we) {

System.exit(0);

}

});

(5) .add(ex5_6);

frm.setSize(300, 400);

frm.setVisible(true);

}

}

ex5_6.html

<HTML>

<HEAD>

<TITLE>ex5_6</TITLE>

</HEAD>

<BODY>

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

</applet>

</BODY>

</HTML>

●试题二

阅读以下说明和流程图(如图2所示)，回答问题1和问题2，将答案写在答卷的对应栏内。

【说明】

本流程图实现从成绩文件生成学生成绩一览表。

某中学某年级的学生成绩数据(分数)登录在成绩文件F0中，其记录格式见表2：

由该成绩文件生成见表3的学生成绩一览表。生成的学生成绩一览表按学号升序排列。表中的名次是指该生相应课程在年级中的名次。

流程图中的顺序文件F0是学生成绩文件，F0文件经处理1处理后产生顺序文件F，然后经过处理2至处理4对文件F进行处理和更新。在处理5中，仅对文件F的纪录进行学生成绩一览表的编排输出，不进行排序和增加名次等处理。

【问题1】

流程图中文件F的纪录格式设定为见表4形式：

其中的①、②应定义为何种数据项？

【问题2】

简述处理2、处理3和处理4作何种处理，若有排序处理则需指明排序的键及序(升序或降序)。

【流程图】

图 3

试题四（共15分）

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

【说明】

堆数据结构定义如下：

在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图4-1 是一个大顶堆的例子。

堆数据结构常用于优先队列中，以维护由一组元素构成的集合。对应于两类堆结构，优先队列也有最大优先队列和最小优先队列，其中最大优先队列采用大顶堆，最小优先队列采用小顶堆。以下考虑最大优先队列。

假设现已建好大顶堆A，且已经实现了调整堆的函数heapify(A, n, index)。

下面将C代码中需要完善的三个函数说明如下：

（1）heapMaximum(A)：返回大顶堆A中的最大元素。

（2）heapExtractMax(A)：去掉并返回大顶堆 A的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆。

（3）maxHeapInsert(A, key)：把元素key插入到大顶堆 A的最后位置，再将 A调整成大顶堆。

优先队列采用顺序存储方式，其存储结构定义如下：

define PARENT(i) i/2

typedef struct array{

int *int_array; //优先队列的存储空间首地址

int array_size; //优先队列的长度

int capacity; //优先队列存储空间的容量

} ARRAY;

【C代码】

（1）函数heapMaximum

int heapMaximum(ARRAY *A){ return （1） ; }

（2）函数heapExtractMax

int heapExtractMax(ARRAY *A){

int max;

max = A->int_array[0];

（2） ;

A->array_size --;

heapify(A,A->array_size,0); //将剩余元素调整成大顶堆

return max;

}

（3）函数maxHeapInsert

int maxHeapInsert(ARRAY *A,int key){

int i,*p;

if (A->array_size == A->capacity) { //存储空间的容量不够时扩充空间

p = (int*)realloc(A->int_array, A->capacity *2 * sizeof(int));

if (!p) return -1;

A->int_array = p;

A->capacity = 2 * A->capacity;

}

A->array_size ++;

i = （3） ;

while (i > 0 && （4） ){

A->int_array[i] = A->int_array[PARENT(i)];

i = PARENT(i);

}

（5） ;

return 0;

}

【问题 1】（10分）

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

【问题 2】（3分）

根据以上C代码，函数heapMaximum、heapExtractMax和 maxHeapInsert的时间复杂度的紧致上界分别为 （6） 、 （7） 和 （8） （用O 符号表示）。

【问题 3】（2分）

若将元素10插入到堆A =〈15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1〉中，调用 maxHeapInsert函数进行操作，则新插入的元素在堆A中第 （9） 个位置（从 1 开始）。

●试题二

阅读以下说明和流程图，回答问题1和问题2，将答案写在答卷的对应栏内。

【说明】

某供销系统接受顾客的订货单，当库存中某配件的数量小于订购量或库存量低于一定数量时，向供应商发出采购单；当某配件的库存量大于或等于定购粮食，或者收到供应商的送货单并更新了库存后，向顾客发出提货单。该系统还可随时向总经理提供销售和库存情况表。该供销系统的分层数据流图中部分数据流和文件的组成如下：

文件

配件库存=配件号+配件名+规格+数量+允许的最低库存量

数据流

订货单=配件号+配件名+规格+数量+顾客名+地址

提货单=订货单+金额

采购单=配件号+配件名+规格+数量+供应商名+地址

送货单=配件号+配件名+规格+数量+金额

假定顶层图(如图6所示)是正确的，"供应商"文件已由其他系统生成。

【问题1】

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

【问题2】

指出在哪些图中遗漏了哪些数据流。回答时使用如下形式之一：

(1) XX图中遗漏了XX加工(或文件)流向XX加工(或文件)的XX数据流；

(2) XX图中XX加工遗漏了XX输入(或输出)数据流。

【流程图】

顶层图

图6

0层图

图7

加工1子图

图8

加工2子图

图9

试题六（共 15 分）

阅读下列说明和 C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。

【说明】

已知某企业的采购审批是分级进行的，即根据采购金额的不同由不同层次的主管人员来审批，主任可以审批 5 万元以下（不包括 5 万元）的采购单，副董事长可以审批 5 万元至 10 万元（不包括 10 万元）的采购单，董事长可以审批 10 万元至 50 万元（不包括 50万元）的采购单，50 万元及以上的采购单就需要开会讨论决定。 采用责任链设计模式（Chain of Responsibility）对上述过程进行设计后得到的类图如图 6-1 所示

[C++代码]

include <string>

include <iostream>

using namespace std;

class PurchaseRequest {

public:

double Amount; // 一个采购的金额

int Number; // 采购单编号

string Purpose; // 采购目的

};

class Approver { // 审批者类

public:

Approver(){ successor = NULL; }

virtual void ProcessRequest(PurchaseRequest aRequest){

if (successor != NULL){ successor-> （1） ; }

}

void SetSuccessor(Approver *aSuccesssor){ successor = aSuccesssor; }

private:

（2） successor;

};

class Congress : public Approver {

public:

void ProcessRequest(PurchaseRequest aRequest){

if(aRequest.Amount >= 500000){ /* 决定是否审批的代码省略 */ }

else （3） ProcessRequest(aRequest);

}

};

class Director : public Approver {

public:

void ProcessRequest(PurchaseRequest aRequest){ /* 此处代码省略 */ }

};

class President : public Approver {

public:

void ProcessRequest(PurchaseRequest aRequest){ /* 此处代码省略 */ }

};

class VicePresident : public Approver {

public:

void ProcessRequest(PurchaseRequest aRequest){ /* 此处代码省略 */ }

};

void main(){

Congress Meeting; VicePresident Sam; Director Larry ; President Tammy;

// 构造责任链

Meeting.SetSuccessor(NULL); Sam.SetSuccessor( （4） );

Tammy.SetSuccessor( （5） ); Larry.SetSuccessor( （6） );

PurchaseRequest aRequest; // 构造一采购审批请求

cin >> aRequest.Amount; // 输入采购请求的金额

（7） .ProcessRequest(aRequest); // 开始审批

return ;

}

试题四(共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 中的元素。

【问题 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 分）

阅读下列说明和 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 中员工和顾客之间是什么关系，并解释该关系的内涵。