試題3
閱讀下列說明和圖，回答問題1至問題3，將解答填入答題紙的對應欄內。
【說明】
某指紋門禁系統(tǒng)的體系結構如圖3-1所示，其主要部件有：主機(MainFrame)、鎖控器(LockController)、指紋采集器(FingerReader)和電控鎖(Lock)。
(1)系統(tǒng)中的每個電控鎖都有一個惟一的編號。鎖的狀態(tài)有兩種：“已鎖住”和“未
鎖住”。
(2)在主機上可以設置每把鎖的安全級別以及用戶的開鎖權限。只有當用戶的開鎖權限大于或等于鎖的安全級別并且鎖處于“已鎖住”狀態(tài)時，才能將鎖打開。
(3)用戶的指紋信息、開鎖權限以及鎖的安全級別都保存在主機上的數(shù)據(jù)庫中。
(4)用戶開鎖時，只需按一下指紋采集器。指紋采集器將發(fā)送一個中斷事件給鎖控器，鎖控器從指紋采集器讀取用戶的指紋并將指紋信息發(fā)送到主機，主機根據(jù)數(shù)據(jù)庫中存儲的信息來判斷用戶是否具有開鎖權限，若有且鎖當前處于“已鎖住”狀態(tài)，則將鎖打開；否則系統(tǒng)報警。
該系統(tǒng)采用面向對象方法開發(fā)，系統(tǒng)中的類以及類之間的關系用UML類圖表示，圖3-2是該系統(tǒng)類圖的一部分；系統(tǒng)的動態(tài)行為采用UML序列圖表示，圖3-3是用戶成功開鎖的序列圖。


【問題1】
圖3-2是該系統(tǒng)類圖的一部分，依據(jù)上述說明中給出的術語，給出類Lock的主要屬性。


【問題2】
依據(jù)上述說明中給出的詞語，將圖3-3中的(1)～(5)處補充完整。


【問題3】
組裝(composition)和聚集(aggregation)是UML中兩種非常重要的關系。請說明組裝和聚集分別表示什么含義?兩者的區(qū)別是什么?

試題4
閱讀下列說明和圖，回答問題1至問題3，將解答填入答題紙的對應欄內。
【說明】
在并發(fā)系統(tǒng)設計中，通過對信號量S的P、V操作實現(xiàn)進程的同步與互斥控制。
P(S):S:=S-1，若S≥0，則執(zhí)行P操作的進程繼續(xù)執(zhí)行：若S＜0，則置該進程為阻塞狀態(tài)，并將其插入阻塞隊列。
V(S):S:=S+1，若S＞0，則執(zhí)行V操作的進程繼續(xù)執(zhí)行；若S≤0，則從阻塞隊列喚醒一個進程，并將其插入就緒隊列，然后執(zhí)行V操作的進程繼續(xù)執(zhí)行。


【問題1】
在某并發(fā)系統(tǒng)中，有一個發(fā)送進程A、一個接收進程B、一個環(huán)形緩沖區(qū)BUFFER、信號量S1和S2。發(fā)送進程不斷地產生消息并寫入緩沖區(qū)BUFFER，接收進程不斷地從緩沖區(qū)BUFFER取消息。假設發(fā)送進程和接收進程可以并發(fā)地執(zhí)行，那么，當緩沖區(qū)的容量為N時，如何使用P、V操作才能保證系統(tǒng)的正常工作。發(fā)送進程A和接收進程B的工作流程如圖4-1所示。請在圖4-1中的空(1)～(4)處填入正確的內容。


【問題2】
若系統(tǒng)中有多個發(fā)送進程和接收進程，進程間的工作流程如圖4-2所示，其中空 (1)～(4)的內容與圖4-1相同。發(fā)送進程產生消息并順序地寫入環(huán)形緩沖區(qū)BUFFER，接收者進程順序地從BUFFER中取消息，且每條消息只能讀取一次。為了保證進程間的正常通信，增加了信號量SA和SB。
①請說明信號量SA和SB的物理意義，并在圖4-2中的空(5)和空(6)處填入正確的內容。
②請從圖4-2的(a)～(1)中選擇四個位置正確地插入P(SA)、V(SA)、P(SB)、V(SB)。


【問題3】
設系統(tǒng)中只有進程A和進程B，除了互斥地使用CPU和打印機R外，進程A和B不使用其他資源。另外，進程B的優(yōu)先級比A高，而進程A先于B準備好。進程A和 B的執(zhí)行情況如圖4-3所示，其中粗實線表示進程在執(zhí)行中，細實線表示打印機R在使用中(每個進程具有三種狀態(tài)：運行、就緒和阻塞)。


請分別說明進程A和B在圖4-3所示的t1、t2、t3、t4時刻所處的狀態(tài)；若是阻塞狀態(tài)，請說明阻塞原因。

13、閱讀下列函數(shù)說明和c代碼，將應填入  (n)  處的字句寫在答題紙的對應欄內。
【說明】
函數(shù)int Toplogical(Linded WDipaph  G.的功能是對圖G中的頂點進行拓撲排序，并返回關鍵路徑的長度。其中圖G表示一個具有n個頂點的AOE-網(wǎng)，圖中頂點從1～n依次編號，圖G的存儲結構采用鄰接表表示，其數(shù)據(jù)類型定義如下：
typedefstruct Gnode{               /* 鄰接表的表結點類型*/
iht adjvex;                  /* 鄰接頂點編號*/
iht weight;                 /* 弧上的權值*/
street Gnode *nextarc;          /* 指示下一個弧的結點*/
}Gnode;
typedef struct Adjlist{           /* 鄰接表的頭結點類型*/
char vdata;                  /*頂點的數(shù)據(jù)信息*/
struct Gnode *Firstadj;        /* 指向鄰接表的第一個表結點*/
}Adjlist;
typedef street LinkedWDigraph{      /* 圖的類型*/
int n, e;                  /* 圖中頂點個數(shù)和邊數(shù)*/
struct Adjlist *head;         /*指向圖中第一個頂點的鄰接表的頭結點 */
} LinkedWDigraph;
例如，某AOE-網(wǎng)如圖5-1所示，其鄰接表存儲結構如圖5-2所示。

【函數(shù)】
iht Toplogical(LinkedWDigraph G.
{ Gnode *p;
intj, w, top = 0;
iht *Stack, *ye, *indegree;
ye = (int *)malloe((G.n+1) * sizeof(int));
indegree = (int *)malloc((G.n+1)*sizeof(int));   /* 存儲網(wǎng)中各頂點的入度*/
Stack = (int *)malloe((G.n+1)*sizeof(int));     /* 存儲入度為0的頂點的編號*/
if(!ve||!indegree || !Stack)      exit(0);
for (j = 1;j ＜= G.n;j++) {
ve[j] = 0;    indegree[j]= 0;
}/*for*/
for(j= 1;j<=G.n;j++) { /* 求網(wǎng)中各頂點的入度*/
p = G.head[j].Firstadj;
while (p) {
(1)  ;  p = p→nextarc;
}/*while*/
}/*for*/
for (j = 1; j ＜= G.n; j++)                  /*求網(wǎng)中入度為0的頂點并保存其編號*/
if (!indegree[j])     Stack[++top] =j;
while (top ＞ 0) {
w=   (2)  ;
printf("%e  ", G.head[w].vdata);
p = G.head[w].Firstadj;
while (p) {
(3)   ;
if ( !indegree [p→adjvex])
Staek[++top] = p→adjvex;
if(   (4)  )
ve[p→adjvex] = ve[w] + p→weight;
p = p→nextarc;
}/* while */
}/* while */ return   (5)   ; }/*Toplogieal*/

閱讀以下說明和Java代碼，將應填入  (n)  處的字句寫在答題紙的對應欄內。
說明
類Queue表示隊列，類中的方法如下表所示。





類Node表示隊列中的元素；類EmptyQueueException 給出了隊列操作中的異常處理操作。
Java 代碼
public class TestMain{                            // 主類
public static void main(String args[]) {
Queue q = new Queue();
q.enqueue("first!");
q.enqueue("second!");
q.enqueue("third!");
(1)  {
while(true)
System.out.println(q. dequeue());
}
catch(   (2)  )  ( }
}
}
public class Queue {                              // 隊列
Node m_FirstNode;
public Queue() { m_FirstNode = null; }
public boolean isEmpty() {
if(m_FirstNode == null)  return true;
else  return false;
}
public void enqueue(Object newNode) {// 入隊操作
Node next = m_FirstNode;
if(next==null)  m_FirstNode = new Node(newNode);
else {
while(next.getNext() != null)  next = next.getNext();
next.setNext(new Node(newNode));
}
}
public Object dequeue()     (3)   {// 出隊操作
Object node;
if (isEmpty())
(4)   ;      // 隊列為空，拋出異常
else {
node = m_FirstNode.getObject();
m_FirstNode = m_FirstNode.getNext();
return node;
}
}
}
public class Node {                              // 隊列中的元素
Object m_Data;
Node m_Next;
public Node(Object data)          { m_Data = data;   m_Next = null; }
public Node(Object data, Node next)  { m_Data = data;   m_Next = next; }
public void setObject(Object data)   { m_Data = data; }
public Object getObject0          { return m_Data; }
public void setNext(Node next)      { m_Next = next; }
public Node getNext()             { return m_Next; }
}


public class EmptyQueueException extends     (5)   {  // 異常處理類
public EmptyQueueException0  {
System.out.println("隊列已空 ! ");
}
}