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

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

1、2009年上半年（下午）《軟件設(shè)計(jì)師》真題 注意：圖片可根據(jù)實(shí)際需要調(diào)整大小 卷面總分：7分 答題時(shí)間：240分鐘 試卷題量：7題 練習(xí)次數(shù)：0次 問(wèn)答題 （共7題，共7分） 1.某銀行計(jì)劃開發(fā)一個(gè)自動(dòng)存提款機(jī)模擬系統(tǒng)（ATM?System）。系統(tǒng)通過(guò)讀卡器（CardReader）讀取ATM卡；系統(tǒng)與客戶（Customer）的交互由客戶控制臺(tái)（CustomerConsole）實(shí)現(xiàn)；銀行操作員（Operator）可控制系統(tǒng)的啟動(dòng)（System?Startup）和停止（System?Shutdown）；系統(tǒng)通

2、過(guò)網(wǎng)絡(luò)和銀行系統(tǒng)（Bank）實(shí)現(xiàn)通信。 當(dāng)讀卡器判斷用戶已將ATM卡插入后，創(chuàng)建會(huì)話（Session）。會(huì)話開始后，讀卡器進(jìn)行讀卡，并要求客戶輸入個(gè)人驗(yàn)證碼（PIN）。系統(tǒng)將卡號(hào)和個(gè)人驗(yàn)證碼信息送到銀行系統(tǒng)進(jìn)行驗(yàn)證。驗(yàn)證通過(guò)后，客戶可從菜單選擇如下事務(wù)（Transaction）： 1.從ATM卡賬戶取款（Withdraw）； 2.向ATM卡賬戶存款（Deposit）； 3.進(jìn)行轉(zhuǎn)賬（Transfer）； 4.查詢（Inquire）ATM卡賬戶信息。 一次會(huì)話可以包含多個(gè)事務(wù)，每個(gè)事務(wù)處理也會(huì)將卡號(hào)和個(gè)人驗(yàn)證碼信息送到銀行系統(tǒng)進(jìn)行驗(yàn)證。若個(gè)人驗(yàn)證碼錯(cuò)誤，則轉(zhuǎn)個(gè)人驗(yàn)證碼錯(cuò)誤處理（Inv

3、alid?PIN?Process）。每個(gè)事務(wù)完成后，客戶可選擇繼續(xù)上述事務(wù)或退卡。選擇退卡時(shí)，系統(tǒng)彈出ATM卡，會(huì)話結(jié)束。 系統(tǒng)采用面向?qū)ο蠓椒ㄩ_發(fā)，使用UML進(jìn)行建模。系統(tǒng)的頂層用例圖如圖3-1所示，一次會(huì)話的序列圖（不考慮驗(yàn)證）如圖3-2所示。消息名稱參見表3-1。 可能的消息名稱列表 【問(wèn)題1】（7分） 根據(jù)中的描述，給出圖3-1中A1和A2所對(duì)應(yīng)的參與者，U1至U3所對(duì)應(yīng)的用例，以及該圖中空（1）所對(duì)應(yīng)的關(guān)系。（U1至U3的可選用例包括：Session、Transaction、Insert?Card．Invalid?PIN?Process和Transfer） 【問(wèn)題2】（

4、6分） 根據(jù)中的描述，使用表3-1中的英文名稱，給出圖3-2中6～9對(duì)應(yīng)的消息。 【問(wèn)題3】（2分） 解釋圖3-1中用例U3和用例Withdraw、Deposit等四個(gè)用例之間的關(guān)系及其內(nèi)涵。 正確答案： 本題解析： 【問(wèn)題1】 A1：Customer A2：Bank?U1：Session U2：Invalid?PIN?Process U3：Transaction（1）：＜＜extend>> 【問(wèn)題2】 6：readPIN()7：PIN 8：creat(atm，this，card，

5、pin) 9：performTransaction() 【問(wèn)題3】 Transaction是一個(gè)抽象泛化用例，具有其他事務(wù)類型共有的屬性和行為，每個(gè)具體的事務(wù)類型繼承它，并實(shí)現(xiàn)適合白己的特定的操作。 本題涉及面向?qū)ο笙到y(tǒng)開發(fā)時(shí)的UML用例圖、序列圖以及用例之間的關(guān)系。 【問(wèn)題1】 構(gòu)建用例圖時(shí)，常用的方式是先識(shí)別參與者，然后確定用例以及用例之間的關(guān)系。 識(shí)別參與者時(shí)，考查和系統(tǒng)交互的人員和外部系統(tǒng)。本題中，與系統(tǒng)交互的人員包括客戶”（Customer）和銀行操作員（Operator），與本模擬系統(tǒng)交互的外部系統(tǒng)包括銀行系統(tǒng)（Bank）。 考查用例時(shí)，通過(guò)判斷哪一個(gè)特定參與者發(fā)起

6、或者觸發(fā)了與系統(tǒng)的哪些交互，來(lái)識(shí)別用例并建立和參與者之間的關(guān)聯(lián)。考查用例之間的關(guān)系時(shí)，＜＜include>>（包含）定義了用例之間的包含關(guān)系，用于一個(gè)用例包含另一個(gè)用例的行為的建模；如果可以從一個(gè)用例的執(zhí)行中，在需要時(shí)轉(zhuǎn)向執(zhí)行另一個(gè)用例，執(zhí)行完返回之前的用例繼續(xù)執(zhí)行，用例即存在＜＜include>>關(guān)系。 本題中，客戶一旦插卡成功，系統(tǒng)就創(chuàng)建會(huì)話（Session），會(huì)話中可以執(zhí)行用戶從菜單選擇的Withdraw、Deposit、Transfer和Inquire等事務(wù)（Transaction）。由圖中U3和Withdraw之間的泛化關(guān)系，可知U3為Transaction；又由Ul和U3之間的＜

7、＜include>>關(guān)系，得知U1為Session，進(jìn)而判定圖中A1為Customer，A2為Bank。每個(gè)事務(wù)處理也會(huì)將卡號(hào)和個(gè)人驗(yàn)證碼碼信息送到銀行系統(tǒng)進(jìn)行驗(yàn)證，若個(gè)人驗(yàn)證碼錯(cuò)誤，則轉(zhuǎn)個(gè)人驗(yàn)證碼錯(cuò)誤處理（Invalid?PIN?Process，圖中U2），所以（1）處應(yīng)填＜＜extend>>。 【問(wèn)題2】 序列圖是場(chǎng)景的圖形化表示，描述了以時(shí)間順序組織的對(duì)象之間的交互活動(dòng)。構(gòu)造序列圖時(shí)遵循如下指導(dǎo)原則：確定順序圖的范圍，描述這個(gè)用例場(chǎng)景或一個(gè)步驟；繪制參與者和接口類，如果范圍包括這些內(nèi)容的話；沿左手邊列出用例步驟；對(duì)控制器類及必須在順序中協(xié)作的每個(gè)實(shí)體類，基于它擁有的屬性或己經(jīng)分配給它

8、的行為繪制框；為持續(xù)類和系統(tǒng)類繪制框；繪制所需消息，并把每條消息指到將實(shí)現(xiàn)響應(yīng)消息的責(zé)任的類上：添加活動(dòng)條指示每個(gè)對(duì)象實(shí)例的生命期；為清晰起見，添加所需的返回消息；如果需要，為循環(huán)、可選步驟和替代步驟等添加框架。 本題中，根據(jù)說(shuō)明中的描述，從ATM機(jī)判斷卡已插入（cardInserted()）開始會(huì)話，即為當(dāng)前ATM創(chuàng)建會(huì)話（create(this)）并開始執(zhí)行會(huì)話(performSession())；讀卡器讀卡（readCard()）獲得ATM卡信息（card），然后從控制臺(tái)讀取個(gè)人入驗(yàn)證碼輸（readPIN()，圖中標(biāo)號(hào)6處）并獲得個(gè)人驗(yàn)證碼信息（PIN，圖中標(biāo)號(hào)7處）；然后根據(jù)用戶選擇

9、啟動(dòng)并執(zhí)行事務(wù)，即為當(dāng)前會(huì)話創(chuàng)建事務(wù)（creat(atm，this，card，pin)，圖中標(biāo)號(hào)8處）和執(zhí)行事務(wù)（performTransaction()，圖中標(biāo)號(hào)9處）；可以選擇繼續(xù)執(zhí)行某個(gè)事務(wù)（doAgain）循環(huán)，或者選擇退卡（ejectCard()）。 【問(wèn)題3】 用例之間的繼承關(guān)系表示子類型“是一種”父類型。其中父類型通常是一個(gè)抽象泛化用例，具有子類型共有的屬性和行為，每個(gè)具體的子類型繼承它，并實(shí)現(xiàn)適合自己的持定的操作。 本題中Transaction和Withdraw、Deposit等四個(gè)用例之間的關(guān)系即為繼承關(guān)系，Transaction即是一個(gè)抽象泛化用例，具有其他事務(wù)類型共

10、有的屬性和行為，每個(gè)具體的事務(wù)類型繼承它，并實(shí)現(xiàn)適合自己的特定的操作。 2.假設(shè)某大型商業(yè)企業(yè)由商品配送中心和連鎖超市組成，其中商品配送中心包括采購(gòu)、財(cái)務(wù)、配送等部門。為實(shí)現(xiàn)高效管理，設(shè)計(jì)了商品配送中心信息管理系統(tǒng)，其主要功能描述如下： 1.系統(tǒng)接收由連鎖超市提出的供貨請(qǐng)求，并將其記錄到供貨請(qǐng)求記錄文件。 2.在接到供貨請(qǐng)求后，從商品庫(kù)存記錄文件中進(jìn)行商品庫(kù)存信息查詢。如果庫(kù)存滿足供貨請(qǐng)求，則給配送處理發(fā)送配送通知；否則，向采購(gòu)部門發(fā)出缺貨通知。 3.配送處理接到配送通知后，查詢供貨請(qǐng)求記錄文件，更新商品庫(kù)存記錄文件，并向配送部門發(fā)送配送單，在配送貨品的同

11、時(shí)記錄配送信息至商品配送記錄文件。 4.采購(gòu)部門接到缺貨通知后，與供貨商洽談，進(jìn)行商品采購(gòu)處理，合格商品入庫(kù)，并記錄采購(gòu)清單至采購(gòu)清單記錄文件、向配送處理發(fā)出配送通知，同時(shí)通知財(cái)務(wù)部門給供貨商支付貨款。 該系統(tǒng)采用結(jié)構(gòu)化方法進(jìn)行開發(fā)，得到待修改的數(shù)據(jù)流圖（如圖1-1所示）。 【問(wèn)題1】（8分） 使用中的詞語(yǔ)，給出圖1-1中外部實(shí)體E1至E4的名稱和數(shù)據(jù)存儲(chǔ)D1至D4的名稱。 【問(wèn)題2】（7分） 圖1-1中存在四處錯(cuò)誤數(shù)據(jù)流，請(qǐng)指出各自的起點(diǎn)和終點(diǎn)；若將上述四條錯(cuò)誤數(shù)據(jù)流刪除，為保證數(shù)據(jù)流圖的正確性，應(yīng)補(bǔ)充三條數(shù)據(jù)流，請(qǐng)給出所補(bǔ)充數(shù)據(jù)流的起點(diǎn)和終點(diǎn)。（起點(diǎn)和終點(diǎn)請(qǐng)采用數(shù)據(jù)流圖1-

12、1中的符號(hào)或名稱） 正確答案： 本題解析： 【問(wèn)題1】 E1：財(cái)務(wù)部門E2：采購(gòu)部門E3：連鎖超市E4：配送部門 D1：采購(gòu)清單記錄文件D2：商品庫(kù)存記錄文件 D3：商品配送記錄文件D4：供貨請(qǐng)求記錄文件 【問(wèn)題2】 本題考查DFD的分析與設(shè)計(jì)，問(wèn)題一主要考查DFD中的外部實(shí)體和數(shù)據(jù)存儲(chǔ)，由于在題干中已經(jīng)提到“系統(tǒng)接收由連鎖超市提出的供貨請(qǐng)求，并將其記錄到供貨請(qǐng)求記錄文件”，因此可以明確出“連鎖超市”外部實(shí)體和“供貨請(qǐng)求記錄文件”數(shù)據(jù)存儲(chǔ)；對(duì)應(yīng)到DFD圖中為E3和D4。描述中的

13、第二項(xiàng)提出“從商品庫(kù)存記錄文件中進(jìn)行商品庫(kù)存信息查詢。如果庫(kù)存滿足供貨請(qǐng)求，則給配送處發(fā)送配送通知；否則，向采購(gòu)部門發(fā)出缺貨通知”，因?yàn)榕渌屯ㄖ枰l(fā)送到采購(gòu)部門，因此采購(gòu)部門將成為系統(tǒng)的外部實(shí)體；同時(shí)，商品庫(kù)存記錄文件能夠提供庫(kù)存信息，所以DFD圖中E2和D2分別為采購(gòu)部門和商品配送記錄文件。第三項(xiàng)需求“配送處理接到配送通知后，查詢供貨請(qǐng)求記錄文件，更新商品庫(kù)存記錄文件，并向配送部門發(fā)送配送單，在配送貨品的同時(shí)記錄配送信息至商品配送記錄文件”，所以配送處理需要查詢供貨請(qǐng)求記錄文件，更新商品庫(kù)存記錄文件與商品配送記錄文件，因此D3為商品配送記錄文件；采購(gòu)處理需要記錄采購(gòu)清單同時(shí)通知財(cái)務(wù)部門，所

14、以E1應(yīng)該為財(cái)務(wù)部門，D1為采購(gòu)清單記錄文件，剩下的E4則為配送部門。 DFD中出現(xiàn)的錯(cuò)誤數(shù)據(jù)流為：E1到E2，E1與E2的數(shù)據(jù)流不屬于系統(tǒng)的范圍；D3到E4，多余的數(shù)據(jù)流：D2到采購(gòu)處理，數(shù)據(jù)流方問(wèn)錯(cuò)誤；D4到供貨請(qǐng)求處理，數(shù)據(jù)流方向錯(cuò)誤。 需要補(bǔ)充的數(shù)據(jù)流為：E2到采購(gòu)處理，因?yàn)镋2是采購(gòu)部門，采購(gòu)部門需要給采購(gòu)處提供入庫(kù)商品信息：采購(gòu)處到D2需要一條數(shù)據(jù)流，因?yàn)椴少?gòu)處理需要更改庫(kù)存信息；供貨請(qǐng)求處理到D4需要一條數(shù)據(jù)流，因?yàn)楣┴浾?qǐng)求處理需要記錄供貨請(qǐng)求信息。 3.某集團(tuán)公司擁有多個(gè)大型連鎖商場(chǎng)，公司需要構(gòu)建一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)以方便管理其業(yè)務(wù)運(yùn)作活動(dòng)。 【

15、需求分析結(jié)果】 1.商場(chǎng)需要記錄的信息包括商場(chǎng)編號(hào)（編號(hào)唯一），商場(chǎng)名稱，地址和聯(lián)系電話。某商場(chǎng)信息如表2-1所示。 2.每個(gè)商場(chǎng)包含有不同的部門，部門需要記錄的信息包括部門編號(hào)（集團(tuán)公司分配），部門名稱，位置分布和聯(lián)系電話。某商場(chǎng)的部門信息如表2-2所示。 3.每個(gè)部門雇用多名員工處理日常事務(wù)，每名員工只能隸屬于一個(gè)部門（新進(jìn)員工在培訓(xùn)期不隸屬于任何部門）。員工需要記錄的信息包括員工編號(hào)（集團(tuán)公司分配），姓名，崗位，電話號(hào)碼和工資。員工信息如表2-3所示。 4.每個(gè)部門的員工中有一名是經(jīng)理，每個(gè)經(jīng)理只能管理一個(gè)部門，系統(tǒng)需要記錄每個(gè)經(jīng)理的任職時(shí)間。 【概念模型設(shè)計(jì)】

16、根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖和關(guān)系模式（不完整）如下： 【關(guān)系模式設(shè)計(jì)】 商場(chǎng)（商場(chǎng)編號(hào)，商場(chǎng)名稱，地址，聯(lián)系電話） 部門（部門編號(hào)，部門名稱，位置分布，聯(lián)系電話，（a）） 員工（員工編號(hào)，員工姓名，崗位，電話號(hào)碼，工資，（b）） 經(jīng)理（（c），任職時(shí)間） 【問(wèn)題1】（6分） 根據(jù)問(wèn)題描述，補(bǔ)充四個(gè)聯(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。 【問(wèn)題2】（6分） 根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中的空（a）~（c）補(bǔ)充完整，并分別給出部門、員工和經(jīng)理關(guān)系模式的主鍵和外鍵。 【問(wèn)題3】（3分）

17、 為了使商場(chǎng)有緊急事務(wù)時(shí)能聯(lián)系到輪休的員工，要求每位員工必須且只能登記一位緊急聯(lián)系人的姓名和聯(lián)系電話，不同的員工可以登記相同的緊急聯(lián)系人。則在圖2-1中還需添加的實(shí)體是（1），該實(shí)體和圖2-1中的員工存在（2）聯(lián)系（填寫聯(lián)系類型）。給出該實(shí)體的關(guān)系模式。 正確答案： 本題解析： 【問(wèn)題1】（圖中的m、n也可用*表示，對(duì)聯(lián)系名稱可不做要求，但不能出現(xiàn)重名） 【問(wèn)題2】 （a）商場(chǎng)編號(hào) （b）部門編號(hào) （c）員工編號(hào) 部門關(guān)系模式的主鍵：部門編號(hào) 外鍵：商場(chǎng)編號(hào) 員工關(guān)系模式的主鍵：?jiǎn)T工編

18、號(hào) 外鍵：部門編號(hào) 經(jīng)理關(guān)系模式的主鍵：?jiǎn)T工編號(hào) 外鍵：?jiǎn)T工編號(hào) 【問(wèn)題3】 （d）緊急聯(lián)系人（e）1:n 關(guān)系模式：緊急聯(lián)系人（員工編號(hào)，姓名，聯(lián)系電話） 本題考查數(shù)據(jù)庫(kù)概念結(jié)構(gòu)設(shè)計(jì)及概念結(jié)構(gòu)向邏輯結(jié)構(gòu)轉(zhuǎn)換的過(guò)程。 此類題目要求考生認(rèn)真閱讀題目對(duì)現(xiàn)實(shí)問(wèn)題的描述，經(jīng)過(guò)分類、聚集和概括等方法從中確定實(shí)體及其聯(lián)系。題目已經(jīng)給出了4個(gè)實(shí)體，需要根據(jù)需求描述給出實(shí)體間的聯(lián)系。 【問(wèn)題1】 由“每個(gè)商場(chǎng)包含有不同的部門”可知商場(chǎng)與部門間為1:m聯(lián)系，由“每個(gè)部門雇用了多名員工處理日常事務(wù)”可知部門與員工間為1:n聯(lián)系；由“每個(gè)部門的員工中有一個(gè)經(jīng)理……每個(gè)經(jīng)理只能管理一個(gè)部門”可知部

19、門與經(jīng)理間為1:1聯(lián)系，并且員工是經(jīng)理的超類型，經(jīng)理是員工的子類型。 【問(wèn)題2】 商場(chǎng)的屬性信息中，商場(chǎng)編號(hào)由集團(tuán)公司分配，不會(huì)重復(fù)，可作為商場(chǎng)的主鍵屬性：部門的屬性信息中，部門編號(hào)由集團(tuán)公司分配，不會(huì)重復(fù)，可作為部門的主鍵屬性，商場(chǎng)與部門的聯(lián)系需要通過(guò)將商場(chǎng)的主鍵（商場(chǎng)編號(hào)）加入到部門中來(lái)表達(dá)；員工的屬性信息中，員工編號(hào)由集團(tuán)公司分配，不會(huì)重復(fù)，可作為員工的主鍵屬性，部門與員工的聯(lián)系需要通過(guò)將部門的主鍵（部門編號(hào)）加入到員工中來(lái)表達(dá)；經(jīng)理除了包含員工的屬性信息外，還需要任職時(shí)間屬性。完整的關(guān)系模式如下： 商場(chǎng)（商場(chǎng)編號(hào)，商場(chǎng)名稱，地址，聯(lián)系電話） 部門（部門編號(hào)，部門名稱，位置分

20、布，聯(lián)系電話，商場(chǎng)編號(hào)） 員工（員工編號(hào)，姓名，崗位，電話號(hào)碼，工資，部門編號(hào)） 經(jīng)理（員工編號(hào)，任職時(shí)間） 【問(wèn)題3】 員工的緊急聯(lián)系人信息通過(guò)添加緊急聯(lián)系人關(guān)系來(lái)實(shí)現(xiàn)，由“每位員工必須且只能登記一位緊急聯(lián)系人的姓名和聯(lián)系電話”，但可能存在多位員工登記同一位緊急聯(lián)系人，可知員工與緊急聯(lián)系人間為n:1聯(lián)系；由“不同員工可以登記相同的緊急聯(lián)系人”可知，員工編號(hào)可作為緊急聯(lián)系人的主鍵屬性。所以需要添加的關(guān)系模式如下： 緊急聯(lián)系人（員工編號(hào)，姓名，聯(lián)系電話） 4.現(xiàn)需在某城市中選擇一個(gè)社區(qū)建一個(gè)大型超市，使該城市的其它社區(qū)到該超市的距離總和最小。用圖模型表示

21、該城市的地圖，其中頂點(diǎn)表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長(zhǎng)度。現(xiàn)設(shè)計(jì)一個(gè)算法來(lái)找到該大型超市的最佳位置：即在給定圖中選擇一個(gè)頂點(diǎn)，使該頂點(diǎn)到其它各頂點(diǎn)的最短路徑之和最小。算法首先需要求出每個(gè)頂點(diǎn)到其它任一頂點(diǎn)的最短路徑，即需要計(jì)算任意兩個(gè)頂點(diǎn)之間的最短路徑；然后對(duì)每個(gè)頂點(diǎn)，計(jì)算其它各頂點(diǎn)到該頂點(diǎn)的最短路徑之和；最后，選擇最短路徑之和最小的頂點(diǎn)作為建大型超市的最佳位置。 【問(wèn)題1】（12分） 本題采用Floyd-Warshall算法求解任意兩個(gè)頂點(diǎn)之間的最短路徑。已知圖G的頂點(diǎn)集合為V={1，2，...，n}，W=｛Wij｝n*n為權(quán)重矩陣。設(shè)d(k)ij為從頂點(diǎn)i到頂點(diǎn)j

22、的一條最短路徑的權(quán)重。當(dāng)k=0時(shí)，不存在中間頂點(diǎn)，因此d(0)ij=wij；當(dāng)k>0時(shí)，該最短路徑上所有的中間頂點(diǎn)均屬于集合{1，2，...，k｝若中間頂點(diǎn)包括頂點(diǎn)k，則d(k)ij=d(k-1)ik+d(k-1)kj；若中間頂點(diǎn)不包括頂點(diǎn)k，則d(k)ij=d(k-1)ij。于是得到如下遞歸式 因?yàn)閷?duì)于任意路徑，所有的中間頂點(diǎn)都在集合{1，2，...，n｝內(nèi)，因此矩陣D(n)=｛d(n)ij｝n*n給出了任意兩個(gè)頂點(diǎn)之間的最短路徑，即對(duì)所有i，j∈V，d(n)ij表示頂點(diǎn)i到頂點(diǎn)j的最短路徑。 下面是求解該問(wèn)題的偽代碼，請(qǐng)?zhí)畛淦渲锌杖钡?1)至(6)處。偽代碼中的主要變量說(shuō)明如下： W

23、：權(quán)重矩陣 n：圖的頂點(diǎn)個(gè)數(shù) SP：最短路徑權(quán)重之和數(shù)組，SP[i]表示頂點(diǎn)i到其它各頂點(diǎn)的最短路徑權(quán)重之和，i從1到n min_SP：最小的最短路徑權(quán)重之和 min_v：具有最小的最短路徑權(quán)重之和的頂點(diǎn) i：循環(huán)控制變量 j：循環(huán)控制變量 k：循環(huán)控制變量 【問(wèn)題2】（3分） 【問(wèn)題1】中偽代碼的時(shí)間復(fù)雜度為（7）（用Ο符號(hào)表示）。 正確答案： 本題解析： 【問(wèn)題1】 （1）k=1 to n （2） （3） （4） （5）min_v=1 （6）min_v 【問(wèn)題

24、2】 （7）O(n3) 本題考查的是算法的設(shè)計(jì)和分析技術(shù)。 【問(wèn)題1】 本問(wèn)題考查算法流程。第（1）空表示主循環(huán)，k是循環(huán)控制變量，故第（1）空填k=1?to?n。第（2）和（3）空根據(jù)題意和遞歸式，可分別得到答案為和。計(jì)算了任意兩個(gè)頂點(diǎn)之間的最短路徑之后，對(duì)每個(gè)頂點(diǎn)，開始統(tǒng)計(jì)其到所有其他頂點(diǎn)的最短路徑之和，因此第（4）空填。第13和第14行初始化，假設(shè)最小的到所有其他頂點(diǎn)的最短路徑之和為第一個(gè)頂點(diǎn)的最小路徑之和，大型超市的最佳位置為第一個(gè)頂點(diǎn)，故第（5）空填min_v=1。最后要求返回大型超市的最佳位置，即到所有其他項(xiàng)點(diǎn)的最短路徑之和最小的頂點(diǎn)，故第（6）空填min_v。 【問(wèn)題2

25、】 本問(wèn)題考查【問(wèn)題1】中的偽代碼第2~8行，計(jì)算任意兩點(diǎn)之間的最短路徑，有三重循環(huán)，故時(shí)間復(fù)雜度為O（n3）。第9~12行，計(jì)算每個(gè)點(diǎn)到任意其他點(diǎn)的最短路徑之和，有兩重循環(huán)，故時(shí)間復(fù)雜度為O（n2）。第15~18行，在所有點(diǎn)的最短路徑之和中找到最小的最短路徑之和，時(shí)間復(fù)雜度為O（n）。故算法總的時(shí)間復(fù)雜度為O（n3）。 5.對(duì)二叉樹進(jìn)行遍歷是二叉樹的一個(gè)基本運(yùn)算。遍歷是指按某種策略訪問(wèn)二叉樹的每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)僅訪問(wèn)一次的過(guò)程。函數(shù)InOrder（　?。┙柚鷹?shí)現(xiàn)二叉樹的非遞歸中序遍歷運(yùn)算。 設(shè)二叉樹采用二叉鏈表存儲(chǔ)，結(jié)點(diǎn)類型定義如下： typedef

26、?struct?BtNode{ ElemType data;/*結(jié)點(diǎn)的數(shù)據(jù)域，ElemType的具體定義省略*/ struct?BtNode*lchild，*rchild;/*結(jié)點(diǎn)的左、右孩子指針域*/ }BtNode，*BTree; 在函數(shù)InOrder（　　）中，用棧暫存二叉樹中各個(gè)結(jié)點(diǎn)的指針，并將棧表示為不含頭結(jié)點(diǎn)的單向鏈表（簡(jiǎn)稱鏈棧），其結(jié)點(diǎn)類型定義如下： typedef?struct?StNode{/*鏈棧的結(jié)點(diǎn)類型*/ BTree?elem;/*棧中的元素是指向二叉鏈表結(jié)點(diǎn)的指針*/ struct?StNode*link; }StNode; 假設(shè)從棧頂?shù)綏５椎脑?/p>

27、為en、en-1、…、e1，則不含頭結(jié)點(diǎn)的鏈棧示意圖如圖5-1所示。 【C函數(shù)】 int?InOrder(BTree root)/*實(shí)現(xiàn)二叉樹的非遞歸中序遍歷*/ { BTree ptr;/*ptr用于指向二叉樹中的節(jié)點(diǎn)*/ StNode*q;/*q暫存鏈棧中新創(chuàng)建或待刪除的節(jié)點(diǎn)指針*/ StNode*stacktop=NULL;/*初始化空棧的棧頂指針stacktop*/ ptr=root;/*ptr指向二叉樹的根節(jié)點(diǎn)*/ while((1)||stacktop!=NULL){ while(ptr!=NULL){ q=(StNode*)malloc(sizeof(St

28、Node)); if(q==NULL) return-1 q->elem=ptr; （2）; stacktop=q/*stacktop指向新的棧頂*/ ptr=(3);/*進(jìn)入左子樹*/ } q=stacktop; (4);/*棧頂元素出棧*/ visit(q);/*visit是訪問(wèn)節(jié)點(diǎn)的函數(shù)，其具體定義省略*/ ptr=(5);/*進(jìn)入右子樹*/ free(q);/*釋放原棧頂元素的節(jié)點(diǎn)空間*/ } return 0; }/*InOrder*/ 正確答案： 本題解析： （1

29、）ptr!=NULL，或ptr!=0，或ptr （2）q->link=stacktop （3）ptr->lchild （4）stacktop=stacktop->link，或stacktop=q->link （5）q->elem->rchild 本題考查基本數(shù)據(jù)結(jié)構(gòu)和C語(yǔ)言程序設(shè)計(jì)能力。 對(duì)非空二叉樹進(jìn)行中序遍歷的方法是：先中序遍根節(jié)點(diǎn)的左子樹，然后訪問(wèn)根節(jié)點(diǎn)，最后中序遍歷根節(jié)點(diǎn)的右子樹。用遞歸方式描述的算法如下： void?In_Order_Traversing(BiTree root) {//root是指向二叉樹根節(jié)點(diǎn)的指針 if(root!=NULL){ in_Or

30、der_Traversing(root->Leftchild); visit(root); In_Order_Traversing(root->Rightchild); } } 從以上算法的執(zhí)行過(guò)程中可知，從樹根出發(fā)進(jìn)行遍歷時(shí)，遞歸調(diào)用In_Order_Traversing(root->LeftChild）使得遍歷過(guò)程沿著左孩子分支直走向下層節(jié)點(diǎn)，直到到達(dá)二叉樹中最左下方的節(jié)點(diǎn)（設(shè)為f）的空左子樹為止，然后返回f節(jié)點(diǎn)，再由遞歸調(diào)用In_Order_Traversing(root->RightChild)進(jìn)入f的右子樹，并重復(fù)以上過(guò)程。在遞歸算法執(zhí)行過(guò)程中，輔助實(shí)現(xiàn)遞歸調(diào)用和返回處理的

31、控制棧實(shí)際上起著保存從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑信息。 用非遞歸算法實(shí)現(xiàn)二叉樹的中序遍歷時(shí)，可以由一個(gè)循環(huán)語(yǔ)句實(shí)現(xiàn)從指定的根節(jié)點(diǎn)出發(fā)，沿著左孩子分支一直到頭（到達(dá)一個(gè)沒(méi)有左子樹的節(jié)點(diǎn)）的處理，從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑信息（節(jié)點(diǎn)序列）可以明確構(gòu)造一個(gè)棧來(lái)保存。 本題目的難點(diǎn)在于將棧的實(shí)現(xiàn)和使用混合在一起來(lái)處理，而且棧采用單鏈表存儲(chǔ)結(jié)構(gòu)。下面分析題中給出的代碼。 空（1）是遍歷的條件之一，由于另外個(gè)條件stacktop!=NULL初始時(shí)是不成立的，因此空（1）所表示的條件必須滿足，由于是對(duì)非空二叉樹進(jìn)行遍歷，顯然該條件代表二叉樹非空，即ptr!=NULL或其等價(jià)表示形式。 臨時(shí)指針ptr初始時(shí)

32、指向整個(gè)二叉樹的根節(jié)點(diǎn)，此后用以下代碼表示一直沿左孩子指針鏈向下走的處理，臨時(shí)指針q用于在鏈棧中加入新元素時(shí)使用。處理思路是：若當(dāng)前節(jié)點(diǎn)有左子樹，則將當(dāng)前節(jié)點(diǎn)的指針存入棧中，然后進(jìn)入當(dāng)前節(jié)點(diǎn)的左子樹。入棧時(shí)，先申請(qǐng)?jiān)卦阪湕Ｖ械墓?jié)點(diǎn)空間，然后設(shè)置節(jié)點(diǎn)數(shù)據(jù)域的值（即當(dāng)前節(jié)點(diǎn)的指針），最后將新申請(qǐng)的節(jié)點(diǎn)加入鏈棧首部。 while(ptr!=Null){ q=(StNode*)malloc(sizeof(StNode));/*為新入棧的元素創(chuàng)建節(jié)點(diǎn)*/ if(q==Null)/*若創(chuàng)建新節(jié)點(diǎn)失敗，則退出*/ return-1； q->elem=ptr;/*在棧頂保存指向當(dāng)前節(jié)點(diǎn)的指針*/

33、 q->link=stacktop;/*新節(jié)點(diǎn)加入棧頂*/ stacktop=q;/*更新棧頂指針，即stacktop指向新的棧頂*/ ptr=ptr->lchild;/*進(jìn)入當(dāng)前節(jié)點(diǎn)的左子樹*/ } 當(dāng)上述過(guò)程進(jìn)入一棵空的子樹時(shí)（ptr為空指針），循環(huán)結(jié)束。此后，應(yīng)該從空的子樹返回其父節(jié)點(diǎn)并進(jìn)行訪問(wèn)。由于進(jìn)入空的左子樹前已將其父節(jié)點(diǎn)指針壓入棧中，因此，棧頂元素即為該父節(jié)點(diǎn)，對(duì)應(yīng)的處理就是彈棧。相應(yīng)地，在鏈棧中要?jiǎng)h除表頭節(jié)點(diǎn)并釋放節(jié)點(diǎn)空間： q=stacktop;/*q指向鏈棧中需要?jiǎng)h除的節(jié)點(diǎn)，即棧頂元素*/ stack=stacktop->link;/*棧頂元素出棧*/ vis

34、it(q);/*訪問(wèn)節(jié)點(diǎn)* free(q);/*釋放節(jié)點(diǎn)空間*/ 由于還需要通過(guò)q指針進(jìn)入被刪除節(jié)點(diǎn)的右子樹，因此，釋放節(jié)點(diǎn)空間的操作free(q)操作之前，使ptr抬向q所指節(jié)點(diǎn)的右子樹指針，以得到被刪除節(jié)點(diǎn)的數(shù)據(jù)域信息，即空（5）所在語(yǔ)句ptr=q->elem->rchild。 指針是C語(yǔ)言中靈活且非常強(qiáng)大的工具，是否熱練掌握C語(yǔ)言的判斷條件之一就是對(duì)指針的理解和使用。軟件設(shè)計(jì)師需要熟練掌握這些內(nèi)容。 6.現(xiàn)欲實(shí)現(xiàn)一個(gè)圖像瀏覽系統(tǒng)，要求該系統(tǒng)能夠顯示BMP、JPEG和GIF三種格式的文件，并且能夠在Windows和Linux兩種操作系統(tǒng)上運(yùn)行。系統(tǒng)首先

35、將BMP、JPEG和GIF三種格式的文件解析為像素矩陣，然后將像素矩陣顯示在屏幕上。系統(tǒng)需具有較好的擴(kuò)展性以支持新的文件格式和操作系統(tǒng)。為滿足上述需求并減少所需生成的子類數(shù)目，采用橋接（Bridge）設(shè)計(jì)模式進(jìn)行設(shè)計(jì)，所得類圖如圖6-1所示。 采用該設(shè)計(jì)模式的原因在于：系統(tǒng)解析BMP、GIF與JPEG文件的代碼僅與文件格式相關(guān)，而在屏幕上顯示像素矩陣的代碼則僅與操作系統(tǒng)相關(guān)。 【C++代碼】 class Matrix{//各種格式的文件最終都被轉(zhuǎn)化為像素矩陣 //此處代碼省略 }; class ImageImp{ public: virtual void doPaint(M

36、atrix m)=0;//顯示像素矩陣m }; class WinImp:public ImageImp{ public: void doPaint(Matrix m){/*調(diào)用Windows系統(tǒng)的繪制函數(shù)繪制像素矩陣*/} }; class LinuxImp:public ImageImp{ public: void doPaint(Matrix m){/*調(diào)用Linux系統(tǒng)的繪制函數(shù)繪制像素矩陣*/} }; class Image{ public: void setImp(ImageImp*Imp){(1)=imp;} virtual void parseFile

37、(string fileName)=0; protected: (2)*imp; }; class?BMP:public Image{ public: void parseFile(string fileName){ //此處解析BMP文件并獲得一個(gè)像素矩陣對(duì)象m (3);//顯示像素矩陣m } }; class?GIF:public Image{ //此處代碼省略 }； class?JPEG:public Image{ //此處代碼省略 }； void main（　　）{ //在windows操作系統(tǒng)上查看demo.bmp圖像文件 Image*image

38、1=（4）; ImageImp*imageImp1=（5）; (6); Image1->parseFile(“demo.bmp”); } 現(xiàn)假設(shè)該系統(tǒng)需要支持10種格式的圖像文件和5種操作系統(tǒng)，不考慮類Matrix，若采用橋接設(shè)計(jì)模式則至少需要設(shè)計(jì)（7）個(gè)類。 正確答案： 本題解析： （1）this->imp （2）ImageImp （3）imp->doPaint(m) （4）new?BMP() （5）new?WinImp() （6）image1->setImp(imageImp1）

39、 （7）17 根據(jù)題目描述，在設(shè)計(jì)該圖像顯示系統(tǒng)時(shí)主要分為兩個(gè)步驟：一是讀取各種文件并將文件內(nèi)容轉(zhuǎn)換成像素矩陣，因?yàn)楦鞣N圖片格式不同，因此需要針對(duì)每一種圖片格式編寫文件讀取代碼，而該代碼與操作系統(tǒng)平臺(tái)無(wú)關(guān)。將像素矩陣顯示到屏幕上時(shí)，由于和操作系統(tǒng)相關(guān)，因此需要把該代碼和讀取文件代碼相分離。設(shè)計(jì)中的Image類表示抽象的圖像概念，Image類中就包含了讀取文件接口和設(shè)置實(shí)現(xiàn)平臺(tái)接口；Image的子類BMP、GIF和JPEG分別負(fù)責(zé)讀取各種不同格式的文件；ImageImp的主要任務(wù)是將像素矩陣顯示在屏幕上，因此，它存在兩個(gè)子類，分別實(shí)現(xiàn)Windows系統(tǒng)和Linux系統(tǒng)上的圖像顯示代碼?？杖保?/p>

40、1）處主要是設(shè)置將在哪個(gè)平臺(tái)上進(jìn)行實(shí)現(xiàn)，因此該處應(yīng)該存儲(chǔ)參數(shù)所傳遞的對(duì)象，由于該類的成員變量也是imp，與參數(shù)相同，因此需要填寫this->imp；同理，該成員變量的類型和參數(shù)的類型應(yīng)該保持相同，空（2）處應(yīng)該填寫ImageImp；空（3）處需要根據(jù)imp成員變量存儲(chǔ)的實(shí)現(xiàn)對(duì)象來(lái)顯示圖像；在空（4）處需要生成一個(gè)BMP對(duì)象；由于需要在Windows平臺(tái)上實(shí)現(xiàn)，因此空（5）處需要生成一個(gè)WinImp對(duì)象，同時(shí)，還需設(shè)置該BMP對(duì)象，應(yīng)采用WinImp對(duì)象來(lái)實(shí)現(xiàn)顯示。采用橋接模式能夠?qū)⑽募治龃a和圖像顯示代碼分解在不同的類層次結(jié)構(gòu)中，如果不考慮中間使用的Matrix等類，那么最后需要設(shè)計(jì)的類包括

41、2個(gè)父類，對(duì)應(yīng)文件格式子類，對(duì)應(yīng)操作系統(tǒng)平臺(tái)類，因此10種圖像格式和5種操作系統(tǒng)需要17個(gè)類。 7.現(xiàn)欲實(shí)現(xiàn)一個(gè)圖像瀏覽系統(tǒng)，要求該系統(tǒng)能夠顯示BMP、JPEG和GIF三種格式的文件，并且能夠在Windows和Linux兩種操作系統(tǒng)上運(yùn)行。系統(tǒng)首先將BMP、JPEG和GIF三種格式的文件解析為像素矩陣，然后將像素矩陣顯示在屏幕上。系統(tǒng)需具有較好的擴(kuò)展性以支持新的文件格式和操作系統(tǒng)。為滿足上述需求并減少所需生成的子類數(shù)目，采用橋接（Bridge）設(shè)計(jì)模式進(jìn)行設(shè)計(jì)所得類圖如圖7-1所示 采用該設(shè)計(jì)模式的原因在于：系統(tǒng)解析BMP、GIF與JPEG文件的代碼僅與文

42、件格式相關(guān)，而在屏幕上顯示像素矩陣的代碼則僅與操作系統(tǒng)相關(guān)。 【Java代碼】 class Matrix{//各種格式的文件最終都被轉(zhuǎn)化為像素矩陣 //此處代碼省略 }; abstract class ImageImp{ public?abstract void doPaint(Matrix m);//顯示像素矩陣m }; class WinImp extends ImageImp{ public void doPaint(Matrix m){/*調(diào)用Windows系統(tǒng)的繪制函數(shù)繪制像素矩陣*/} }； class LinuxImp extends ImageImp{

43、public void doPaint(Matrix m)(/*調(diào)用Linux系統(tǒng)的繪制函數(shù)繪制像素矩陣*/) }； abstract class Image{ public void setImp(ImageImp imp){ (1)=imp;} public abstract void parseFile(String fileName)； protected（2）imp； }； class BMP extends Image{ public void parseFile(String fileName){ //此處解析BMP文件并獲得一個(gè)像素矩陣對(duì)象m (3);//

44、顯示像素矩陣m } }; class?GIF extends Image{ //此處代碼省略 }; class?JPEG extends Image{ //此處代碼省略 }; public class javaMain{ public static void main(string[]args){ //在windows操作系統(tǒng)上查看demo.bmp圖像文件 Image image1=（4）； ImageImp?imageImp1=（5）； （6）； Image1.parseFile（“demo.bmp”）; } } 現(xiàn)假設(shè)該系統(tǒng)需要支持10種格式的圖像文件和

45、5種操作系統(tǒng)，不考慮類Matrix，若采用橋接設(shè)計(jì)模式則至少需要設(shè)計(jì)（7）個(gè)類。 正確答案： 本題解析： （1）this.imp （2）ImageImp （3）imp.doPaint(m) （4）new?BMP() （5）new?WinImp() （6）image1.setImp(imageImp1） （7）17 根據(jù)題目描述，在設(shè)計(jì)該圖像顯示系統(tǒng)時(shí)主要分為兩個(gè)步驟：一是讀取各種文件并將文件內(nèi)容轉(zhuǎn)換為像素矩陣，因?yàn)楦鞣N圖片格式不同，因此需要針對(duì)每一種圖片格式編寫文件讀取代碼，而該代碼與操作

46、系統(tǒng)平臺(tái)無(wú)關(guān)。將像素矩陣顯示到屏幕上時(shí)，由于和操作系統(tǒng)相關(guān)，因此需要把該代碼和讀取文件代碼相分離。設(shè)計(jì)中的Image類表示抽象的圖像概念，Image類中就包含了讀取文件接口和設(shè)置實(shí)現(xiàn)平臺(tái)接口；Image的子類BMP、GIF和JPEG分別負(fù)責(zé)讀取各種不同格式的文件；Imagelmp的主要任務(wù)是將像素矩陣顯示在屏幕上，因此，它存在兩個(gè)子類，分別實(shí)現(xiàn)Windows系統(tǒng)和Linux系統(tǒng)上的圖像顯示代碼?？杖保?）處主要是設(shè)置將在哪個(gè)平臺(tái)上進(jìn)行實(shí)現(xiàn)，因此該處應(yīng)該存儲(chǔ)參數(shù)所傳遞的對(duì)象，由于該類的成員變量也是imp，與參數(shù)相同，因此需要填寫this.imp；同理，該成員變量的類型和參數(shù)的類型應(yīng)該保持相同，空（2）處應(yīng)該填寫ImageImp；空（3）處需要根據(jù)imp成員變量存儲(chǔ)的實(shí)現(xiàn)對(duì)象來(lái)顯示圖像；在空（4）處需要生成一個(gè)BMP對(duì)象；由于需要在Windows平臺(tái)上實(shí)現(xiàn)，因此空（5）處需要生成一個(gè)WinImp對(duì)象，同時(shí)，還需設(shè)置該BMP對(duì)象，應(yīng)采用WinImp對(duì)象來(lái)實(shí)現(xiàn)顯示。采用橋接模式能夠?qū)⑽募治龃a和圖像顯示代碼分解在不同的類層次結(jié)構(gòu)中，如果不考慮中間使用的Matrix等類，那么最后需要設(shè)計(jì)的類包括2個(gè)父類，對(duì)應(yīng)文件格式數(shù)目的子類，對(duì)應(yīng)操作系統(tǒng)數(shù)目的平臺(tái)類，因此10種圖像格式和5種操作系統(tǒng)需要17個(gè)類。