2015年下半年（下午）《軟件設計師》真題

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

1、2015年下半年（下午）《軟件設計師》真題 注意：圖片可根據(jù)實際需要調(diào)整大小 卷面總分：6分 答題時間：240分鐘 試卷題量：6題 練習次數(shù)：0次 問答題 （共6題，共6分） 1.某大型購物中心欲開發(fā)一套收銀軟件，要求其能夠支持購物中心在不同時期推出的各種促銷活動，如打折、返利（例如，滿300返100）等等?，F(xiàn)采用策略（Strategy）模式實現(xiàn)該要求，得到如圖5-1所示的類圖。 圖5-1策略模式類圖 【C++代碼】 #include＜iostream> using namespace std

2、; enum TYPE{NORMAL,CASH_DISCOUNT,CASH_RETURN}; class CashSuper{ public: （1）; }; class CashNormal:public CashSuper{//正常收費子類 public: double acceptCash(double money){retum money;} }; class CashDiscount:public CashSuper{ private: double moneyDiscount;//折扣率 public: CashDiscount(double disco

3、unt){moneyDiscount=discount;} double acceptCash(double money){retum money*moneyDiscount;} }; class CashRetum:public CashSuper{//滿額返利 private: double moneyCondition;//滿額數(shù)額 double moneyReturn;//返利數(shù)額 public: CashRetnm(double motieyCondition,double moneyReturn){ this->moneyCondition=moneyCondit

4、ion; this->moneyReturn=moneyReturn; } double acceptCash(double money){ double result=money; if(money>=moneyCondition) result=money-(int)(money/moneyCondition)*moneyReturn; return?result; } }; class CashContext{ private: CashSuper*cs; public: CashContext(int type){ switch(type){ case

5、NORMAL://正常收費 （2）; break; case CASH_RETURN://滿300返100 （3）; break; case CASH_DISCOUNT://打八折 （4）; break; } } double GetResult(double money){ （5）; } }; //此處略去main（　?。┖瘮?shù) 正確答案： 本題解析： （1）virtual double acceptCash(double money)=0 （2）cs=new CashN

6、ormal() （3）cs=new CashReturn(300,100) （4）cs=new CashDiscount(0.8) （5）return cs->acceptCash(money) 本題考查策略（Strategy）模式的基本概念和應用。 Strategy模式的設計意圖是，定義一系列的算法，把它們一個個封裝起來，并且使它們可以相互替換。此模式使得算法可以獨立于使用它們的客戶而變化，其結構圖如下圖所示。 ?Strategy（策略）定義所有支持的算法的公共接口。Context使用這個接口來調(diào)用某ConcreteStrategy定義的算法。 ?ConcreteStrat

7、egy(具體策略)以Strategy接口實現(xiàn)某具體算法。 ?Context（上下文）用一個ConcreteStrategy對象來配置；維護一個對Strategy對象的引用；可定義一個接口來讓Strategy訪問它的數(shù)據(jù)。 Strategy模式適用于： ?許多相關的類僅僅是行為有異?！安呗浴碧峁┝艘环N用多個行為中的一個行為來配置一個類的方法。 ?需要使用一個算法的不同變體。例如，定義一些反應不同空間的空間/時間權衡的算法。當這些變體實現(xiàn)為一個算法的類層次時，可以使用策略模式。 ?算法使用客戶不應該知道的數(shù)據(jù)?？墒褂貌呗阅Ｊ揭员苊獗┞稄碗s的、與算法相關的數(shù)據(jù)結構。 一個類定義了多種行為

8、，并且這些行為在這個類的操作中以多個條件語旬的形式出現(xiàn)，將相關的條件分支移入它們各自的Strategy類中，以代替這些條件語句。 本題中類CashSuper對應于上圖中的類Strategy，類CashNormal、CashDiscout和CashReturn分別代表3種不同的具體促銷策略。CashSuper類提供其3個子類的公共操作接口，由子類給出3種不同促銷策略的具體實現(xiàn)。在C++語言中，可以采用繼承+（純）虛擬函數(shù)來實現(xiàn)。從3個子類CashNormal、CashDiscout和CashReturn的代碼可以看出，公共操作接口為double acceptCash(double money)

9、。由于不需要父類CashSuper提供任何的促銷實現(xiàn)方式，所以這里采用純虛擬函數(shù)。應填入空（1）處的語句是"virtual double acceptCash(double money)=0"。 空（2）-（4）都出現(xiàn)在類CashContext中，該類對應于上圖中的類Context，其作用是依據(jù)策略對象來調(diào)用不同的策略算法。因此空（2）-（4）的是根據(jù)不同的case分支來創(chuàng)建不同的策略對象。由此可知空（2）-（4）分別應填入"cs=newCashNormal()"、"cs=new CashReturn(300，100)"和"cs=new CashDiscount(0.8)"。 方法GetR

10、esult是對接口的調(diào)用，從而計算出來用不同促銷策略之后應付的費用，這里需要通過CashSuper的對象cs來調(diào)用公共操作接口，因此第（5）空應填入"return cs->acceptCash(money)"。 2.某慕課教育平臺欲添加在線作業(yè)批改系統(tǒng)，以實現(xiàn)高效的作業(yè)提交與批改，并進行統(tǒng)計。學生和講師的基本信息已經(jīng)初始化為數(shù)據(jù)庫中的學生表和講師表。系統(tǒng)的主要功能如下： （1）提交作業(yè)。驗證學生標識后，學生將電子作業(yè)通過在線的方式提交，并進行存儲。系統(tǒng)給學生發(fā)送通知表明提交成功，通知中包含唯一編號；并通知講師有作業(yè)提交。 （2）下載未批改作業(yè)。驗證講師標識后

11、，講師從系統(tǒng)中下載學生提交的作業(yè)。下載的作業(yè)將顯示在屏幕上。 （3）批改作業(yè)。講師按格式為每個題目進行批改打分，并進行整體評價。 （4）上傳批改后的作業(yè)。將批改后的作業(yè)（包括分數(shù)和評價）返回給系統(tǒng)，進行存儲。 （5）記錄分數(shù)和評價。將批改后的作業(yè)的分數(shù)和評價記錄在學生信息中，并通知學生作業(yè)已批改。 （6）獲取已批改作業(yè)。根據(jù)學生標識，給學生查看批改后的作業(yè)，包括提交的作業(yè)、分數(shù)和評價。 （7）作業(yè)抽檢。根據(jù)教務人員標識抽取批改后的作業(yè)樣本，給出抽檢意見，然后形成抽檢報告給講師。 現(xiàn)采用結構化方法對在線作業(yè)批改系統(tǒng)進行分析與設計，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層

12、數(shù)據(jù)流圖。 圖1-1上下文數(shù)據(jù)流圖 圖1-2 0層數(shù)據(jù)流圖 【問題1】（3分） 使用說明中的詞語，給出圖1-1中的實體E1～E3的名稱。 【問題2】（4分） 使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲D1～D4的名稱。 【問題3】（6分） 根據(jù)說明和圖中術語，補充圖1-2中缺失的數(shù)據(jù)流及其起點和終點。 【問題4】（2分） 若發(fā)送給學生和講師的通知是通過第三方Email系統(tǒng)進行的，則需要對圖1-1和圖1-2進行哪些修改？用100字以內(nèi)文字加以說明。 正確答案： 本題解析： 【問題

13、1】 E1：學生E2：講師E3：教務人員 【問題2】 D1：提交的作業(yè)表D2：學生表D3：講師表D4：批改后的作業(yè)表 【問題3】 【問題4】 增加外部實體“第三方Email系統(tǒng)”，將原來的兩條“通知”數(shù)據(jù)流合并為一條“通知”數(shù)據(jù)流，終點為“第三方Email系統(tǒng)”。 【問題1】 要求識別E1-E3具體為哪個外部實體，通讀試題說明，可以了解到適合充當外部實體的包括：學生、講師、教務人員。具體的對應關系，可以通過將頂層圖與題目說明進行匹配得知。如：從圖中可看出E1會向系統(tǒng)發(fā)出數(shù)據(jù)流“作業(yè)、學生標識”，會從系統(tǒng)接收到“批改后的作業(yè)、通知”；而從試題說明“驗證學生標識后，學生將電子

14、作業(yè)通過在線的方式提交，并進行存儲。系統(tǒng)給學生發(fā)送通知表明提交成功，通知中包含唯一編號”可以看出，E1對應的，便是學生。E2、E3同理可得。 【問題2】 要求識別存儲，解決這類問題，以圖的分析為主，配合說明給存儲命名，因為存儲相關的數(shù)據(jù)流一般展現(xiàn)了這個存儲中到底存了些什么信息，如從圖中可以看到D3中有講師信息，而D2中有學生信息，題目說明中又有“學生和講師的基本信息已經(jīng)初始化為數(shù)據(jù)庫中的學生表和講師表?！弊匀籇2應為學生表，D3應為講師表。同理，D1應存儲了學生的作業(yè)、D4存儲了批改后的作業(yè)，由于這兩個內(nèi)容在說明中沒有“**表”“**文件”的表達，所以該存儲的命名直接從說明中取合適的詞來總

15、結，D1應為作業(yè)，D4應為批改后的作業(yè)。 【問題3】 缺失數(shù)據(jù)流1 名稱：通知起點：提交作業(yè)終點：E1 理由：頂層圖有從在線作業(yè)批改系統(tǒng)到E1的數(shù)據(jù)流“通知”，而0層圖沒有，依據(jù)平衡原則可知缺失了，進一步分析試題說明，了解到“提交作業(yè)”這個功能有操作“系統(tǒng)給學生發(fā)送通知表明提交成功”，所以缺失數(shù)據(jù)流的起點為“提交作業(yè)”。 缺失數(shù)據(jù)流2 名稱：抽檢報告起點：作業(yè)抽檢終點：E2 理由：題目說明中，對于“作業(yè)抽檢”的描述為“根據(jù)教務人員標識抽取批改后的作業(yè)樣本，給出抽檢意見，然后形成抽檢報告給講師?！睋?jù)此可以了解到從該功能應有數(shù)據(jù)流“抽檢報告”至E2。 缺失數(shù)據(jù)流3 名稱：分數(shù)和評

16、價起點：記錄分數(shù)和評價終點：D2 理由：首先值得注意的是“記錄分數(shù)和評價”只有輸入，沒有輸出，這是破壞了數(shù)據(jù)平衡原則的。這種情況，必然是有缺失數(shù)據(jù)流的。從題目描述“將批改后的作業(yè)的分數(shù)和評價記錄在學生信息中”可以了解到，應有數(shù)據(jù)流從“記錄分數(shù)和評價”到D2。 缺失數(shù)據(jù)流4 名稱：通知起點：記錄分數(shù)和評價終點：E1 理由：從題目描述“并通知學生作業(yè)已批改”可以了解到，應有數(shù)據(jù)流從“記錄分數(shù)和評價”到E1。 【問題4】 強調(diào)發(fā)送郵件采用了“第三方Email系統(tǒng)”，這個“第三方Email系統(tǒng)”屬于典型的外部實體，所以需要增加外部實體“第三方Email系統(tǒng)”，并將原來的兩條“通知”數(shù)據(jù)流合

17、并為一條“通知”數(shù)據(jù)流，終點為“第三方Email系統(tǒng)”。 3.某企業(yè)擬構建一個高效、低成本、符合企業(yè)實際發(fā)展需要的辦公自動化系統(tǒng)。工程師小李主要承擔該系統(tǒng)的公告管理和消息管理模塊的研發(fā)工作。公告管理模塊的主要功能包括添加、修改、刪除和查看公告。消息管理模塊的主要功能是消息群發(fā)。 小李根據(jù)前期調(diào)研和需求分析進行了概念模型設計，具體情況分述如下： 【需求分析結果】 （1）該企業(yè)設有研發(fā)部、財務部、銷售部等多個部門，每個部門只有一名部門經(jīng)理，有多名員工，每名員工只屬于一個部門，部門信息包括：部門號、名稱、部門經(jīng)理和電話，其中部門號唯一確定部門關系的每一個元組。

18、 （2）員工信息包括：員工號、姓名、崗位、電話和密碼。員工號唯一確定員工關系的每一個元組；崗位主要有經(jīng)理、部門經(jīng)理、管理員等，不同崗位具有不同的權限。一名員工只對應一個崗位，但一個崗位可對應多名員工。 （3）消息信息包括：編號、內(nèi)容、消息類型、接收人、接收時間、發(fā)送時間和發(fā)送人。其中（編號，接收人）唯一標識消息關系中的每一個元組。一條消息可以發(fā)送給多個接收人，一個接收人可以接收多條消息。 （4）公告信息包括：編號、標題、名稱、內(nèi)容、發(fā)布部門、發(fā)布時間。其中編號唯一確定公告關系的每一個元組。一份公告對應一個發(fā)布部門，但一個部門可以發(fā)布多份公告；一份公告可以被多名員工閱讀，一名員工可以閱讀多份

19、公告。 【概念模型設計】 根據(jù)需求分析階段收集的信息，設計的實體聯(lián)系圖（不完整）如圖2-1所示： 圖2-1實體聯(lián)系圖 【邏輯結構設計】 根據(jù)概念模型設計階段完成的實體聯(lián)系圖，得出如下關系模式（不完整）： 部門（（a），部門經(jīng)理，電話） 員工（員工號，姓名，崗位號，部門號，電話，密碼） 崗位（崗位號，名稱，權限） 消息（（b），消息類型，接收時間，發(fā)送時間，發(fā)送人） 公告（（c），名稱，內(nèi)容，發(fā)布部門，發(fā)布時間） 閱讀公告（（d），閱讀時間） 【問題1】（5分） 根據(jù)問題描述，補充四個聯(lián)系，完善圖2-1所示的實體聯(lián)系圖。聯(lián)系名可用聯(lián)系1、聯(lián)系2、聯(lián)系3和聯(lián)系4代替，

20、聯(lián)系的類型分為1:1、1:n和m:n（或1:1、1:*和*:*）。 【問題2】（8分） （1）根據(jù)實體聯(lián)系圖，將關系模式中的空（a）～（d）補充完整。 （2）給出“消息”和“閱讀公告”關系模式的主鍵與外鍵。 【問題3】（2分） 消息和公告關系中都有“編號”屬性，請問它是屬于命名沖突嗎？用100字以內(nèi)文字說明原因。 正確答案： 本題解析： 【問題1】 【問題2】 （a）部門號，名稱 （b）編號，內(nèi)容，接收人 （c）編號，標題 （d）員工號，公告編號 消息主鍵：（編號，接收人）外鍵

21、：接收人，發(fā)送人 閱讀公告主鍵：（員工號，公告編號）外鍵：員工號，公告編號 【問題3】 不屬于命名沖突。 命名沖突是在合并ER模型時提出的概念，合并ER模型時之所以產(chǎn)生沖突，是因為對于同樣的對象，不同的局部ER模型有著不同的定義，在本題中，本就是不同對象的屬性，所以不存在沖突的說法。 【問題1】 根據(jù)題干中的需求分析可以得到完整的ER圖和聯(lián)系類型。 “一名員工只對應一個崗位，但一個崗位可對應多名員工”，可以得出員工與崗位間是有一個“對應”的聯(lián)系的，而且聯(lián)系類型是n:1。 “一條消息可以發(fā)送給多個接收人，一個接收人可以接收多條消息”，可以得出消息與發(fā)送人和接收人有多對多的聯(lián)系，而

22、在題干描述中可以看到發(fā)送人和接收人都是員工，因此，可以得到如圖所示的消息收發(fā)關系。 “一份公告對應一個發(fā)布部門，但一個部門可以發(fā)布多份公告”，可以看到公告與部門有多對1的發(fā)布聯(lián)系。 “一份公告可以被多名員工閱讀，一名員工可以閱讀多份公告”，可以看到公告與員工之間有多對多的閱讀聯(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】 （1）根據(jù)題干中列出的內(nèi)容，可以把關系模式填完整。 “部門信息包括：部門號、名稱、部門經(jīng)理和電話”，因此（a）缺少部門號，名稱。 “消息信息包括：編號、內(nèi)容、消息類型、接收人

23、、接收時間、發(fā)送時間和發(fā)送人”，因此（b）缺少編號，內(nèi)容。 “公告信息包括：編號、標題、名稱、內(nèi)容、發(fā)布部門、發(fā)布時間”，因此（c）缺少編號，標題。 對于閱讀公告，是員工與公告二者的聯(lián)系，并且是多對多的聯(lián)系，因此除了自身屬性外，還需要補充員工和公告的主鍵，因此（d）缺少員工號，公告編號。 （2）消息（編號，內(nèi)容，消息類型，接收人，接收時間，發(fā)送時間，發(fā)送人），“其中（編號，接收入）唯一標識消息關系中的每一個元組”可知，其主鍵為編號和接收人；而接收人和發(fā)送人都需要員工號，所以為外鍵。 閱讀公告（公告編號，員工號，閱讀時間）也是同樣的道理。 【問題3】 命名沖突是在合并ER模型時提出的

24、概念，合并ER模型時之所以產(chǎn)生沖突，是因為對于同樣的對象，不同的局部ER模型有著不同的定義，在本題中，本就是不同對象的屬性，所以不存在沖突的說法。 4.某出版社擬開發(fā)一個在線銷售各種學術出版物的網(wǎng)上商店（ACShop），其主要的功能需求描述如下： （1）ACShop在線銷售的學術出版物包括論文、學術報告或講座資料等。 （2）ACShop的客戶分為兩種：未注冊客戶和注冊客戶。 （3）未注冊客戶可以瀏覽或檢索出版物，將出版物添加到購物車中。未注冊客戶進行注冊操作之后，成為ACShop注冊客戶。 （4）注冊客戶登錄之后，可將待購買的出版物添加到購物車中，并進行

25、結賬操作。結賬操作的具體流程描述如下： ①從預先填寫的地址列表中選擇一個作為本次交易的收貨地址。如果沒有地址信息，則可以添加新地址。 ②選擇付款方式。ACShop支持信用卡付款和銀行轉賬兩種方式。注冊客戶可以從預先填寫的信用卡或銀行賬號中選擇一個付款。若沒有付款方式信息，則可以添加新付款方式。 ③確認提交購物車中待購買的出版物后，ACShop會自動生成與之相對應的訂單。 （5）管理員負責維護在線銷售的出版物目錄，包括添加新出版物或者更新在售出版物信息等操作。 現(xiàn)采用面向對象方法分析并設計該網(wǎng)上商店ACShop，得到如圖3-1所示的用例圖和圖3-2所示的類圖。 圖3-1用例圖

26、 圖3-2類圖 【問題1】（4分） 根據(jù)說明中的描述，給出圖3-1中（1）～（4）所對應的用例名。 【問題2】（4分） 根據(jù)說明中的描述，分別說明用例“添加新地址”和“添加新付款方式”會在何種情況下由圖3-1中的用例（3）和（4）擴展而來？ 【問題3】（7分） 根據(jù)說明中的描述，給出圖3-2中（1）～（7）所對應的類名。 正確答案： 本題解析： 【問題1】 （1）添加出版物到購物車 （2）結賬 （3）選擇收貨地址 （4）選擇付款方式 【問題2】 當選擇收貨地址時，沒有地址信息，

27、則使用擴展用例“添加新地址”來完成新地址的添加。 當選擇付款方式時，沒有付款方式信息，則使用擴展用例“添加新付款方式”來完成新付款方式的添加。 【問題3】 （1）出版物目錄 （2）待購買的出版物 （3）學術出版物 （4）-（6）論文、學術報告、講座資料 （7）訂單 本題屬于軟件設計師關于UML的傳統(tǒng)考題，主要考查的是用例圖和類圖。 【問題1】 問題1是對用例圖的補充。對于用例是對系統(tǒng)業(yè)務功能的描述，一般為動詞+名詞或名詞+動詞的形式，解題一般從題干說明中分析其中的用例，并且參考用例圖中用例之間的關系來確定對應的用例名。 其中（3）和（4）分別于添加新付款方式和添加新地址有

28、擴展關系，因此對應的（3）應該是選擇收貨地址（從描述“①從預先填寫的地址列表中選擇一個作為本次交易的收貨地址”提煉），（4）應該是選擇付款方式（“②選擇付款方式”）。 其中（2）包含用例（1）和用例（3）選擇收貨地址、用例（4）選擇付款方式，根據(jù)“結賬操作的具體流程描述如下：①②…”，因此用例（2）是結賬。 其中用例（1）于參與者客戶、注冊客戶都相關，即未注冊客戶也可以做的操作，應該包括瀏覽或檢索出版物、將出版物添加到購物車中，前者已經(jīng)列出，因此用例（1）為將出版物添加到購物車。 【問題2】 問題2涉及到的是擴展關系運作機制，在擴展關系中，一個用例稱為基礎用例，另一個用例稱為擴展用例，

29、其中擴展用例是對基礎用例的補充，擴展用例不是每次都執(zhí)行，要特定條件滿足才執(zhí)行。 以本題中用例“添加新地址”為例，他就是一個擴展用例，什么時候他會執(zhí)行呢？就是當選擇收貨地址時，系統(tǒng)檢測發(fā)現(xiàn)沒有地址信息，此時會“添加新地址”來完成新地址的添加，然后再先擇收貨地址。添加新付款方式用例情況與此類似。 【問題3】 問題3是對類圖的補充，類名一般為名詞形式，根據(jù)題干描述，我們可以找到很多類名，包括：ACShop、學術出版物、論文、學術報告、講座資料、客戶、未注冊客戶、注冊客戶、待購買的出版物、購物車、地址列表、收貨地址、付款方式、信用卡付款、銀行轉賬、訂單、管理員、出版物目錄等，再根據(jù)類圖當中的關系

30、來確定對應的類名。 根據(jù)“（1）ACShop在線銷售的學術出版物包括論文、學術報告或講座資料等”，可以看到這里的學術出版物是論文、學術報告、講座資料的泛化，也就是父類，根據(jù)類圖可以看到，類（3）和類（4）、（5）、（6）滿足此關系，因此類（3）是學術出版物，而（4）（5）（6）分別為論文、學術報告、講座資料，三者位置可以互換。 類（7）與付款方式和收貨地址相關的應該是訂單，而（2）與訂單和購物車都有著部分-整體關系的，應該是待購買的出版物。 根據(jù)ACShop是網(wǎng)上商店，它應該包括管理員、客戶、購物車，還有出售的物品，而本商店出售的物品是以出版物目錄的形式進行管理，因此（1）應該是出版物目

31、錄。 5.某大型購物中心欲開發(fā)一套收銀軟件，要求其能夠支持購物中心在不同時期推出的各種促銷活動，如打折、返利（例如，滿300返100）等等。現(xiàn)采用策略（Strategy）模式實現(xiàn)該要求，得到如圖6-1所示的類圖。 圖6-1策略模式類圖 【Java代碼】 import java.util.*; enum TYPE{NORMAL,CASH_DISCOUNT,CASH_RETURN}; interface CashSuper{ public（1）; } class CashNormal implements CashSuper{//正常收費子類

32、public double acceptCash(double money){ return money; } } class CashDiscount implements CashSuper{ private double moneyDiscount;//折扣率 public CashDiscount(double moneyDiscount){ this moneyDiscount=moneyDiscount; } public double acceptCash(double money){ return money*moneyDiscount; } } cl

33、ass CashReturn implements CashSuper{//滿額返利 private double moneyCondition; private double moneyReturn; public CashReturn(double moneyCondition,double moneyReturn){ this.moneyCondition=moneyCondition;//滿額數(shù)額 this.moneyReturn=moneyReturn;//返利數(shù)額 } public double acceptCash(double money){ double re

34、sult=money; if(money>=moneyCondition) result=money-Math.floor(money/moneyCondition)*moneyReturn; return result; } } class CashContext_{ private CashSuper cs; private TYPE?t； public CashContext(TYPE t){ switch(t){ case NORMAL：//正常收費 （2）; break; case CASH_DISCOUNT://打8折 （3）; break; ca

35、se CASH_RETURN://滿300返100 （4）; break; } } public double GetResult(double money){ （5）; } //此處略去main（　?。┖瘮?shù) } 正確答案： 本題解析： （1）double acceptCash(double money) （2）cs=new CashNormal() （3）cs=new CashDiscount(0.8) （4）cs=new CashReturn(300,100) （5）ret

36、urn cs.acceptCash(money) 本題考查策略（Strategy）模式的基本概念和應用。 Strategy模式的設計意圖是，定義一系列的算法，把它們一個個封裝起來，并且使它們可以相互替換。此模式使得算法可以獨立于使用它們的客戶而變化，其結構圖如下圖所示。 ?Strategy(策略)定義所有支持的算法的公共接口。Context使用這個接口來調(diào)用某ConcreteStrategy定義的算法。 ?ConcreteStrategy(具體策略)以Strategy接口實現(xiàn)某具體算法。 ?Context（上下文）用一個ConcreteStrategy對象來配置；維護一個對Str

37、ategy對象的引用；可定義一個接口來讓Strategy訪問它的數(shù)據(jù)。 Strategy模式適用于： ?許多相關的類僅僅是行為有異。“策略”提供了一種用多個行為中的一個行為來配置一個類的方法。 ?需要使用一個算法的不同變體。例如，定義一些反應不同空間的空間/時間權衡的算法。當這些變體實現(xiàn)為一個算法的類層次時，可以使用策略模式。 ?算法使用客戶不應該知道的數(shù)據(jù)?？墒褂貌呗阅Ｊ揭员苊獗┞稄碗s的、與算法相關的數(shù)據(jù)結構。 一個類定義了多種行為，并且這些行為在這個類的操作中以多個條件語旬的形式出現(xiàn)，將相關的條件分支移入它們各自的Strategy類中，以代替這些條件語句。 本題中類CashSu

38、per對應于上圖中的類Strategy，類CashNormal、CashDiscout和CashReturn分別代表3種不同的具體促銷策略。CashSuper是父類接口，提供其3個子類的公共操作接口，由子類給出3種不同促銷策略的具體實現(xiàn)。從3個子類CashNormal、CashDiscout和CashReturn的代碼可以看出，公共操作方法為double acceptCash(double money)。由于不需要父類CashSuper提供任何的促銷實現(xiàn)方式，在接口CashSuper中double acceptCash(double money)方式是沒有具體實現(xiàn)內(nèi)容的。應填入空（1）處的語句

39、是"double acceptCash(double money)"。 空（2）-（4）都出現(xiàn)在類CashContext中，該類對應于上圖中的類Context，其作用是依據(jù)策略對象來調(diào)用不同的策略算法。因此空（2）-（4）的是根據(jù)不同的case分支來創(chuàng)建不同的策略對象。由此可知空（2）-（4）分別應填入"cs=newCashNormal()"、"cs=new CashDiscount(0.8)"和"cs=new CashReturn(300，100)"。 方法GetResult是對接口的調(diào)用，從而計算出來用不同促銷策略之后應付的費用，這里需要通過CashSuper的對象cs來調(diào)用公共操作接

40、口，因此第（5）空應填入"return cs.acceptCash(money)"。 6.計算兩個字符串x和y的最長公共子串（Longest Common Substring）。 假設字符串x和字符串y的長度分別為m和n，用數(shù)組c的元素c[i][j]記錄x中前i個字符和y中前j個字符的最長公共子串的長度。 c[i][j]滿足最優(yōu)子結構，其遞歸定義為： 計算所有c[i][j](0≤i≤m，0≤j≤n)的值，值最大的c[i][j]即為字符串x和y的最長公共子串的長度。根據(jù)該長度即i和j，確定一個最長公共子串。 【C代碼】 （1）常量和變量說明 x，y

41、：長度分別為m和n的字符串 c[i][j]：記錄x中前i個字符和y中前j個字符的最長公共子串的長度 max：x和y的最長公共子串的長度 maxi,maXj：分別表示x和y的某個最長公共子串的最后一個字符在x和y中的位置（序號） （2）C程序 #include＜stdio.h> #include＜string.h> int c[50][50]; int maxi; int maxj; int lcs(char*x,int m,char*y,int n){ int i,j; int max=0; maxi=0; maxj=0; for(i=0;i＜=m;i++)c[i

42、][0]=0; for(i=1;i＜=n;i++)c[0][i]=0; for(i=1;i＜=m;i++){ for(j=1;j＜=n;j++){ if((1)){ c[i][j]=c[i-1][j-1]+1; if(max＜c[i][j]){ (2); maxi=i; maxj=j; } } else(3); } } return max; } void printLCS(int max,char*x){ int i=0; if(max==0)return; for((4);i＜maxi;i++) printf("%c",x[i]); } voi

43、d main（　?。﹞ char*x="ABCADAB"; char*y="BDCABA"; int max=0; int m=strlen(x); int n=strlen(y); max=lcs(x,m,y,n); printLCS(max,x); } 【問題1】（8分） 根據(jù)以上說明和C代碼，填充C代碼中的空（1）～（4）。 【問題2】（4分） 根據(jù)題干說明和以上C代碼，算法采用了（5）設計策略。 分析時間復雜度為（6）（用O符號表示）。 【問題3】（3分） 根據(jù)題干說明和以上C代碼，輸入字符串x="ABCADAB'，'y="BDCABA"，則輸出為（7）。

44、 正確答案： 本題解析： 【問題1】 （1）x[i-1]==y[j-1] （2）max=c[i][j] （3）c[i][j]=0 （4）i=maxi-max 【問題2】 （5）動態(tài)規(guī)劃法 （6）O(m*n) 【問題3】 （7）AB 首先對于C語言算法題，一般的解題思路是先解決除程序填空以外的問題，這些問題弄清楚，有利于程序填空部分的分析。 第一步，分析程序所采用的算法，常見的算法包括：分治法、動態(tài)規(guī)劃法、回溯法、貪心法。本題中要求的是兩個串的最長公共子串，在程序中采用了數(shù)組來記錄子

45、問題的中間結果，這一特征與動態(tài)規(guī)劃法的做法非常吻合，所以應選動態(tài)規(guī)劃法。 第二步，解決“輸入字符串x="ABCADAB’，'y="BDCABA"，則輸出為（7）”的問題，該問題相對容易解決，因為題目已告知程序的作用是求最長公共子串，而且從程序的輸出函數(shù)可以看出，要輸出的，只有子串，沒有其他信息，所以我們只需要手動求兩個串的公共子串，并寫出答案即可。兩個串第一個公共子串明顯是“AB”，所以輸出的結果為“AB”。 第三步，求時間復雜度，由于程序中最多雙重循環(huán)，其中外層循環(huán)的規(guī)模為m，而內(nèi)層循環(huán)的規(guī)模為n，所以時間復雜度為O(m*n)。 第四步，也是最難的一步，是解決程序填空的問題。動態(tài)規(guī)劃的

46、問題，一般都會給出遞歸定義式，這個式子，往往是多個空的關鍵點。以本題為例： 第1空是判斷的條件，輸出的結果是c[i][j]=c[i-1][j-1]+1，此時根據(jù)遞歸式可以看到，所需的條件是x[i-1]=y[j-1]，因此第1空填寫判斷條件x[i-1]==y[j-1]。 第2空是在if(max＜c[i][j])跟隨的大括號中，根據(jù)前后代碼和此處的判斷條件，當max小于當前時，應該改變max的值，并記錄此時的maxi和maxj，此處缺少改變max的值，因此，第2空應該將當前最大值賦值給max，即max=c[i][j]。 第3空是第一個if語句的else選擇，根據(jù)遞歸式，if（x[i-1]==y[j-1]）不滿足時，屬于其他情況，應該賦值為0，因此第3空填寫c[i][j]=0。 而第4空是用于打印結果，由于maxi記錄了子串末尾+1的位置信息，子串長度為max，所以用maxi-max定位至子串開始位置，以便打印子串，因此第4空填寫i=maxi-max。