试题二
阅读以下说明和表，回答问题1～问题4。
【说明】
某公司信息管理系统的需求分析和部分关系模式设计的结果描述如下。
1．公司有多个部门，每个部门有一名负责人、一间办公室、一部电话、多名职员，每个职员最多属于一个部门，负责人也是一名公司职员。
2．公司职员的月工资大于等于1000元且小于等于8000元。
3．数据库的部分关系模式设计如下：
职员(职员号，职员姓名，月工资，部门号，办公室，电话)
部门(部门号，部门名，负责人代码，任职时间)
4．“职员”和“部门”的关系示例分别如表2-1和表2-2所示。

【问题1】
根据上述说明，请给出
(1)“职员”关系模式的主键和外键。
(2)“部门”关系模式的主键和外键。
【问题2】
(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_Totfls，D_AvgPay)As
(Select部门号，  (c)
from  职员
(d)  count(*)＞=2 WHERE 部门号 IS NOT NULL)；
【问题3】
对于表2-1、表2-2所示的“职员”和“部门”关系，请指出下列各行是否可以插入“职员”关系，为什么?

【问题4】
原来的“职员”关系模式存在什么问题?在不增加新关系模式的前提下，请给出修改后的“职员”和“部门”关系模式。

试题三
阅读以下说明和流程图，从供选择的答案中选出应填入流程图  (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-3】





中使用的主要符号如表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

试题四
阅读以下说明和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；    /*设置min的初始值，大于可能的总费用*/
int task[N]，temp[N]，workerIN]；
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=0；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++)
pnntf("Task%d iB assigned toWorker%d\n",i,temp[i])；
}/*main*/