試題二
閱讀以下說明和表，回答問題1～問題4。
【說明】
某公司信息管理系統(tǒng)的需求分析和部分關(guān)系模式設(shè)計(jì)的結(jié)果描述如下。
1．公司有多個(gè)部門，每個(gè)部門有一名負(fù)責(zé)人、一間辦公室、一部電話、多名職員，每個(gè)職員最多屬于一個(gè)部門，負(fù)責(zé)人也是一名公司職員。
2．公司職員的月工資大于等于1000元且小于等于8000元。
3．?dāng)?shù)據(jù)庫的部分關(guān)系模式設(shè)計(jì)如下：
職員(職員號(hào)，職員姓名，月工資，部門號(hào)，辦公室，電話)
部門(部門號(hào)，部門名，負(fù)責(zé)人代碼，任職時(shí)間)
4．“職員”和“部門”的關(guān)系示例分別如表2-1和表2-2所示。

【問題1】
根據(jù)上述說明，請(qǐng)給出
(1)“職員”關(guān)系模式的主鍵和外鍵。
(2)“部門”關(guān)系模式的主鍵和外鍵。
【問題2】
(1)用SQL定義“職員”關(guān)系模式，請(qǐng)?jiān)诳杖碧幪钊胝_的內(nèi)容。
Create Table 職員 ( 職員號(hào)CHAR(5)    (a)  ，
職員姓名CHAR(8)，
月工資  NUMBER(4)，
部門號(hào)  CHAR(1)，
辦公室  CHAR(20)，
電話    CHAR(8)，
(b)  (部門號(hào))，
CHECK (月工資＞=1000 AND月工資＜=8000))；
(2)針對(duì)人數(shù)大于等于2的部門創(chuàng)建視圖D_View(Dept，D_num，D_Totals， D_AvgPay)，其中，Dept為部門號(hào)，D_num為部門人數(shù)，D_Totals為工資總數(shù)，D_AvgPay為平均工資，請(qǐng)?jiān)诳杖碧幪钊胝_的內(nèi)容。
Create View D_View (Dept，D_num，D_Totfls，D_AvgPay)As
(Select部門號(hào)，  (c)
from  職員
(d)  count(*)＞=2 WHERE 部門號(hào) IS NOT NULL)；
【問題3】
對(duì)于表2-1、表2-2所示的“職員”和“部門”關(guān)系，請(qǐng)指出下列各行是否可以插入“職員”關(guān)系，為什么?

【問題4】
原來的“職員”關(guān)系模式存在什么問題?在不增加新關(guān)系模式的前提下，請(qǐng)給出修改后的“職員”和“部門”關(guān)系模式。

試題三
閱讀以下說明和流程圖，從供選擇的答案中選出應(yīng)填入流程圖  (n)  處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
一個(gè)印刷電路板的布線區(qū)域可分成n×m個(gè)方格，如圖3-1(a)所示，現(xiàn)在需要確定電路板中給定的兩個(gè)方格的中心點(diǎn)之間的最短布線方案。電路只能沿水平或垂直方向布線，如圖3-1(b)中虛線所示。為了避免線路相交，應(yīng)將已布過線的方格做封鎖標(biāo)記，其他線路不允許穿過被封鎖的方格。

設(shè)給定印刷電路板的起始方格x與目的方格y尚未布線，求這兩個(gè)方格間最短布線方案的基本思路是：從起始方格x開始，先考查距離起始方格距離為1的可達(dá)方格并用一個(gè)路徑長度值標(biāo)記，然后依次考查距離為2，3，…的可達(dá)方格，直到距離為k的某一個(gè)可達(dá)方格就是目標(biāo)方格y時(shí)為止，或者由于不存在從x到y(tǒng)的布線方案而終止。布線區(qū)域中的每一個(gè)方格與其相鄰的上、下、左、右四個(gè)方格之間的距離為1，依次沿下、右、上、左這四個(gè)方向考查，并用一個(gè)隊(duì)列記錄可達(dá)方格的位置。表3-1給出了沿這四個(gè)方向前進(jìn)1步時(shí)相對(duì)于當(dāng)前方格的相對(duì)偏移量。

例如，設(shè)印刷電路板的布線區(qū)域可劃分為一個(gè)6×8的方格陣列，如圖3-2(a)所示，其中陰影表示已封鎖方格。從起始方格x(位置[3，2]，標(biāo)記為0)出發(fā)，按照下、右、上、左的方向依次考查，所標(biāo)記的可達(dá)方格如圖3-2(a)所示，目標(biāo)方格為y(位置[4，7]，標(biāo)記為10)，相應(yīng)的最短布線路徑如圖3-2(b)虛線所示。 【圖3-2】


圖3-3和圖3-4所示的流程圖即利用上述思路，在電路板方格陣列中進(jìn)行標(biāo)記，圖【圖3-3】





中使用的主要符號(hào)如表3-2所示。在圖3-4中，設(shè)置電路板初始格局即將可布線方格置為數(shù)值-1、已布線方格(即封鎖方格)置為-9。設(shè)置方格陣列“圍墻”的目的是省略方格位置的邊界條件判定，方法是在四周附加方格，并將其標(biāo)記為-9(與封鎖標(biāo)記相同)。

供選擇的答案
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程序，將應(yīng)填入  (n)  處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
假設(shè)需要將N個(gè)任務(wù)分配給N個(gè)工人同時(shí)去完成，每個(gè)人都能承擔(dān)這N個(gè)任務(wù)，
但費(fèi)用不同。下面的程序用回溯法計(jì)算總費(fèi)用最小的一種工作分配方案，在該方案中，為每個(gè)人分配1個(gè)不同的任務(wù)。
程序中，N個(gè)任務(wù)從0開始依次編號(hào)，N個(gè)工人也從0開始依次編號(hào)，主要的變量說明如下：
c[i][j]：將任務(wù)i分配給工人j的費(fèi)用；
task[i]：值為0表示任務(wù)i未分配，值為j表示任務(wù)i分配給工人j；
worker[k]：值為0表示工人k未分配任務(wù)，值為1表示工人k已分配任務(wù)；
mincost：最小總費(fèi)用。


【C程序】
#include＜stdio.h＞
#define N  8    /*N表示任務(wù)數(shù)和工人數(shù)*/
int c[N][N]；
unsigned int mincost=65535；    /*設(shè)置min的初始值，大于可能的總費(fèi)用*/
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++)    /*分配任務(wù)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++) { /*設(shè)置每個(gè)任務(wù)由不同工人承擔(dān)時(shí)的費(fèi)用及全局?jǐn)?shù)組的初值*/
worker[i]=0；task[i]=0；  temp[i]=0；
for(j=0；j＜N；j++)
scanf ("%d"，&c[i][j])；
}
Plan (0，0)；    /*從任務(wù)0開始分配*/
printf("\n最小費(fèi)用=%d\n"，mincost)；
for(i二0；i＜N；i++)
pnntf("Task%d iB assigned toWorker%d\n",i,temp[i])；
}/*main*/