第2題： 閱讀下列說(shuō)明和圖，回答問(wèn)題1至問(wèn)題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
某學(xué)校擬開(kāi)發(fā)一套實(shí)驗(yàn)管理系統(tǒng)，對(duì)各課程的實(shí)驗(yàn)安排情況進(jìn)行管理。
【需求分析】
一個(gè)實(shí)驗(yàn)室可進(jìn)行多種類(lèi)型不同的實(shí)驗(yàn)。由于實(shí)驗(yàn)室和實(shí)驗(yàn)員資源有限，需根據(jù)學(xué)生人數(shù)分批次安排實(shí)驗(yàn)室和實(shí)驗(yàn)員。一門(mén)課程可以為多個(gè)班級(jí)開(kāi)設(shè)，每個(gè)班級(jí)每學(xué)期可以開(kāi)設(shè)多門(mén)課程。一門(mén)課程的一種實(shí)驗(yàn)可以根據(jù)人數(shù)、實(shí)驗(yàn)室的可容納人數(shù)和實(shí)驗(yàn)類(lèi)型，分批次開(kāi)設(shè)在多個(gè)實(shí)驗(yàn)室的不同時(shí)間段。一個(gè)實(shí)驗(yàn)室的一次實(shí)驗(yàn)可以分配多個(gè)實(shí)驗(yàn)員負(fù)責(zé)輔導(dǎo)實(shí)驗(yàn)，實(shí)驗(yàn)員給出學(xué)生的每次實(shí)驗(yàn)成績(jī)。
（1）課程信息包括：課程編號(hào)、課程名稱(chēng)、實(shí)驗(yàn)學(xué)時(shí)、授課學(xué)期和開(kāi)課的班級(jí)等信息；實(shí)驗(yàn)信息記錄該課程的實(shí)驗(yàn)進(jìn)度信息，包括：實(shí)驗(yàn)名、實(shí)驗(yàn)類(lèi)型、學(xué)時(shí)、安排周次等信息，如表2-1所示。

（2）以課程為單位制定實(shí)驗(yàn)安排計(jì)劃信息，包括：實(shí)驗(yàn)地點(diǎn)，實(shí)驗(yàn)時(shí)間、實(shí)驗(yàn)員等信息，實(shí)驗(yàn)計(jì)劃如表2-2所示。

（3）由實(shí)驗(yàn)員給出每個(gè)學(xué)生每次實(shí)驗(yàn)的成績(jī)，包括：實(shí)驗(yàn)名、學(xué)號(hào)、姓名、班級(jí)、實(shí)驗(yàn)成績(jī)等信息，實(shí)驗(yàn)成績(jī)?nèi)绫?-3所示。

（4）學(xué)生的實(shí)驗(yàn)課程總成績(jī)根據(jù)每次實(shí)驗(yàn)的成績(jī)以及每次實(shí)驗(yàn)的難度來(lái)計(jì)算。
【概念模型設(shè)計(jì)】
根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖（不完整）如圖2-1所示。

【邏輯結(jié)構(gòu)設(shè)計(jì)】
根據(jù)概念模型設(shè)計(jì)階段完成的實(shí)體聯(lián)系圖，得出如下關(guān)系模式（不完整）：
課程（課程編號(hào)，課程名稱(chēng)，授課院系，實(shí)驗(yàn)學(xué)時(shí)）
班級(jí)（班級(jí)號(hào)，專(zhuān)業(yè)，所屬系）
開(kāi)課情況（ （1）  ，授課學(xué)期）
實(shí)驗(yàn)（   （2）    ，實(shí)驗(yàn)類(lèi)型，難度，學(xué)時(shí)，安排周次）
實(shí)驗(yàn)計(jì)劃（ （3） ，實(shí)驗(yàn)時(shí)間，人數(shù)）
實(shí)驗(yàn)員（  （4）  ，級(jí)別）
實(shí)驗(yàn)室（實(shí)驗(yàn)室編號(hào)，地點(diǎn)，開(kāi)放時(shí)間，可容納人數(shù)，實(shí)驗(yàn)類(lèi)型）
學(xué)生（   （5）  ，姓名，年齡，性別）
實(shí)驗(yàn)成績(jī)（   （6）    ，實(shí)驗(yàn)成績(jī)，評(píng)分實(shí)驗(yàn)員）
【問(wèn)題1】（6分）
補(bǔ)充圖2-1中的聯(lián)系和聯(lián)系的類(lèi)型。
【問(wèn)題2】（6分）
根據(jù)圖2-1，將邏輯結(jié)構(gòu)設(shè)計(jì)階段生成的關(guān)系模式中的空（1）~（6）補(bǔ)充完整并用下劃線指出這六個(gè)關(guān)系模式的主鍵。
【問(wèn)題3】（3分）
如果需要記錄課程的授課教師，新增加“授課教師”實(shí)體。請(qǐng)對(duì)圖2-1進(jìn)行修改，畫(huà)出修改后的實(shí)體間聯(lián)系和聯(lián)系的類(lèi)型。
答案解析與討論：m.xiexiliangjiufa.com/st/380925985.html

第3題： 閱讀下列說(shuō)明和圖，回答問(wèn)題1至問(wèn)題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
某運(yùn)輸公司決定為新的售票機(jī)開(kāi)發(fā)車(chē)票銷(xiāo)售的控制軟件。圖3-1給出了售票機(jī)的面板示意圖以及相關(guān)的控制部件。

售票機(jī)相關(guān)部件的作用如下所述：
（1）目的地鍵盤(pán)用來(lái)輸入行程目的地的代碼（例如，200表示總站）。
（2）乘客可以通過(guò)車(chē)票鍵盤(pán)選擇車(chē)票種類(lèi)（單程票、多次往返票和座席種類(lèi)）。
（3）繼續(xù)/取消鍵盤(pán)上的取消按鈕用于取消購(gòu)票過(guò)程，繼續(xù)按鈕允許乘客連續(xù)購(gòu)買(mǎi)多張票。
（4）顯示屏顯示所有的系統(tǒng)輸出和用戶提示信息。
（5）插卡口接受MCard（現(xiàn)金卡），硬幣口和紙幣槽接受現(xiàn)金。
（6）打印機(jī)用于輸出車(chē)票。
假設(shè)乘客總是支付恰好需要的金額而無(wú)需找零，售票機(jī)的維護(hù)工作（取回現(xiàn)金、放入空白車(chē)票等）由服務(wù)技術(shù)人員完成。
系統(tǒng)采用面向?qū)ο蠓椒ㄩ_(kāi)發(fā)，使用UML進(jìn)行建模。系統(tǒng)的頂層用例圖和類(lèi)圖分別如圖3-2和圖3-3所示。

【問(wèn)題1】（5分）
根據(jù)說(shuō)明中的描述，給出圖3-2中A1和A2所對(duì)應(yīng)的參與者，U1所對(duì)應(yīng)的用例，以及（1）、（2）處所對(duì)應(yīng)的關(guān)系。
【問(wèn)題2】（7分）
根據(jù)說(shuō)明中的描述，給出圖3-3中缺少的C1~C4所對(duì)應(yīng)的類(lèi)名以及（3）～（6）處所對(duì)應(yīng)的多重度。
【問(wèn)題3】（3分）
圖3-3中的類(lèi)圖設(shè)計(jì)采用了中介者（Mediator）設(shè)計(jì)模式，請(qǐng)說(shuō)明該模式的內(nèi)涵。
答案解析與討論：m.xiexiliangjiufa.com/st/380935084.html

第4題： 閱讀下列說(shuō)明和C代碼，回答問(wèn)題1至問(wèn)題3，將解答寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
對(duì)有向圖進(jìn)行拓?fù)渑判虻姆椒ㄊ牵?br />（1）初始時(shí)拓?fù)湫蛄袨榭眨?br />（2）任意選擇一個(gè)入度為0的頂點(diǎn)，將其放入拓?fù)湫蛄兄?，同時(shí)從圖中刪除該頂點(diǎn)以及從該頂點(diǎn)出發(fā)的?。?br />（3）重復(fù)（2），直到不存在入度為0的頂點(diǎn)為止（若所有頂點(diǎn)都進(jìn)入拓?fù)湫蛄袆t完成拓?fù)渑判?，否則由于有向圖中存在回路無(wú)法完成拓?fù)渑判颍?br />函數(shù)int* TopSort(LinkedDigraph G)的功能是對(duì)有向圖G中的頂點(diǎn)進(jìn)行拓?fù)渑判颍祷赝負(fù)湫蛄兄械捻旤c(diǎn)編號(hào)序列，若不能完成拓?fù)渑判?，則返回空指針。其中，圖G中的頂點(diǎn)從1開(kāi)始依次編號(hào)，頂點(diǎn)序列為v1，v2，…，vn，圖G采用鄰接表示，其數(shù)據(jù)類(lèi)型定義如下：
#define MAXVNUM 50  /*最大頂點(diǎn)數(shù)*/
typedef struct ArcNode{ /*表結(jié)點(diǎn)類(lèi)型*/
int adjvex;    /*鄰接頂點(diǎn)編號(hào)*/
struct ArcNode *nextarc;   /*指示下一個(gè)鄰接頂點(diǎn)*/
}ArcNode;
typedef struct AdjList{ /*頭結(jié)點(diǎn)類(lèi)型*/
char vdata;   /*頂點(diǎn)的數(shù)據(jù)信息*/
ArcNode *firstarc;   /*指向鄰接表的第一個(gè)表結(jié)點(diǎn)*/
}AdjList;
typedef struct LinkedDigraph{     /*圖的類(lèi)型*/
int n;    /*圖中頂點(diǎn)個(gè)數(shù)*/
AdjList Vhead[MAXVNUM];   /*所有頂點(diǎn)的頭結(jié)點(diǎn)數(shù)組*/
}LinkedDigraph;
例如，某有向圖G如圖4-1所示，其鄰接表如圖4-2所示。

函數(shù)TopSort中用到了隊(duì)列結(jié)構(gòu)(Queue的定義省略)，實(shí)現(xiàn)隊(duì)列基本操作的函數(shù)原型如下表所示：

函 數(shù) 原 型	說(shuō)      明
void InitQueue（Queue*Q）	初始化隊(duì)列（構(gòu)造一個(gè)空隊(duì)列）
bool IsEmpty（Queue Q）	判斷隊(duì)列是否為空，若是則返回true，否則返回false
void EnQueue（Queue*Q,int e）	元素入隊(duì)列
void DeQueue（Queue*Q,int*p）	元素出隊(duì)列

【C代碼】
int *TopSort(LinkedDigraph G) {
ArcNode *p;  /*臨時(shí)指針，指示表結(jié)點(diǎn)*/
Queue Q; /*臨時(shí)隊(duì)列，保存入度為0的頂點(diǎn)編號(hào)*/
int k = 0;    /*臨時(shí)變量，用作數(shù)組元素的下標(biāo)*/
int j = 0， w = 0;    /*臨時(shí)變量，用作頂點(diǎn)編號(hào)*/
int *topOrder， *inDegree;
topOrder = (int *)malloc((G.n+1) * sizeof(int));   /*存儲(chǔ)拓?fù)湫蛄兄械捻旤c(diǎn)編號(hào)*/
inDegree = (int *)malloc((G.n+1) * sizeof(int));   /*存儲(chǔ)圖G中各頂點(diǎn)的入度*/
if (!inDegree || !topOrder) return NULL;
（1）  ;   /*構(gòu)造一個(gè)空隊(duì)列*/
for ( j = 1; j <= G.n; j++ ) { /*初始化*/
topOrder[j] = 0;  inDegree[j] = 0;
}
for (j = 1; j <= G.n; j++) /*求圖G中各頂點(diǎn)的入度*/
for( p = G.Vhead[j].firstarc; p; p = p->nextarc )
inDegree[p-> adjvex] += 1;
for (j = 1; j <= G.n; j++) /*將圖G中入度為0的頂點(diǎn)保存在隊(duì)列中*/
if ( 0 == inDegree[j] ) EnQueue(&Q，j);
while (!IsEmpty(Q)) {
（2） ; /*隊(duì)頭頂點(diǎn)出隊(duì)列并用w保存該頂點(diǎn)的編號(hào)*/
topOrder[k++] = w;
/*將頂點(diǎn)w的所有鄰接頂點(diǎn)的入度減1（模擬刪除頂點(diǎn)w及從該頂點(diǎn)出發(fā)的弧的操作）*/
for(p = G.Vhead[w].firstarc; p; p = p->nextarc) {
（3）-= 1;
if (0 ==（4）) EnQueue(&Q， p->adjvex);
}/* for */
}/* while */
free(inDegree);
if (  （5）  )
return NULL;
return topOrder;
} /*TopSort*/
【問(wèn)題1】（9分）
根據(jù)以上說(shuō)明和C代碼，填充C代碼中的空（1）～（5）。
【問(wèn)題2】（2分）
對(duì)于圖4-1所示的有向圖G，寫(xiě)出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄?。若將函?shù)TopSort中的隊(duì)列改為棧，寫(xiě)出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄小?br />【問(wèn)題3】（4分）
設(shè)某有向無(wú)環(huán)圖的頂點(diǎn)個(gè)數(shù)為n、弧數(shù)為e，那么用鄰接表存儲(chǔ)該圖時(shí)，實(shí)現(xiàn)上述拓?fù)渑判蛩惴ǖ暮瘮?shù)TopSort的時(shí)間復(fù)雜度是（6）。
若有向圖采用鄰接矩陣表示（例如，圖4-1所示有向圖的鄰接矩陣如圖4-3所示），且將函數(shù)TopSort中有關(guān)鄰接表的操作修改為針對(duì)鄰接矩陣的操作，那么對(duì)于有n個(gè)頂點(diǎn)、e條弧的有向無(wú)環(huán)圖，實(shí)現(xiàn)上述拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是（7）。

從下列的2道試題（試題五和試題六）中任選1道解答。如果解答的試題數(shù)超過(guò)1道，則題號(hào)小的1道解答有效。
答案解析與討論：m.xiexiliangjiufa.com/st/3809416600.html