程序員考試下午

1、試題一（共15分）閱讀下列說明和圖，回答問題1至問題4，將解答填入答題紙的對應欄內(nèi)。 【說明】某大型企業(yè)的數(shù)據(jù)中心為了集中管理、控制用戶對數(shù)據(jù)的訪問并支持大量的連接需求，欲構建數(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é)構化方法對系統(tǒng)進行分析與設計，獲得如圖1-1所示的頂層數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖?！締栴} 1】（3分）使用說明中的詞語，給出圖1-1中的實體E1E3的名稱?！締栴} 2】（3分）使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲D1D3的名稱?！締栴}3】（6分）給出圖1-2中加工P的名稱及其輸入、輸出流。除加工P的輸入與輸出流外，圖1-2還缺失了兩條數(shù)據(jù)流，請給出這兩條數(shù)據(jù)流的起點和終點。注：名稱使用說明中的

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

4、驗室的一次實驗可以分配多個實驗員負責輔導實驗，實驗員給出學生的每次實驗成績。（1）課程信息包括：課程編號、課程名稱、實驗學時、授課學期和開課的班級等信息；實驗信息記錄該課程的實驗進度信息，包括：實驗名、實驗類型、學時、安排周次等信息，如表2-1所示。表 2-1 課程及實驗信息（2）以課程為單位制定實驗安排計劃信息，包括：實驗地點，實驗時間、實驗員等信息，實驗計劃如表2-2所示。（3）由實驗員給出每個學生每次實驗的成績，包括：實驗名、學號、姓名、班級、實驗成績等信息，實驗成績?nèi)绫?-3所示。（4）學生的實驗課程總成績根據(jù)每次實驗的成績以及每次實驗的難度來計算?！靖拍钅Ｐ驮O計】根據(jù)需求階段收集的信

5、息，設計的實體聯(lián)系圖（不完整）如圖2-1所示?！具壿嫿Y(jié)構設計】根據(jù)概念模型設計階段完成的實體聯(lián)系圖，得出如下關系模式（不完整）：課程（課程編號，課程名稱，授課院系，實驗學時） 班級（班級號，專業(yè)，所屬系） 開課情況（     （1）      ，授課學期）實驗（   （2）    ，實驗類型，難度，學時，安排周次）實驗計劃（     （3）     ，實驗時間，人數(shù)） 實驗員（

6、      （4）      ，級別） 實驗室（實驗室編號，地點，開放時間，可容納人數(shù)，實驗類型）學生（       （5）      ，姓名，年齡，性別）實驗成績（       （6）        ，實驗成績，評分實驗員）【問題1】（6分） 補充

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

8、以通過車票鍵盤選擇車票種類（單程票、多次往返票和座席種類）。（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所示?！締栴}1】（5分）根據(jù)說明中的描述，給出圖3-2中A1和A2所對應的參與者，U1所對應的用例，以及（1）、（

9、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的頂點，將其放入拓撲序列中，同時從圖中刪除該頂點以及從該頂點出發(fā)的?。唬?）重復（2），直到不存在入度為0的頂點為止（若所有頂點都進入拓撲序列則完成拓撲排序，否則由于有向圖中存在回路無法完成拓撲

10、排序）。 函數(shù)int* TopSort(LinkedDigraph G)的功能是對有向圖G中的頂點進行拓撲排序，返回拓撲序列中的頂點編號序列，若不能完成拓撲排序，則返回空指針。其中，圖G中的頂點從1開始依次編號，頂點序列為v1，v2，vn，圖G采用鄰接表示，其數(shù)據(jù)類型定義如下：#define MAXVNUM 50                      /*最大頂點數(shù)*/ty

11、pedef struct ArcNode                     /*表結(jié)點類型*/ int adjvex;                      &

12、#160;   /*鄰接頂點編號*/ struct ArcNode *nextarc;             /*指示下一個鄰接頂點*/ArcNode; typedef struct AdjList               /*頭結(jié)點類型*/ char vdata; 

13、60;                       /*頂點的數(shù)據(jù)信息*/ ArcNode *firstarc;                   /*指向鄰接表的第一個表結(jié)點*/AdjL

14、ist;typedef struct LinkedDigraph               /*圖的類型*/ int n;                           &

15、#160;  /*圖中頂點個數(shù)*/ AdjList VheadMAXVNUM;                 /*所有頂點的頭結(jié)點數(shù)組*/LinkedDigraph;例如，某有向圖G如圖4-1所示，其鄰接表如圖4-2所示。 函數(shù)TopSort中用到了隊列結(jié)構(Queue的定義省略)，實現(xiàn)隊列基本操作的函數(shù)原型如下表所示：【C代碼】int *TopSort(LinkedDigraph G)  Ar

16、cNode *p;                            /*臨時指針，指示表結(jié)點*/ Queue Q; /*臨時隊列，保存入度為0的頂點編號*/ int k = 0;          

17、60;                         /*臨時變量，用作數(shù)組元素的下標*/ int j = 0, w = 0;                  

18、60;           /*臨時變量，用作頂點編號*/ int *topOrder, *inDegree; topOrder = (int *)malloc(G.n+1) * sizeof(int);   /*存儲拓撲序列中的頂點編號*/ inDegree = (int *)malloc(G.n+1) * sizeof(int);   /*存儲圖G中各頂點的入度*/ if (!inDegree | !topOrd

19、er) return NULL; （1）  ;                                   /*構造一個空隊列*/ for ( j = 1; j <= G.n; j+ )   &#

20、160;                  /*初始化*/ topOrderj = 0;      inDegreej = 0;for (j = 1; j <= G.n; j+)               

21、60;          /*求圖G中各頂點的入度*/ for( p = G.Vheadj.firstarc; p; p = p->nextarc ) inDegreep-> adjvex += 1;for (j = 1; j <= G.n; j+)                  

22、60;    /*將圖G中入度為0的頂點保存在隊列中*/ if ( 0 = inDegreej ) EnQueue(&Q,j);while (!IsEmpty(Q)  （2） ;                              &#

23、160;  /*隊頭頂點出隊列并用w保存該頂點的編號*/topOrderk+ = w;  /*將頂點w的所有鄰接頂點的入度減1（模擬刪除頂點w及從該頂點出發(fā)的弧的操作）*/ for(p = G.Vheadw.firstarc; p; p = p->nextarc)  （3）-= 1; if (0 =（4）) EnQueue(&Q, p->adjvex); /* for */* while */free(inDegree);if (  （5）  ) return NULL; r

24、eturn topOrder; /*TopSort*/【問題1】（9分） 根據(jù)以上說明和C代碼，填充C代碼中的空（1）（5）?！締栴}2】（2分） 對于圖4-1所示的有向圖G，寫出函數(shù)TopSort執(zhí)行后得到的拓撲序列。若將函數(shù)TopSort中的隊列改為棧，寫出函數(shù)TopSort執(zhí)行后得到的拓撲序列。【問題3】（4分） 設某有向無環(huán)圖的頂點個數(shù)為n、弧數(shù)為e，那么用鄰接表存儲該圖時，實現(xiàn)上述拓撲排序算法的函數(shù)TopSort的時間復雜度是（6）。 若有向圖采用鄰接矩陣表示（例如，圖4-1所示有向圖的鄰接矩陣如圖4-3所示），且將函數(shù)TopSort中有關鄰接表

25、的操作修改為針對鄰接矩陣的操作，那么對于有n個頂點、e條弧的有向無環(huán)圖，實現(xiàn)上述拓撲排序算法的時間復雜度是（7）。試題五（共15分） 閱讀下列說明和C+代碼，將應填入 （n） 處的字句寫在答題紙的對應欄內(nèi)。【說明】 某軟件公司現(xiàn)欲開發(fā)一款飛機飛行模擬系統(tǒng)，該系統(tǒng)主要模擬不同種類飛機的飛行特征與起飛特征。需要模擬的飛機種類及其特征如表5-1所示。 為支持將來模擬更多種類的飛機，采用策略設計模式（Strategy）設計的類圖如圖5-1所示。圖5-1中，AirCraft為抽象類，描述了抽象的飛機，而類Helicopter、AirPlane、Fighter和Harrier分別描述具

26、體的飛機種類，方法fly()和takeOff()分別表示不同飛機都具有飛行特征和起飛特征；類FlyBehavior與TakeOffBehavior為抽象類，分別用于表示抽象的飛行為與起飛行為；類SubSonicFly與SuperSonicFly分別描述亞音速飛行和超音速飛行的行為；類VerticalTakeOff與LongDistanceTakeOff分別描述垂直起飛與長距離起飛的行為。【C+ 代碼】 #include<iostream>using namespace std;class FlyBehavior  public : virtual void fly() =

27、 0;class SubSonicFly:public FlyBehavior public: void fly() cout << "亞音速飛行！" << endl; ;class SuperSonicFly:public FlyBehavior public: void fly() cout << "超音速飛行！" << endl; ;class TakeOffBehavior  public: virtual void takeOff() = 0;class Vertic

28、alTakeOff:public TakeOffBehavior public: void takeOff() cout << "垂直起飛！" << endl; ;class LongDistanceTakeOff:public TakeOffBehavior  public: void takeOff () cout << "長距離起飛！" << endl; ;class AirCraftprotected:（1）   ;（2）   ;publi

29、c: void fly()（3）;  void takeOff() （4）; ;class Helicopter: public AirCraft public: Helicopter () flyBehavior = new（5）; takeOffBehavior = new（6）;（7） if(!flyBehavior) delete flyBehavior; if(!takeOffBehavior) delete takeOffBehavior; /其它代碼省略試題六（共15分） 閱讀下列說明和Ja

30、va代碼，將應填入 （n） 處的字句寫在答題紙的對應欄內(nèi)。【說明】 某軟件公司現(xiàn)欲開發(fā)一款飛機飛行模擬系統(tǒng)，該系統(tǒng)主要模擬不同種類飛機的飛行特征與起飛特征。需要模擬的飛機種類及其特征如表6-1所示。為支持將來模擬更多種類的飛機，采用策略設計模式（Strategy）設計的類圖如圖6-1所示。 圖6-1中，AirCraft為抽象類，描述了抽象的飛機，而類Helicopter、AirPlane、Fighter和Harrier分別描述具體的飛機種類，方法fly()和takeOff()分別表示不同飛機都具有飛行特征和起飛特征類FlyBehavior與TakeOffBehavior為抽象類，分別用于表示抽象的飛行為與起飛行為；類Sub