1、試題一（共15分）閱讀下列說明和圖，回答問題1至問題4,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f明】某大型企業(yè)的數(shù)據(jù)中心為了集中管理、控制用戶對(duì)數(shù)據(jù)的訪問并支持大量的連接 需求，欲構(gòu)建數(shù)據(jù)管理中間件，其主要功能如下：（1）數(shù)據(jù)管理員可通過中間件進(jìn)行用戶管理、操作管理和權(quán)限管理。用戶管理 維護(hù)用戶信息，用戶信息（用戶名、密碼）存儲(chǔ)在用戶表中；操作管理維護(hù)數(shù)據(jù) 實(shí)體的標(biāo)準(zhǔn)操作及其所屬的后端數(shù)據(jù)庫信息， 標(biāo)準(zhǔn)操作和后端數(shù)據(jù)庫信息存放在 操作表中；權(quán)限管理維護(hù)權(quán)限表，該表存儲(chǔ)用戶可執(zhí)行的操作信息。大的好像）， 若用戶無權(quán)執(zhí)行該操作，則返回權(quán)限不足信息，否則進(jìn)行連接管理。（4）連接管理連接相應(yīng)的后臺(tái)數(shù)據(jù)庫并提交

2、操作。連接管理先檢查是否存在空 閑的數(shù)據(jù)庫連接，如果不存在，新建連接；如果存在，則重用連接。（5）后端數(shù)據(jù)庫執(zhí)行操作并將結(jié)果傳給中間件，中間件對(duì)收到的操作結(jié)果進(jìn)行 處理后，將其返回給前端應(yīng)用?，F(xiàn)采用結(jié)構(gòu)化方法對(duì)系統(tǒng)進(jìn)行分析與設(shè)計(jì)， 獲得如圖1-1所示的頂層數(shù)據(jù)流圖和 圖1-2所示的0層數(shù)據(jù)流圖。幡式轂伉鬼用戶佐息I L巳辻按請(qǐng)求1-1中的實(shí)體E1E3的名稱。1-2中的數(shù)據(jù)存儲(chǔ)D1D3的名稱E5圖1-1頂層數(shù)據(jù)硫圖【問題1】（3分）使用說明中的詞語，給出圖【問題2】（3分） 使用說明中的詞語，給出圖【冋題3】（6分）給出圖1-2中加工P的名稱及其輸入、輸出流除加工P的輸入與輸出流外，圖1-2還缺

3、失了兩條數(shù)據(jù)流，請(qǐng)給出這兩條數(shù)據(jù)流 的起點(diǎn)和終點(diǎn)。注：名稱使用說明中的詞匯，起點(diǎn)和終點(diǎn)均使用圖 1-2中的符號(hào)或詞匯?！締栴}4】（3分）在繪制數(shù)據(jù)流圖時(shí)，需要注意加工的繪制。請(qǐng)給出三種在繪制加工的輸入、 輸出 時(shí)可能出現(xiàn)的錯(cuò)誤。試題二（共15分）閱讀下列說明和圖，回答問題1至問題3,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f明】某學(xué)校擬開發(fā)一套實(shí)驗(yàn)管理系統(tǒng)，對(duì)各課程的實(shí)驗(yàn)安排情況進(jìn)行管理。【需求分析】一個(gè)實(shí)驗(yàn)室可進(jìn)行多種類型不同的實(shí)驗(yàn)。由于實(shí)驗(yàn)室和實(shí)驗(yàn)員資源有限，需根 據(jù)學(xué)生人數(shù)分批次安排實(shí)驗(yàn)室和實(shí)驗(yàn)員。 一門課程可以為多個(gè)班級(jí)開設(shè)，每個(gè)班 級(jí)每學(xué)期可以開設(shè)多門課程。一門課程的一種實(shí)驗(yàn)可以根據(jù)人數(shù)、 實(shí)

4、驗(yàn)室的可容 納人數(shù)和實(shí)驗(yàn)類型，分批次開設(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)成績。（1）課程信息包括：課程編號(hào)、課程名稱、實(shí)驗(yàn)學(xué)時(shí)、授課學(xué)期和開課的班級(jí) 等信息；實(shí)驗(yàn)信息記錄該課程的實(shí)驗(yàn)進(jìn)度信息， 包括：實(shí)驗(yàn)名、實(shí)驗(yàn)類型、學(xué)時(shí)、 安排周次等信息，如表2-1所示。表2-1課程及實(shí)驗(yàn)信息野那1】他迎程4斟亍屯規(guī)原用生舲學(xué)時(shí)12血 0501.宿0501陽氣1帚曲G和 = -H15 ?-： ?SfiE性0.52 丫51. / ( 9（2）以課程為單位制定實(shí)驗(yàn)安排計(jì)劃信息，包括：實(shí)驗(yàn)地點(diǎn)，實(shí)驗(yàn)時(shí)間、實(shí)驗(yàn) 員等

5、信息，實(shí)驗(yàn)計(jì)劃如表2-2所示。表2-2實(shí)驗(yàn)安排計(jì)劃諛程名稱安搏學(xué)期2009年枕總扎數(shù)實(shí)腕油寸實(shí)聆時(shí)角地1505403701:孑視頗AID A坤茨訕-；第3周周豳1:定驗(yàn)腌別0I1505403WK AD-OP 出皺瞥趴-3周周汕噸1：垛驗(yàn)三樓和。1I5Q54O37OJiis劉衣5ft 1：嫁三樓3!】31505403701了池imu :出吳.SU &1哋上實(shí)臉訛31】.二1505372需X,劉X衍5網(wǎng)出1 一實(shí)監(jiān) P4I5 4101（3）由實(shí)驗(yàn)員給出每個(gè)學(xué)生每次實(shí)驗(yàn)的成績，包括：實(shí)驗(yàn)名、學(xué)號(hào)、姓名、班 級(jí)、實(shí)驗(yàn)成績等信息，實(shí)驗(yàn)成績?nèi)绫?2-3所示。表2-3實(shí)驗(yàn)咸績實(shí)驗(yàn)弘 寤x寶驗(yàn)瞎E t? AD

6、-DA 董驗(yàn)姓名030501002fl*i050l?K04怕I)】 CM?】| 0501（4）學(xué)生的實(shí)驗(yàn)課程總成績根據(jù)每次實(shí)驗(yàn)的成績以及每次實(shí)驗(yàn)的難度來計(jì)算。 【概念模型設(shè)計(jì)】根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖（不完整）如圖 2-1所示。1學(xué)生www【邏輯結(jié)構(gòu)設(shè)計(jì)】根據(jù)概念模型設(shè)計(jì)階段完成的實(shí)體聯(lián)系圖，得出如下關(guān)系模式（不完整）： 課程（課程編號(hào)，課程名稱，授課院系，實(shí)驗(yàn)學(xué)時(shí)） 班級(jí)（班級(jí)號(hào)，專業(yè)，所屬系）開課情況（1），授課學(xué)期）實(shí)驗(yàn)（2），實(shí)驗(yàn)類型，難度，學(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)，開放時(shí)間，可容納人數(shù)，實(shí)驗(yàn)類型）學(xué)生

7、（5），姓名，年齡，性別）實(shí)驗(yàn)成績（6），實(shí)驗(yàn)成績，評(píng)分實(shí)驗(yàn)員）【問題1】（6分）補(bǔ)充圖2-1中的聯(lián)系和聯(lián)系的類型?！締栴}2】（6分）根據(jù)圖2-1，將邏輯結(jié)構(gòu)設(shè)計(jì)階段生成的關(guān)系模式中的空（1）（6）補(bǔ)充完 整并用下劃線指出這六個(gè)關(guān)系模式的主鍵。【問題3】（3分）如果需要記錄課程的授課教師，新增加“授課教師”實(shí)體。請(qǐng)對(duì)圖2-1進(jìn)行修改, 畫出修改后的實(shí)體間聯(lián)系和聯(lián)系的類型。試題三（共15分）閱讀下列說明和圖，回答問題1至問題3,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f明】某運(yùn)輸公司決定為新的售票機(jī)開發(fā)車票銷售的控制軟件。圖3-1給出了售票機(jī)的 面板示意圖以及相關(guān)的控制部件。售票機(jī)相關(guān)部件的作用如下所述：

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

9、2)due” 送_圖3-2 頂層用例圏【冋題1】（5分）根據(jù)說明中的描述，給出圖3-2中A1和A2所對(duì)應(yīng)的參與者，U1所對(duì)應(yīng)的用例， 以及（1）、（ 2）處所對(duì)應(yīng)的關(guān)系?！締栴}2】（7分）根據(jù)說明中的描述，給出圖3-3中缺少的C1C4所對(duì)應(yīng)的類名以及（3）（6） 處所對(duì)應(yīng)的多重度?！締栴}3】（3分）圖3-3中的類圖設(shè)計(jì)采用了中介者（Mediator ）設(shè)計(jì)模式，請(qǐng)說明該模式的內(nèi)涵試題四（共15分）閱讀下列說明和C代碼，回答問題1至問題3,將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。 【說明】對(duì)有向圖進(jìn)行拓?fù)渑判虻姆椒ㄊ牵海?）初始時(shí)拓?fù)湫蛄袨榭?；?）任意選擇一個(gè)入度為0的頂點(diǎn)，將其放入拓?fù)湫蛄兄校瑫r(shí)從圖中

10、刪除該 頂點(diǎn)以及從該頂點(diǎn)出發(fā)的??；（3）重復(fù)（2），直到不存在入度為0的頂點(diǎn)為止（若所有頂點(diǎn)都進(jìn)入拓?fù)湫蛄袆t完成拓?fù)渑判?，否則由于有向圖中存在回路無法完成拓?fù)渑判颍┖瘮?shù)int* TopSort（LinkedDigraph G）的功能是對(duì)有向圖 G中的頂點(diǎn)進(jìn)行拓?fù)渑判?，返回拓?fù)湫蛄兄械捻旤c(diǎn)編號(hào)序列，若不能完成拓?fù)渑判?，則返回空指針。其中，圖G中的頂點(diǎn)從1開始依次編號(hào)，頂點(diǎn)序列為v1, v2，vn,圖G采 用鄰接表示，其數(shù)據(jù)類型定義如下：#define MAXVNUM 50/* 最大頂點(diǎn)數(shù)*/typedef struct ArcNode/* 表結(jié)點(diǎn)類型*/int adjvex;接頂點(diǎn)編號(hào)*/str

11、uct ArcNode *n extarc;點(diǎn)*/*鄰/*指示下一個(gè)鄰接頂ArcNode;typedef struct AdjList char vdata;的數(shù)據(jù)信息*/ArcNode *firstarc;的第一個(gè)表結(jié)點(diǎn)*/*頭結(jié)點(diǎn)類型*/*頂點(diǎn)/*指向鄰接表AdjList;typedef struct LinkedDigraph int n;圖中頂點(diǎn)個(gè)數(shù)*/AdjList VheadMAXVNUM;的頭結(jié)點(diǎn)數(shù)組*/*圖的類型*/*/*所有頂點(diǎn)Lin kedDigraph;例如，某有向圖G如圖4-1所示，其鄰接表如圖4-2所示15! 4-1有向慚門閣有向腳。的鄰接表朮歳|1函數(shù)TopSort

12、中用到了隊(duì)列結(jié)構(gòu)（Queue的定義省略），實(shí)現(xiàn)隊(duì)列基本操作的函 數(shù)原型如下表所示：型明aiJ hiilQueulQurui? Qj初始化隊(duì)列（構(gòu)造一個(gè)吒隊(duì)列bLHl I,!LltipLj 1 Qu劌隨艮列是齊洎*1匕imi!r/rWSInl仙HnQtiQULi：QLLii? |2I int 亡：朮索入臥列void DeQueue(Queue *Q：Jit *p:【C代碼】int *TopSort(Li nkedDigraph G) ArcNode*p；/*臨時(shí)指針,指示表結(jié)點(diǎn)*/Queue Q; /*臨時(shí)隊(duì)列，保存入度為0的頂點(diǎn)編號(hào)*/int k = 0;/*臨時(shí)變量，用作數(shù)組元素的下標(biāo)*/*

13、臨時(shí)變/*存儲(chǔ)拓?fù)湫蛄?*存儲(chǔ)圖G中各int j = 0, w =0；量，用作頂點(diǎn)編號(hào)*/int *topOrder, *i nDegree;topOrder = (int *)malloc(G.n+1) * sizeof(int); 中的頂點(diǎn)編號(hào)*/in Degree = (int *)malloc(G. n+1) * sizeof(i nt); 頂點(diǎn)的入度*/if (!i nDegree | !topOrder) return NULL;(1);/*構(gòu)造一個(gè)空隊(duì)列*/for ( j = 1; j = G. n; j+ )/*初始化*/topOrderj = 0;in Degreej = 0

14、;for (j = 1; j n extarc )in Degreep- adjvex += 1;for (j = 1; j n extarc） （3）-= 1;if （0 =（4） EnQueue（&Q, p-adjvex）;/* for */ /* while */ free（i nDegree）; if （ 5）return NULL;return topOrder; /*TopSort*/【問題1】（9分）根據(jù)以上說明和C代碼，填充C代碼中的空（1）（5）?！締栴}2】（2分）對(duì)于圖4-1所示的有向圖G,寫出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄小Ｈ魧?函數(shù)TopSort中的隊(duì)列改為棧，

15、寫出函數(shù) TopSort執(zhí)行后得到的拓?fù)湫蛄?。【問題31（ 4分）設(shè)某有向無環(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條弧的有向無環(huán)圖，實(shí)現(xiàn)上述拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度 是（7）。2v4Xi 0I1G00nAti44nG0u0s00ITru000I00110D000I0Q00000i-0000T0圖41件向罔0的鄰M昨試題五（共15分）閱讀下列說明和C

16、+弋碼，將應(yīng)填入 （n）處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。 【說明】某軟件公司現(xiàn)欲開發(fā)一款飛機(jī)飛行模擬系統(tǒng)，該系統(tǒng)主要模擬不同種類飛機(jī)的飛 行特征與起飛特征。需要模擬的飛機(jī)種類及其特征如表5-1所示。鱗講類起瞬征飛価征“直升機(jī)(1坷旳Ft起飛陀rimlTikeOH客機(jī)(AirPtane)艮距離起無業(yè)沁的SubSotttcFly)ir殲擊機(jī)(FigliteN性距肉起飛 CDii dneeTiikeOff 1起冷速飛存f SujKJi Sanicny )鵬式戰(zhàn)斗機(jī)(Harrier、垂豈削 也r VferncAlTnkeOfr?越沁飛打1 SuprSumer 1 )為支持將來模擬更多種類的飛機(jī)，采用策略

17、設(shè)計(jì)模式(Strategy )設(shè)計(jì)的類圖 如圖5-1所示。圖5-1中，AirCraft 為抽象類，描述了抽象的飛機(jī)，而類Helicopter、AirPlane、 Fighter和Harrier分別描述具體的飛機(jī)種類，方法 fly()和takeOff()分別表 示不同飛機(jī)都具有飛行特征和起飛特征；類FlyBehavior與TakeOffBehavior為抽象類，分別用于表示抽象的飛行為與起飛行為；類 SubSonicFly與 SuperSonicFly分別描述亞音速飛行和超音速飛行的行為；類 VerticalTakeOff 與LongDistanceTakeOff分別描述垂直起飛與長距離起飛的行

18、為?！綜+代碼】#in cludeusing n amespace std;class FlyBehavior public : virtual void fly() = 0;class SubS oni cFly:public FlyBehaviorpublic: void fly() cout 亞音速飛行！ en dl; ;class SuperS oni cFly:public FlyBehaviorpublic: void fly() cout 超音速飛行！ en dl; ;class TakeOffBehavior public: virtual void takeOff() = 0

19、;；class VerticalTakeOff:public TakeOffBehaviorpublic: void takeOff() cout 垂直起飛！ en dl; ;class Lon gDista nceTakeOff:public TakeOffBehavior public: void takeOff () cout 長距離起飛！ 1 iJ.呼 ven：c；：ori)ijlij C( + y . .r; Su perSiD filcFIa,、為支持將來模擬更多種類的飛機(jī)，采用策略設(shè)計(jì)模式(Strategy )設(shè)計(jì)的類圖如 圖6-1所示。:Sub$piikl$uper$QiMcF

20、lyAxrClaftrakeOffBehaviof t 弓時(shí) 1 Hrio-r Hydehev ior -WeQIfBetubVbor. Tali*(JtfBehaorVefticalTAeOffLqngDivtdfK eTakeOff亍。同HeiicofiterAirPfaneFiqhfierHarrir圖6-1中，AirCraft為抽象類，描述了抽象的飛機(jī)，而類Helicopter、AirPlane、 Fighter和Harrier分別描述具體的飛機(jī)種類，方法 fly()和takeOff()分別表 示不同飛機(jī)都具有飛行特征和起飛特征類FlyBehavior與TakeOffBehavior為抽象類，分別用于表示抽象的飛行為與起飛行為；類SubSonicFly與SuperSonicFly 分別描述亞音速飛行和超音速飛行的行為；類 VerticalTakeOff 與 LongDistanceTakeOff分別描述垂直起飛與長距離起飛的行為?！綣ava代碼】in terface Fly