阅读以下说明和Java代码，将应填入（n)处的字句写在答题纸的对应栏内。【说明】 某绘图系统存在Point、

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

说明

某网上订书系统的E-R图(已消除了不必要的冗余)如图2-1所示(图中没有标出主码)。图中实体的说明如表2-1所示，相关属性说明如表2-2所示。

一个顾客可以在同一天填写多张购书单，每张购书单上可填写多种图书，每种图书可以订购多本，bid相同的图书在同一张购书单上不能出现多次。

注：为简化起见，不考虑信用卡号码泄漏所带来的安全性等问题。

根据E-R图中给出的词汇，按照“关系模式名(属性，属性，…)”的格式，将此 E-R图转换为4个关系模式，并指出每个关系模式中的主码和外码，其中模式名根据需要取实体名或联系名。

试题四（共15分）

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

【说明】

用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间（所有作业被处理的时间之和）最少。

算法步骤：

（1）确定候选解上界为R短的单台处理机处理所有作业的完成时间m，

（2）用p（x,y,k）=1表示前k个作业可以在A用时不超过x且在B用时不超过y时间 内处理完成，则p（x,y,k）=p（x-ak,y,k-1）||p（x,y-bk,k-1）（||表示逻辑或操作）。

（3）得到最短处理时问为min（max（x，y））。

【C代码】

下面是该算法的C语言实现。

（1）常量和变量说明

n: 作业数

m: 候选解上界

a: 数组，长度为n，记录n个作业在A上的处理时间，下标从0开始

b: 数组，长度为n，记录n个作业在B上的处理时间，下标从0开始

k: 循环变量

p: 三维数组，长度为（m+1）*（m+1）*（n+1）

temp: 临时变量

max: 最短处理时间

（2）C代码

include<stdio.h>

int n, m;

int a[60], b[60], p[100][100][60];

void read(){ /*输入n、a、b，求出m，代码略*/}

void schedule(){ /*求解过程*/

int x,y,k;

for（x=0；x<=m；x++）{

for(y=0；y<m；y++）{

（1）

for（k=1；k<n；k++）

p[x][y][k]=0；

}

}

for（k=1；k<n；k++）{

for（x=0；x<=m；x++）{

for（y=0；y<=m；y++）{

if（x - a[k-1]>=0） （2） ；

if（ （3） ）p[x][y][k]=(p[x][y][k] ||p[x][y-b[k-1]][k-1]);

}

}

}

}

void write(){ /*确定最优解并输出*/

int x，y，temp，max=m;

for（x=0；x<=m；x++）{

for（y=0;y<=m;y++）{

if( （4） ）{

temp=（5） ；

if（temp< max）max = temp;

}

}

}

printf("\n%d\n"，max）,

}

void main(){read();schedule();write();}

【问题1】 （9分）

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

【问题2】（2分）

根据以上C代码，算法的时间复杂度为（6）（用O符号表示）。

【问题3】（4分）

考虑6个作业的实例，各个作业在两台处理机上的处理时间如表4-1所示。该实例的最优解为（7），最优解的值（即最短处理时间）为（8）。最优解用（x1,x2,x3,x4,x5,x6）表示，其中若第i个作业在A上赴理，则xi=l，否则xi=2。如（1，1，1，1，2，2）表示作业1，2，3和4在A上处理，作业5和6在B上处理。

试题六（共15分）

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

【说明】

某大型商场内安装了多个简易的纸巾售卖机，自动出售2元钱一包的纸巾，且每次仅售出一包纸巾。纸巾售卖机的状态图如图6-1所示。

采用状态( State)模式来实现该纸巾售卖机，得到如图6-2所示的类图。其中类State为抽象类，定义了投币、退币、出纸巾等方法接口。类SoldState、SoldOutState、NoQuarterState和HasQuarterState分别对应图6-1中纸巾售卖机的4种状态：售出纸巾、纸巾售完、没有投币、有2元钱。

【Java代码】

import j ava.util.*;

interface State{

public void insertQuarter(); //投币

public void ejectQuarter(); //退币

public void turnCrank();腑安下“出纸巾”按钮

public void dispense(); //出纸巾

}

class TissueMachine {

( 1 ) soldOutState, noQuarterState, hasQuarterState, soldState, state;

state = soldOutState;

int count = 0; //纸巾数

public TissueMachine(intnumbers) { /*实现代码省略 */}

public StategetHasQuarterState() { returnhasQuarterState; }

public StategetNoQuarterState() { returnnoQuarterState, }

public State getSoldState() { return soldState; }

public State getSoldOutState() { return soldOutState; }

public int getCount() { return count, }

//其余代码省略

}

class NoQuarterState implements State {

TissueMachine tissueMachine;

public void insertQuarter() {

tissueMachine.setState( (2));

}

//构造方法以及其余代码省略

}

class HasQuarterState implements State {

TissueMachine tissueMachine;

public void ejectQuarter() {

tissueMachine.setState ((3));

}

//构造方法以及其余代码省略

}

class SoldState implements State {

TissueMachine tissueMachine;

public void dispense() {

if(tissueMachine.getCount() > 0) {

tissueMachine.setState ((4));

} else {

tissueMachine.setState ((5)); }

}

}

阅读以下说明和Visual Basic代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

某绘图系统定义了一个抽象类IShape，现有三个类CPoint、CLine和CCircle，它们都具有IShape界面。相应的类图关系如图7-1所示。

已知某第三方库已经提供了XCircle类，且完全满足CCircle图元显示时所需的功能。代码7-1是抽象类IShape的类模块内容，代码7-2实现了类CCircle的IShape界面，并使用了XCircle提供的显示功能。

XCimle提供的显示功能方法接口为displayIt。

【代码7-1】

Public Color As Long

Sub draw()

'方法体不包括可执行语句

End Sub

Sub move(stepx As Single，stepy As Smgle)

'方法体不包括可执行语句

End Sub

【代码7-2】

(1)

Private color As Long

… ‘其他定义省略

Private bridged As (2)

Private Sub Class_Initialize ( )

Set bridged=(3)

End Sub

Private Property (4) ( )As Long

IShape_Color = color

End Property

Private Property (5) (ByVal newColor As Long)

color=newColor

End Property

Private Sub IShape_draw ( ) '使用XCirele提供的显示功能

(6)

End Sub

Private Sub IShape_move (stepx As Single, stepy As Single)

… '省略描述

End Sub

阅读以下说明和Java代码，将应填入(n)处的字句写在对应栏内。

[说明]

在一些大型系统中，大多数的功能在初始化时要花费很多时间，如果在启动的时候，所有功能(连不用的功能)都要全面初始化的话，会连带影响到应用软件要花很多时间才能启动。因此常将程序设计成到了实际要使用某种功能的阶段才初始化该功能。

以下示例展示了Proxy(代理)模式，PrinterProxy类执行一些比较“轻”的方法——设置名称和取得名称，需要真正执行“重”的方法——真正打印——时才初始Print类。图6-1显示了各个类间的关系。

[图6-1]

[Java代码]

//Printable.Java

publiC (1) Printable{

public abstract void setPrinterName(String name)；

public abstract String getprinterName()；

public abstract void print(String string)；

}

//Printer.Java

public class Printer implements Printable{

private String name；

public Printer(){

System.out.println("正在产生Printer的对象实例")；

}

public Printer(String name){

this.name=name；

heavyJob("正在产生Printer的对象实例("+name+")")；

public void setPrinterName(String name){

this.name=name；

public String getPrinterName(){

return name；

public void print(String string){

System.out.println("===" +name+" ====")；

System.out.println(string)；

}

}

//PrinterProxy.Java

public class PrinterProxy (2) Printable{

private String name；

private Printer real；

public PrinterProxy(){}

public PrinterProxy(String name){

this.name=name；

}

public gynchronized void setPrinterName(String name){

if( (3) ){

real.setPrinterName(name)；

}

this.name=name；

}

public String getprinterName(){

return name；

}

public void print(String string){

(4)；

real.print(string)；

}

private synchronized void realize(){//产生真正的Printer对象

if(real==null){

real=(5)；

}

}

}

(1)

阅读以下说明和程序流程图，将应填入 (n) 处的字句写在对应栏内。

[说明]

假定用一个整型数组表示一个长整数，数组的每个元素存储长整数的一位数字，则实际的长整数m表示为：

m=a[k]×10k-2+a[k-1]×10k-3+…+a[3]×10+a[2]

其中a[1]保存该长整数的位数，a[0]保存该长整数的符号：0表示正数、1表示负数。注：数组下标从0开始。

流程图(图4-1)用于计算长整数的加(减)法。运算时先决定符号，再进行绝对值运算。对于绝对值相减情况，总是绝对值较大的减去绝对值较小的，以避免出现不够减情况。注，此处不考虑溢出情况，即数组足够大。这样在程序中引进两个指针pA和pB，分别指向绝对值较大者和较小者。而对绝对值相加,情况，让pA指向LA，pB指向LB，不区分绝对值大小。pA±pB可用通式pA+flag*pB来计算，flag为+1时即对应pA+pB，flag为-1时即对应pA-pB。需特别注意的是，对于相减，不够减时要进行借位，而当

最高位借位后正好为0时，结果的总位数应减1；对于加法，有最高进位时，结果的总位数应加1。

流程图中涉及的函数说明如下：

(1)cmp(int *LA，int *LB)函数，用于比较长整数LA与LB的绝对值大小，若LA绝对值大于LB绝对值则返回正值，LA绝对值小于LB绝对值返回负值，相等则返回0。

(2)max(int A，int B)函数，用于返回整数A与B中较大数。

另外，对流程图中的写法进行约定：(1)“：=”表示赋值，如“flag：=LA[0]+LB[0]”表示将“LA[0]+LB[0]”的结果赋给flag，相当于C中的赋值语句：“flag=LA[0]+LB[0]；”；(2)“：”表示比较运算，如“flag：1”表示flag与1比较。

(1)

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

【说明】

某绘图系统存在Point、Line、Square三种图元，它们具有Shape接口，图元的类图关系如图5-1所示。现要将Circle图元加入此绘图系统以实现功能扩充。已知某第三方库已经提供了XCircle类，且完全满足系统新增的Circle图元所需的功能，但XCircle不是由Shape派生而来，它提供的接口不能被系统直接使用。代码5-1既使用了XCircle又遵循了Shape规定的接口，既避免了从头，开发一个新的Circle类，又可以不修改绘图系统中已经定义的接口。代码5-2根据用户指定的参数生成特定的图元实例，并对之进行显示操作。

绘图系统定义的接口与XCircle提供的显示接口及其功能如下表所示：

【代码5-1】

class Circle：public (1) {

pfivme：

(2) m_circle；

public：

void display(){

m_circle． (3)；

}

}；

【代码5-2】

class Factory{

public：

(4) getShapeInstance (int type){ //生成特定类实例

switch (type){

case 0：rcturn new Point；

Case l：return new Rectangle；

case 2: return new Line;

case 3: return new Circle;

default: return NULL;

} void main (int argo, char *argv[]) {

if (argc!=2) {

cout ＜＜ "error parameters !" ＜＜ endl; return; inttype=atoi (argv[1]) ;

Factory factory;

Shape *s;

s = factory. (5):

if (s==NULL) {

cout ＜＜ "Error get the instance !" ＜＜ endl;

return;

}

s-＞display () ;

(6);

return;

阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在答题纸的对应栏内。

【说明】

一个印刷电路板的布线区域可分成n×m个方格，如图3-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图3-1(b)中虚线所示。为了避免线路相交，应将已布过线的方格做封锁标记，其他线路不允许穿过被封锁的方格。

设给定印刷电路板的起始方格x与目的方格y尚未布线，求这两个方格间最短布线方案的基本思路是：从起始方格x开始，先考查距离起始方格距离为1的可达方格并用一个路径长度值标记，然后依次考查距离为2，3，…的可达方格，直到距离为k的某一个可达方格就是目标方格y时为止，或者由于不存在从x到y的布线方案而终止。布线区域中的每一个方格与其相邻的上、下、左、右四个方格之间的距离为1，依次沿下、右、上、左这四个方向考查，并用一个队列记录可达方格的位置。表3-1给出了沿这四个方向前进1步时相对于当前方格的相对偏移量。

例如，设印刷电路板的布线区域可划分为一个6×8的方格阵列，如图3-2(a)所示，其中阴影表示已封锁方格。从起始方格x(位置[3，2]，标记为0)出发，按照下、右、上、左的方向依次考查，所标记的可达方格如图3-2(a)所示，目标方格为y(位置[4，7]，标记为10)，相应的最短布线路径如图3-2(b)虚线所示。

【图3-2】

图3-3和图3-4所示的流程图即利用上述思路，在电路板方格阵列中进行标记，图

中使用的主要符号如表3-2所示。在图3-4中，设置电路板初始格局即将可布线方格置为数值-1、已布线方格(即封锁方格)置为-9。设置方格阵列“围墙”的目的是省略方格位置的边界条件判定，方法是在四周附加方格，并将其标记为-9(与封锁标记相同)。

供选择的答案

A．Found≠true B．Found=true

C．T=EndPos D．Q．insert(T)

E．T←Q.delete() F．CurPos=EndPos

G．i≥4 H．CurPos←Q．delete()

I．Grid[T.row,T.col]=-1 J．Grid[T.row,T.col]≠-1

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

【说明】

学生住宿服务系统帮助学生在就学的缄市内找到所需的住房，系统对出租的房屋信息、房主信息、需要租房的学生信息以及学生和房主的会面信息进行管理和维护。

房主信息包括姓名、地址、电话号码以及系统分配的唯一身份标识(D)和密码；房屋信息包括房屋地址、类型(单间/套间)、适合住宿的人数、房租、房主的ID以及现在是否可以出租(例如由于装修原因，需等到装修后才可出租或者房屋已被租出)。每当房屋信息发生变化时，房主必须通知系统，系统将更新房屋文件以便学生能够获得准确的可租用房屋信息。房主向系统中加入可租用的房屋信息时，须交纳一定的费用，由系统自动给出费用信息。房主可随时更新房屋的各种属性。

学生可通过系统查询现有的可租用的房屋，但必须先在系统中注册。学生信息包括姓名、现住址、电话号码、出生日期、性别以及系统分配的唯一身份标识(1D)和密码。若学生希望租用某房屋，则需要发出租房请求，请求中包含房屋的详细信息，系统将安排学生与房主会面的时间和地点，并将会面信息通知学生和房主，会面信息包括会面时间、地点以及会面双方的基本信息，系统将记录会面信息。

学生住宿服务系统的顶层图如图1-1所示；学生住宿服务系统的第0层DFD图如图 1-2所示，其中，加工3的细化图如图1-3所示。

(1)数据流图1-1缺少了一条数据流(在图1-2中也未给出该数据流)，请给出此数据流的起点和终点，并采用说明中的词汇给出此数据流名。

(2)数据流图1-2中缺少了与“查询房屋”加工相关的数据流，请指出此数据流的起点和终点。

试题六（共15分）

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

【说明】

某咖啡店当卖咖啡时，可以根据顾客的要求在其中加入各种配料，咖啡店会根据所加入的配料来计算费用。咖啡店所供应的咖啡及配料的种类和价格如下表所示。

【Java代码】

import java.util.*；

（1） class Beverage { //饮料

String description = "Unknown Beverage";

public （2） （）{return description;}

public （3） ;

}

abstract class CondimentDecorator extends Beverage { //配料

（4） ;

}

class Espresso extends Beverage { //蒸馏咖啡

private final int ESPRESSO_PRICE = 25;

public Espresso() { description="Espresso"; }

public int cost() { return ESPRESSO_PRICE; }

}

class DarkRoast extends Beverage { //深度烘焙咖啡

private finalint DARKROAST_PRICE = 20;

public DarkRoast() { description = "DarkRoast"; }

public int cost（）{ rcturn DARKROAST PRICE; }

}

class Mocha extends CondimentDecorator { //摩卡

private final int MOCHA_PRICE = 10;

public Mocha（Beverage beverage） {

this.beverage = beverage;

}

public String getDescription（） {

return beverage.getDescription0 + ", Mocha";

}

public int cost() {

return MOCHA_PRICE + beverage.cost();

}

}

class Whip extends CondimentDecorator { //奶泡

private finalint WHIP_PRICE = 8;

public Whip（Beverage beverage） { this.beverage = beverage; }

public String getDescription（） {

return beverage.getDescription（）+", Whip";

}

public int cost() { return WHIP_PRICE + beverage.cost(); }

}

public class Coffee {

public static void main（String args[]） {

Beverage beverage = new DarkRoast();

beverage=new Mocha（ 5 ）;

beverage=new Whip （ 6 ）;

System.out.println（beverage.getDescription() +"￥" +beverage.cost()）;

}

}

编译运行上述程序，其输出结果为：

DarkRoast, Mocha, Whip ￥38