2010程序員考試下午

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

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

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

4、驗室的可容 納人數(shù)和實驗類型，分批次開設在多個實驗室的不同時間段。 一個實驗室的一次 實驗可以分配多個實驗員負責輔導實驗，實驗員給出學生的每次實驗成績。（1）課程信息包括：課程編號、課程名稱、實驗學時、授課學期和開課的班級 等信息；實驗信息記錄該課程的實驗進度信息， 包括：實驗名、實驗類型、學時、 安排周次等信息，如表2-1所示。表2-1課程及實驗信息野那1】他迎程4斟亍屯規(guī)原用生舲學時12血 0501.宿0501陽氣1帚曲G和 = -H15 ?-： ?SfiE性0.52 丫51. / ( 9（2）以課程為單位制定實驗安排計劃信息，包括：實驗地點，實驗時間、實驗 員等

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

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

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

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

9、2)due” 送_圖3-2 頂層用例圏【冋題1】（5分）根據(jù)說明中的描述，給出圖3-2中A1和A2所對應的參與者，U1所對應的用例， 以及（1）、（ 2）處所對應的關系?！締栴}2】（7分）根據(jù)說明中的描述，給出圖3-3中缺少的C1C4所對應的類名以及（3）（6） 處所對應的多重度?！締栴}3】（3分）圖3-3中的類圖設計采用了中介者（Mediator ）設計模式，請說明該模式的內(nèi)涵試題四（共15分）閱讀下列說明和C代碼，回答問題1至問題3,將解答寫在答題紙的對應欄內(nèi)。 【說明】對有向圖進行拓撲排序的方法是：（1）初始時拓撲序列為空；（2）任意選擇一個入度為0的頂點，將其放入拓撲序列中，同時從圖中

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

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

12、中用到了隊列結(jié)構(gòu)（Queue的定義省略），實現(xiàn)隊列基本操作的函 數(shù)原型如下表所示：型明aiJ hiilQueulQurui? Qj初始化隊列（構(gòu)造一個吒隊列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；/*臨時指針,指示表結(jié)點*/Queue Q; /*臨時隊列，保存入度為0的頂點編號*/int k = 0;/*臨時變量，用作數(shù)組元素的下標*/*

13、臨時變/*存儲拓撲序列/*存儲圖G中各int j = 0, w =0；量，用作頂點編號*/int *topOrder, *i nDegree;topOrder = (int *)malloc(G.n+1) * sizeof(int); 中的頂點編號*/in Degree = (int *)malloc(G. n+1) * sizeof(i nt); 頂點的入度*/if (!i nDegree | !topOrder) return NULL;(1);/*構(gòu)造一個空隊列*/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分）對于圖4-1所示的有向圖G,寫出函數(shù)TopSort執(zhí)行后得到的拓撲序列。若將 函數(shù)TopSort中的隊列改為棧，

15、寫出函數(shù) TopSort執(zhí)行后得到的拓撲序列?！締栴}31（ 4分）設某有向無環(huán)圖的頂點個數(shù)為n、弧數(shù)為e,那么用鄰接表存儲該圖時，實現(xiàn) 上述拓撲排序算法的函數(shù)TopSort的時間復雜度是（6）。若有向圖采用鄰接矩陣表示（例如，圖 4-1所示有向圖的鄰接矩陣如圖4-3 所示），且將函數(shù)TopSort中有關鄰接表的操作修改為針對鄰接矩陣的操作，那么對于有n個頂點、e條弧的有向無環(huán)圖，實現(xiàn)上述拓撲排序算法的時間復雜度 是（7）。2v4Xi 0I1G00nAti44nG0u0s00ITru000I00110D000I0Q00000i-0000T0圖41件向罔0的鄰M昨試題五（共15分）閱讀下列說明和C

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

17、設計模式(Strategy )設計的類圖 如圖5-1所示。圖5-1中，AirCraft 為抽象類，描述了抽象的飛機，而類Helicopter、AirPlane、 Fighter和Harrier分別描述具體的飛機種類，方法 fly()和takeOff()分別表 示不同飛機都具有飛行特征和起飛特征；類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,、為支持將來模擬更多種類的飛機，采用策略設計模式(Strategy )設計的類圖如 圖6-1所示。:Sub$piikl$uper$QiMcF

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