中級軟件設(shè)計(jì)師2010上半年下午試題

中級軟件設(shè)計(jì)師2010上半年下午試題試題一 閱讀下列說明和圖，回答問題1至問題4，將解答填入對應(yīng)欄內(nèi)。 說明 某大型企業(yè)的數(shù)據(jù)中心為了集中管理、控制用戶對數(shù)據(jù)的訪問并支持大量的連接需求，欲構(gòu)建數(shù)據(jù)管理中問件，其主要功能如下： 1數(shù)據(jù)管理員可通過中間件進(jìn)行用戶管理、操作管理和權(quán)限管理。用戶管理維護(hù)用戶信息，用戶信息(用戶名、密碼)存儲在用戶表中；操作管理維護(hù)數(shù)據(jù)實(shí)體的標(biāo)準(zhǔn)操作及其所屬的后端數(shù)據(jù)庫信息，標(biāo)準(zhǔn)操作和后端數(shù)據(jù)庫信息存放在操作表中；權(quán)限管理維護(hù)權(quán)限表，該表存儲用戶可執(zhí)行的操作信息。 2中間件驗(yàn)證前端應(yīng)用提供的用戶信息。若驗(yàn)證不通過，返回非法用戶信息；若驗(yàn)證通過，中間件將等待前端應(yīng)用提交操作請求。 3前端應(yīng)用提交操作請求后，中間件先對請求進(jìn)行格式檢查。如果格式不正確，返回格式錯誤信息；如果格式正確，則進(jìn)行權(quán)限驗(yàn)證(驗(yàn)證用戶是否有權(quán)執(zhí)行請求的操作)，若用戶無權(quán)執(zhí)行該操作，則返回權(quán)限不足信息，否則進(jìn)行連接管理。 4連接管理連接相應(yīng)的后臺數(shù)據(jù)庫并提交操作。連接管理先檢查是否存在空閑的數(shù)據(jù)庫連接，如果不存在，新建連接；如果存在，則重用連接。 5后端數(shù)據(jù)庫執(zhí)行操作并將結(jié)果傳給中間件，中間件對收到的操作結(jié)果進(jìn)行處理后，將其返回給前端應(yīng)用。 現(xiàn)采用結(jié)構(gòu)化方法對系統(tǒng)進(jìn)行分析與設(shè)計(jì)，獲得如圖1-1所示的頂層數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。 1、使用說明中的詞語，給出圖1-1中的實(shí)體E1E3的名稱。 2、使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲D1D3的名稱 3、給出圖1-2中加工P的名稱及其輸入、輸出流。名稱起點(diǎn)終點(diǎn)輸入流P輸出流P 除加工P的輸入與輸出流外，圖1-2還缺失了兩條數(shù)據(jù)流，請給出這兩條數(shù)據(jù)流的起點(diǎn)和終點(diǎn)。 起點(diǎn)終點(diǎn) 注：名稱使用說明中的詞匯，起點(diǎn)和終點(diǎn)均使用圖1-2中的符號或詞匯。 4、在繪制數(shù)據(jù)流圖時(shí)，需要注意加工的繪制。請給出三種在繪制加工的輸入、輸出時(shí)可能出現(xiàn)的錯誤。 試題二 閱讀下列說明，回答問題1至問題3，將解答填入對應(yīng)欄內(nèi)。 說明 某學(xué)校擬開發(fā)一套實(shí)驗(yàn)管理系統(tǒng)，對各課程的實(shí)驗(yàn)安排情況進(jìn)行管理。 需求分析 一個實(shí)驗(yàn)室可進(jìn)行多種類型不同的實(shí)驗(yàn)。由于實(shí)驗(yàn)室和實(shí)驗(yàn)員資源有限，需根據(jù)學(xué)生人數(shù)分批次安排實(shí)驗(yàn)室和實(shí)驗(yàn)員。一門課程可以為多個班級開設(shè)，每個班級每學(xué)期可以開設(shè)多門課程。一門課程的一種實(shí)驗(yàn)可以根據(jù)人數(shù)、實(shí)驗(yàn)室的可容納人數(shù)和實(shí)驗(yàn)類型，分批次開設(shè)在多個實(shí)驗(yàn)室的不同時(shí)問段。一個實(shí)驗(yàn)室的一次實(shí)驗(yàn)可以分配多個實(shí)驗(yàn)員負(fù)責(zé)輔導(dǎo)實(shí)驗(yàn)，實(shí)驗(yàn)員給出學(xué)生的每次實(shí)驗(yàn)成績。 (1)課程信息包括：課程編號、課程名稱、實(shí)驗(yàn)學(xué)時(shí)、授課學(xué)期和丌課的班級等信息；實(shí)驗(yàn)信息記錄該課程的實(shí)驗(yàn)進(jìn)度信息，包括：實(shí)驗(yàn)名、實(shí)驗(yàn)類型、學(xué)時(shí)、安排周次等信息，如表2-1所示。 表2-1 課程及實(shí)驗(yàn)信息課程編號15054037課程名稱數(shù)字電視原刪實(shí)驗(yàn)學(xué)時(shí)12班級電0501，信0501，計(jì)0501授課院系機(jī)械與電氣工程授課學(xué)期第三學(xué)期序號實(shí)驗(yàn)名實(shí)驗(yàn)類難度學(xué)時(shí)安排周次1505403701音視頻AD-DA實(shí)驗(yàn)驗(yàn)證性1231505403702音頻編碼實(shí)驗(yàn)驗(yàn)證性2251505403703視頻編碼實(shí)驗(yàn)演示性0.519 (2)以課程為單位制定實(shí)驗(yàn)安排計(jì)劃信息，包括：實(shí)驗(yàn)地點(diǎn)，實(shí)驗(yàn)時(shí)間、實(shí)驗(yàn)員等信息，實(shí)驗(yàn)計(jì)劃如表2-2所示。 表2-2 實(shí)驗(yàn)安排計(jì)劃 課程編號15054037課程名稱數(shù)字電視原理安排學(xué)期2009年秋總?cè)藬?shù)220實(shí)驗(yàn)編號實(shí)驗(yàn)名實(shí)驗(yàn)員實(shí)驗(yàn)員地點(diǎn)批次號人數(shù)1505403701音視頻AD-DA丈驗(yàn)盛，陳第3周周四晚上實(shí)驗(yàn)三樓3101601505403701音視頻AD-DA實(shí)驗(yàn)盛，陳第3周周四晚上實(shí)驗(yàn)三樓3102601505403701音視頻AD-DA實(shí)驗(yàn)吳，劉第3周周五晚上實(shí)驗(yàn)三樓3113601505403701音視頻AD-DA實(shí)驗(yàn)吳第3周周五晚上實(shí)驗(yàn)三樓3114401505403702音頻編碼實(shí)驗(yàn)盛，劉第5周周一下午實(shí)驗(yàn)四樓410170 (3)由實(shí)驗(yàn)員給出每個學(xué)生每次實(shí)驗(yàn)的成績，包括：實(shí)驗(yàn)名、學(xué)號、姓名、班級、實(shí)驗(yàn)成績等信息，實(shí)驗(yàn)成績?nèi)绫?-3所示。 表2-3 實(shí)驗(yàn)成績 實(shí)驗(yàn)員： 盛 實(shí)驗(yàn)名音視頻AD-DA實(shí)驗(yàn)課程名數(shù)字電視原理學(xué)號姓名班級實(shí)驗(yàn)成績030501001陳民信050187030501002劉志信050178040501001張勤計(jì)050186 (4)學(xué)生的實(shí)驗(yàn)課程總成績根據(jù)每次實(shí)驗(yàn)的成績以及每次實(shí)驗(yàn)的難度來計(jì)算。 概念模型設(shè)計(jì) 根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖(不完整)如圖2-1所示。 邏輯結(jié)構(gòu)設(shè)計(jì) 根據(jù)概念模型設(shè)計(jì)階段完成的實(shí)體聯(lián)系圖，得出如下關(guān)系模式(不完整)： 課程(課程編號，課程名稱，授課院系，實(shí)驗(yàn)學(xué)時(shí)) 班級(班級號，專業(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) ，級別) 實(shí)驗(yàn)室(實(shí)驗(yàn)室編號，地點(diǎn)，開放時(shí)間，可容納人數(shù)，實(shí)驗(yàn)類型) 學(xué)生( (5) ，姓名，年齡，性別) 實(shí)驗(yàn)成績( (6) ，實(shí)驗(yàn)成績，評分實(shí)驗(yàn)員) 5、補(bǔ)充圖2-1中的聯(lián)系和聯(lián)系的類型。 根據(jù)圖2-1，將邏輯結(jié)構(gòu)設(shè)計(jì)階段生成的關(guān)系模式中的空67補(bǔ)充完整并用下劃線指出這六個關(guān)系模式的主鍵。12、如果需要記錄課程的授課教師，新增加“授課教師”實(shí)體。請對圖2-1進(jìn)行修改，畫出修改后的實(shí)體問聯(lián)系和聯(lián)系的類型。試題三閱讀下列說明和圖，回答問題1至問題3，將解答填入對應(yīng)欄內(nèi)。 說明 某運(yùn)輸公司決定為新的售票機(jī)開發(fā)車票銷售的控制軟件。圖3-1給出了售票機(jī)的面板示意圖以及相關(guān)的控制部件。 售票機(jī)相關(guān)部件的作用如下所述： 13目的地鍵盤用來輸入行程目的地的代碼(例如，200表示總站)。 14乘客可以通過車票鍵盤選擇車票種類(單程票、多次往返票和座席種類)。 15繼續(xù)/取消鍵盤上的取消按鈕用于取消購票過程，繼續(xù)按鈕允許乘客連續(xù)購買多張票。 16顯示屏顯示所有的系統(tǒng)輸出和用戶提示信息。 17插卡口接受MCard(現(xiàn)金卡)，硬幣口和紙幣槽接受現(xiàn)金。 18打印機(jī)用于輸出車票。 假設(shè)乘客總是支付恰好需要的金額而無需找零，售票機(jī)的維護(hù)工作(取回現(xiàn)金、放入空白車票等)由服務(wù)技術(shù)人員完成。 系統(tǒng)采用面向?qū)ο蠓椒ㄩ_發(fā)，使用UML進(jìn)行建模。系統(tǒng)的頂層用例圖和類圖分別如圖3-2和圖3-3所示。 13、根據(jù)說明中的描述，給出圖3-2中A1和A2所對應(yīng)的參與者，U1所對應(yīng)的用例，以及(1)、(2)處所對應(yīng)的關(guān)系。 14、根據(jù)說明中的描述，給出圖3-3中缺少的C1C4所對應(yīng)的類名以及(3)(6)處所對應(yīng)的多重度。 15、圖3-3中的類圖設(shè)計(jì)采用了中介者(Mediator)設(shè)計(jì)模式，請說明該模式的內(nèi)涵。 試題四 閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在對應(yīng)欄內(nèi)。 說明 對有向圖進(jìn)行拓?fù)渑判虻姆椒ㄊ牵?(1)初始時(shí)拓?fù)湫蛄袨榭眨?(2)任意選擇一個入度為0的頂點(diǎn)，將其放入拓?fù)湫蛄兄?，同時(shí)從圖中刪除該頂點(diǎn)以及從該頂點(diǎn)出發(fā)的?。?(3)重復(fù)(2)，直到不存在入度為0的頂點(diǎn)為止(若所有頂點(diǎn)都進(jìn)入拓?fù)湫蛄袆t完成拓?fù)渑判?，否則由于有向圖中存在回路無法完成拓?fù)渑判?。 函數(shù)int* TopSort(LinkedDigraphG.的功能是對有向圖G中的頂點(diǎn)進(jìn)行拓?fù)渑判?，返回拓?fù)湫蛄兄械捻旤c(diǎn)編號序列，若不能完成拓?fù)渑判?，則返回空指針。其中，圖G中的頂點(diǎn)從1開始依次編號，頂點(diǎn)序列為v1，v2，vn，圖G采用鄰接表表示，其數(shù)據(jù)類型定義如下： #define MAXVNUM 50 /*最大頂點(diǎn)數(shù)*/ typedef struct ArcNode /*表結(jié)點(diǎn)類型*/ int adjvex; /*鄰接頂點(diǎn)編號*/ struct ArcNode *nextarc; /*指示下一個鄰接頂點(diǎn)*/ ArcNode; typedef struct AdjList /*頭結(jié)點(diǎn)類型*/ char vdata; /*頂點(diǎn)的數(shù)據(jù)信息*/ ArcNode *fimstarc; /*指向鄰接表的第一個表結(jié)點(diǎn)*/ AdjList; typedef struct LinkedDigraph /*圖的類型*/ int n; /*圖中頂點(diǎn)個數(shù)*/ AdjList VheadMAXVNUM; /*所有頂點(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ù)原型說明void InitQueue(Queue *Q)初始化隊(duì)列(構(gòu)造一個卒隊(duì)列)bool IsEmpty(Queue Q)判斷隊(duì)列是否為空，若是則返回true，否則返回falsevoid EnQueue(Queue *Q，int e)元素入隊(duì)列void DeQueue(Queue *Q，int *p)元素出隊(duì)列 C代碼 int *TopSort(LinkedDigraphG. ArcNode *p; /*臨時(shí)指針，指示表結(jié)點(diǎn)*/ Queue Q; /*臨時(shí)隊(duì)列，保存入度為0的頂點(diǎn)編號*/ int k=0; /*臨時(shí)變量，用作數(shù)組元素的下標(biāo)*/ intj=0，w=0; /*臨時(shí)變量，用作頂點(diǎn)編號*/ int *topOrder，*inDegree; topOrder=(int *)malloc(G.n+1) *sizeof(int); /*存儲拓?fù)湫蛄兄械捻旤c(diǎn)編號*/ inDegree=(int *)malloc(G.n+1) *sizeof(int); /*存儲圖G中各頂點(diǎn)的入度*/ if(!inDegree | !topOrder) return NULL; (1) ; /*構(gòu)造一個空隊(duì)列*/ for(j=1; j=G.n; j+)/*初始化*/ topOrderj=0; inDegreej=0; for(j=1;j=G.n;j+) /*求圖G中各頂點(diǎn)的入度*/ for(p=G.Vheadj.firstarc; P; P=P-nextarc) inDegreeP-adjvex+=1; for(j=1; j=G.n;j+) /*將圖G中入度為0的頂點(diǎn)保存在隊(duì)列中*/ if(0=inDegreej) EnQueue(Q,j); while(!IsEmpty(Q) (2) ; /*隊(duì)頭頂點(diǎn)出隊(duì)列并用w保存該頂點(diǎn)的編號*/ topOrderk+=w; /*將頂點(diǎn)w的所有鄰接頂點(diǎn)的入度減1(模擬刪除頂點(diǎn)w及從該頂點(diǎn)出發(fā)的弧的操作)*/ for(p=G.Vheadw.firstarc;P; p=p-nextarc) (3) -=1; if(0= (4) ) EnQueue(Q，P-adjvex); 1/for$/ /*while*/ free(inDegree); if( (5) ) return NULL; return topOrder; /*TopSort*/根據(jù)以上說明和C代碼，填充C代碼中的空1617。21、對于圖4-1所示的有向圖G，寫出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄小Ｈ魧⒑瘮?shù)TopSort中的隊(duì)列改為棧，寫出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄小?設(shè)某有向無環(huán)圖的頂點(diǎn)個數(shù)為n、弧數(shù)為e，那么用鄰接表存儲該圖時(shí)，實(shí)現(xiàn)上述拓?fù)渑判蛩惴ǖ暮瘮?shù)TopSort的時(shí)間復(fù)雜度是 22 。 若有向圖采用鄰接矩陣表示(例如，圖4-1所示有向圖的鄰接矩陣如圖4-3所示)，且將函數(shù)TopSort中有關(guān)鄰接表的操作修改為針對鄰接矩陣的操作，那么對于有n個頂點(diǎn)、e條弧的有向無環(huán)圖，實(shí)現(xiàn)上述拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是 23 。 試題五閱讀下列說明和C+弋碼，將應(yīng)填入 (n) 處的字句寫在對應(yīng)欄內(nèi)。 說明 某軟件公司現(xiàn)欲開發(fā)一款飛機(jī)飛行模擬系統(tǒng)，該系統(tǒng)主要模擬不同種類飛機(jī)的飛行特征與起飛特征。需要模擬的飛機(jī)種類及其特征如表5-1所示。 表5-1飛機(jī)種類起飛特征飛行特征直升機(jī)(Helicopter)垂直起飛(VerticalTakeOff)亞音速飛行(SubSonicFly)客機(jī)(AirPlane)長距離起飛(LongDistanceTakeOff)亞音速飛行(SubSonicFly)殲擊機(jī)(Fighter)長距離起飛(LongDistanceTakeOff)超音速飛行(SuperSonicFly)鷂式戰(zhàn)斗機(jī)(Harrier)垂直起飛(VerticalTakeOff)超音速飛行(SuperSonicFly) 為支持將來模擬更多種類的飛機(jī)，采用策略設(shè)計(jì)模式(strategy)設(shè)計(jì)的類圖如圖5-1所示。 圖5-1中，AirCraft為抽象類，描述了抽象的飛機(jī)，而類Helicopter、AirPlane、Fighter和Harrier分別描述具體的飛機(jī)種類，方法fly31和takeOff31分別表示不同飛機(jī)都具有飛行特征和起飛特征；類FlyBehavior與TakeOffBehavior為抽象類，分別用于表示抽象的飛行行為與起飛行為；類SubSonicFly與SuperSonicFly分別描述亞音速飛行和超音速飛行的行為；類VerticalTakeOff與LongDistanceTakeOff分別描述垂直起飛與長距離起飛的行為。 C+代碼 #includeiostream using namespace std; class FlyBehaVior public: virtual void fly31=0; ; class SubSonicFly: public FlyBehaVior public: void fly31cout亞音速飛行!endl;) ; class SupersonicFly: public FlyBehaVior public: void fly31cout超音速飛行!endl;) ; class TakeOffBehavior publie: virtual void takeOff31=0; ; class VerticalTakeOff: public TakeOffBehavior public: void takeOff31cout垂直起飛!endl ; class LongDistanceTakeOff: public TakeOffBehavior public: void takeOff31cout長距離起飛!endl; ; class AirCraft protected: 24 ; 25 ; public: void fly31 26 ; void takeoff31 27 ; ; ; class Helicopter: public AirCraft public: Helicopter 31 flyBehavior=new 28 ; takeoffBehavior=new 29 ; 30 if(!flyBehaVior) delete flyBehaVior; if(!takeoffBehavior) delete takeoffBehaVior; ; /其他代碼省略 試題六 閱讀下列說明和Java代碼，將應(yīng)填入(n)處的字句寫在對應(yīng)欄內(nèi)。 說明 某軟件公司現(xiàn)欲開發(fā)一款飛機(jī)飛行模擬系統(tǒng)，該系統(tǒng)主要模擬不同種類飛機(jī)的飛行特征與起飛特征。需要模擬的飛機(jī)種類及其特征如表6-1所示。 表6-1飛機(jī)種類起飛特征飛行特征直升機(jī)(Helicopter)垂直起飛(VerticalTakeOff)亞音速飛行(SubSonicFly)客機(jī)(AirPlane)長距離起飛(LongDistanceTakeOff)亞音速飛行(SubSonicFly)殲擊機(jī)(Fighter)長距離起飛(LongDistanceTakeOff)超音速飛行(SuperSonicFly)鷂式戰(zhàn)斗機(jī)(Harrier)垂直起飛(VerticalTakeOff)超音速飛行(SuperSonicFly) 為支持將來模擬更多種類的飛機(jī)，采用策略設(shè)計(jì)模式(Strategy)設(shè)計(jì)的類圖如圖6-1所示。 圖6-1中，AirCraft為抽象類，描述了抽象的飛機(jī)，而類Helicopter、AirPlane、Fighter和Harrier分別描述具體的飛機(jī)種類，方法fly38和takeOff38分別表示不同飛機(jī)都具有飛行特征和起飛特征；類FlyBehavior與TakeOffBehavior為抽象類，分別用于表示抽象的飛行行為與起飛行為；類SubSonicFly與SuperSonicFly分別描述亞音速飛行和超音速飛行的行為；類VerticalTakeOff與LongDistanceTakeOff分別描述垂直起飛與長距離起飛的行為。 Java代碼 interface FlyBehavior public void fly38; ; class SubSonicFly implements FlyBehavior public void fly38(System.out.println(業(yè)音速飛行!);) ; class SuperSonicFly implements FlyBehavior public void fly38 System.out.println(超音速飛行!); ; interface TakeOffBehavior public void takeOff38; ; class VerticalTakeOff implements TakeOffBehavior public void takeOff38 System.out.println(垂直起飛!); ; class LongDistanceTakeOff implements TakeOffBehavior public void takeOff38 System.out.println(長距離起飛!); ; abstract class AirCraft protected 31 ; protected 32 ; public void fly38 33 ; public void takeOff38 34 ; ; class Helicopter 35 AirCraft public Helicopter38 flyBehavior=new 36 ; takeOffBehavior=new 37 ; ; /其他代碼省略 答案:試題一1、E1：前端應(yīng)用 E2：數(shù)據(jù)管理員 E3：后端數(shù)據(jù)庫本問題考查頂層DFD。頂層DFD一般用來確定系統(tǒng)邊界，將待開發(fā)系統(tǒng)看作一個加工，因此圖中只有唯一的一個加工和一些外部實(shí)體，以及這兩者之間的輸入輸出數(shù)據(jù)流。題目要求根據(jù)描述確定圖中的外部實(shí)體。分析題目中的描述，并結(jié)合已經(jīng)在頂層數(shù)據(jù)流圖中給出的數(shù)據(jù)流進(jìn)行分析。題目中有信息描述：數(shù)據(jù)管理員可通過中間件進(jìn)行用戶管理、操作管理和權(quán)限管理；前端應(yīng)用提交操作請求；連接管理連接相應(yīng)的后臺數(shù)據(jù)庫并提交操作。由此可知該中間件系統(tǒng)有數(shù)據(jù)管理員、前端應(yīng)用和后端數(shù)據(jù)庫三個外部實(shí)體。從圖1-1中數(shù)據(jù)流和實(shí)體的對應(yīng)關(guān)系可知，E1為前端應(yīng)用，E2為數(shù)據(jù)管理員，E3為后端數(shù)據(jù)庫。2、D1：用戶表 D2：操作表 D3：權(quán)限表本問題考查0層DFD中數(shù)據(jù)存儲的確定。說明中描述：用戶信息(用戶名、密碼)存儲在用戶表中；標(biāo)準(zhǔn)操作和后端數(shù)據(jù)庫信息存放在操作表中；權(quán)限管理維護(hù)信息存放在權(quán)限表中。因此數(shù)據(jù)存儲為用戶表、操作表以及權(quán)限表。再根據(jù)圖1-2可知D1的輸入數(shù)據(jù)流從用戶管理來，D2的輸入數(shù)據(jù)流從操作管理來，D3的輸入數(shù)據(jù)流從權(quán)限管理來，所以D1為用戶表，D2為操作表，D3為權(quán)限表。3、P的名稱：操作結(jié)果處理 名稱起點(diǎn)終點(diǎn)輸入流操作結(jié)果E3P輸出流處理后的操作結(jié)果PE1 缺少的數(shù)據(jù)流： 起點(diǎn)終點(diǎn)D2權(quán)限驗(yàn)證D3權(quán)限驗(yàn)證本問題考查0層DFD中缺失的加工和數(shù)據(jù)流。比較圖1-1和圖1-2，可知頂層DFD中的操作結(jié)果和處理后的操作結(jié)果沒有在0層DFD中體現(xiàn)。再根據(jù)描述“后端數(shù)據(jù)庫執(zhí)行操作并將結(jié)果傳給中問件，中間件對收到的操作結(jié)果進(jìn)行處理后，將其返回給前端應(yīng)用”可知，需要有操作結(jié)果處理，因此P為操作結(jié)果處理，其輸入流為從后端數(shù)據(jù)庫E3來的操作結(jié)果，輸出結(jié)果為處理后的操作結(jié)果，并返回給前端應(yīng)用E1。 考查完P(guān)及其輸入輸出流之后，對圖1-2的內(nèi)部數(shù)據(jù)流進(jìn)行考查，以找出缺失的另外2條數(shù)據(jù)流。從圖中可以看出D2和D3只有輸入流沒有輸出流，這是常見DFD設(shè)計(jì)時(shí)的錯誤，所以首先考查D2和D3的輸出流。描述中有“權(quán)限驗(yàn)證是驗(yàn)證用戶是否有權(quán)執(zhí)行請求的操作，若用戶有權(quán)執(zhí)行該操作，進(jìn)行連接管理；連接管理連接相應(yīng)的后臺數(shù)據(jù)庫并提交操作；權(quán)限表存儲用戶可執(zhí)行的操作信息”。因此，權(quán)限驗(yàn)證有從權(quán)限表D3來的輸入數(shù)據(jù)流。而要連接后端數(shù)據(jù)庫，需要數(shù)據(jù)庫信息，從權(quán)限驗(yàn)證的輸出流中包含有數(shù)據(jù)庫信息可知，權(quán)限驗(yàn)證需要獲取到數(shù)據(jù)庫信息，所以還需從操作表D2來的輸入流。4、在繪制數(shù)據(jù)流圖的加工時(shí)，可能出現(xiàn)的輸入、輸出錯誤： 只有輸入而無輸出或者黑洞 只有輸出而無輸入或者奇跡 輸入的數(shù)據(jù)流無法通過加工產(chǎn)生輸出流或者灰洞 輸入的數(shù)據(jù)流與輸出的數(shù)據(jù)流名稱相同本問題考查在繪制數(shù)據(jù)流圖中加工繪制時(shí)的注意事項(xiàng)。繪制加工時(shí)可能出現(xiàn)的錯誤有：加工的輸入、輸出時(shí)可能出現(xiàn)只有輸入而無輸出、只有輸出而無輸入、輸入的數(shù)據(jù)流無法通過加工產(chǎn)生輸出流以及輸入的數(shù)據(jù)流與輸出的數(shù)據(jù)流名稱相同等錯誤。試題二5、根據(jù)題意，由“一門含實(shí)驗(yàn)的課程可以開設(shè)給多個班級，每個班級每學(xué)期可以開設(shè)多門含實(shí)驗(yàn)的課程”可知課程和班級之間的開設(shè)關(guān)系為m:n聯(lián)系。由“一個實(shí)驗(yàn)室的一次實(shí)驗(yàn)可以分配多個實(shí)驗(yàn)員負(fù)責(zé)輔導(dǎo)實(shí)驗(yàn)”可知實(shí)驗(yàn)、實(shí)驗(yàn)室與實(shí)驗(yàn)員之問的安排關(guān)系為k:n:m聯(lián)系。由“實(shí)驗(yàn)員給出學(xué)生的每次實(shí)驗(yàn)成績”可知實(shí)驗(yàn)、學(xué)生與實(shí)驗(yàn)員之間的成績關(guān)系為k:n:m聯(lián)系。班級和學(xué)生之問的包含關(guān)系為1:n聯(lián)系。6、課程編號，班級號 7、實(shí)驗(yàn)編號，課程編號 8、實(shí)驗(yàn)編號，批次號，安排學(xué)期，實(shí)驗(yàn)室編號，實(shí)驗(yàn)員編號 9、實(shí)驗(yàn)員編號，實(shí)驗(yàn)員姓名 10、學(xué)號，班級號 11、實(shí)驗(yàn)編號，學(xué)號 其他關(guān)系模式主鍵： 課程(課程編號，課程名稱，授課院系，實(shí)驗(yàn)學(xué)時(shí)) 班級(班級號，專業(yè)，所屬系) 實(shí)驗(yàn)室(實(shí)驗(yàn)室編號，地點(diǎn)，開放時(shí)間，可容納人數(shù)，實(shí)驗(yàn)課類型)根據(jù)題意可知課程編號是課程的主鍵，班級號是班級的主鍵。從表2-1可知，開課情況是體現(xiàn)課程與班級問的m:n聯(lián)系，因此開課情況關(guān)系模式應(yīng)該包含課程編號和班級號，并共同作為主鍵。一門課程包含多次實(shí)驗(yàn)，實(shí)驗(yàn)與課程之間是m:1關(guān)系，因此，根據(jù)表2-1，實(shí)驗(yàn)關(guān)系模式應(yīng)包含實(shí)驗(yàn)編號和課程編號，并且以實(shí)驗(yàn)編號為主鍵，以課程編號為外鍵。在制定試驗(yàn)計(jì)劃時(shí)，每個班的每次實(shí)驗(yàn)可能按實(shí)驗(yàn)室被分成多個批次，每個批次的實(shí)驗(yàn)會有若干名實(shí)驗(yàn)員來輔導(dǎo)學(xué)生實(shí)驗(yàn)并打分。實(shí)驗(yàn)員關(guān)系模式應(yīng)該記錄實(shí)驗(yàn)員編號和實(shí)驗(yàn)員姓名，并以實(shí)驗(yàn)員編號為主鍵。實(shí)驗(yàn)室編號是實(shí)驗(yàn)室的主鍵。從表2-2可見，實(shí)驗(yàn)計(jì)劃關(guān)系模式應(yīng)記錄實(shí)驗(yàn)編號、批次號和授課學(xué)期，并且共同作為主鍵。從表2-3可見，實(shí)驗(yàn)成績關(guān)系模式記錄每個學(xué)生的每次實(shí)驗(yàn)成績，應(yīng)包含學(xué)號和實(shí)驗(yàn)編號，并共同作為主鍵。12、由于授課教師負(fù)責(zé)給若干個班級開設(shè)若干門課程，因此，課程、班級和授課教師之問的開設(shè)關(guān)系是k:n:m聯(lián)系。 試題三13、A1：乘客 A2：服務(wù)技術(shù)人員 U1：支付 (1)include (2)include本問題考查用例圖。用例圖用于確定系統(tǒng)邊界，識別與系統(tǒng)交互的參與者，通過判斷參與者發(fā)起的用例，建立和參與者之間的關(guān)聯(lián)，然后再確認(rèn)用例之間的關(guān)系。 本題中對售票機(jī)的描述為“乘客可以通過車票鍵盤選擇車票種類(單程票、多次往返票和座席種類)；售票機(jī)的維護(hù)工作(取回現(xiàn)金、放入空白車票等)由服務(wù)技術(shù)人員完成”。由此可知，圖3-1中A1為乘客，A2為服務(wù)技術(shù)人員。 對購票用例，要選擇目的地和車票類型、通過插卡口進(jìn)行支付才可完成購票。因此U2為支付。 在考查用例之間的關(guān)系時(shí)，購票過程可以取消，也允許乘客連續(xù)購買多張票，因此，購票時(shí)可以包含多次選擇目的地和車票類型、支付，即購票用例包含(關(guān)系include)選擇目的地和車票類型以及支付。14、C1：鍵盤 C2：目的地鍵盤 C3：車票鍵盤 C4：繼續(xù)/取消鍵盤 (3)(6)：1本問題考查類圖。類圖設(shè)計(jì)的重點(diǎn)是類的抽象和繼承關(guān)系以及多重度。售票機(jī)的面板由多個控制部件組成。根據(jù)說明這些控制部件有目的地鍵盤、車票鍵盤和繼續(xù)/取消鍵盤、顯示屏、卡驅(qū)動器、硬幣/紙幣槽、打印機(jī)。圖3-3中只有前3個部件在圖中沒有給出，而要填如4個類。從圖中已經(jīng)抽象出的硬件組件，給出了抽象的思路，從而可以把鍵盤抽象出來。由C1與C2、C3、C4的繼承關(guān)系中C1為基類，可知C1為鍵盤。由C2、C3和C4給出的方法名稱可知，C2為目的地鍵盤獲取目的地代碼，C3為車票鍵盤選擇產(chǎn)品類型，C4為繼續(xù)/和取消動作。 本題中的重復(fù)度比較簡單。從圖3-1售票機(jī)的圖示中可以看出，一個售票機(jī)只包含一個目的地鍵盤、一個車票鍵盤和一個繼續(xù)/取消鍵盤，因此(3)(6)均為1。15、使用Mediator模式，可以使各個對象問的耦合松散，只需關(guān)心和Mediator的關(guān)系，使多對多的關(guān)系變成了一對多的關(guān)系，可以降低系統(tǒng)的復(fù)雜性，提高可修改擴(kuò)展性。本問題考查設(shè)計(jì)模式。設(shè)計(jì)模式題目雖然比較難，但是本題題目中已經(jīng)給出了所采用的設(shè)計(jì)模式為：Mediator模式，只需說明設(shè)計(jì)模式的內(nèi)涵即可，也比較容易。使用Mediator模式，可以使各個對象問的耦合松散，只需關(guān)心和Mediator的關(guān)系，使多對多的關(guān)系變成了一對多的關(guān)系，可以降低系統(tǒng)的復(fù)雜性，提高可修改擴(kuò)展性。試題四16、InitQueue(Q) 17、DeQueue(Q，w) 18、inDegreep-adjvex 或其等價(jià)形式 19、inDegreep-adjvex 或其等價(jià)形式 20、kGn 或k!=Gn 或其等價(jià)形式拓?fù)渑判蚴菍⒂邢驘o環(huán)圖中所有頂點(diǎn)排成一個線性序列的過程，并且該序列滿足：若在有向圖中從頂點(diǎn)vi到vj有一條路徑，則在該線性序列中，頂點(diǎn)vi必然在頂點(diǎn)vj之前。 對AOE網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ㄈ缦拢?在AOE網(wǎng)中選擇一個入度為零(沒有前驅(qū))的頂點(diǎn)且輸出它； 從網(wǎng)中刪除該頂點(diǎn)及其與該頂點(diǎn)有關(guān)的所有邊； 重復(fù)上述兩步，直至網(wǎng)中不存在入度為零的頂點(diǎn)為止。 在拓?fù)渑判蜻^程中，需要將入度為0的頂點(diǎn)臨時(shí)存儲起來。函數(shù)中用一個隊(duì)列暫存入度為0且沒有進(jìn)入拓?fù)湫蛄械捻旤c(diǎn)。顯然，空(1)處應(yīng)填入InitOueue(Q)。 進(jìn)行拓?fù)渑判蛑?，?yīng)先求出網(wǎng)中每個頂點(diǎn)的入度并存入數(shù)組inDegree中，從而將“從網(wǎng)中刪除該頂點(diǎn)及其與該頂點(diǎn)有關(guān)的所有邊”的操作轉(zhuǎn)換為“相關(guān)頂點(diǎn)的入度減1”，一旦發(fā)現(xiàn)某個頂點(diǎn)的入度變?yōu)?，就將其編號壓入堆棧。從而將選擇入度為0的頂點(diǎn)操作轉(zhuǎn)化為令隊(duì)頭所代表的頂點(diǎn)出隊(duì)。 根據(jù)注釋，空(2)處應(yīng)填入DeQueue(Q，w)，實(shí)現(xiàn)隊(duì)頭元素出隊(duì)列的處理。 題中圖采用鄰接表存儲結(jié)構(gòu)，當(dāng)指針p指向vi鄰接表中的結(jié)點(diǎn)時(shí)，p-adjvex表示vi的一個鄰接頂點(diǎn)，刪除vi至頂點(diǎn)p-adjvex的弧的操作實(shí)現(xiàn)為頂點(diǎn)p-adjvex的入度減1，因此，空(3)處應(yīng)填入inDegreep-adjvex，當(dāng)頂點(diǎn)p-adjvex的入度為0時(shí)，需要將其加入隊(duì)列，因此空(4)處也應(yīng)填入inDegreep-adjvex。 空(5)處判斷是否所有頂點(diǎn)都加入了拓?fù)湫蛄校惴ㄖ凶兞縦用于對加入序列的頂點(diǎn)計(jì)數(shù)，因此，空(5)處應(yīng)填入“kGn”或“k!=Gn”。21、隊(duì)列方式：v1 v2 v5 v4 v3 v7 v6 或者1 2 5 4 3 7 6 棧方式：v1 v2 v5 v4 v7 v3 v6 或者1 2 5 4 7 3 6使用棧和隊(duì)列的差別在于拓?fù)湫蛄兄许旤c(diǎn)的排列次序可能不同。對于本題中的有向圖，在使用隊(duì)列的方式下： (1)開始時(shí)僅頂點(diǎn)v1的入度為O，因此頂點(diǎn)v1入隊(duì)； (2)隊(duì)頭頂點(diǎn)v1出隊(duì)，并進(jìn)入拓?fù)湫蛄?，然后刪除從頂點(diǎn)v1出發(fā)的弧后，僅使頂點(diǎn)v2的入度為0，因此頂點(diǎn)v2入隊(duì)； (3)隊(duì)頭頂點(diǎn)v2出隊(duì)，并進(jìn)入拓?fù)湫蛄?，然后刪除從頂點(diǎn)v2出發(fā)的弧后，僅使頂點(diǎn)v5的入度為0，因此頂點(diǎn)v5入隊(duì)； (4)隊(duì)頭頂點(diǎn)v5出隊(duì)，并進(jìn)入拓?fù)湫蛄?，然后刪除從頂點(diǎn)v5出發(fā)的弧后，僅使頂點(diǎn)v4的入度為0，因此頂點(diǎn)v4入隊(duì)； (5)隊(duì)頭頂點(diǎn)v4出隊(duì)，并進(jìn)入拓?fù)湫蛄?，然后刪除從頂點(diǎn)v4出發(fā)的弧后，僅使頂點(diǎn)v3和v7的入度為0，因此頂點(diǎn)v3和v7依次入隊(duì)； (6)隊(duì)頭頂點(diǎn)v3出隊(duì)，并進(jìn)入拓?fù)湫蛄?，然后刪除從頂點(diǎn)v3出發(fā)的弧后，沒有產(chǎn)生新的入度為0的頂點(diǎn)； (7)隊(duì)頭頂點(diǎn)v7出隊(duì)，并進(jìn)入拓?fù)湫蛄?，然后刪除從頂點(diǎn)v7出發(fā)的弧后，使頂點(diǎn)v6的入度為0，因此頂點(diǎn)v6入隊(duì)； (8)隊(duì)頭頂點(diǎn)v6出隊(duì)，并進(jìn)入拓?fù)湫蛄?，然后刪除從頂點(diǎn)v6出發(fā)的弧后，沒有產(chǎn)生新的入度為0的頂點(diǎn)，隊(duì)列已空，因此結(jié)束拓?fù)渑判蜻^程，得到的拓?fù)湫蛄袨関1 V2 v5v4 v3 v7 v6。 使用棧保存入度為0的頂點(diǎn)時(shí)，前4步都是一樣的，因?yàn)槊看蝺H有一個元素進(jìn)棧，因此出棧序列與入棧序列一致。到第5步時(shí)，v3和v7依次入棧后，出棧時(shí)的次序?yàn)関7和v3，因此得到的拓?fù)湫蛄袨関1 v2 v5 v4 v7 v3 v6。22、O(n+e) 23、O(n2)以鄰接表為存儲結(jié)構(gòu)時(shí)，計(jì)算各頂點(diǎn)入度的時(shí)問復(fù)雜度為O(e)，建立零入度頂點(diǎn)隊(duì)列的時(shí)間復(fù)雜度為O(n)。在拓?fù)渑判蜻^程中，(圖中無環(huán)情況下)每個頂點(diǎn)進(jìn)出隊(duì)列各1次，入度減1的操作在while循環(huán)中共執(zhí)行e次，所以總的時(shí)間復(fù)雜度為O(n+e)。 以鄰接矩陣為存儲結(jié)構(gòu)時(shí)，計(jì)算各頂點(diǎn)入度時(shí)需要遍歷整個矩陣，因此時(shí)間復(fù)雜度為O(n2)，建立零入度頂點(diǎn)隊(duì)列的時(shí)間復(fù)雜度為O(n)。在拓?fù)渑判蜻^程中，(圖中無環(huán)情況下)每個頂點(diǎn)進(jìn)出隊(duì)列各1次，實(shí)現(xiàn)入度減1操作時(shí)需遍歷每個頂點(diǎn)的行向量1遍(時(shí)問復(fù)雜度為O(n)，所以總的時(shí)間復(fù)雜度為O(n2)。 試題五24、 FlyBehavior *flyBehavior 25、 TakeOffBehavjor *=takeOffBehavior 26、 flyBehavior-fly() 27、 takeOffBehavior-takeOff()_ 28、 SubSo