试题一（15分） 
　　阅读以下说明和数据流图，回答问题1至问题3，将解答题纸的对应栏内。
[说明] 
　　学生住宿服务系统帮助学生在就学的城市内找以所需的住房，系统对出租的房屋信息、房主信息、需要租房的学生信息以及学生和房主的会面住处进行管理和维护。
　　房主信息包括姓名、地址、电话号码以及系统分配的唯一身份标识（ID）和密码；房屋信息包括房屋地址、类型（单间/套间）、适合住宿的人数、房租、房主的ID以及现在是否可以出租（例如由于装修原因，需等到装修后才可出租或者房屋已被租出）。每当房房屋信息发生变化时，房主须通知系统，系统将更新房到文件以便学生能够获得准确的可租用房屋信息，房主向系统中加入可租用的房屋信息时，需交纳一定的费用，由系统自动给出费用信息。房主可随时更新房屋的各种属性。
　　学生可通过系统查询现有的可租用的房屋，但必须先在系统中注册。学生信息包括姓名、现住址、电话号码、出生日期、性别以及系统分配的唯一身份标识（ID）和密码。若学生希望租用某房屋，则需要发出租房请求，请求中包含房屋的详细信息，系统将安排学生与房主会面的时间和地点，并将会面信息通知学生和房主，会面信息包括会面时间、地点以及会面双方的基本信息，系统将记录会面信息。
　　学生住宿服务系统的顶层图如图1-1所示；学生住宿服务系统的第0层DFD图如图1-2所示，其中，加工3的细化图如图1-3所示。 
[问题1]（6分） 
　　（1）数据流图1-1缺少了一条数据流（在图1-2中也未给出该数据流），请给出此数据流的起点和终点，并采用说明中的词汇给出此数据流名。
　　（2）数据流图1-2中缺少了与"查询房屋"加工相关的数据流，请指出此数据流的起点和终点。
[问题2]（4分） 
　　"安排会面"加工除需要写入会面文件外，还需要访问哪些文件？
[问题3]（5分） 
　　请补齐下列数据字典条目：
　　登录信息=学生ID+密码
　　注册信息= 
[数据流图1-1]  

[数据流图1-2]  

[数据流图1-3]  

试题二（15分） 
　　阅读以下说明和表，回答问题1至问题4，将解答填入答题纸的对应栏内。
[说明] 
　　某公司信息管理系统的需求分析和部分关系模式的结果描述如下：
　　1. 公司有多个部门，每个部门有一名负责人、一间办公室、一部电话、多名职员，每个职员最多数一个部门，负责人也是公司一名职员。
　　2. 公司职员的工资大于等于1000元且最小等于8000。
　　3. 数据库的部分关系模式设计如下：
　　职员（职员号，职工姓名，月工资。部门号、办公室，电话）
　　部门（部门号，部门名，负责人代码，任职时间）
　　4."职员"和"部门"的关系示例分别如表2-1和表2-2所示
[表2-1]  

"职员"关系

[表2-2]  

"部门"关系

[问题1]（4分） 
　　根据上述说明，请给出
　　（1）"职员"关系模式的主键和外键。
　　（2）"部门"关系模式的主键和外键。
[问题2]（4分） 
　　（1）用SQL定义"职员"关系模式，请在空缺处填入正确的内容。
　　　　Create Table职员（职员号CHAR（5）__(a)__ ，
　　　　　　　　　　职员姓名 CHAR（8），
　　　　　　　　　　月工资 NUMBER（4），
　　　　　　　　　　部门号 CHAR（1），
　　　　　　　　　　办公室 CHAR（20）
　　　　　　　　　　电话 CHAR（8），
　　　　　　　　　　__(b)__ （部门号），
　　　　　　　　　　CHECK（月工资＞=1000 AND月工资＜=8000））；
　　（2）针对人数大于等于2的部门创建视图D_View（Dept， D_num，D_Totals，D_Avgpay），其中，Dept为部门号，D num为部门人数，D_Totals为部门人数，D_Avgpay为平均工资，请在空缺处填入正确的内容。
　　　　Create View D_View（Dept，D_num，D_Totals，D_AvgPay）As
　　　　　　　　　　(Select部门号，__(c)__ 
　　　　　　　　　　from 职员
　　　　　　　　　　__(d)__ count（*）>=2 WHERE 部门号IS NOT NULL）：
[问题3]（3分） 
　　对于表2-1、表2-2所示的"职员"和"部门"关系，请指出下列各行是否可以插入"职员"关系，为什么？

[问题4]（4分） 
　　原来的"职员"关系模式存在什么问题？在不增加新关系模式的前提下，请给出修出改后的"职员"和"关系模式"。

试题三（15分） 
　　阅读以下说明和流程图，从供选择的答案中选出应填入流程图 __(n)__ 处的字句写在答题纸的对应栏内。
[说明] 
　　一个印刷电路板的布线区域可分成n×m个方格，如图3-1（a）所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布线方案。电路只能沿水平或垂直方向布线，如图3-1（b）中虚线所示。为了避免线路相交，应将已布过线的方格作成封锁标记，其他线路不允许穿过被封锁的方格。
[图3-1]   

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

[图3-3]  

[图3-4]  

　　●供选择的答案 
　　[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

试题四（15分） 
　　阅读以下说明和C程序，将应填入__(n)__ 处的字句写在答题纸对应栏内。
[说明] 
　　假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配1个不同的任务。
　　程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，主要的变量说明如下：
　　c[i][j]:将任务i分配给工人j的费用；
　　task[i]:值为0表示任务i未分配，值为j表示任务i分配给工人j；
　　worker[k]:值为0表示工人k未分配任务，值为1表示工人k已分配任务；
　　mincost:最小总费用。
[C程序] 
　　＃include <stdio.h>
　　＃define N 8　　　　　　　　　　/*N 表示任务数和工人数*/
　　int c[N][N]；
　　unsigned int mincost = 65535；　/*设置的初始值，大于可能的费用*/
　　int task[N]，temp[N]，worker[N]；
　　void plan(int k,unsigned int cost)
　　{ int i；
　　　if（ __(1)__ && cost<mincost）{
　　　　mincost = cost；
　　　　for(i=0；i<N；i++) temp[i]=task[i]；}
　　　else{
　　　　for(i=0；i<N；i++)　　　　　/*分配任务 k*/
　　　　if (worker[i]==0 && __(2)__){
　　　　　worker[i]=1；task[k]= __(3)__；
　　　　　Plan( __(4)__，cost+c[k][i])；
　　　　　__(5)__； task[k] = 0；
　　　　}/*if*/
　　　}
　　}/*Plan*/

　　void main()
　　{ int i,j；
　　for(i=o；i<N；i++){　　　　/*设置每个人任务由不同工人承担时的费用及全局数组的初值*/
　　　worker[i]=0；task[i]=0；temp[i]=0；
　　　for(j=0；j<n；j++)
　　　　scanf("%d",&c[i][j])；
　　　}
　　　Plan(0，0)； /*从任务0开始分配*/
　　　printf("\n最小差用=%d\n"，mincost)；
　　　for(i=0；i<N；i++)
　　　printf("Task% is assigned to Worker%d\n",i,temp[i])；
　　}　　　　　　/*main*/

试题五（15分） 
　　阅读以下说明和C++码，将应填入 __(n)__ 处的字名写在答题纸的对应栏内。
[说明] 
　　某绘图系统存在Point、Line、Square三种图元，它们具有Shape接口，图元的类图关系如图5-1所示。现要将Circle图元加入此绘图系统以实现功能扩充。已知某第三方库已经提供了XCircle不是由Shape派生而来，它提供了的接口不被系统直接使用。代码5-1既使用了XCircle又遵循了Shape规定的接口，即避免了从头开发一个新的Circle类，又可以不修改绘图系统中已经定义的接口。代码5-2根据用户指定的参数生成特定的图元实例，并对之进行显示操作。
　　绘图系统定义的接口与XCircle提供的显示接口及其功能如下表所示：

[图5-1]  

[代码5-1] 
　　class Circle：public __(1)__{
　　　Private:
　　　__(2)__ m_circle；
　　　public:
　　　void display () {
　　　　__(3)__
　　　}
　　}；
[代码5-2] 
　　class Factory{
　　　public:
　　　__(4)__ getShapeInstance(int type){　　//生成特定类实例
　　　　switch(type){
　　　　　case 0:returnnewPoint；
　　　　　case 1:return new Rectangle；
　　　　　case 2:return new Line；
　　　　　case 3: return new Circle；
　　　　　default : return NULL；
　　　　}
　　　}
　　}；
　　void main(int argc,char *argv[]){
　　　if(argc !=2){
　　　　cout<<"error parameters ！"<<endl；
　　　　return；
　　　}
　　　int type=atoi(argv[1]):
　　　Factory factory；
　　　Shape *s；
　　　S=factory.__(5)__；
　　　if(s==NULL){
　　　　cout<<"Error get the instance!"<<end；
　　　　return；
　　　}
　　　s->display()；
　　　__(6)__ ；
　　　return；
　　}

试题六（15分） 
　　阅读以下说明和Java代码，将应填入 __(n)__ 处的字名写在答题纸的对应栏内。
[说明] 
　　某绘图系统存在Point、Line、Square三种图元，它们具有Shape接口，图元的类图关系如图6-1所示。现要将Circle图元加入此绘图系统以实现功能扩充。已知某第三方库已经提供了XCircle类，且完全满足系统新增的Circle图元所需的功能，但XCircle又遵循了Shape规定的接口。既避免了从头开发一个新的Cicle类，又可以不修改绘图系统中已经定义的接口，代码6-2根据用户指定的参数生成特定的图元实例，并对之进行显示操作。
　　绘图系统定义的接口与XCircle提供的显示接口及其功能如下表所示：

[图6-1]  

[代码6-1] 
　　class Circle ___(1)___{
　　　private ___(2)___ pxc;
　　　public Circle () {　pxc = new ___(3)___;
　　　}
　　　public void display(){
　　　　pxc. ___(4)___;
　　　}
　　}
[代码6-2] 
　　public class Factory{
　　　public ___(5)___ getShapeInstance(int type){ //生成特定类实例
　　　　Switch(type){
　　　　　case 0：return new point()；
　　　　　case 1：return new Rectangle()；
　　　　　case 2：return new Line()；
　　　　　case 3：return new Circle()；
　　　　　default：return null；
　　　　}
　　　}
　　}；
　　public class App{
　　　public static void main(String argv[]){
　　　　if(argv.length !=1){
　　　　　System.out.println("error parameters!")；
　　　　　return；
　　　　}
　　　　int type=(new Integer(argv[0])).intValue()；
　　　　Factory factory=new Factory()；
　　　　if(s==null){
　　　　　System.out.println("Error get instance!")；
　　　　　Return；
　　　　}
　　　　s.display()；
　　　　return；
　　　}
　　}

试题七（15分钟） 
　　阅读以下说明和Visual Basic代码，将应填入 __(n)__ 处的字名写在答题纸的对应栏内。
[说明] 
　　某绘图系统定义了一个抽象类IShape, 现有三个类CPoint，CLine和CCircle,它们都具有IShape界面。相应的类图关系如图7-1所示。
　　已知某第三方库已经提供了XCircle类，且完全满足CCircle图元显示时所需的功能。化码7-1是抽象类IShape类模块内容,代码7-2实现了类CCircle的IShape界面，并使用了XCircle提供的显示功能。
XCircle提供的显示功能方法接口为displayIt。 
[图7-1]  

[代码7-1] 
　　Public Color As Long

　　Sub draw()
　　’方法体不包括可执行语句
　　End Sub

　　Sub move(stepx As Single，stepy As Single)
　　’方法体不包括可执行语句
　　End Sub

[代码7-2] 
　　__(1)__ 
　　Private color As Long
　　…　　’其他定义省略
　　Private ridged 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()　　　’使用XCircle提供的显示功能
　　　__(6)__
　　End Sub

　　Private Sub IShape_move (stepx As Single，stepy As Single)
　　　… 　　’省略描述
　　End Sub

下午答案 
试题一 
[问题1]
　（1）起点：学生住宿服务系统 终点：房主
　　 数据流名：费用信息 或 交纳的费用 或费用
　（2）起点：房屋文件　　　　　　　　终点：查询房屋　或　4　
[问题2] 
　　 房主文件 和 学生文件
[问题3] 
　　 姓名+现住址+电话号码+出生日期+性别

试题二 
[问题1] 
　（1）主键：职员号 外键：部门号
　（2）主键：部门号 ，或部门名 外键：负责人代码
[问题2] 
　（a） PRIMARY KEY
　（b） FOREIGN KEY（部门号），REFERENCES 部门
　（c） Count（*），Sum（月工资），Avg（月工资）
　（d） GROUP by 部门号 HAVING count（*）
[问题3] 
　（1）该行不能插入"职员"关系，它违反了用户定义完整性中月工资的取值范围必须大于等于1000元，小于等于8000元。
　（2）该行不能插入"职员"关系，因为职员号"60802"在表2-1中已存在，违反了实体完整性中主键必须唯一区分关系中的每一个属性。
　（3）该行可以插入"职员"关系，尽管部门号、电话和办公室为空，但是它表示该职员没有分配到某个部门。
[问题4] 
　　"职员"关系模式主要的问题是：
　　数据冗余问题。因为某部门的职员人数有多少，其办公室和电话将要重复存入多少。
　　数据修改不一致问题。因为某部门的办公室变了可能会导致某些职员的修改了，某些职员的未修改。
　　将关系模式修改为：职员（职员号，职员姓名，月工资，部门号）
　　　　　　　　　　　部门（部门号，部门名，负责人代码，任职时间，办公室，电话）

试题三 
　(1) [i]　或　i
　(2) [c]　或　c
　(3) [d]　或　d
　(4) [a]　或　a
　(5) [h]　或　h

试题四 
　(1) k>=N 或　k= =N
　(2) cose + c[k][i] < mincost
　(3) i
　(4) k+1
　(5) worker[i] = 0

试题五 
　(1) Shape
　(2) Xcircle
　(3) DisplayIt()
　(4) Shape *
　(5) getShapeInstance(type)
　(6) delete s

试题六 
　(1) implements Shape
　(2) XCircle
　(3) XCircle()
　(4) displayIt()
　(5) Shape
　(6) getShapeInstance(type)

试题七 
　(1) Implements IShape
　(2) XCircle
　(3) New XCircle
　(4) Get IShape_Color
　(5) Let Ishape_Color
　(6) bridged.displayIt