2016年下半年（下午）《軟件設(shè)計師》真題

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

1、2016年下半年（下午）《軟件設(shè)計師》真題 注意：圖片可根據(jù)實(shí)際需要調(diào)整大小 卷面總分：6分 答題時間：240分鐘 試卷題量：6題 練習(xí)次數(shù)：0次 問答題 （共6題，共6分） 1.某發(fā)票（lnvoice）由抬頭（Head）部分、正文部分和腳注（Foot）部分構(gòu)成?，F(xiàn)采用裝飾（Decorator）模式實(shí)現(xiàn)打印發(fā)票的功能，得到如圖5-1所示的類圖。 【C++代碼】 #include using namespace std; class Invoice{ public: （1）{ cout＜＜

2、"This is the content of the invoice!"＜＜endl; } }; class Decorator:public Invoice{ Invoice*ticket; public: Decorator(lnvoice*t){ticket=t;} void printInvoice（　　）{ if(ticket!=NULL) （2）; } }; class HeadDecorator:public Decorator{ public: HeadDecorator(lnvoice*t):Decorator(t){} void printI

3、nvoice（　　）{ cout＜＜"This is the header of the invoice!"＜＜endl; （3）; } }; class FootDecorator:public Decorator{ public: FootDecorator(Invoice*t):Decorator(t){} void printlnvoice（　?。﹞ （4）; cout＜＜"This is the footnote of the invoice!"＜＜endl; } }; int main(void){ Invoice t; FootDecorator f

4、(&t); HeadDecorator h(&f); h.printInvoice（　?。? cout＜＜”------------------------”＜＜endl; FootDecorator a(NULL); HeadDecorator b(（5）); b.printInvoice（　?。? return 0; } 程序的輸出結(jié)果為： This is the header of the invoice! This is the content of the invoice! This is the footnote of the invoice! -----

5、----------------------- This is the header of the invoice! This is the footnote of the invoice! 正確答案： 本題解析： （1）virtual void printInvoice() （2）ticket->printInvoice() （3）Decorator::printInvoice() （4）Decorator::printInvoice() （5）&a 1.Invoice類下，定義虛函數(shù)，

6、按類圖，函數(shù)名是printInvoice。 2.前面定義對象名是ticket，那么在ticket不為空的時候調(diào)用函數(shù)printInvoice。 3.這部分填寫發(fā)票的抬頭，看類圖應(yīng)該實(shí)現(xiàn)函數(shù)printInvoice，Decorator裝飾模式使用該方法。 4.這部分是發(fā)票的腳注，看類圖應(yīng)該實(shí)現(xiàn)函數(shù)printInvoice，Decorator裝飾模式使用該方法。 5.FootDecorator a(NULL)；腳步的裝飾參數(shù)是a，調(diào)用a參數(shù)。 2.某證券交易所為了方便提供證券交易服務(wù)，欲開發(fā)一證券交易平臺，該平臺的主要功能如下： （1）開戶。根據(jù)客戶服務(wù)助

7、理提交的開戶信息，進(jìn)行開戶，并將客戶信息存入客戶記錄中，賬戶信息（余額等）存入賬戶記錄中； （2）存款?？蛻艨梢韵蚱滟~戶中存款，根據(jù)存款金額修改賬戶余額； （3）取款?？蛻艨梢詮钠滟~戶中取款，根據(jù)取款金額修改賬戶余額； （4）證券交易?？蛻艉徒?jīng)紀(jì)人均可以進(jìn)行證券交易（客戶通過在線方式，經(jīng)紀(jì)人通過電話），將交易信息存入交易記錄中； （5）檢查交易。平臺從交易記錄中讀取交易信息，將交易明細(xì)返回給客戶。 現(xiàn)采用結(jié)構(gòu)化方法對該證券交易平臺進(jìn)行分析與設(shè)計，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。 【問題1】（3分） 使用說明中的詞語，給出圖1-1中的實(shí)體E1

8、-E3的名稱。 【問題2】（3分） 使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲D1-D3的名稱。 【問題3】（4分） 根據(jù)說明和圖中的術(shù)語，補(bǔ)充圖1-2中缺失的數(shù)據(jù)流及其起點(diǎn)和終點(diǎn)。 【問題4】（5分） 實(shí)際的證券交易通常是在證券交易中心完成的，因此，該平臺的“證券交易”功能需將交易信息傳遞給證券交易中心。針對這個功能需求，需要對圖1-1和圖1-2進(jìn)行哪些修改，請用200字以內(nèi)的文字加以說明。 正確答案： 本題解析： 【問題1】 E1：客戶服務(wù)助理，E2：客戶，E3：經(jīng)紀(jì)人。 【問題2】

9、 D1：客戶記錄，D2：賬戶記錄，D3：交易記錄。 【問題3】 【問題4】 圖1增加外部實(shí)體“證券交易中心”，增加“證券交易平臺”到“證券交易中心”，數(shù)據(jù)流：交易信息。 圖2增加外部實(shí)體“證券交易中心”，增加“證券交易（在線）”到“證券交易中心”，數(shù)據(jù)流：交易信息。 圖2增加“證券交易（電話）”到“證券交易中心”，數(shù)據(jù)流：交易信息。 【問題1】 要求識別E1-E3具體為哪個外部實(shí)體，通讀試題說明，可以了解到適合充當(dāng)外部實(shí)體的包括：客戶、客戶服務(wù)助理、經(jīng)記人。具體的對應(yīng)關(guān)系，可以通過將頂層圖與題目說明進(jìn)行匹配得知。如：從圖中可看出E1會向交易平臺發(fā)出數(shù)據(jù)流“開戶信息”；而從試

10、題說明“根據(jù)客戶服務(wù)助理提交的開戶信息，進(jìn)行開戶，并將客戶信息存入客戶記錄中，賬戶信息存入賬戶記錄中”可以看出，E1對應(yīng)是客戶服務(wù)助理。E2、E3同理可得。 【問題2】 要求識別存儲，解決這類問題，以圖的分析為主，配合說明給存儲命名，因?yàn)榇鎯ο嚓P(guān)的數(shù)據(jù)流一般展現(xiàn)了這個存儲中到底存了些什么信息，如從圖中可以看到D1中有客戶信息，而D2中有賬戶信息，題目說明中又有“根據(jù)客戶服務(wù)助理提交的開戶信息，進(jìn)行開戶，并將客戶信息存入客戶記錄中，賬戶信息存入賬戶記錄中?！弊匀籇1應(yīng)為客戶記錄，D2應(yīng)為賬戶記錄。同理，D3為交易記錄。 【問題3】 缺失數(shù)據(jù)流1 名稱：修改賬戶余額，起點(diǎn)：存款，終點(diǎn)：D

11、2。 理由：從試題說明“客戶可以向其賬戶中存款，根據(jù)存款金額修改賬戶余額”可以看出，這個功能有操作“根據(jù)存款金額修改賬戶余額”。據(jù)此可以了解到從該功能應(yīng)有數(shù)據(jù)流“存款”至D2，而0層圖沒有。 缺失數(shù)據(jù)流2 名稱：修改賬戶余額，起點(diǎn)：取款，終點(diǎn)：D2。 理由：從試題說明“客戶可以從其賬戶中取款，根據(jù)取款金額修改賬戶余額”可以看出，這個功能有操作“根據(jù)取款金額修改賬戶余額”。據(jù)此可以了解到從該功能應(yīng)有數(shù)據(jù)流“取款”至D2，而0層圖沒有。 缺失數(shù)據(jù)流3-4 名稱：交易信息存入交易記錄，起點(diǎn)：證券交易（分為在線與電話），終點(diǎn)：D3。 理由：從試題說明“客戶和經(jīng)紀(jì)人均可以進(jìn)行證券交易，將交

12、易信息存入交易記錄中”可以看出，這個功能有操作“將交易信息存入交易記錄中”。據(jù)此可以了解到從該功能應(yīng)有數(shù)據(jù)流“證券交易”至D3，而0層圖沒有。 3.某賓館為了有效地管理客房資源，滿足不同客戶需求，擬構(gòu)建一套賓館信息管理系統(tǒng)，以方便賓館管理及客房預(yù)訂等業(yè)務(wù)活動。 【需求分析結(jié)果】 該系統(tǒng)的部分功能及初步需求分析的結(jié)果如下： （1）賓館有多個部門，部門信息包括部門號、部門名稱、電話、經(jīng)理。每個部門可以有多名員工，每名員工只屬于一個部門；每個部門只有一名經(jīng)理，負(fù)責(zé)管理本部門。 （2）員工信息包括員工號、姓名、崗位、電話、工資，其中，員工號唯一標(biāo)識員工關(guān)系中的一

13、個元組，崗位有經(jīng)理、業(yè)務(wù)員。 （3）客房信息包括客房號（如1301、1302等）、客房類型、收費(fèi)標(biāo)準(zhǔn)、入住狀態(tài)（已入?。慈胱。渲锌头刻栁ㄒ粯?biāo)識客房關(guān)系中的一個元組，不同客房類型具有不同的收費(fèi)標(biāo)準(zhǔn)。 （4）客戶信息包括客戶號、單位名稱、聯(lián)系人、聯(lián)系電話、聯(lián)系地址，其中客戶號唯一標(biāo)識客戶關(guān)系中的一個元組。 （5）客戶預(yù)訂客房時，需要填寫預(yù)訂申請。預(yù)訂申請信息包括申請?zhí)枴⒖蛻籼?、入住時間、入住天數(shù)、客房類型、客房數(shù)量，其中，一個申請?zhí)栁ㄒ粯?biāo)識預(yù)訂申請中的一個元組；一位客戶可以有多個預(yù)訂申請，但一個預(yù)訂申請對應(yīng)唯一的一位客戶。 （6）當(dāng)客戶入住時，業(yè)務(wù)員根據(jù)客戶的預(yù)訂申請負(fù)責(zé)安排入住客房

14、事宜。安排信息包括客房號、姓名、性別、身份證號、入住時間、天數(shù)、電話，其中客房號、身份證號和入住時間唯一標(biāo)識一次安排。一名業(yè)務(wù)員可以安排多個預(yù)訂申請，一個預(yù)訂申請只由一名業(yè)務(wù)員安排，而且可安排多間同類型的客房。 【概念模型設(shè)計】 根據(jù)需求階段收集的信息，設(shè)計的實(shí)體聯(lián)系圖如圖2-1所示。 【關(guān)系模式設(shè)計】 部門（部門號，部門名稱，經(jīng)理，電話） 員工（員工號，（a），姓名，崗位，電話，工資） 客戶（（b），聯(lián)系人，聯(lián)系電話，聯(lián)系地址） 客房（客房號，客房類型，收費(fèi)標(biāo)準(zhǔn)，入住狀態(tài)） 預(yù)訂申請（（c），入住時間，天數(shù)，客房類型，客房數(shù)量） 安排（申請?zhí)?，客房號，姓名，性別，（d）

15、，天數(shù)，電話，業(yè)務(wù)員） 【問題1】（4分） 根據(jù)問題描述，補(bǔ)充四個聯(lián)系，完善圖2-1，的實(shí)體聯(lián)系圖。聯(lián)系名可用聯(lián)系1、聯(lián)系2、聯(lián)系3和聯(lián)系4代替，聯(lián)系的類型為1:1、1:n和m:n（或1:1，和1:*和*:*）。 【問題2】（8分） （1）根據(jù)題意，將關(guān)系模式中的空（a）～（d）補(bǔ)充完整，并填入答題紙對應(yīng)的位置上。 （2）給出“預(yù)訂申請”和“安排”關(guān)系模式的主鍵和外鍵。 【問題3】（3分） 【關(guān)系模式設(shè)計】中的“客房”關(guān)系模式是否存在規(guī)范性問題，請用100字以內(nèi)文字解釋你的觀點(diǎn)（若存在問題，應(yīng)說明如何修改“客房”關(guān)系模式）。

16、正確答案： 本題解析： 【問題1】 1、經(jīng)理與部門之間存在1:1的聯(lián)系。 2、部門與員工之間存在1:n的聯(lián)系。 3、客戶與預(yù)訂申請之間存在1:n的聯(lián)系。 4、業(yè)務(wù)員、客房、預(yù)訂申請之間存在1:m:n的聯(lián)系。 【問題2】 （a）部門號。 （b）客戶號、單位名稱 （c）申請?zhí)?、客戶號? （d）身份證號、入住時間。 ”預(yù)訂申請“關(guān)系模式中的主鍵是申請?zhí)枺怄I是客戶號。 ”安排“關(guān)系模式中的主鍵是：（客房號、身份證號、入住時間），外鍵是：申請?zhí)?、客房號、業(yè)務(wù)員。 【問題3】 根據(jù)試題中的描述，客房信息中客房號是唯一標(biāo)識客房關(guān)系的一個元

17、組，即可以作為唯一的主鍵。在客房關(guān)系模式中，不存在其他部分依賴關(guān)系，但客房號→類型→收費(fèi)標(biāo)準(zhǔn)，存在傳遞函數(shù)依賴，所以冗余，添加異常，修改異常，刪除異常均存在。 可以對客房關(guān)系進(jìn)行分解，具體如下： 客房1（客房號，客房類型，入住狀態(tài)）； 客房2（客房類型，收費(fèi)標(biāo)準(zhǔn)）。 【問題1】 本題主要考查對實(shí)體聯(lián)系圖的補(bǔ)充。 關(guān)于聯(lián)系可以根據(jù)題干描述查找。 由“每個部門可以有多名員工，每名員工只屬于一個部門；每個部門只有一名經(jīng)理，負(fù)責(zé)管理本部門”，可知部門與員工之間為1:n的聯(lián)系，部門與經(jīng)理之間，有1:1的聯(lián)系。 由“一位客戶可以有多個預(yù)訂申請，但一個預(yù)訂申請對應(yīng)唯一的一位客戶”，可以指客戶

18、與預(yù)訂申請有1:n的聯(lián)系。 由“一名業(yè)務(wù)員可以安排多個預(yù)訂申請，一個預(yù)訂申請只由一名業(yè)務(wù)員安排，而且可安排多間同類型的客房”，可知業(yè)務(wù)員、預(yù)訂申請、客房之間存在聯(lián)系，且預(yù)訂申請為多端，客房為多端，業(yè)務(wù)員為1端，故三者關(guān)系為1:n:m。 可以得到如下所示的完整實(shí)體聯(lián)系圖。 【問題2】 問題2要求補(bǔ)充關(guān)系模式，主要從題干描述查找遺漏的屬性，部分屬性需要參照實(shí)體間的聯(lián)系類型，看是否需要補(bǔ)充。 由“員工信息包括員工號、姓名、崗位、電話、工資”，可知員工屬性已給出，那么缺少的屬性應(yīng)該是根據(jù)聯(lián)系得出的，員工與部門為n:1的聯(lián)系，因此可以將二者的聯(lián)系歸并到員工實(shí)體，此時需要補(bǔ)充部門的主鍵，即a

19、填寫部門號。 由“客戶信息包括客戶號、單位名稱、聯(lián)系人、聯(lián)系電話、聯(lián)系地址”，可知客戶信息缺少屬性客戶號，單位名稱，客戶為聯(lián)系的1端，不能將聯(lián)系歸并進(jìn)去，此時b空應(yīng)該填寫的內(nèi)容是客戶號，單位名稱。 由“預(yù)訂申請信息包括申請?zhí)枴⒖蛻籼?、入住時間、入住天數(shù)、客房類型、客房數(shù)量”，可知預(yù)訂申請信息缺少申請?zhí)?，客戶號，對于預(yù)訂申請與客戶之間1:n的聯(lián)系，已通過客戶號表示，不需要再補(bǔ)充，因此c空填寫申請?zhí)枺蛻籼枴Ｓ擅枋觥耙粋€申請?zhí)栁ㄒ粯?biāo)識預(yù)訂申請中的一個元組”可知，預(yù)訂申請的主鍵為申請?zhí)枴６渲锌蛻籼柺强蛻粜畔⒌闹麈I，在預(yù)訂申請中是它的外鍵。 由“安排信息包括客房號、姓名、性別、身份證號、入住時

20、間、天數(shù)、電話”，可知安排信息缺少身份證號，入住時間。因此，d空填寫身份證號，時間。由描述“其中客房號、身份證號和入住時間唯一標(biāo)識一次安排”可知，安排信息的主鍵是客房號、身份證號、入住時間的組合鍵。在該關(guān)系模式中，客房號是客房關(guān)系的主鍵，申請?zhí)柺穷A(yù)訂申請關(guān)系的主鍵，業(yè)務(wù)員為該員工的員工號，為員工關(guān)系的主鍵，因此客房號、申請?zhí)?、員工號是該關(guān)系模式的外鍵。 【問題3】 根據(jù)試題中的描述，客房信息中客房號是唯一標(biāo)識客房關(guān)系的一個元組，即可以作為唯一的主鍵。在客房關(guān)系模式中，不存在其他部分依賴關(guān)系，但客房號→類型→收費(fèi)標(biāo)準(zhǔn)，存在傳遞函數(shù)依賴，所以冗余，添加異常，修改異常，刪除異常均存在。 可以對

21、客房關(guān)系進(jìn)行分解，具體如下： 客房1（客房號，客房類型，入住狀態(tài)）； 客房2（客房類型，收費(fèi)標(biāo)準(zhǔn)）。 4.某種出售罐裝飲料的自動售貨機(jī)（Vending Machine）的工作過程描述如下： （1）顧客選擇所需購買的飲料及數(shù)量。 （2）顧客從投幣口向自動售貨機(jī)中投入硬幣（該自動售貨機(jī)只接收硬幣）。硬幣器收集投入的硬幣并計算其對應(yīng)的價值。如果所投入的硬幣足夠購買所需數(shù)量的這種飲料且飲料數(shù)量足夠，則推出飲料，計算找零，顧客取走飲料和找回的硬幣；如果投入的硬幣不夠或者所選購的飲料數(shù)量不足，則提示用戶繼續(xù)投入硬幣或重新選擇飲料及數(shù)量。 （3）一次購買結(jié)束之后，將

22、硬幣器中的硬幣移走（清空硬幣器），等待下一次交易。自動售貨機(jī)還設(shè)有一個退幣按鈕，用于退還顧客所投入的硬幣。已經(jīng)成功購買飲料的錢是不會被退回的。 現(xiàn)采用面向?qū)ο蠓椒ǚ治龊驮O(shè)計該自動售貨機(jī)的軟件系統(tǒng)，得到如圖3-1所示的用例圖，其中，用例“購買飲料”的用例規(guī)約描述如下。 參與者：顧客。 主要事件流： 1．顧客選擇需要購買的飲料和數(shù)量，投入硬幣； 2．自動售貨機(jī)檢查顧客是否投入足夠的硬幣； 3．自動售貨機(jī)檢查飲料儲存?zhèn)}中所選購的飲料是否足夠； 4．自動售貨機(jī)推出飲料； 5．自動售貨機(jī)返回找零。 備選事件流： 2a．若投入的硬幣不足，則給出提示并退回到1； 3a．若所選購的飲

23、料數(shù)量不足，則給出提示并退回到1。 根據(jù)用例“購買飲料”得到自動售貨機(jī)的4個狀態(tài)：“空閑”狀態(tài)、“準(zhǔn)備服務(wù)”狀態(tài)、“可購買”狀態(tài)以及“飲料出售”狀態(tài)，對應(yīng)的狀態(tài)圖如圖3-2所示。 所設(shè)計的類圖如圖3-3所示。 【問題1】（6分） 根據(jù)說明中的描述，使用說明中的術(shù)語，給出圖3-2中的S1～S4所對應(yīng)的狀態(tài)名。 【問題2】（4分） 根據(jù)說明中的描述，使用說明中的術(shù)語，給出圖3-2中的E1～E4所對應(yīng)的事件名稱。 【問題3】（5分） 根據(jù)說明中的描述，使用說明中的術(shù)語，給出圖3-3中C1～C5所對應(yīng)的類名。 正確答案：

24、 本題解析： 【問題】 S1：空閑，S2：準(zhǔn)備服務(wù)，S3：飲料出售，S4：可購買。 【問題2】 E1：飲料數(shù)量不足，E2：選擇飲料【硬幣數(shù)量足夠】。 E3：飲料數(shù)量足夠/推出飲料，E4：取走飲料/返回找零并清空硬幣器。 【問題3】 C1：自動售貨機(jī)，C2：硬幣器，C3：飲料儲存?zhèn)}，C4：硬幣，C5：飲料。 【問題1】 本題問題1系統(tǒng)中的狀態(tài)圖，是對狀態(tài)轉(zhuǎn)換的圖形化表達(dá)。從題目的說明部分可知，在狀態(tài)轉(zhuǎn)換過程中，涉及到的狀態(tài)一共有四種：空閑、準(zhǔn)備服務(wù)、可購買、飲料出售。從狀態(tài)圖涉及的轉(zhuǎn)換可知S1~S4分別為：空閑、準(zhǔn)備服務(wù)、飲料出售、可購買。關(guān)于狀

25、態(tài)轉(zhuǎn)換的分析如下： （1）清空硬幣器后，自動售貨機(jī)等待下一次交易，進(jìn)入空閑狀態(tài)。此時可任意的進(jìn)行飲料選擇數(shù)量，一旦顧客投入硬幣，自動售貨機(jī)便進(jìn)入準(zhǔn)備服務(wù)狀態(tài)。 （2）當(dāng)自動售貨機(jī)進(jìn)行準(zhǔn)備服務(wù)狀態(tài)時，開始計算硬幣價值，如果硬幣不夠則提示顧客繼續(xù)投入硬幣。如果硬幣足夠，則進(jìn)入可購買狀態(tài)。 （3）進(jìn)行可購買狀態(tài)后，自動售貨機(jī)判斷飲料數(shù)量。如果數(shù)量不夠，則返回準(zhǔn)備服務(wù)狀態(tài)提示用戶重新選擇飲料。如果數(shù)量足夠，則推出飲料進(jìn)入飲料出售狀態(tài)。 （4）進(jìn)行飲料出售狀態(tài)后，自動售貨機(jī)計算找零，并返回進(jìn)入空閑狀態(tài)等待下一次交易。 【問題2】 本題問題2主要是分析四種狀態(tài)中的跳轉(zhuǎn)事件。根據(jù)狀態(tài)圖和試題主要

26、事件流的描述可以推出： E1：飲料數(shù)量不足 E2：選擇飲料【硬幣數(shù)量足夠】 E3：飲料數(shù)量足夠/推出飲料 E4：取走飲料/返回找零并清空硬幣器 【問題3】 本題問題3根據(jù)主要事件流的描述，可以推斷出C1~C5的類名分別對應(yīng)自動售貨機(jī)、硬幣器、飲料儲存?zhèn)}、硬幣、飲料。 5.某發(fā)票（lnvoice）由抬頭（Head）部分、正文部分和腳注（Foot）部分構(gòu)成?，F(xiàn)采用裝飾（Decorator）模式實(shí)現(xiàn)打印發(fā)票的功能，得到如圖6-1所示的類圖。 【java代碼】 class invoice{ public void printInvoice（　　）{

27、 System.out.println("This is the content of the invoice!"); } } class Decorator extends Invoice{ protected Invoice ticket; public Decorator(lnvoice t){ ticket=t; } public void printInvoice（　?。﹞ if(ticket!=null) （1）; } } class HeadDecorator extends Decorator{ public HeadDecorator(lnvoi

28、ce t){ super(t); } public void printInvoice（　?。﹞ Systent.out.println("This is the header of the invoice!"); （2）; } } class FootDecorator extends Decorator{ public FootDecorator(Invoice t){ super(t); } public void printlnvoice（　?。﹞ （3）; Systent.out.println("This is the footnote of the i

29、nvoice!"); } } Class test{ public static void main(String[]args){ Invoice t=new Invioce（　?。? Invoice ticket; ticket=（4）; ticket.printInvoice（　　）; Systent.out.println(“------------------“); ticket=（5）; ticket.printInvoice（　?。? } } 程序的輸出結(jié)果為： This is the header of the invoice! This is t

30、he content of the invoice! This is the footnote of the invoice! ---------------------------- This is the header of the invoice! This is the footnote of the invoice! 正確答案： 本題解析： （1）ticket.printInvoice() （2）super.printInvoice() （3）super.printInvoice(

31、) （4）new HeadDecorator(new FootDecorator(t)) （5）new HeadDecorator(new FootDecorator(null)) 本題考查的是面向?qū)ο蟪绦蛟O(shè)計和設(shè)計模式。本題涉及的設(shè)計模式是裝飾模式。 裝飾模式（Decorator）：動態(tài)地給一個對象添加一些額外的職責(zé)。它提供了用子類擴(kuò)展功能的一個靈活的替代，比派生一個子類更加靈活。 對于程序填空可以參照代碼上下文、題干說明和設(shè)計模式綜合考慮。 對于第（1）空，是對printInvoice方法的具體調(diào)用，在Decorator是裝飾類，繼承了Invoice發(fā)票類。此處需要填寫的是pr

32、intInvoice方法的方法體，根據(jù)Decorator類的上下文，已定義ticket對象，所以此處調(diào)用printInvoice方法的是ticket，第（1）空填寫ticket.printInvoice()。 對于第（2）（3）空，根據(jù)類圖可知，分別是HeadDecorator抬頭類、FootDecorator腳注類調(diào)用printInvoice方法的方法體，由于在這兩個類中并沒有定義屬性，只有借助其超類的構(gòu)造函數(shù)，所以這兩個地方調(diào)用printInvoice方法的是它們的超類，即（2）（3）填寫的是super.printInvoice()。 對于第（4）（5）空，考查的是對裝飾模式的調(diào)用，都

33、是main函數(shù)中實(shí)例化的過程，根據(jù)輸出結(jié)果可以看到，第（4）空實(shí)例化ticket對象，可以輸出抬頭、內(nèi)容、腳注3個部分，因此需要調(diào)用三者的printInvoice()方法，前面已經(jīng)實(shí)例化了一個Invoice對象t，可以利用t給子類實(shí)例化，因此第（4）空填寫new HeadDecorator(new FootDecorator(t))；而第（5）空沒有輸出具體內(nèi)容，只有抬頭和腳注部分，可以看到這里的Invoice對象應(yīng)該是空，所以第（5）空填寫new HeadDecorator(new FootDecorator(null))。 6.模式匹配是指給定主串t和子串s

34、，在主串t中尋找子串s的過程，其中s稱為模式。如果匹配成功，返回s在t中的位置，否則返回-1。 KMP算法用next數(shù)組對匹配過程進(jìn)行了優(yōu)化。KMP算法的偽代碼描述如下： 1．在串t和串s中，分別設(shè)比較的起始下標(biāo)i=j=0。 2．如果串t和串s都還有字符，則循環(huán)執(zhí)行下列操作： （1）如果j=-l或者t[i]=s[j]，則將i和j分別加1，繼續(xù)比較t和s的下一個字符； （2）否則，將j向右滑動到next[j]的位置，即j=next[j]。 3．如果s中所有字符均已比較完畢，則返回匹配的起始位置（從1開始）；否則返回-1。 其中，next數(shù)組根據(jù)子串s求解。求解next數(shù)組的代碼已由

35、get_next函數(shù)給出。 【C代碼】 （1）常量和變量說明 t，s：長度為lt和Is的字符串 next:next數(shù)組，長度為ls （2）C程序 #include＜stdio.h> #include＜stdlib.h> #include＜string.h> /*求next[]的值*/ void get_next(int*next,char*s,int ls){ int i=0，j=-1; next[0]=-1;/*初始化next[0]*/ while(i＜ls){/*還有字符*/ if(j==-1l ls[i]==s[j]){/*匹配*/ j++; i++;

36、if(s[i]==s[j]) next[i]=next[j]; else Next[i]=j; } else j=next[j]; } } int kmp(int*next,char*t,char*s,int lt,int Is) { Int i=0,j=0; while(i＜lt&&（1）){ if(j==-1||（2）){ i++; j++; }else （3）; } if(j>=ls) return（4）; else return-1; } 【問題1】（8分） 根據(jù)題干說明，填充C代碼中的空（1）～（4）. 【問題2】（2分） 根據(jù)題

37、干說明和C代碼，分析出kmp算法的時間復(fù)雜度為（5）（主串和子串的長度分別為lt和ls，用O符號表示）。 【問題3】（5分） 根據(jù)C代碼，字符串“BBABBCAC”的next數(shù)組元素值為（6）（直接寫素值，之間用逗號隔開）。若主串為“AABBCBBABBCACCD”，子串為“BBABBCAC”，則函數(shù)Kmp的返回值是（7）。 正確答案： 本題解析： 【問題1】 （1）：j＜ls; （2）：t[i]==s[j]; （3）：j=next[j]; （4）：i-ls+1或其等價形式; 【問題2】

38、 O(It+Is) 【問題3】 （6）：[-1,-1,1,-1,-1,2,0,0]，（7）6。 【問題1】 本題問題1根據(jù)KMP算法的偽代碼描述進(jìn)行推導(dǎo)。 根據(jù)偽代碼中第2步可以推導(dǎo)（1）是判斷字符串s是否還有字符，即j＜ls。i表示字符串t的下標(biāo)，j表示字符串s的下標(biāo)。 根據(jù)偽代碼第2.1步可以推導(dǎo)（2）是判斷字符串t和字符串s當(dāng)前位置的字符是否相同，即t[i]==s[j]。 根據(jù)偽代碼第2.2步可以推導(dǎo)（3）是當(dāng)?shù)?.1步判斷條件不滿足時，改變j所指向的字符位置。即j=next[j]。 根據(jù)偽代碼第3步可以推導(dǎo)（4）是返回匹配的起始位置。由于當(dāng)前i所指向字符串中匹配子串的最

39、后一個字符的位置，且已知子串的長度為ls。（4）的代碼為i-ls+1或其等價形式。 【問題2】 本題問題2是計算KMP算法的復(fù)雜度。算法的復(fù)雜度一般考慮最壞情況，那么在子串讀到ls及主串讀到It的時候是最壞情況。所以復(fù)雜度是O(It+Is) 【問題3】 本題問題3中已知字符串“BBABBCAC”，則根據(jù)get_next()函數(shù)可以求得next數(shù)組的元素值為[-1,-1,1,-1,-1,2,0,0]。并計算得到起始位置為6。 代入字符串“BBABBCAC”到get_next函數(shù)。 void get_next(int*next,char*s,int ls){ int i=0，j=-1

40、; next[0]=-1;/*初始化next[0]*/ while(i＜ls){/*還有字符*/ if(j==-1l ls[i]==s[j]){/*匹配*/ j++; i++; if(s[i]==s[j]) next[i]=next[j]; else Next[i]=j; } else j=next[j]; } } 這里涉及的只是代碼的代入分析過程，注意循環(huán)的處理即可。 下面將循環(huán)過程依次代入數(shù)值并且寫作順序處理過程如下： 傳參：s[]={B,B,A,B,B,C,A,C}，ls=8，next[]數(shù)組只聲明未取值。 初始化：i=0,j=-1,next[0]=-

41、1。 while(i＜ls)執(zhí)行后面的循環(huán)體，即當(dāng)i＜8時執(zhí)行循環(huán)。 （1）當(dāng)i=0,j=-1時： 判斷if(j==-1||s[0]==s[-1])，滿足條件1執(zhí)行下一步：i++=1,j++=0。 判斷if(s[1]==s[0])，滿足條件執(zhí)行下一步next[1]=next[0]=-1。 【此時i=1,j=0】 （2）當(dāng)i=1,j=0時： 判斷if(j==-1||s[1]==s[0])，滿足條件2執(zhí)行下一步：i++=2,j++=1。 判斷if(s[2]==s[1])，不滿足條件執(zhí)行else下一步next[2]=j=1。 【此時i=2,j=1】 （3）當(dāng)i=2,j=1時：

42、判斷if(j==-1||s[2]==s[1])，不滿足條件1和2執(zhí)行else下一步：j=next[1]=-1。 【此時i=2,j=-1】 （4）當(dāng)i=2,j=-1時： 判斷if(j==-1||s[2]==s[-1])，滿足條件1執(zhí)行下一步：i++=3,j++=0。 判斷if(s[3]==s[0])，滿足條件執(zhí)行下一步next[3]=next[0]=-1。 【此時i=3,j=0】 （5）當(dāng)i=3,j=0時： 判斷if(j==-1||s[3]==s[0])，滿足條件2執(zhí)行下一步：i++=4,j++=1。 判斷if(s[4]==s[1])，滿足條件執(zhí)行下一步next[4]=next[

43、1]=-1。 【此時i=4,j=1】 （6）當(dāng)i=4,j=1時： 判斷if(j==-1||s[4]==s[1])，滿足條件2執(zhí)行下一步：i++=5,j++=2。 判斷if(s[5]==s[2])，不滿足條件執(zhí)行else下一步next[5]=j=2。 【此時i=5,j=2】 （7）當(dāng)i=5,j=2時： 判斷if(j==-1||s[5]==s[2])，不滿足條件1和2執(zhí)行else下一步：j=next[2]=1。 【此時i=5,j=1】 （8）當(dāng)i=5,j=1時： 判斷if(j==-1||s[5]==s[1])，不滿足條件1和2執(zhí)行else下一步：j=next[1]=-1。 【

44、此時i=5,j=-1】 （9）當(dāng)i=5,j=-1時： 判斷if(j==-1||s[5]==s[-1])，滿足條件1執(zhí)行下一步：i++=6,j++=0。 判斷if(s[6]==s[0])，不滿足條件執(zhí)行else下一步next[6]=j=0。 【此時i=6,j=0】 （10）當(dāng)i=6,j=0時： 判斷if(j==-1||s[6]==s[0])，不滿足條件1和2執(zhí)行else下一步：j=next[0]=-1。 【此時i=6,j=-1】 （11）當(dāng)i=6,j=-1時： 判斷if(j==-1||s[6]==s[-1])，滿足條件1執(zhí)行下一步：i++=7,j++=0。 判斷if(s[7]==s[0])，不滿足條件執(zhí)行else下一步next[7]=j=0。 【此時i=7,j=0】 （12）當(dāng)i=7,j=0時： 判斷if(j==-1||s[7]==s[0])，不滿足條件1和2執(zhí)行else下一步：j=next[0]=-1。 【此時i=7,j=-1】 （13）當(dāng)i=7,j=-1時： 判斷if(j==-1||s[7]==s[0])，滿足條件1執(zhí)行下一步：i++=8，i=ls，退出while循環(huán)。 next[]數(shù)組下標(biāo)從0到7，結(jié)果分別為：[-1，-1，1，-1，-1，2，0，0]