【问题

3】（3 分）

　　对于表

2-1、表 2-2 所示的

“职员”和“部门”关系，请指出下列各行是否可以插入“职员”关系，为什么？

 

【问题

4】（4 分）

原 来 的

“ 职 员 ”

关 系 模 式 存 在 什 么

问题？在不增加新关系模式的前提下，请给出修改后的

“职员”和“部门”关系模式。

试题三（

15 分）

　　阅读以下说明和流程图，从供选择的答案中选出应填入流程图

___(n)___处的字句写在答题纸的对应栏内。

[说明]

　　一个印刷电路板的布线区域可分成

n*m 个方格，如图 3-1(a)所示，现在需要确定电路板中给定的两个方格的中心点之间的最短布

线方案。电路只能沿水平或垂直方向布线，如图

3-1（b）中虚线所示。为了避免线路相交，应将已布过线的方格作封锁标记，其他线路不

允许穿过被封锁的方格。

[图 3-1]

　 　 设 给 定 印 刷 电 路 板

的起始方格

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]