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

1、2009年下半年（下午）《軟件設(shè)計(jì)師》真題 注意：圖片可根據(jù)實(shí)際需要調(diào)整大小 卷面總分：6分 答題時(shí)間：240分鐘 試卷題量：6題 練習(xí)次數(shù)：1次 問(wèn)答題 （共6題，共6分） 1.某企業(yè)為了方便員工用餐，餐廳開(kāi)發(fā)了一個(gè)訂餐系統(tǒng)（COS：Cafeteria?Ordering?System），企業(yè)員工可通過(guò)企業(yè)內(nèi)聯(lián)網(wǎng)使用該系統(tǒng)。 企業(yè)的任何員工都可以查看菜單和今日特價(jià)。 系統(tǒng)的顧客是注冊(cè)到系統(tǒng)的員工，可以訂餐（如果未登錄，需先登錄）、注冊(cè)工資支付、預(yù)約規(guī)律的訂餐，在特殊情況下可以覆蓋預(yù)訂。 餐廳員工是特

2、殊顧客，可以進(jìn)行備餐、生成付費(fèi)請(qǐng)求和請(qǐng)求送餐，其中對(duì)于注冊(cè)工資支付的顧客生成付費(fèi)請(qǐng)求并發(fā)送給工資系統(tǒng)。 菜單管理員是餐廳特定員工，可以管理菜單。 送餐員可以打印送餐說(shuō)明，記錄送餐信息（如送餐時(shí)間）以及記錄收費(fèi)（對(duì)于沒(méi)有注冊(cè)工資支付的顧客，由送餐員收取現(xiàn)金后記錄）。 顧客訂餐過(guò)程如下： 1．顧客請(qǐng)求查看菜單； 2．系統(tǒng)顯示菜單和今日特價(jià)； 3．顧客選菜； 4．系統(tǒng)顯示訂單和價(jià)格； 5．顧客確認(rèn)訂單； 6．系統(tǒng)顯示可送餐時(shí)間； 7．顧客指定送餐時(shí)間、地點(diǎn)和支付方式； 8．系統(tǒng)確認(rèn)接受訂單，然后發(fā)送Email給顧客以確認(rèn)訂餐，同時(shí)發(fā)送相關(guān)訂餐信息通知給餐廳員工。 系統(tǒng)采用面向

3、對(duì)象方法開(kāi)發(fā)，使用UML進(jìn)行建模。系統(tǒng)的頂層用例圖和一次訂餐的活動(dòng)圖初稿分別如圖3-1和圖3-2所示。 圖3-1?COS系統(tǒng)頂層用例圖 圖3-2一次訂餐的活動(dòng)圖 【問(wèn)題1】（2分） 根據(jù)中的描述，給出圖3-1中A1和A2所對(duì)應(yīng)的參與者。 【問(wèn)題2】（8分） 根據(jù)中的描述，給出圖3-1中缺少的四個(gè)用例及其所對(duì)應(yīng)的參與者。 【問(wèn)題3】（4分） 根據(jù)中的描述，給出圖3-2中（1）~（4）處對(duì)應(yīng)的活動(dòng)名稱(chēng)或圖形符號(hào)。 【問(wèn)題4】（1分） 指出圖3-1中員工和顧客之間是什么關(guān)系，并解釋該關(guān)系的內(nèi)涵。 圖3-1?COS系統(tǒng)頂層用例圖 圖3-2一次訂餐的活動(dòng)圖

4、 正確答案： 本題解析： 【問(wèn)題1】（2分，各1分） A1：工資系統(tǒng)A2：菜單管理員 【問(wèn)題2】（8分，每行2分） （注：四行順序可以不同，但是每行必須對(duì)應(yīng)，其中，用例名稱(chēng)及其對(duì)應(yīng)的參與者都正確給2分，只有用例名正確給1分，其余情況不得分） 【問(wèn)題3】（4分，各1分） 【問(wèn)題4】（1分） 泛化關(guān)系（一般/特殊關(guān)系、繼承關(guān)系）。泛化關(guān)系描述了一個(gè)參與者可以完成另一個(gè)參與者同樣的任務(wù)，并可補(bǔ)充額外的角色功能。 本題考查面向?qū)ο笙到y(tǒng)開(kāi)發(fā)時(shí)，采用UML模型進(jìn)行建模的方法。 此類(lèi)題目要求考生認(rèn)真閱

5、讀題目說(shuō)明中對(duì)現(xiàn)實(shí)問(wèn)題的描述，使用UML建模時(shí)的原則，從中確定用例圖、活動(dòng)圖以及圖中的各種關(guān)系。題目給出了未完成的用例圖和活動(dòng)圖，需要根據(jù)描述給出參與者、用例、活動(dòng)圖中的活動(dòng)和符號(hào)，以及參與者之間的關(guān)系內(nèi)涵。 用例圖是用例建模的一個(gè)重要產(chǎn)物，它以圖形化的方式將系統(tǒng)描述成用例、參與者及其之間的關(guān)系。用例圖在高層交流了系統(tǒng)必須處理的業(yè)務(wù)事件的范圍，是描述系統(tǒng)與其他外部系統(tǒng)以及用戶(hù)之間交互的圖形。發(fā)起或者觸發(fā)用例的外部用戶(hù)稱(chēng)為參與者。為了完成某些業(yè)務(wù)任務(wù)，參與者發(fā)起系統(tǒng)活動(dòng)，即用例。在構(gòu)建用例圖時(shí)，常用的方式是先識(shí)別參與者，然后確定用例以及用例之間的關(guān)系。 UML活動(dòng)圖用于建模系統(tǒng)的過(guò)程步驟或活

6、動(dòng)。構(gòu)造活動(dòng)圖通常先為用例添加開(kāi)始和結(jié)束點(diǎn)，為用例的主要步驟添加一個(gè)活動(dòng)，從每個(gè)活動(dòng)到其他活動(dòng)、決策點(diǎn)和終點(diǎn)添加轉(zhuǎn)換，并行活動(dòng)的地方添加同步條。 【問(wèn)題1】 識(shí)別參與者時(shí)，考查和系統(tǒng)交互的人員和外部系統(tǒng)。本題中，與系統(tǒng)交互的人員包括員工、注冊(cè)到系統(tǒng)的員工（顧客）、餐廳員工、菜單管理員、送餐員以及工資系統(tǒng)。 由“菜單管理員是餐廳特定員工”以及圖中A2和圖中餐廳員工之間的“是一種”關(guān)系可知，A2為菜單管理員；圖中還缺少描述中與工資系統(tǒng)的交互，由“……并發(fā)送給工資系統(tǒng)”可知，A1為工資系統(tǒng)。 【問(wèn)題2】 考查用例及其和參與者之間的關(guān)系時(shí)，通過(guò)判斷哪一個(gè)特定參與者發(fā)起或者觸發(fā)了與系統(tǒng)的哪些交

7、互，來(lái)識(shí)別用例并建立和參與者之間的關(guān)聯(lián)。 本題中，由“任何員工都可以查看菜單和今日特價(jià)”可知，圖中缺少用例查看今日特價(jià)，對(duì)應(yīng)參與者是員工；由“系統(tǒng)的顧客是……，注冊(cè)工資支付、……”可知，圖中缺少用例注冊(cè)工資支付，對(duì)應(yīng)參與者是顧客和工資系統(tǒng)；由“餐廳員工是……，可以進(jìn)行備餐、生成付費(fèi)請(qǐng)求……發(fā)送給工資系統(tǒng)”可知，圖中缺少用例“生成付費(fèi)請(qǐng)求”，對(duì)應(yīng)的參與者是餐廳員工和工資系統(tǒng)；由“菜單管理員是餐廳特定員工，可以管理菜單”可知，圖中缺少用例管理菜單，對(duì)應(yīng)的參與者是菜單管理員。 需要注意的是，在注冊(cè)工資支付所對(duì)應(yīng)的參與者中，雖然沒(méi)有明確說(shuō)明要和工資系統(tǒng)交互，但是由“對(duì)于注冊(cè)工資支付的顧客生成付費(fèi)請(qǐng)

8、求并發(fā)送給工資系統(tǒng)”可知，工資支付是由工資系統(tǒng)控制，所以注冊(cè)也需要和工資系統(tǒng)交互。 【問(wèn)題3】 在顧客訂餐過(guò)程的描述中，在“顧客選菜”之前，圖中缺少符號(hào)和活動(dòng)。由說(shuō)明中顧客“可以訂餐（如果未登錄，需先登錄）”可以判斷，在系統(tǒng)“顯示菜單和今日特價(jià)”之后“顧客選菜”之前，需要判斷（判定符號(hào)）當(dāng)前用戶(hù)身份是否為顧訂餐信息通知給餐于員工”可知，發(fā)送E-mail和通知餐廳員工為并行活動(dòng)，需要在前后有同步條（或縱向）。 【問(wèn)題4】 參與者之間的關(guān)系表示子類(lèi)型“是一種”父類(lèi)型，即泛化關(guān)系。其中父類(lèi)型通常是一個(gè)抽象泛化的參與者，可以完成子類(lèi)型可完成的共同行為，每個(gè)具體的子類(lèi)型繼承它，可以完成父類(lèi)型參與

9、者同樣的任務(wù)，并可以補(bǔ)充額外的角色功能。 2.現(xiàn)準(zhǔn)備為某銀行開(kāi)發(fā)一個(gè)信用卡管理系統(tǒng)CCMS，該系統(tǒng)的基本功能為： 1．信用卡申請(qǐng)。非信用卡客戶(hù)填寫(xiě)信用卡申請(qǐng)表，說(shuō)明所要申請(qǐng)的信用卡類(lèi)型及申請(qǐng)者的基本信息，提交CCMS。如果信用卡申請(qǐng)被銀行接受，CCMS將記錄該客戶(hù)的基本信息，并發(fā)送確認(rèn)函給該客戶(hù)，告知客戶(hù)信用卡的有效期及信貸限額；否則該客戶(hù)將會(huì)收到一封拒絕函。非信用卡客戶(hù)收到確認(rèn)函后成為信用卡客戶(hù)。 2．信用卡激活。信用卡客戶(hù)向CCMS提交激活請(qǐng)求，用信用卡號(hào)和密碼激活該信用卡。激活操作結(jié)束后，CCMS將激活通知發(fā)送給客戶(hù)，告知客戶(hù)其信用卡是否被成功激活。

10、 3．信用卡客戶(hù)信息管理。信用卡客戶(hù)的個(gè)人信息可以在CCMS中進(jìn)行在線(xiàn)管理。每位信用卡客戶(hù)可以在線(xiàn)查詢(xún)和修改個(gè)人信息。 4．交易信息查詢(xún)。信用卡客戶(hù)使用信用卡進(jìn)行的每一筆交易都會(huì)記錄在CCMS中。信用卡客戶(hù)可以通過(guò)CCMS查詢(xún)并核實(shí)其交易信息（包括信用卡交易記錄及交易額）。 圖1-1和圖1-2分別給出了該系統(tǒng)的頂層數(shù)據(jù)流圖和0層數(shù)據(jù)流圖的初稿。 圖1-1頂層數(shù)據(jù)流圖 圖1-2 0層數(shù)據(jù)流圖 【問(wèn)題1】（3分） 根據(jù)，將圖1-1中的E1~E3填充完整。 【問(wèn)題2】（3分） 圖1-1中缺少三條數(shù)據(jù)流，根據(jù)，分別指出這三條數(shù)據(jù)流的起點(diǎn)和終點(diǎn)。（注：數(shù)據(jù)流的起點(diǎn)和終點(diǎn)均采用圖中的符

11、號(hào)和描述） 【問(wèn)題3】（5分） 圖1-2中有兩條數(shù)據(jù)流是錯(cuò)誤的，請(qǐng)指出這兩條數(shù)據(jù)流的名稱(chēng)，并改正。（注：數(shù)據(jù)流的起點(diǎn)和終點(diǎn)均采用圖中的符號(hào)和描述） 【問(wèn)題4】（4分） 根據(jù)，將圖1-2中P1~P4的處理名稱(chēng)填充完整。 圖1-1頂層數(shù)據(jù)流圖 圖1-2 0層數(shù)據(jù)流圖 正確答案： 本題解析： 【問(wèn)題1】（3分） E1：非信用卡客戶(hù)（1分） E2：信用卡客戶(hù)（1分） E3：銀行（1分） 【問(wèn)題2】（3分） 注：每條數(shù)據(jù)流的起點(diǎn)和終點(diǎn)全部答對(duì)方可給1分 【問(wèn)題3】（5分） 錯(cuò)

12、誤的數(shù)據(jù)流 注：每個(gè)名稱(chēng)各0.5分 改正后的數(shù)據(jù)流： 注：每條數(shù)據(jù)流的名稱(chēng)、起點(diǎn)和終點(diǎn)全部答對(duì)方可給2分 【問(wèn)題4】（4分） P1：交易信息查詢(xún)P2：客戶(hù)信息管理 P3：信用卡激活P4：信用卡申請(qǐng) 本題屬于經(jīng)典的考題，主要考查對(duì)DFD的理解。 【問(wèn)題1】 根據(jù)題目中的說(shuō)明，可以很容易找到與CCMS系統(tǒng)進(jìn)行信息交互的角色有非信用卡客戶(hù)、信用卡客戶(hù)以及銀行。下面要做的事情是在上圖(a)中找到對(duì)應(yīng)的位置。 根據(jù)圖(a)給出的輸入和輸出數(shù)據(jù)流，可知E1表示非信用卡客戶(hù)；E2表示信用卡客戶(hù)；E3表示銀行。 【問(wèn)題2】 這道題目主要考查父圖與子圖的平衡問(wèn)題。對(duì)照上圖(a)和

13、(b)可以發(fā)現(xiàn)，數(shù)據(jù)流“信用卡申請(qǐng)表”、“激活請(qǐng)求”、“信用卡交易信息”出現(xiàn)在圖(b)中，卻沒(méi)有出現(xiàn)在圖(a)中。下一步只要正確地標(biāo)出這三條數(shù)據(jù)流的起點(diǎn)和終點(diǎn)就可以了。 【問(wèn)題3】 數(shù)據(jù)流的錯(cuò)誤主要有與錯(cuò)誤的加工相連接、沒(méi)有經(jīng)過(guò)任何的加工、數(shù)據(jù)流方向錯(cuò)誤等。在圖(b)中，并沒(méi)有出現(xiàn)任何的數(shù)據(jù)流沒(méi)有經(jīng)過(guò)加工，那錯(cuò)誤就在于與數(shù)據(jù)流相連接的加工有問(wèn)題或者數(shù)據(jù)流方向錯(cuò)誤。 這樣，可以找兩條有錯(cuò)誤的數(shù)據(jù)流“激活請(qǐng)求”和“信用卡申請(qǐng)表”。從圖(a)中可知，“激活請(qǐng)求”是從系統(tǒng)流向外部實(shí)體E2的，而在圖(b)中，“激活請(qǐng)求”卻出現(xiàn)在兩個(gè)加工之間。數(shù)據(jù)流“信用卡申請(qǐng)表”是在問(wèn)題2中補(bǔ)充找到的數(shù)據(jù)流，它應(yīng)

14、該從外部實(shí)體E1流向CCMS系統(tǒng)。 【問(wèn)題4】 這道題要求將圖(b)中的加工補(bǔ)充完整。加工的名稱(chēng)在說(shuō)明中已經(jīng)明確給出了： 信用卡申請(qǐng)、信用卡激活、信用卡客戶(hù)信息管理以及交易信息查詢(xún)。下一步需要根據(jù)圖(b)中給出的數(shù)據(jù)流關(guān)系將這4個(gè)加工對(duì)號(hào)入座即可。這樣可以得到P1表示交易信息查詢(xún)；P2表示信用卡客戶(hù)信息管理；P3表示信用卡激活；P4表示信用卡申請(qǐng)。 3.某公司擬開(kāi)發(fā)一多用戶(hù)電子郵件客戶(hù)端系統(tǒng)，部分功能的初步需求分析結(jié)果如下： （1）郵件客戶(hù)端系統(tǒng)支持多個(gè)用戶(hù)，用戶(hù)信息主要包括用戶(hù)名和用戶(hù)密碼，且系統(tǒng)中的用戶(hù)名不可重復(fù)。 （2）郵件帳號(hào)信息包括郵件地址及

15、其相應(yīng)的密碼，一個(gè)用戶(hù)可以擁有多個(gè)郵件地址（如userl＠）。 （3）一個(gè)用戶(hù)可擁有一個(gè)地址薄，地址簿信息包括聯(lián)系人編號(hào)、姓名、電話(huà)、單位、地址、郵件地址1、郵件地址2、郵件地址3等信息。地址薄中一個(gè)聯(lián)系人只能屬于一個(gè)用戶(hù)，且聯(lián)系人編號(hào)唯一標(biāo)識(shí)一個(gè)聯(lián)系人。 （4）一個(gè)郵件帳號(hào)可以含有多封郵件，一封郵件可以含有多個(gè)附件。郵件主要包括郵件號(hào)、發(fā)件人地址、收件人地址、郵件狀態(tài)、郵件主題、郵件內(nèi)容、發(fā)送時(shí)間、接收時(shí)間。其中，郵件號(hào)在整個(gè)系統(tǒng)內(nèi)唯一標(biāo)識(shí)一封郵件，郵件狀態(tài)有己接收、待發(fā)送、已發(fā)送和已刪除4種，分別表示郵件是屬于收件箱、發(fā)件箱、己發(fā)送箱和廢件箱。一封郵件可以發(fā)送給多個(gè)用戶(hù)。附件信息主要包

16、括附件號(hào)、附件文件名、附件大小。一個(gè)附件只屬于一封郵件，附件號(hào)僅在一封郵件內(nèi)唯一。 【問(wèn)題1】（5分） 根據(jù)以上說(shuō)明設(shè)計(jì)的E-R圖如圖2-1所示，請(qǐng)指出地址簿與用戶(hù)、電子郵件帳號(hào)與郵件、郵件與附件之間的聯(lián)系類(lèi)型。 2-1電子郵件客戶(hù)端系統(tǒng)E-R圖 【問(wèn)題2】（4分） 該郵件客戶(hù)端系統(tǒng)的主要關(guān)系模式如下，請(qǐng)?zhí)钛a(bǔ)(a)~(c)的空缺部分。 用戶(hù)（用戶(hù)名，用戶(hù)密碼） 地址簿（（a），聯(lián)系人編號(hào)，姓名，電話(huà)，單位地址，郵件地址1，郵件地址2，郵件地址3） 郵件帳號(hào)（郵件地址，郵件密碼，用戶(hù)名） 郵件（（b），收件人地址，郵件狀態(tài)，郵件主題，郵件內(nèi)容，發(fā)送時(shí)間，接收時(shí)間） 附件（

17、（c），附件號(hào)，附件文件名，附件大?。? 【問(wèn)題3】（6分） （1）請(qǐng)指出【問(wèn)題2】中給出的地址簿、郵件和附件關(guān)系模式的主鍵，如果關(guān)系模式存在外鍵請(qǐng)指出。 （2）附件屬于弱實(shí)體嗎？請(qǐng)用50字以?xún)?nèi)的文字說(shuō)明原因?！締?wèn)題1】（5分） （1）1（1分） （2）1（1分） （3）m或n或*（1分） （4）1（1分） （5）m或n或*（1分） 【問(wèn)題2】（4分） （a）用戶(hù)名（1分） （b）郵件號(hào)，發(fā)件人地址（2分） 注：郵件號(hào)和發(fā)件人地址都答對(duì)方可給1分，郵件帳號(hào)答對(duì)給1分 （c）郵件號(hào)（1分） 【問(wèn)題3】（6分） （1）（3分，每空0.5分）

18、 正確答案： 本題解析： 【問(wèn)題1】（5分） （1）1（1分） （2）1（1分） （3）m或n或*（1分） （4）1（1分） （5）m或n或*（1分） 【問(wèn)題2】（4分） （a）用戶(hù)名（1分） （b）郵件號(hào)，發(fā)件人地址（2分） 注：郵件號(hào)和發(fā)件人地址都答對(duì)方可給1分，郵件帳號(hào)答對(duì)給1分 （c）郵件號(hào)（1分） 【問(wèn)題3】（6分） （1）（3分，每空0.5分） （2）附件屬于弱實(shí)體，因?yàn)楦郊拇嬖诒仨氁脏]件的存在為前提，即附件總是依附于某郵件。（3分） 本題考查數(shù)據(jù)庫(kù)系統(tǒng)中實(shí)體聯(lián)系模型（E-R模型）的設(shè)計(jì)

19、和關(guān)系模式的設(shè)計(jì)。 【問(wèn)題1】 兩個(gè)實(shí)體模型之間的聯(lián)系可以分為三類(lèi)：一對(duì)一聯(lián)系（1:1）、一對(duì)多聯(lián)系（1:n）和多對(duì)多聯(lián)系（m:n）。 根據(jù)題意，地址簿與用戶(hù)之間應(yīng)該是一個(gè)1:1的聯(lián)系，空（1）應(yīng)填1。電子郵件賬號(hào)與郵件之間應(yīng)該是一個(gè)1:m的聯(lián)系，故空（2）和空（3）應(yīng)分別填寫(xiě)1和m。郵件與附件之間應(yīng)該是一個(gè)1:m的聯(lián)系，故空（4）和空（5）應(yīng)分別填寫(xiě)1和m。得到的E-R圖如下圖所示。 【問(wèn)題2】 空（a）分析：根據(jù)題意可知郵件客戶(hù)端系統(tǒng)支持多個(gè)用戶(hù)，用戶(hù)信息主要包括用戶(hù)名和用戶(hù)密碼，且系統(tǒng)中的用戶(hù)名不可重復(fù)，“用戶(hù)名”可以作為用戶(hù)關(guān)系模式主鍵。地址簿關(guān)系模式中與用戶(hù)關(guān)系模式是一

20、個(gè)1:1的聯(lián)系，必須將任一方的主鍵加入另一方，以建立它們之間的聯(lián)系，故空（a）處應(yīng)填寫(xiě)“用戶(hù)名”。 空（b）分析：根據(jù)題意可知郵件號(hào)在整個(gè)系統(tǒng)內(nèi)唯一標(biāo)識(shí)一封郵件，故郵件關(guān)系模式必須有屬性“郵件號(hào)”，另外一封郵件需要填寫(xiě)“發(fā)件人地址”，故空（b）處應(yīng)填寫(xiě)“郵件號(hào)，發(fā)件人地址”。 空（c）分析：根據(jù)題意可知郵件和附件是一個(gè)1:m的聯(lián)系，按照E-R模型向關(guān)系模型的轉(zhuǎn)換規(guī)則對(duì)于1:m的聯(lián)系應(yīng)將1端的主鍵并入多端，故空（c）處應(yīng)填寫(xiě)“郵件號(hào)”。 【問(wèn)題3】 （1）地址簿關(guān)系模式的主鍵為“聯(lián)系人編號(hào)”，外鍵為“用戶(hù)名”，因?yàn)椤坝脩?hù)名”是參考用戶(hù)關(guān)系模式的“用戶(hù)名”主鍵。郵件關(guān)系模式的主鍵為“郵件號(hào)

21、”，外鍵為“發(fā)件人地址”或“收件人地址”，因?yàn)楫?dāng)用戶(hù)向其他人發(fā)郵件的時(shí)候，“發(fā)件人地址”是參考郵件賬號(hào)關(guān)系模式的“郵件地址”的主鍵；當(dāng)用戶(hù)收郵件的時(shí)候，“收件人地址”是參考郵件賬號(hào)關(guān)系模式的“郵件地址”的主鍵。附件關(guān)系模式的主鍵為“郵件號(hào)，附件號(hào)”，外鍵為“郵件號(hào)”，因?yàn)樵摗班]件號(hào)”參考郵件關(guān)系模式的“郵件號(hào)”的主鍵。 （2）附件屬于弱實(shí)體，因?yàn)槿绻麤](méi)有郵件，附件也就不存在。 4.0-1背包問(wèn)題可以描述為：有n個(gè)物品，對(duì)i=1，2，…，n，第i個(gè)物品價(jià)值為vi，重量為wi（vi，和wi為非負(fù)數(shù)），背包容量為W（W為非負(fù)數(shù)），選擇其中一些物品裝入背包，使裝入背包

22、物品的總價(jià)值最大，即，且總重量不超過(guò)背包容量，即，其中，xi∈{0，1}，xi=0表示第i個(gè)物品不放入背包，xi=1表示第i個(gè)物品放入背包。 【問(wèn)題1】（8分） 用回溯法求解此0-1背包問(wèn)題，請(qǐng)?zhí)畛湎旅鎮(zhèn)未a中（1）~（4）處空缺。 回溯法是一種系統(tǒng)的搜索方法。在確定解空間后，回溯法從根結(jié)點(diǎn)開(kāi)始，按照深度優(yōu)先策略遍歷解空間樹(shù)，搜索滿(mǎn)足約束條件的解。對(duì)每一個(gè)當(dāng)前結(jié)點(diǎn)，若擴(kuò)展該結(jié)點(diǎn)己經(jīng)不滿(mǎn)足約束條件，則不再繼續(xù)擴(kuò)展。為了進(jìn)一步提高算法的搜索效率，往往需要設(shè)計(jì)一個(gè)限界函數(shù)，判斷并剪枝那些即使擴(kuò)展了也不能得到最優(yōu)解的結(jié)點(diǎn)?，F(xiàn)在假設(shè)已經(jīng)設(shè)計(jì)了BOUND（v，w，k，W）函數(shù)，其中v，w，k和W分別

23、表示當(dāng)前已經(jīng)獲得的價(jià)值、當(dāng)前背包的重量、己經(jīng)確定是否選擇的物品數(shù)和背包的總?cè)萘俊?duì)應(yīng)于搜索樹(shù)中的某個(gè)結(jié)點(diǎn)，該函數(shù)值表示確定了部分物品是否選擇之后，對(duì)剩下的物品在滿(mǎn)足約束條件的前提下進(jìn)行選擇可能獲得的最大價(jià)值，若該價(jià)值小于等于當(dāng)前已經(jīng)得到的最優(yōu)解，則該結(jié)點(diǎn)無(wú)需再擴(kuò)展。 下面給出0-1背包問(wèn)題的回溯算法偽代碼。 函數(shù)參數(shù)說(shuō)明如下： W：背包容量；n：物品個(gè)數(shù)；w：重量數(shù)組；v：價(jià)值數(shù)組；fw：獲得最大價(jià)值時(shí)背包的重量；fp：背包獲得的最大價(jià)值；X：?jiǎn)栴}的最優(yōu)解。 變量說(shuō)明如下： cw：當(dāng)前的背包重量；cp：當(dāng)前獲得的價(jià)值；k：當(dāng)前考慮的物品編號(hào)；Y：當(dāng)前已獲得的部分解。 BKNAP(W

24、,n,w,v,fw,fp,X) 1 cw←cp←0 2(1) 3 fp←-1 4?while true 5 while k≤n and cw+w[k]≤W do 6(2) 7 cp←cp+v[k] 8 Y[k]←1 9 k←k+1 10 if k>n then 11?if fp＜cp then 12?fp←cp 13 fw←cw 14?k←n 15 x←Y 16?else Y(k)←0 17 while BOUND(cp,cw,k,W)≤fp do 18 while k≠0 and Y(k)≠1 do 19(3) 20 if k=0 then retur

25、n 21 Y(k)←0 22 cw←cw-w[k] 23?cp←cp-v[k] 24(4) 【問(wèn)題2】（7分） 考慮表4-1的實(shí)例，假設(shè)有3個(gè)物品，背包容量為22。圖4-1中是根據(jù)上述算法構(gòu)造的搜索樹(shù)，其中結(jié)點(diǎn)的編號(hào)表示了搜索樹(shù)生成的順序，邊上的數(shù)字1/0分別表示選擇／不選擇對(duì)應(yīng)物品。除了根結(jié)點(diǎn)之外，每個(gè)左孩子結(jié)點(diǎn)旁邊的上下兩個(gè)數(shù)字分別表示當(dāng)前背包的重量和已獲得的價(jià)值，右孩子結(jié)點(diǎn)旁邊的數(shù)字表示擴(kuò)展了該結(jié)點(diǎn)后最多可能獲得的價(jià)值。為獲得最優(yōu)解，應(yīng)該選擇物品（5），獲得的價(jià)值為（6）。 對(duì)于表4-1的實(shí)例，若采用窮舉法搜索整個(gè)解空間，則搜索樹(shù)的結(jié)點(diǎn)數(shù)為（7），而用了上述回溯法，

26、搜索樹(shù)的結(jié)點(diǎn)數(shù)為（8）。 正確答案： 本題解析： 【問(wèn)題1】（共8分，各2分） （1）k←1或其等價(jià)形式 （2）cw←cw+w[k]或其等價(jià)形式 （3）k←k–1或其等價(jià)形式 （4）k←k+1或其等價(jià)形式 【問(wèn)題2】（共7分） （5）物品2和物品3（2分） （6）35（1分） （7）15（2分） （8）8（2分） 本題考查算法設(shè)計(jì)技術(shù)——回溯法。 此類(lèi)題目要求考生掌握基本的算法設(shè)計(jì)技術(shù)，包括分治法、動(dòng)態(tài)規(guī)劃法、貪心算法、回溯法和分支限界法等，然后結(jié)合具體的問(wèn)題，用對(duì)應(yīng)的算法設(shè)計(jì)技術(shù)

27、來(lái)解決問(wèn)題。 【問(wèn)題1】 本題考查的是用回溯法求解0-1背包問(wèn)題?；厮莘ㄓ袃深?lèi)算法框架：非遞歸形式和遞歸形式，本題采用非遞歸形式表示。理解回溯法的基本思想和這兩類(lèi)算法框架是正確解答本題的根本要求。 回溯法從第一項(xiàng)物品開(kāi)始考慮是否應(yīng)該裝入背包中，因此當(dāng)前考慮的物品編號(hào)k從1開(kāi)始，即k←1。然后逐項(xiàng)往后檢查，若能全部放入背包則將該項(xiàng)放入背包，此時(shí)背包的重量應(yīng)該是當(dāng)前的重量加上當(dāng)前考慮物品的重量，即cw←cw+w[k]，當(dāng)然背包中物品的價(jià)值也為當(dāng)前的價(jià)值加上當(dāng)前考慮物品的價(jià)值。若己經(jīng)考慮完了所有的物品，則得到一個(gè)解，判斷該解是否為當(dāng)前最優(yōu)，若為最優(yōu)，則將該解的信息放入變量fp、fw和X中。若還

28、沒(méi)有考慮完所有的物品，意味著有些物品不能放入背包，此時(shí)先判斷若不將當(dāng)前的物品放入背包中，則其余物品放入背包是否可能得到比當(dāng)前最優(yōu)解更優(yōu)的解，若得不到則回溯；否則繼續(xù)考慮其余的物品。 【問(wèn)題2】 根據(jù)問(wèn)題1中給出的偽代碼運(yùn)行該實(shí)例，可以很容易得到此0-1背包問(wèn)題的最優(yōu)解，應(yīng)該選擇物品2和物品3，此時(shí)背包的重量為10＋10＝20，獲得的價(jià)值為17＋18＝35。 若采用窮舉法搜索整個(gè)解空間，即要構(gòu)造一顆完全二叉樹(shù)，此時(shí)搜索樹(shù)的結(jié)點(diǎn)數(shù)應(yīng)為24-1=15，而采用了上述回溯法，搜索樹(shù)的結(jié)點(diǎn)數(shù)僅為8個(gè)，如上圖所示。 5.現(xiàn)欲構(gòu)造一文件／目錄樹(shù)，采用組合（Composit

29、e）設(shè)計(jì)模式來(lái)設(shè)計(jì)，得到的類(lèi)圖如6-1所示： {圖} 圖6-1類(lèi)圖 【Java代碼】 import java.util.ArrayList; import.java.util.List; (1)class AbstractFile{ protected String name; public void printName（　　）{System.out.println(name);} public abstract boolean addChild(AbstractFile file); public abstract boolean removeChild(AbstracF

30、ile file); public abstract List＜AbstractFile>getChildren（　?。? } class File extends AbstractFile{ public File(String name){this.name=name;} public?boolean addChild(AbstractFile file){return false;} public?boolean?removeChild(AbstracFile file){return false;} public?List＜AbstractFile>getChildren

31、（　?。﹞return(2);} } class Folder extends AbstractFile{ private List＜AbstracFile>childList; public Folder(String name){ this.name=name; this.childList=new ArrayList＜AbstractFile>（　?。? } public boolean addChild(AbstractFile file){return childList.add(file);} public boolean removeChild(Abstract

32、File file){return childList.remove(file);} public(3)＜AbstractFile>getChildren（　　）{return(4);} } public class Client{ public static void main(String[]args){ //創(chuàng)造一個(gè)樹(shù)形的文件/目錄結(jié)構(gòu) AbstractFile rootFolder=new Folder(“c:\\”); AbstractFile compositeFolder=new Folder(“composite”); AbstractFile windowsF

33、older=new Folder(“windows”); AbstractFile file=new File(“TestComposite.java”); rootFolder.addChild(compositeFolder); rootFolder.addChild(windowsFolder); compositeFolder.addChild(file); //打印目錄文件數(shù) printTree（rootFolder）; } private static void printTree(AbstractFile ifile){ ifile.printName（　?。?

34、 List＜AbstractFile>children=ifile.getChildren（　?。? if(Children==null)return; for(AbstractFile file:Children){ (5); } } } 該程序運(yùn)行后輸出結(jié)果為： c:\ composite TestComposite.java Windows 【Java代碼】 import java.util.ArrayList; import.java.util.List; (1)class AbstractFile{ protected String name; p

35、ublic void printName（　?。﹞System.out.println(name);} public abstract boolean addChild(AbstractFile file); public abstract boolean removeChild(AbstracFile file); public abstract List＜AbstractFile>getChildren（　?。? } class File extends AbstractFile{ public File(String name){this.name=name;} publi

36、c?boolean addChild(AbstractFile file){return false;} public?boolean?removeChild(AbstracFile file){return false;} public?List＜AbstractFile>getChildren（　?。﹞return(2);} } class Folder extends AbstractFile{ private List＜AbstracFile>childList; public Folder(String name){ this.name=name; this.chil

37、dList=new ArrayList＜AbstractFile>（　?。? } public boolean addChild(AbstractFile file){return childList.add(file);} public boolean removeChild(AbstractFile file){return childList.remove(file);} public(3)＜AbstractFile>getChildren（　　）{return(4);} } public class Client{ public static void main(Stri

38、ng[]args){ //創(chuàng)造一個(gè)樹(shù)形的文件/目錄結(jié)構(gòu) AbstractFile rootFolder=new Folder(“c:\\”); AbstractFile compositeFolder=new Folder(“composite”); AbstractFile windowsFolder=new Folder(“windows”); AbstractFile file=new File(“TestComposite.java”); rootFolder.addChild(compositeFolder); rootFolder.addChild(windowsFo

39、lder); compositeFolder.addChild(file); //打印目錄文件數(shù) printTree（rootFolder）; } private static void printTree(AbstractFile ifile){ ifile.printName（　　）; List＜AbstractFile>children=ifile.getChildren（　?。? if(Children==null)return; for(AbstractFile file:Children){ (5); } } } 該程序運(yùn)行后輸出結(jié)果為： c:\ c

40、omposite TestComposite.java Windows 正確答案： 本題解析： （1）abstract （2）null （3）List （4）childList （5）printTree(file) 本題考查基本面向?qū)ο笤O(shè)計(jì)中設(shè)計(jì)模式的運(yùn)用能力。 組合設(shè)計(jì)模式主要是表達(dá)整體和部分的關(guān)系，并且對(duì)整體和部分對(duì)象的使用無(wú)差別。題目中AbstractFile是File類(lèi)和Folder類(lèi)的父類(lèi)，它抽象了兩個(gè)類(lèi)的共有屬性和行為，在后續(xù)main方法的使用中，不論是File對(duì)象還是Fol

41、der對(duì)象，都可被當(dāng)作AbstractFile對(duì)象來(lái)使用。另外，由于Folder對(duì)象可以聚合其他的Folder對(duì)象和File對(duì)象，等價(jià)于Folder對(duì)象可以聚合另一個(gè)AbslractFile對(duì)象。 題目中AbstractFile類(lèi)應(yīng)該為抽象類(lèi)，因此其修飾符應(yīng)該包括abstract，空（2）處返回File類(lèi)對(duì)象的孩子，但File類(lèi)對(duì)象沒(méi)有孩子節(jié)點(diǎn)，因此其返回值應(yīng)該為NULL。getChildren方法是繼承自抽象父類(lèi)AbstractFile，所以其返回類(lèi)型應(yīng)該和父類(lèi)的定義保持一致，空（4）處返回存儲(chǔ)孩子節(jié)點(diǎn)的集合對(duì)象childList。該程序的運(yùn)行能夠打印出文件目錄樹(shù)，因此空（5）處應(yīng)該為打印

42、方法的調(diào)用。 6.現(xiàn)欲構(gòu)造一文件／目錄樹(shù)，采用組合（Composite）設(shè)計(jì)模式來(lái)設(shè)計(jì)，得到的類(lèi)圖如5-1所示： 圖5-1類(lèi)圖 【C++代碼】 #include＜List> #include＜iostrem> #include＜string> using namespace std; class AbstractFile{ protected: string name;//文件或目錄名稱(chēng) public： void printName（　　）{cout＜＜name;}//打印文件或目錄名稱(chēng) virtual void addChild(A

43、bstractFile*file)=0；//給一個(gè)目錄增加子目錄或文件 virtual void removeChild(AbstractFile*file)=0；//刪除一個(gè)目錄的子目錄或文件 virtual list＜AbstractFile*>*getChildren（　?。?0；//獲得一個(gè)目錄的子目錄或文件 }； class File:public AbstracFile{ public: File(string name){(1)=name;} void addChild(AbstractFile*file){return;} void removeChild(Ab

44、stractFile*file){return;} (2)getChildren（　?。﹞return(3);} }; classFolder:public AbstractFile{ private: list＜AbstractFile*>childList;//存儲(chǔ)子目錄或文件 public： Folder(string name){(4)name;} void addChild(AbstractFile*file){childList.push_back(file);} void removeChild(AbstractFile*file){childList.remo

45、ve(file);} list＜AbstractFile*>*getChildren（　　）{return(5);} }; void main（　?。﹞ //構(gòu)造一個(gè)樹(shù)形的文件/目錄結(jié)構(gòu) AbstractFile*rootFolder=new Folder(“c:\\”); AbstractFile*compositeFolder=new Folder(“composite”); AbstractFile*windowsFolder=new Folder(“windows”); AbstractFile*file=new File(“TestComposite.java”);

46、 rootFolder->addChild(compositeFolder); rootFolder->addChild(windowsFolder); compositeFolder->addChild(file); } 圖5-1類(lèi)圖 【C++代碼】 #include＜List> #include＜iostrem> #include＜string> using namespace std; class AbstractFile{ protected: string name;//文件或目錄名稱(chēng) public： void printName（　　）{cout＜＜

47、name;}//打印文件或目錄名稱(chēng) virtual void addChild(AbstractFile*file)=0;//給一個(gè)目錄增加子目錄或文件 virtual void removeChild(AbstractFile*file)=0;//刪除一個(gè)目錄的子目錄或文件 virtual list＜AbstractFile>*getChildren（　　）=0;//獲得一個(gè)目錄的子目錄或文件 }； class File:public AbstractFile{ public: File(string name){(1)=name;} void addChild(Abstra

48、ctFile*file){return;} void removeChild(AbstractFile*file){return;} (2)getChildren（　　）{return(3);} }; classFolder:public AbstractFile{ private: list＜AbstractFile*>childList;//存儲(chǔ)子目錄或文件 public： Folder(string name){(4)name;} void addChild(AbstractFile*file){childList.push_back(file);} void rem

49、oveChild(AbstractFile*file){childList.remove(file);} list＜AbstractFile*>*getChildren（　?。﹞return(5);} }; void main（　?。﹞ //構(gòu)造一個(gè)樹(shù)形的文件/目錄結(jié)構(gòu) AbstractFile*rootFolder=new Folder(“c:\\”); AbstractFile*compositeFolder=new Folder(“composite”); AbstractFile*windowsFolder=new Folder(“windows”); Abstract

50、File*file=new file(“TestComposite.java”); rootFolder->addChild(compositeFolder); rootFolder->addChild(windowsFolder); compositeFolder->addChild(file); } 正確答案： 本題解析： （1）this->name （2）list＜AbstractFile*＞* （3）NULL （4）this->name （5）&childList 本題考查基本

51、面向?qū)ο笤O(shè)計(jì)中設(shè)計(jì)模式的運(yùn)用能力。 組合設(shè)計(jì)模式主要是表達(dá)整體和部分的關(guān)系，并且對(duì)整體和部分對(duì)象的使用無(wú)差別。題目中AbstractFile是File類(lèi)和Folder類(lèi)的父類(lèi)，它抽象了兩個(gè)類(lèi)的共有屬性和行為，在后續(xù)main方法的使用中，不論是File對(duì)象還是Folder對(duì)象，都可被當(dāng)作AbstractFile對(duì)象來(lái)使用。另外，由于Folder對(duì)象可以聚合其他的Folder對(duì)象和File對(duì)象，等價(jià)于Folder對(duì)象可以聚合另一個(gè)AbslractFile對(duì)象。 在類(lèi)File和類(lèi)Folder的構(gòu)造函數(shù)中都需要記錄文件或目錄的名稱(chēng)，因此空（1）和空（4）處主要是設(shè)置對(duì)象的名稱(chēng)。因?yàn)镕ile對(duì)象不再聚合其他的對(duì)象，所以File對(duì)象沒(méi)有孩子節(jié)點(diǎn)，因此，空（3）處應(yīng)該返回NULL。getChildren()方法繼承自AbstractFile類(lèi)，因此其返回類(lèi)型也應(yīng)保持一致。對(duì)于空（5），要求返回Folder對(duì)象的孩子對(duì)象，因此返回其成員childList的地址。