2010年上半年（下午）《軟件設(shè)計(jì)師》真題

《2010年上半年（下午）《軟件設(shè)計(jì)師》真題》由會員分享，可在線閱讀，更多相關(guān)《2010年上半年（下午）《軟件設(shè)計(jì)師》真題（9頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、2010年上半年（下午）《軟件設(shè)計(jì)師》真題 注意：圖片可根據(jù)實(shí)際需要調(diào)整大小 卷面總分：6分 答題時間：240分鐘 試卷題量：6題 練習(xí)次數(shù)：0次 問答題 （共6題，共6分） 1.某運(yùn)輸公司決定為新的售票機(jī)開發(fā)車票銷售的控制軟件。圖3-1給出了售票機(jī)的面板示意圖以及相關(guān)的控制部件。 售票機(jī)相關(guān)部件的作用如下所述： （1）目的地鍵盤用來輸入行程目的地的代碼（例如，200表示總站）。 （2）乘客可以通過車票鍵盤選擇車票種類（單程票、多次往返票和座席種類）。 （3）繼續(xù)/取消鍵盤上的取消按鈕用于取消

2、購票過程，繼續(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所示。 圖3-3類圖 【問題1】（5分） 根據(jù)說明中的描述，給出圖3-2中A1和A2所對應(yīng)的參與者，U1所對應(yīng)的用例，以及（1）、（2）處所對應(yīng)的關(guān)系。 【問題2】（7分） 根據(jù)說明中的描

3、述，給出圖3-3中缺少的C1~C4所對應(yīng)的類名以及（3）～（6）處所對應(yīng)的多重度。 【問題3】（3分） 圖3-3中的類圖設(shè)計(jì)采用了中介者（Mediator）設(shè)計(jì)模式，請說明該模式的內(nèi)涵。 正確答案： 本題解析： 【問題1】（5分，各1分）A1：乘客A2：服務(wù)技術(shù)人員 U1：支付（1）＜＜include>>（2）＜＜include>> 【問題2】（7分） C1：鍵盤（2分） C2：目的地鍵盤（1分） C3：車票鍵盤（1分） C4：繼續(xù)/取消鍵盤（1分） （3）~（6）：1（各0.5分）

4、 【問題3】（3分） 使用Mediator模式，可以使各個對象間的耦合松散（1分），只需關(guān)心和Mediator的關(guān)系，使多對多的關(guān)系變成了一對多的關(guān)系（1分），可以降低系統(tǒng)的復(fù)雜性，提高可修改擴(kuò)展性(1分）。 本題考查面向?qū)ο箝_發(fā)相關(guān)知識，涉及UML用例圖、類圖以及類圖設(shè)計(jì)時的設(shè)計(jì)模式。UML目前在面向?qū)ο筌浖_發(fā)中廣泛使用，是面向?qū)ο筌浖_發(fā)考查的重要內(nèi)容。 【問題1】 本問題考查用例圖。用例圖用于確定系統(tǒng)邊界，識別與系統(tǒng)交互的參與者，通過判斷參與者發(fā)起的用例，建立和參與者之間的關(guān)聯(lián)，然后再確認(rèn)用例之間的關(guān)系。 本題中對售票機(jī)的描述為“乘客可以通過車票鍵盤選擇車票種類（單程票、多次

5、往返票和座席種類）；售票機(jī)的維護(hù)工作（取回現(xiàn)金、放入空白車票等）由服務(wù)技術(shù)人員完成”。由此可知，圖3-1中A1為乘客，A2為服務(wù)技術(shù)人員。 對購票用例，要選擇目的地和車票類型、通過插卡口進(jìn)行支付才可完成購票。因此U2為支付。 在考查用例之間的關(guān)系時，購票過程可以取消，也允許乘客連續(xù)購買多張票，因此，購票時可以包含多次選擇目的地和車票類型、支付，即購票用例包含（關(guān)系＜＜include>>)選擇目的地和車票類型以及支付。 【問題2】 本問題考查類圖。類圖設(shè)計(jì)的重點(diǎn)是類的抽象和繼承關(guān)系以及多重度。售票機(jī)的面板由多個控制部件組成。根據(jù)說明這些控制部件有目的地鍵盤、車票鍵盤和繼續(xù)／取消鍵盤、顯示

6、屏、卡驅(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。 【問題３】 本問題考查設(shè)計(jì)模式。設(shè)計(jì)模式題目雖然比較難，但是本題題目中已經(jīng)給出了所采用的設(shè)計(jì)

7、模式為Mediator模式，只需說明設(shè)計(jì)模式的內(nèi)涵即可，也比較容易。使用Mediator模式，可以使各個對象間的耦合松散，只需關(guān)心和Mediator的關(guān)系，使多對多的關(guān)系變成了一對多的關(guān)系，可以降低系統(tǒng)的復(fù)雜性，提高可修改擴(kuò)展性。 2.某大型企業(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ù)庫信息存放在操作

8、表中；權(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é)

9、果進(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】（3分） 使用說明中的詞語，給出圖1-1中的實(shí)體E1~E3的名稱。 【問題2】（3分） 使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲D1~D3的名稱。 【問題3】（6分） 給出圖1-2中加工P的名稱及其輸入、輸出流。 圖1-1頂層數(shù)據(jù)流圖 圖1-2 0層數(shù)據(jù)流圖 除加工P的輸入與輸出流外，圖1-2還缺失了兩條數(shù)據(jù)流，請給出這兩條數(shù)據(jù)流的起點(diǎn)和終點(diǎn)。 注：名稱使用說明中的詞匯，起點(diǎn)和終點(diǎn)均使用圖1-2中的符號或詞匯

10、。 【問題4】（3分） 在繪制數(shù)據(jù)流圖時，需要注意加工的繪制。請給出三種在繪制加工的輸入、輸出時可能出現(xiàn)的錯誤。 正確答案： 本題解析： 【問題1】（3分，各1分） E1：前端應(yīng)用E2：數(shù)據(jù)管理員E3：后端數(shù)據(jù)庫 【問題2】（3分，各1分） D1：用戶表D2：操作表D3：權(quán)限表 【問題3】（6分） P的名稱：操作結(jié)果處理（1分） 缺少的數(shù)據(jù)流： 【問題4】（3分） 在繪制數(shù)據(jù)流圖時，可能出現(xiàn)的輸入、輸出錯誤： 只有輸入而無輸出或者黑洞（1分） 只有輸出而無輸入或者奇跡（1

11、分） 輸入的數(shù)據(jù)流無法通過加工產(chǎn)生輸出流或者灰洞（1分） 輸入的數(shù)據(jù)流與輸出的數(shù)據(jù)流名稱相同（1分） 注：總分3分，答對上述1個即可給1分，多答不多給分。 本題考查數(shù)據(jù)流圖(DFD）的應(yīng)用，是比較傳統(tǒng)的題目，要求考生細(xì)心分析題目中所描述的內(nèi)容。 DFD是一種便于用戶理解、分析系統(tǒng)數(shù)據(jù)流程的圖形工具。是系統(tǒng)邏輯模型的重要組成部分。 【問題1】 本問題考查頂層DFD。頂層DFD一般用來確定系統(tǒng)邊界，將待開發(fā)系統(tǒng)看作一個加工，因此圖中只有唯一的一個加工和一些外部實(shí)體，以及這兩者之間的輸入輸出數(shù)據(jù)流。題目要求根據(jù)描述確定圖中的外部實(shí)體。分析題目中的描述，并結(jié)合已經(jīng)在頂層數(shù)據(jù)流圖中給出的數(shù)

12、據(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】 本問題考查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ù)流從操作

13、管理來，D3的輸入數(shù)據(jù)流從權(quán)限管理來，所以D1為用戶表，D2為操作表，D3為權(quán)限表。 【問題3】 本問題考查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只有輸

14、入流沒有輸出流，這是常見DFD設(shè)計(jì)時的錯誤，所以首先考查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ù)流圖中加工繪制時的注意事項(xiàng)。繪制加工時可能出現(xiàn)的錯誤有：加工的輸入、輸出時可能出現(xiàn)只有輸入而無輸出、只有輸出而無輸入、輸入的數(shù)據(jù)流無法通過加

15、工產(chǎn)生輸出流以及輸入的數(shù)據(jù)流與輸出的數(shù)據(jù)流名稱相同等錯誤。 3.某學(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í)驗(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é)時、授課學(xué)期和開課的班級等信

16、息；實(shí)驗(yàn)信息記錄該課程的實(shí)驗(yàn)進(jìn)度信息，包括：實(shí)驗(yàn)名、實(shí)驗(yàn)類型、學(xué)時、安排周次等信息，如表2-1所示。 （2）以課程為單位制定實(shí)驗(yàn)安排計(jì)劃信息，包括：實(shí)驗(yàn)地點(diǎn)，實(shí)驗(yàn)時間、實(shí)驗(yàn)員等信息，實(shí)驗(yàn)計(jì)劃如表2-2所示。 （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)成績 （4）學(xué)生的實(shí)驗(yàn)課程總成績根據(jù)每次實(shí)驗(yàn)的成績以及每次實(shí)驗(yàn)的難度來計(jì)算。 【概念模型設(shè)計(jì)】 根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖（不完整）如圖2-1所示。 圖2-1實(shí)體聯(lián)系圖 【邏輯結(jié)構(gòu)設(shè)計(jì)】 根據(jù)概念模型設(shè)計(jì)階段完成的實(shí)

17、體聯(lián)系圖，得出如下關(guān)系模式（不完整）： 課程（課程編號，課程名稱，授課院系，實(shí)驗(yàn)學(xué)時） 班級（班級號，專業(yè)，所屬系） 開課情況（（1），授課學(xué)期） 實(shí)驗(yàn)（（2），實(shí)驗(yàn)類型，難度，學(xué)時，安排周次） 實(shí)驗(yàn)計(jì)劃（（3），實(shí)驗(yàn)時間，人數(shù)） 實(shí)驗(yàn)員（（4），級別） 實(shí)驗(yàn)室（實(shí)驗(yàn)室編號，地點(diǎn)，開放時間，可容納人數(shù)，實(shí)驗(yàn)類型） 學(xué)生（（5），姓名，年齡，性別） 實(shí)驗(yàn)成績（（6），實(shí)驗(yàn)成績，評分實(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ǔ)充完整并用下劃線指出這六個關(guān)系模式的主

18、鍵。 【問題3】（3分） 如果需要記錄課程的授課教師，新增加“授課教師”實(shí)體。請對圖2-1進(jìn)行修改，畫出修改后的實(shí)體間聯(lián)系和聯(lián)系的類型。 正確答案： 本題解析： 【問題1】（6分） 注：聯(lián)系的名稱不做要求。 課程與班級之間的聯(lián)系1分，聯(lián)系的類型1分 班級與學(xué)生之間的聯(lián)系1分，聯(lián)系的類型0.5分 實(shí)驗(yàn)、實(shí)驗(yàn)員與學(xué)生之間的聯(lián)系1分，聯(lián)系的類型1分 實(shí)驗(yàn)、實(shí)驗(yàn)員與實(shí)驗(yàn)室之間的聯(lián)系及類型0.5分 【問題2】（6分） （1）課程編號，班級號 （2）實(shí)驗(yàn)編號，課程編號 （3）實(shí)驗(yàn)編號，批次

19、號，安排學(xué)期，實(shí)驗(yàn)室編號，實(shí)驗(yàn)員編號 （4）實(shí)驗(yàn)員編號，實(shí)驗(yàn)員姓名 （5）學(xué)號，班級號 （6）實(shí)驗(yàn)編號，學(xué)號 注：每個空0.5分，每個主鍵0.5分。 【問題3】（3分） 授課教師、課程與班級之間的聯(lián)系1.5分，聯(lián)系的類型1.5分。 本題考查數(shù)據(jù)庫概念結(jié)構(gòu)設(shè)計(jì)及向邏輯結(jié)構(gòu)轉(zhuǎn)換的掌握。 此類題目要求考生認(rèn)真閱讀題目，根據(jù)題目的需求描述，給出實(shí)體間的聯(lián)系。 【問題1】 根據(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)

20、員之間的安排關(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)系。 【問題2】 根據(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í)驗(yàn)可能按實(shí)驗(yàn)室被分成多個批次，每個批次的實(shí)驗(yàn)會有若干名實(shí)驗(yàn)員來輔導(dǎo)學(xué)生

21、實(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)編號，并共同作為主鍵。 【問題3】 由于授課教師負(fù)責(zé)給若干個班級開設(shè)若干門課程，因此，課程、班級和授課教師之間的開設(shè)關(guān)系是k:n:m聯(lián)系。 4.某軟件公司現(xiàn)欲開發(fā)一款飛機(jī)飛行模擬系統(tǒng)，該系統(tǒng)主要模擬不同種類飛機(jī)的飛行特征與起飛特征。需要模擬的飛機(jī)種類及其特征如表6-1所示。 表6-1 為支

22、持將來模擬更多種類的飛機(jī)，采用策略設(shè)計(jì)模式（Strategy）設(shè)計(jì)的類圖如圖6-1所示。 圖6-1中，AirCraft為抽象類，描述了抽象的飛機(jī)，而類Helicopter、AirPlane、Fighter和Harrier分別描述具體的飛機(jī)種類，方法fly（　?。┖蛅akeOff（　?。┓謩e表示不同飛機(jī)都具有飛行特征和起飛特征類FlyBehavior與TakeOffBehavior為抽象類，分別用于表示抽象的飛行為與起飛行為；類SubSonicFly與SuperSonicFly分別描述亞音速飛行和超音速飛行的行為；類VerticalTakeOff與LongDistanceTakeOff分別

23、描述垂直起飛與長距離起飛的行為。 【Java代碼】 interface FlyBehavior{ public void fly（　?。? }; class SubSonicFly implements FlyBehavior{ public void fly（　?。﹞System.out.println("亞音速飛行！");} }; class SuperSonicFly implements FlyBehavior{ public void fly（　?。﹞System.out.println("超音速飛行！");} }; interface TakeOffBehav

24、ior{ public void takeOff（　?。? }; class VerticalTakeOff implements TakeOffBehavior{ public void takeOff（　?。﹞System.out.println("垂直起飛！");} }; class LongDistanceTakeOff implements TakeOffBehavior{ public void takeOff（　?。﹞System.out.println("長距離起飛！");} }; abstract class AirCraft{ protected（1）;

25、 protected（2）; public void fly（　?。﹞（3）;} public void takeOff（　?。﹞（4）;}; }; class Helicopter（5）AirCraft{ public Helicopter（　?。﹞ flyBehavior=new（6）; takeOffBehavior=new（7）; } }; //其它代碼省略 正確答案： 本題解析： （1）FlyBehavior flyBehavior（2分） （2）TakeOffBeha

26、vior takeOffBehavior（2分） （3）flyBehavior.fly()（2分） （4）takeOffBehavior.takeOff()（2分） （5）extends（3分） （6）SubSonicFly()（2分） （7）VerticalTakeOff()（2分） 注：空（1）與空（2）答案可互換 本題目考查了設(shè)計(jì)模式中的策略設(shè)計(jì)模式，實(shí)際上與2007年上半年Java題目的考核內(nèi)容相同。 從本題的敘述中可以看出，存在四種不同的飛機(jī)類型，但每種飛機(jī)類型的起飛特征和飛行特征并不完全相同，這就使得我們很難采用比較直接的方法來實(shí)現(xiàn)重用。例如，定義一個抽象的飛機(jī)類，

27、實(shí)現(xiàn)飛機(jī)的起飛特征，然后四種飛機(jī)直接重用該特征。但是，我們可以觀察到，盡管飛機(jī)的起飛特征和飛行特征有所不同，有一點(diǎn)可以肯定的是，一種飛機(jī)都具備了飛行特征和起飛特征。因此，可以抽象出一個飛機(jī)類，其中含有飛行特征與起飛特征，但關(guān)于兩個特征的實(shí)現(xiàn)要單獨(dú)抽取出來，所以又形成了FIyBehavior類和TakeOffBehavior類，分別表示抽象的飛行特征和起飛特征，而這兩個類的子類則分別現(xiàn)不同的起飛和飛行特征，最終轉(zhuǎn)化為，在創(chuàng)建一個具體的飛機(jī)時，給其配上不同的起飛特征和飛行特征即可。 本題中的空（1）和空（2）應(yīng)該填寫成員變量，根據(jù)類圖可以得知，此處應(yīng)該表示的是飛行和起飛特征變量?？眨?）和空（4

28、）處需要實(shí)現(xiàn)飛行與起飛特征，但AirCraft是抽象的類，所以把實(shí)現(xiàn)代理給指針變量。Helicopter類需要指定由父類繼承而來的成員變量的初始值，因?yàn)镠elicopter的特征是垂直起飛和亞音速飛行，因此生成這兩個特征的對象，分別賦值給flyBehavior和takeOffBchavior變量。 5.某軟件公司現(xiàn)欲開發(fā)一款飛機(jī)飛行模擬系統(tǒng)，該系統(tǒng)主要模擬不同種類飛機(jī)的飛行特征與起飛特征。需要模擬的飛機(jī)種類及其特征如表5-1所示。 表5-1 為支持將來模擬更多種類的飛機(jī)，采用策略設(shè)計(jì)模式（Strategy）設(shè)計(jì)的類圖如圖5-1所示。 圖5-1中，A

29、irCraft為抽象類，描述了抽象的飛機(jī)，而類Helicopter、AirPlane、Fighter和Harrier分別描述具體的飛機(jī)種類，方法fly（　?。┖蛅akeOff（　?。┓謩e表示不同飛機(jī)都具有飛行特征和起飛特征；類FlyBehavior與TakeOffBehavior為抽象類，分別用于表示抽象的飛行為與起飛行為；類SubSonicFly與SuperSonicFly分別描述亞音速飛行和超音速飛行的行為；類VerticalTakeOff與LongDistanceTakeOff分別描述垂直起飛與長距離起飛的行為。 【C++代碼】 #include＜iostream> using n

30、amespace std; class FlyBehavior{ public:virtual void fly（　?。?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（　

31、　）=0; }; class VerticalTakeOff:public TakeOffBehavior{ public:void takeOff（　?。﹞cout＜＜"垂直起飛！"＜＜endl;} }; class LongDistanceTakeOff:public TakeOffBehavior{ public:void takeOff（　　）{cout＜＜"長距離起飛！"＜＜endl;} }; class AirCraft{ protected: （1）; （2）; public: void fly（　　）{（3）;} void takeOff（　?。﹞（

32、4）;}; }; class Helicopter:public AirCraft{ public: Helicopter（　?。﹞ flyBehavior=new（5）; takeOffBehavior=new（6）; } （7）{ if(!flyBehavior)delete flyBehavior; if(!takeOffBehavior)delete takeOffBehavior; } }; // 其它代碼省略 正確答案： 本題解析： （1）FlyBehavior*f

33、lyBehavior（2分） （2）TakeOffBehavior*takeOffBehavior（2分） （3）flyBehavior->fly()（2分） （4）takeOffBehavior->takeOff()（2分） （5）SubSonicFly()（2分） （6）VerticalTakeOff()（2分） （7）~Helicopter()（3分） 注：空（1）與空（2）答案可互換 本題目考查了設(shè)計(jì)模式中的策略設(shè)計(jì)模式，實(shí)際上與2007年上半年考核內(nèi)容相同。 從本題的敘述中可以看出，存在4種不同的飛機(jī)類型，但每種飛機(jī)類型的起飛特征和飛行特征并不完全相同，這就使得我

34、們很難采用比較直接的方法來實(shí)現(xiàn)重用。例如，定義一個抽象的飛機(jī)類，實(shí)現(xiàn)飛機(jī)的起飛特征，然后4種飛機(jī)直接重用該特征。但是，我們可以觀察到，盡管飛機(jī)的起飛特征和飛行特征有所不同，有一點(diǎn)可以肯定的是，每一種飛機(jī)都具備了飛行特征和起飛特征。因此，可以抽象出一個飛機(jī)類，其中含有飛行特征與起飛特征，但關(guān)于兩個特征的實(shí)現(xiàn)要單獨(dú)抽取出來，所以又形成了FlyBehavior類和TakeOffBehavior類分別表示抽象的飛行和起飛特征，而這兩個類的子類則分別實(shí)現(xiàn)不同的起飛特征和飛行特征，最終轉(zhuǎn)化為，在創(chuàng)建一個具體的飛機(jī)時，給其配上不同的起飛特征和飛行特征即可。 本題中的空（1）和空（2）應(yīng)該填寫成員變量，根據(jù)

35、類圖可以得知，此處應(yīng)該表示的是飛行和起飛特征變量，在C++中可以采用指針來表示。空（3）和空（4）處需要實(shí)現(xiàn)飛行與起飛特征，但AirCraft是抽象的類，所以把實(shí)現(xiàn)代理給指針變量。Helicopter類需要指定由父類繼承而來的成員變量的初始值，因?yàn)镠elicopter的特征是垂直起飛和亞音速飛行，因此生成這兩個特征的對象，分別賦值給flyBehavior和takeOffBehavior變量。 6.對有向圖進(jìn)行拓?fù)渑判虻姆椒ㄊ牵? （1）初始時拓?fù)湫蛄袨榭眨? （2）任意選擇一個入度為0的頂點(diǎn)，將其放入拓?fù)湫蛄兄?，同時從圖中刪除該頂點(diǎn)以及從該頂點(diǎn)出發(fā)的?。? （3

36、）重復(fù)（2），直到不存在入度為0的頂點(diǎn)為止（若所有頂點(diǎn)都進(jìn)入拓?fù)湫蛄袆t完成拓?fù)渑判?，否則由于有向圖中存在回路無法完成拓?fù)渑判颍? 函數(shù)int*TopSort(LinkedDigraph G)的功能是對有向圖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 Arc

37、Node*nextarc;/*指示下一個鄰接頂點(diǎn)*/ }ArcNode; typedef struct AdjList{/*頭結(jié)點(diǎn)類型*/ char vdata;/*頂點(diǎn)的數(shù)據(jù)信息*/ ArcNode*firstarc;/*指向鄰接表的第一個表結(jié)點(diǎn)*/ }AdjList; typedef struct LinkedDigraph{/*圖的類型*/ int n;/*圖中頂點(diǎn)個數(shù)*/ AdjList Vhead[MAXVNUM];/*所有頂點(diǎn)的頭結(jié)點(diǎn)數(shù)組*/ }LinkedDigraph; 例如，某有向圖G如圖4-1所示，其鄰接表如圖4-2所示。 圖4-1有向圖G

38、函數(shù)TopSort中用到了隊(duì)列結(jié)構(gòu)(Queue的定義省略)，實(shí)現(xiàn)隊(duì)列基本操作的函數(shù)原型如下表所示： 【C代碼】 int*TopSort(LinkedDigraph G){ ArcNode*p;/*臨時指針，指示表結(jié)點(diǎn)*/ Queue Q;/*臨時隊(duì)列，保存入度為0的頂點(diǎn)編號*/ int k=0;/*臨時變量，用作數(shù)組元素的下標(biāo)*/ int j=0，w=0;/*臨時變量，用作頂點(diǎn)編號*/ int*topOrder，*inDegree; topOrder=(int*)malloc((G.n+1)*sizeof(int));/*存儲拓?fù)湫蛄兄械捻旤c(diǎn)編號*/ inDegree=(

39、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++){/*初始化*/ 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的

40、頂點(diǎn)保存在隊(duì)列中*/ if(0==inDegree[j])EnQueue(&Q，j); while(!IsEmpty(Q)){ （2）;/*隊(duì)頭頂點(diǎn)出隊(duì)列并用w保存該頂點(diǎn)的編號*/ 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*/ free(inDegree); if(（5）) return NULL; return

41、topOrder; }/*TopSort*/ 【問題1】（9分） 根據(jù)以上說明和C代碼，填充C代碼中的空（1）～（5）。 【問題2】（2分） 對于圖4-1所示的有向圖G，寫出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄?。若將函?shù)TopSort中的隊(duì)列改為棧，寫出函數(shù)TopSort執(zhí)行后得到的拓?fù)湫蛄小? 【問題3】（4分） 設(shè)某有向無環(huán)圖的頂點(diǎn)個數(shù)為n、弧數(shù)為e，那么用鄰接表存儲該圖時，實(shí)現(xiàn)上述拓?fù)渑判蛩惴ǖ暮瘮?shù)TopSort的時間復(fù)雜度是（6）。 若有向圖采用鄰接矩陣表示（例如，圖4-1所示有向圖的鄰接矩陣如圖4-3所示），且將函數(shù)TopSort中有關(guān)鄰接表的操作修改為針對鄰接矩陣的

42、操作，那么對于有n個頂點(diǎn)、e條弧的有向無環(huán)圖，實(shí)現(xiàn)上述拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度是（7）。 正確答案： 本題解析： 【問題1】（9分） （1）InitQueue(&Q)（1分）注：函數(shù)名與參數(shù)必須完全正確才可得分 （2）DeQueue(&Q，&w)（2分）注：函數(shù)名與參數(shù)必須完全正確才可得分 （3）inDegree[p->adjvex]及其等價形式（2分） （4）inDegree[p->adjvex]及其等價形式（2分） （5）k＜G.n或k!=G.n（2分） 【問題2】（2分） 隊(duì)列方

43、式：v1 v2 v5 v4 v3 v7 v6（或1 2 5 4 3 7 6）（1分） 棧方式：v1 v2 v5 v4 v7 v3 v6（或1 2 5 4 7 3 6）（1分） 【問題3】（4分） （6）O(n+e)（2分） （7）O（n2）（2分） 本題考查數(shù)據(jù)結(jié)構(gòu)和算法中的拓?fù)渑判蛩惴ā? 【問題１】 拓?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)及

44、其與該頂點(diǎn)有關(guān)的所有邊； ③重復(fù)上述兩步，直至網(wǎng)中不存在入度為零的頂點(diǎn)為止。 在拓?fù)渑判蜻^程中，需要將入度為0的頂點(diǎn)臨時存儲起來。函數(shù)中用一個隊(duì)列暫存入度為0且沒有進(jìn)入拓?fù)湫蛄械捻旤c(diǎn)。顯然，空（1）處應(yīng)填入InitQueue（&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ì)列的處理。

45、 題中圖采用鄰接表存儲結(jié)構(gòu)，當(dāng)指針p指向Vi鄰接表中的結(jié)點(diǎn)時，p->adjvex表示vi的一個鄰接頂點(diǎn)，刪除vi至頂點(diǎn)p->adjvex的弧的操作實(shí)現(xiàn)為頂點(diǎn)p->adjvex的入度減1，因此，空（3）處應(yīng)填入inDegree[p->adjvex]，當(dāng)頂點(diǎn)p->adjvex的入度為0時，需要將其加入隊(duì)列，因此空(4）處也應(yīng)填入inDegree[p->adjvex]。 空（5）處判斷是否所有頂點(diǎn)都加入了拓?fù)湫蛄?，算法中變量k用于對加入序列的頂點(diǎn)計(jì)數(shù)，因此，空（5）處應(yīng)填入“k＜G.n”或“k!=G.n"。 【問題2】 使用棧和隊(duì)列的差別在于拓?fù)湫蛄兄许旤c(diǎn)的排列次序可能不同。對于本題中的有向

46、圖，在使用隊(duì)列的方式更下： （1）開始時僅頂點(diǎn)V1的入度為0，因此頂點(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ù)湫蛄校缓髣h除從頂點(diǎn)v2出發(fā)的弧后，僅使頂點(diǎn)v5的入度為0，因止頂點(diǎn)v5入隊(duì)； （4）隊(duì)頭頂點(diǎn)v5出隊(duì)，并進(jìn)入拓?fù)湫蛄校缓髣h除從頂點(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ù)?/p>

47、序列，然后刪除從頂點(diǎn)v3出發(fā)的弧后，沒有產(chǎn)生新的入度為0的頂點(diǎn)； （7）隊(duì)頭頂點(diǎn)v7出隊(duì)，并進(jìn)入拓?fù)湫蛄校缓髣h除從頂點(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 v5 v4 v3 v7 v6。 使用棧保存入度為0的頂點(diǎn)時，前4步都是一樣的，因?yàn)槊看蝺H有一個元素進(jìn)棧，因此出棧序列與入棧序列一致。到第5步時，v3和v7依次入棧后，出棧時的次序?yàn)関7和v3，因此得到的拓?fù)湫蛄袨関1 v2 v5 v4 v7 v3 v6。 【問題3】 以鄰接表為存儲結(jié)構(gòu)時，計(jì)算各頂點(diǎn)入度的時間復(fù)雜度為O(e)，建立零入度頂點(diǎn)隊(duì)列的時間復(fù)雜度為O(n)。在拓?fù)渑判蜻^程中，（圖中無環(huán)情況下）每個頂點(diǎn)進(jìn)出隊(duì)列各1次，入度減l的操作在while循環(huán)中共執(zhí)行e次，所以總的時間復(fù)雜度為O(n+e)。 以鄰接矩陣為存儲結(jié)構(gòu)時，計(jì)算各頂點(diǎn)入度時需要遍歷整個矩陣，因此時間復(fù)雜度為O（n），建立零入度頂點(diǎn)隊(duì)列的時間復(fù)雜度為O（n）。在拓?fù)渑判蜻^程中，（圖中無環(huán)情況下）每個頂點(diǎn)進(jìn)出隊(duì)列各1次，實(shí)現(xiàn)入度減1操作時需遍歷每個頂點(diǎn)的行向量1遍（時間復(fù)雜度為O(n))，所以總的時間復(fù)雜度為O(n2）。