1、全國(guó)計(jì)算機(jī)技術(shù)與軟件專業(yè)技術(shù)資格（水平）考試2009年上半年軟件設(shè)計(jì)師下午試卷試題一閱讀下列說(shuō)明，回答問(wèn)題1與問(wèn)題2,將解答填入答 題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明假設(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ù)存記錄文

2、件，并向配送部門發(fā)送配送單， 在配送貨品的同時(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)行開(kāi)發(fā)，得到待修改的數(shù)據(jù)流圖如下圖所示。時(shí)款逋知、采購(gòu)處理一入庫(kù)_信息D】采購(gòu)?fù)?清單玦貨通知庫(kù)療 信息配送通知糜存更改佰息供貨謂求業(yè)理配送通知配送處埋_*佻貨箱求供賀請(qǐng)求D4D3問(wèn)題1使用說(shuō)明中的詞語(yǔ),給出上圖中外部實(shí)體E1至E4的名稱與數(shù)據(jù)存儲(chǔ)D1至D4的名稱。E1:財(cái)務(wù)部門E2:采購(gòu)部門E3:連鎖超市E4:配送部門D1:采

3、購(gòu)清單記錄文件D2:商品庫(kù)存記錄文件D3:商品配送記錄文件D4:供貨請(qǐng)求記錄文件問(wèn)題2以上數(shù)據(jù)流圖中存在四處錯(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ù)流圖中 的符號(hào)或名稱）錯(cuò)誤數(shù)據(jù)流1圮點(diǎn)EIE2D3E4D2采購(gòu)奶|:D4供貨請(qǐng)求赴理補(bǔ)充的數(shù)據(jù)流終點(diǎn)E2采D2供貸請(qǐng)求處網(wǎng)D4試題一分析本題考查DFD的分析與設(shè)計(jì)，問(wèn)題一主要考查DFD 中的外部實(shí)體與數(shù)據(jù)存儲(chǔ)，由于在題干中已經(jīng)提到“系 統(tǒng)接收由連鎖超市提出的供貨請(qǐng)求，并將其記錄到供貨 請(qǐng)求記錄文件”，因此可以明確出“連鎖超

4、市”外部實(shí) 體與“供貨請(qǐng)求記錄文件”數(shù)據(jù)存儲(chǔ)：對(duì)應(yīng)到DFD圖中 為E3與D4。描述中的第二項(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í)記錄配送 信息至商品配送記錄文件” ,所以

5、配送處理需要查詢供 貨請(qǐng)求記錄文件 ,更新商品庫(kù)存記錄文件與商品配送記 錄文件 ,因此 D3 為商品配送記錄文件 ;采購(gòu)處理需要記 錄采購(gòu)清單同時(shí)通知財(cái)務(wù)部門 ,所以 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ù)流方向錯(cuò)誤 ;D4 到供貨請(qǐng)求處理 ，數(shù)據(jù)流 方向錯(cuò)誤。需要補(bǔ)充的數(shù)據(jù)流為 :E2 到采購(gòu)處理 ,因?yàn)?E2 就是 采購(gòu)部門 ,采購(gòu)部門需要給采購(gòu)處提供入庫(kù)商品信息 ;采 購(gòu)處到 D2 需要一條數(shù)據(jù)流 ,因?yàn)椴少?gòu)處理需

6、要更改庫(kù)存 信息 ;供貨請(qǐng)求處理到 D4 需要一條數(shù)據(jù)流 ,因?yàn)楣┴浾?qǐng) 求處理需要記錄供貨請(qǐng)求信息。試題二閱讀下列說(shuō)明，回答問(wèn)題1至問(wèn)題3,將解答填入答 題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明某集團(tuán)公司擁有多個(gè)大型連鎖商場(chǎng)，公司需要構(gòu)建 一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)以方便管理其業(yè)務(wù)運(yùn)作活動(dòng)。需求分析結(jié)果1.商場(chǎng)需要記錄的信息包括商場(chǎng)編號(hào)（編號(hào)唯一），商 場(chǎng)名稱,地址與聯(lián)系電話。某商場(chǎng)信息如下表所示。商 場(chǎng)信息表両煬帽號(hào)jutPS2101淮懈肉場(chǎng)港降中略歲佛號(hào)021心15関怡P 掘 902揭大榊時(shí)彳弋魁鼻大圍PS2W3樂(lè)人衍麗場(chǎng)耳林區(qū)東木斷石孚號(hào)r01974 502 S7PS2W1懇塔區(qū)整安中站耗號(hào)血呵2649射2.每個(gè)商場(chǎng)包

7、含有不同的部門，部門需要記錄的信 息包括部門編號(hào)（集團(tuán)公司分配）,部門名稱，位置分布與 聯(lián)系電話。某商場(chǎng)的部門信息如下表所示。部門信息表剖門編號(hào)誌門名稱位賞分布聯(lián)第電話DT002財(cái)務(wù)部82504342DT007偶場(chǎng)地卜副保82504347DT021卜割一層82504358DT005人事部商場(chǎng)大摟六層A2504446DTO1ff理那R250466S3每個(gè)部門雇用多名員工處理日常事務(wù)，每名員工 只能隸屬于一個(gè)部門（新進(jìn)員工在培訓(xùn)期不隸屬于任何 部門）。員工需要記錄的信息包括員工編號(hào)（集團(tuán)公司分 配）,姓名，崗位,電話號(hào)碼與工資。員工信息如下表所示。員工信息表員丁握時(shí)(時(shí)電話號(hào)碼工贊XAmo周趙理M

8、B6O92576SR1500.00SHI 075B4772934S71500,00XA004S五書(shū)花廣桶員1523456789142 乩 00EU3123張 lii 華1S76.OO4每個(gè)部門的員工中有一名就是經(jīng)理 ，每個(gè)經(jīng)理只 能管理一個(gè)部門，系統(tǒng)需要記錄每個(gè)經(jīng)理的任職時(shí)間。概念模型設(shè)計(jì)根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖與關(guān) 系模式（不完整）如下：|商場(chǎng) |邯門經(jīng)理員工實(shí)體聯(lián)系圖關(guān)系模式設(shè)計(jì)商場(chǎng)（商場(chǎng)編號(hào)，商場(chǎng)名稱，地址，聯(lián)系電話）部門（部門編號(hào)，部門名稱，位置分布，聯(lián)系電話，（a）a:商場(chǎng)編號(hào)員工（員工編號(hào)，員工姓名，崗位，電話號(hào)碼，工資，（b） b:部門編號(hào)經(jīng)理（c），任職時(shí)間）c

9、:員工編號(hào)問(wèn)題1根據(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。根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中的空（a）（c）補(bǔ)充完 整，并分別給出部門、員工與經(jīng)理關(guān)系模式的主鍵與外 鍵。問(wèn)題3為了使商場(chǎng)有緊急事務(wù)時(shí)能聯(lián)系到輪休的員工，要 求每位員工必須且只能登記一位緊急聯(lián)系人的姓名與 聯(lián)系電話，不同的員工可以登記相同的緊急聯(lián)系人。則 在圖2 1中還需添加的實(shí)體就是（1），該實(shí)體與圖2-1 中的員工存在 （2/登記 ） 聯(lián)系（填寫(xiě)聯(lián)系類型 ）。給 出該實(shí)體的關(guān)系模式。答:緊急聯(lián)系人 （員工編號(hào) ,姓名 ,聯(lián)系電話 ）試

10、題二分析 本題考查數(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:p 聯(lián)系;由“每個(gè)部門的員工 中有一個(gè)經(jīng)理每個(gè)經(jīng)理只能管理一個(gè)部門”可知部 門與經(jīng)理間為 1:1 聯(lián)系 ,并且員工就是經(jīng)理的超類型 ,經(jīng) 理就是員工的子類型。問(wèn)題2商場(chǎng)的屬性信息中，商場(chǎng)編號(hào)由集團(tuán)公司分配，不會(huì) 重復(fù)，可

11、作為商場(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)，部門名稱，位置分布，聯(lián)系電話，商場(chǎng) 編號(hào)）員工（員工編號(hào)，姓名，崗位，電話號(hào)碼，工資，部門編 號(hào)）經(jīng)理（員工編號(hào)，任職時(shí)間）問(wèn)題3員工的緊急聯(lián)系人信息通過(guò)添

12、加緊急聯(lián)系人關(guān)系 來(lái)實(shí)現(xiàn),由“每位員工必須且只能登記一位緊急聯(lián)系人 的姓名與聯(lián)系電話”，但可能存在多位員工登記同一位 家屬,可知員工與家屬間為n:1聯(lián)系：由“不同員工可以 登記相同的緊急聯(lián)系人”可知，員工編號(hào)可作為家屬的 主鍵屬性。所以需要添加的關(guān)系模式如下：緊急聯(lián)系人(員工編號(hào)，姓名，聯(lián)系電話) 參考答案問(wèn)題1(圖中的m、n也可用*表示，對(duì)聯(liá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工編號(hào)外鍵:部門編號(hào)經(jīng)理關(guān)系模式的主鍵 :員工編號(hào) 外鍵:員工編號(hào) 問(wèn)題 3(d) 緊急聯(lián)系人(e)1:n關(guān)系模式 :緊急聯(lián)系人

13、 (員工編號(hào) ,姓名,聯(lián)系電話 ) 試題三閱讀下列說(shuō)明與圖 ,回答問(wèn)題 1 至問(wèn)題 3,將解答填 入答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明某銀行計(jì)劃開(kāi)發(fā)一個(gè)自動(dòng)存提款機(jī)模擬系統(tǒng) (ATM System)。系統(tǒng)通過(guò)讀卡器 (CardReader讀取 ATM 卡; 系 統(tǒng) 與 客 戶 (Customer) 的 交 互 由 客 戶 控 制 臺(tái) (Customer-Console實(shí)現(xiàn);銀行操作員(Operator)可控制系 統(tǒng)的啟動(dòng)(System Startup)與停止(System Shutdown):系 統(tǒng)通過(guò)網(wǎng)絡(luò)與銀行系統(tǒng)(Bank)實(shí)現(xiàn)通信。當(dāng)讀卡器判斷用戶已將 ATM 卡插入后 ,創(chuàng)建會(huì)話 (Session

14、)b會(huì)話開(kāi)始后，讀卡器進(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)賬(Tra nsfer):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ò)誤處理(Invalid PIN Process。每個(gè)事務(wù)完成后,客戶可選擇繼續(xù)上述事務(wù)或 退卡。選擇退卡時(shí)系統(tǒng)彈

15、出ATM卡會(huì)話結(jié)束。系統(tǒng)采用面向?qū)ο蠓椒ㄩ_(kāi)發(fā)，使用UML進(jìn)行建模。 系統(tǒng)的頂層用例圖如圖3-1所示一次會(huì)話的序列圖(不 考慮驗(yàn)證)如圖3-2所示。tcsiilnartedfl1 created si士* ” 七*ireJ5 Mrt:istDinertonsole1 created si士* ” 七*i:SeisinJjlE伽TiSffi昴紂6.11:氟忙?趣X0B2訛綁冊(cè)般（理酬息）問(wèn)題1根據(jù)說(shuō)明中的描述,給出圖3-1中A1與A2所對(duì)應(yīng) 的參與者,U1至U3所對(duì)應(yīng)的用例，以及該圖中空 （1） 所對(duì)應(yīng)的關(guān)系。(U1至U3的可選用例包括：SessionTran saction、Insert Car

16、d、In valid PIN Process 與 Tran sfer) 答：A1:CustomerA2:Ba nkU1:Sessio nU2:Invalid PIN ProcessU3:Transaction(1):vv exte nd>>問(wèn)題2根據(jù)說(shuō)明中的描述，使用消息名稱列表中的英文 名稱,給出圖3-2中69對(duì)應(yīng)的消息。町能的消息名稱列喪名稱說(shuō)屈器稱說(shuō)明Card 曲 xrledQATM百已捕入pedbrmT ransacti on()執(zhí)pcrfonmScshion()readCard()讀興readPINO讀収個(gè)人驗(yàn)證硏PTNcreaHatm, ttii出 Card* pin)

17、為當(dāng)前令話創(chuàng)建寧務(wù)created his)為書(shū)就ATM創(chuàng)建會(huì)話can!ATM 口信息doAgain瓠行卜J介于務(wù)cjcttCardOATM K6:readPIN()7:PIN8:creat(atm,this,card,pi n)9:preformTra nsactio n()問(wèn)題3解釋圖3-1中用例U3與用例 Withdraw、Deposit等四個(gè)用例之間的關(guān)系及其內(nèi)涵。Transaction 就是一個(gè)抽象泛化用例 ,具有其她事務(wù) 類型共有的屬性與行為 ,每個(gè)具體的事務(wù)類型繼承它 ,并 實(shí)現(xiàn)適合自己的特定的操作。試題三分析本題涉及面向?qū)ο笙到y(tǒng)開(kāi)發(fā)時(shí)的 UML 用例圖、序 列圖以及用例之間的關(guān)系

18、。 問(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ā)起或者 觸發(fā)了與系統(tǒng)的哪些交互 ,宋識(shí)別用例并建立與參與者 之間的關(guān)聯(lián)?？疾橛美g的關(guān)系時(shí)，vv in elude >>(包含 )定義了用例之間的包含關(guān)系 ,用于一個(gè)用例包含 另一個(gè)用例的行為的建模 ;如果可以從一個(gè)用例的執(zhí)行 中 ,在需要時(shí)轉(zhuǎn)向執(zhí)行另一個(gè)用

19、例 ,執(zhí)行完返回之前的用 例繼續(xù)執(zhí)行,用例間即存在vv extend>>關(guān)系。本 題 中 , 客 戶 一 旦 插 卡 成 功 , 系 統(tǒng) 就 創(chuàng) 建 會(huì) 話 (Session)會(huì)話中可以執(zhí)行用戶從菜單選擇的 Withdraw、 Deposit、Transfer 與 Inquire 等事務(wù)(Transaction)。由圖 中 U3 與 Withdraw 之 間 的 擴(kuò) 展 關(guān) 系 ,可 知 U3 為 Transaction又由 U1 與 U3 之間的vv include>>關(guān)系, 得知U1為Session進(jìn)而判定圖中 A1為Customer,A2為 Bank。每個(gè)事務(wù)處理

20、也會(huì)將卡號(hào)與個(gè)人驗(yàn)證碼信息送到 銀行系統(tǒng)進(jìn)行驗(yàn)證 ,若個(gè)人驗(yàn)證碼錯(cuò)誤 ,則轉(zhuǎn)個(gè)人驗(yàn)證碼 錯(cuò)誤處理(1nvalid PIN Process圖中U2),所以處應(yīng)填 vv 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)分配給它的 行為繪制框 ;為持續(xù)類與系統(tǒng)類繪制框 ;繪制所需消息 , 并把每條消息指到將

21、實(shí)現(xiàn)響應(yīng)消息的責(zé)任的類上;添加活動(dòng)條指示每個(gè)對(duì)象實(shí)例的生命期 ;為清晰起見(jiàn) ,添加所 需的返回消息 ;如果需要 ,為循環(huán)、可選步驟與替代步驟 等添加框架。本題中 ,根據(jù)說(shuō)明中的描述 ,從 ATM 機(jī)判斷卡已插 入(card Inserted()開(kāi)始會(huì)話，即為當(dāng)前 ATM創(chuàng)建會(huì)話(create(this)并開(kāi)始執(zhí)行會(huì)話(perform Session()讀卡器讀卡(read Card()獲得ATM卡信息(card),然后從控制臺(tái) 讀取個(gè)人驗(yàn)證碼輸入 (read PIN(), 圖中標(biāo)號(hào) 6 處)并獲得 個(gè)人驗(yàn)證碼信息 (PIN, 圖中標(biāo)號(hào) 7 處):然后根據(jù)用戶選擇 啟動(dòng)并執(zhí)行事務(wù),即為當(dāng)前會(huì)話創(chuàng)

22、建事務(wù) (creat(atm,this,card,pin),圖 中標(biāo)號(hào) 8 處)與執(zhí)行事務(wù) (perform Transaction(),圖中標(biāo)號(hào)9處):可以選擇繼續(xù)執(zhí) 行某個(gè)事務(wù) (do Aga i n )循環(huán),或者選擇退卡 (eject Card()。 問(wèn)題 3 用例之間的繼承關(guān)系表示子類型 “就是一種” 父類 型。其中父類型通常就是一個(gè)抽象泛化用例,具有子類型共有的屬性與行為 ,每個(gè)具體的子類型繼承它 ,并實(shí)現(xiàn) 適合自己的特定的操作。本題中 Transaction與 Withdraw、Deposit 等四個(gè)用 例之間的關(guān)系即為繼承關(guān)系 , Transaction 即就是一個(gè)抽 象泛化用例

23、 ,具有其她事務(wù)類型共有的屬性與行為,每個(gè)具體的事務(wù)類型繼承它 ,并實(shí)現(xiàn)適合自己的特定的操 作。參考答案 問(wèn)題 1A1:Customer A2:Bank U1:SessionU2:Invalid PIN Process U3:Transaction (1): vv extend>> 問(wèn)題 26:read PIN() 7:PIN 8:creat(atm,this,card,pin) 9:perform Transaction() 問(wèn)題 3Transaction 就是一個(gè)抽象泛化用例 ,具有其她事務(wù) 類型共有的屬性與行為 ,每個(gè)具體的事務(wù)類型繼承它 ,并 實(shí)現(xiàn)適合自己的特定的操作。試題

24、四閱讀下列說(shuō)明 ,回答問(wèn)題 1 與問(wèn)題 2,將解答填入答 題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明現(xiàn)需在某城市中選擇一個(gè)社區(qū)建一個(gè)大型超市,使該城市的其她社區(qū)到該超市的距離總與最小。 用圖模型 表示該城市的地圖 ,其中頂點(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

25、本題采用F10y-Warshall算法求解任意兩個(gè)頂點(diǎn)之 間的最短路徑。已知圖G的頂點(diǎn)集合為 V=1,2,n),W=W jj n*n。為權(quán)重矩陣。設(shè)'為從頂點(diǎn) i到頂點(diǎn)j的一條最短路徑的權(quán)重。當(dāng)k=0時(shí)，不存在中 間頂點(diǎn)，因此 =Wij：當(dāng)k>0時(shí)，該最短路徑上所有的中 間頂點(diǎn)均屬于集合1,2,k。若中間頂點(diǎn)包括頂點(diǎn)k,則；若中間頂點(diǎn)不包括頂點(diǎn)k,則娜"嚴(yán)L于就 是得到如下遞歸式。因?yàn)閷?duì)于任意路徑,所有的中間頂點(diǎn)都在集合 1,2,n內(nèi),因此矩陣"”'給出了任意兩個(gè)頂點(diǎn)之 間的最短路徑，即對(duì)所有I,j V,"表示頂點(diǎn)i到頂點(diǎn)j的 最短路徑。下面

26、就是求解該問(wèn)題的偽代碼，請(qǐng)?zhí)畛淦渲锌杖钡?至(6)處。偽代碼中的主要變量說(shuō)明如下：W:權(quán)重矩陣n:圖的頂點(diǎn)個(gè)數(shù)SP:最短路徑權(quán)重之與數(shù)組，SPi表示頂點(diǎn)i到其她 各頂點(diǎn)的最短路徑權(quán)重之與,i從1到nmin_SP:最小的最短路徑權(quán)重之與 min_V:具有最小的最短路徑權(quán)重之與的頂點(diǎn) i:循環(huán)控制變量 j:循環(huán)控制變量k:循環(huán)控制變量LOCATE -SHOPPINGMALL (W, n) D(0) = Wfor (1)k = 1 to nfor i = 1 to nfor j = 1 to nif比r蓋船山+醴山elsefor i = 1 to n10SP i = 011for j = 1 to

27、n12/ SPi=SPi+13min _SP = SP114(5)/ min v=115for i = 2 to n16if min SP >SPi17min SP = SPi18min v = i19return(6)/ min v問(wèn)題2問(wèn)題1中偽代碼的時(shí)間復(fù)雜度為(7)(用0符號(hào)表示)。/(7)0(n3)試題四分析本題考查的就是算法的設(shè)計(jì)與分析技術(shù)。問(wèn)題1本問(wèn)題考查算法流程。第(1)空表示主循環(huán),k就是循 環(huán)控制變量 做第空填k=1 ton。第與空根據(jù)題 意與遞歸式，可分別得到答案為 *嚴(yán))與町W。 計(jì)算了任意兩個(gè)頂點(diǎn)之間的最短路徑之后，對(duì)每個(gè)頂點(diǎn), 開(kāi)始統(tǒng)計(jì)其到所有其她頂點(diǎn)的最短路

28、徑之與，因此第(4)空填SPi=SPi+ /。第13與第14行初始化,假設(shè)最 小的到所有其她頂點(diǎn)的最短路徑之與為第一個(gè)頂點(diǎn)的 最小路徑之與，大型超市的最佳位置為第一個(gè)頂點(diǎn)，故第 (5)空填min v=1。最后要求返回大型超市的最佳位置， 即到所有其她頂點(diǎn)的最短路徑之與最小的頂點(diǎn)，故第(6) 空填min v。問(wèn)題2本問(wèn)題考查問(wèn)題門中的偽代碼第 28行,計(jì)算任 意兩點(diǎn)之間的最短路徑，有三重循環(huán)，故時(shí)間復(fù)雜度為 O(n3)。第912行,計(jì)算每個(gè)點(diǎn)到任意其她點(diǎn)的最短路 徑之與,有兩重循環(huán),故時(shí)間復(fù)雜度為O(n2)。第1518 行，在所有點(diǎn)的最短路徑之與中找到最小的最短路徑之 與,時(shí)間復(fù)雜度為O(n)。

29、故算法總的時(shí)間復(fù)雜度為0(n3)。參考答案問(wèn)題1(1) k=1 to n (2)(3)八“ (4) SPi=SPi+ 呼 (5)min_v=1 (6)min_v問(wèn)題2(7) O(n3)試題五閱讀下列說(shuō)明與C函數(shù)代碼，將應(yīng)填入 (n)處的 字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明對(duì)二叉樹(shù)進(jìn)行遍歷就是二叉樹(shù)的一個(gè)基本運(yùn)算。遍 歷就是指按某種策略訪問(wèn)二叉樹(shù)的每個(gè)節(jié)點(diǎn)，且每個(gè)節(jié) 點(diǎn)僅訪問(wèn)一次的過(guò)程。函數(shù)lnOrder()借助棧實(shí)現(xiàn)二叉樹(shù) 的非遞歸中序遍歷運(yùn)算。設(shè)二叉樹(shù)采用二叉鏈表存儲(chǔ)，節(jié)點(diǎn)類型定義如下：typedef struct BtNodeElemType data; /* 節(jié)點(diǎn)的數(shù)據(jù)域，ElemType的

30、具體定義省略*/struct BtNode * Ichild * rchild;/* 節(jié)點(diǎn)的左、右孩子指針域*/BtNode,*BTree;在函數(shù)InOrder()中，用棧暫存二叉樹(shù)中各個(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*li nk;StNode;假設(shè)從棧頂?shù)綏５椎脑貫閑n、&-1、e1,則不含頭節(jié)點(diǎn)的鏈棧示意圖如圖5-1所示。T 71 *1 C1INULL圖5-1鏈棧示意圖圖

31、5-1鏈棧示意圖C函數(shù)int InOrder(BTree root)/* 實(shí)現(xiàn)二叉樹(shù)的非遞歸中序遍歷*/BTree ptr;/*ptr用于指向二叉樹(shù)中的節(jié)點(diǎn)*/StNode*q;/*q暫存鏈棧中新創(chuàng)建或待刪除的節(jié)點(diǎn)指針*/StNode*stacktop=NULL;/*初始化空棧的棧頂指針 stacktop*/Ptr=root;/*ptr指向二叉樹(shù)的根節(jié)點(diǎn)*/while (1) ptr!=NULL _| | stacktop !=NULL) while (ptr!=NULL) q= (StNode*)malloc(sizeof (StNode);if (q= =NULL)return-1;q-&

32、gt; elem=ptr;(2) q-> lin k=stacktop_;stacktop=q; /*stacktop 指向新的棧頂 */ ptr= ptr->lchild_;/*進(jìn)入左子樹(shù) */q=stacktop;(4) smcktop=stacktop-> link,或 stacktop=q-> link /*棧頂元素出棧*/visit(q);/*visit就是訪問(wèn)節(jié)點(diǎn)的函數(shù),其具體定義省略*/ptr= (5)q->elem->rchild;/*進(jìn)入右子樹(shù) */free(q);/*釋放原棧頂元素的節(jié)點(diǎn)空間*/return 0;/*lnorder*/試題

33、五分析本題考查基本數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言程序設(shè)計(jì)能力。對(duì)非空二叉樹(shù)進(jìn)行中序遍歷的方法就是：先中序遍 歷根節(jié)點(diǎn)的左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后中序遍歷根節(jié) 點(diǎn)的右子樹(shù)。用遞歸方式描述的算法如下：void ln_order_Traversi ng (BiTree root)/ / root就是指向二叉樹(shù)根節(jié)點(diǎn)的指針if (root 匸NULL) In _order_Traversi ng(root-> LeftChild); visit(root);In _order_Traversi ng(root> RightChild);從以上算法的執(zhí)行過(guò)程可知，從樹(shù)根出發(fā)進(jìn)行遍歷 時(shí)，遞歸調(diào)用 ln_

34、Order_Traversing(root-> LeftChild)使得 遍歷過(guò)程沿著左孩子分支一直走向下層節(jié)點(diǎn) ,直到到達(dá) 二叉樹(shù)中最左下方的節(jié)點(diǎn) (設(shè)為 f) 的空左子樹(shù)為止 ,然后 返回 f 節(jié)點(diǎn) ,再由遞歸調(diào)用ln_Order_Traversing(root-> Rightchild)進(jìn)入 f 的右 子樹(shù) ,并重復(fù)以上過(guò)程。在遞歸算法執(zhí)行過(guò)程中,輔助實(shí)現(xiàn)遞歸調(diào)用與返回處理的控制棧實(shí)際上起著保存從根 節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑信息。用非遞歸算法實(shí)現(xiàn)二叉樹(shù)的中序遍歷時(shí) ,可以由一 個(gè)循環(huán)語(yǔ)句實(shí)現(xiàn)從指定的根節(jié)點(diǎn)出發(fā) ,沿著左孩子分支 一直到頭 (到達(dá)一個(gè)沒(méi)有左子樹(shù)的節(jié)點(diǎn) )的處理 ,從

35、根節(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!=ULL 初始時(shí)就是不成立的 ,因此空 (1)所表示的 條件必須滿足 ,由于就是對(duì)非空二叉樹(shù)進(jìn)行遍歷 ,顯然該 條件代表二叉樹(shù)非空 ,即 ptr!=ULL 或其等價(jià)表示形式。臨時(shí)指針 ptr 初始時(shí)指向整個(gè)二叉樹(shù)的根節(jié)點(diǎn) ,此后 用以下代碼表示一直沿左孩子指針鏈向下走的處理,臨時(shí)指針 q 用于在鏈棧中加入新元素時(shí)使用。 處理思路就是:若當(dāng)前節(jié)點(diǎn)有左子

36、樹(shù)，則將當(dāng)前節(jié)點(diǎn)的指針存入棧中 然后進(jìn)入當(dāng)前節(jié)點(diǎn)的左子樹(shù)。入棧時(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!=ULL) q=(StNode *) malloc (sizeof (StNode);/*為 新入棧的元素創(chuàng)建節(jié)點(diǎn)*/if (q= =NULL)失敗,則退出*/return-1;q- > elem=ptr;當(dāng)前節(jié)點(diǎn)的指針*/q- > lin k=stacktop;stacktop=q;stacktop指向新的棧頂*/ ptr=ptr- > 1child左子樹(shù)*/*若創(chuàng)建新節(jié)點(diǎn)/*在

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

38、q臊作之前,使ptr指向q 所指節(jié)點(diǎn)的右子樹(shù)指針，以得到被刪除節(jié)點(diǎn)的數(shù)據(jù)域信 息，即空(5)所在語(yǔ)句 ptr=q- >elem-> rchild。指針就是C語(yǔ)言中靈活且非常強(qiáng)大的工具，就是否 熟練掌握C語(yǔ)言的判斷條件之一就就是對(duì)指針的理解 與使用。軟件設(shè)計(jì)師需要熟練掌握這些內(nèi)容。參考答案(1) ptr!=NULL,或 ptr!=0,或 ptr(2) q- > lin k=stacktop(3) ptr- > lchild(4) smcktop=stacktop-> link,或 stacktop=q-> link(5) q- > elem-> r

39、child試題六閱讀下列說(shuō)明與C+代碼，將應(yīng)填入(n)處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明現(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ì),所得類圖如下圖所示。ImageImaelmp>setlmp()*parseFie(J+doPairM()采用該設(shè)計(jì)模式的原因在于

40、：系統(tǒng)解析BMP、GIF 與JPEG文件的代碼僅與文件格式相關(guān)，而在屏幕上顯 示像素矩陣的代碼則僅與操作系統(tǒng)相關(guān)。C+代碼class Matrix /各種格式的文件最終都被轉(zhuǎn)化 為像素矩陣/ /此處代碼省略;class lmagelmppublic:virtual void doPaint (Matrix m)=0;/ / 顯示像素矩陣m;class Win Imp :public ImageImppublic:void doPaint (Matrix m) /* 調(diào)用 Windows 系統(tǒng)的繪制函數(shù)繪制像素矩陣*/);class Linu xImp : public ImageImppubl

41、ic:void doPaint(Matrix m) /* 調(diào)用 Linux 系統(tǒng)的 繪制函數(shù)繪制像素矩陣*/ ;class Image public:void setImp (ImageImp *imp) (1)this imp = imp;virtual void parse )= 0;protected:(2) Imageimp *imp;；class BMP : public lmage public:void parse ) / /此處解析BMP文件并獲得一個(gè) 像素矩陣對(duì)象m(3) imp- > doPaint(m);/ / 顯示像素矩陣 m;class GIF : public

42、 Image/ /此處代碼省略;class JPEG : public Image/ /此處代碼省略;void mai n()/在 Windows 操作系統(tǒng) 上查瞧 demo、 bmp 圖像文 件Image *imagel = new BMP();ImageImp *imageImpl =(5) new Win lmp() ;(6) imagel-> setImp(imageImpl);imagel- > parseFile("demo bmp");(7) 17現(xiàn)假設(shè)該系統(tǒng)需要支持10種格式的圖像文件與5 種操作系統(tǒng)，不考慮類Matrix,若采用橋接設(shè)計(jì)模式則至

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

44、ws系統(tǒng)與Linux 系統(tǒng)上的圖像顯示代碼?？杖?1)處主要就是設(shè)置將在哪 個(gè)平臺(tái)上進(jìn)行實(shí)現(xiàn)，因此該處應(yīng)該存儲(chǔ)參數(shù)所傳遞的對(duì)象,由于該類的成員變量也就是imp,與參數(shù)相同，因此需 要填寫(xiě)this- > imp;同理，該成員變量的類型與參數(shù)的類 型應(yīng)該保持相同，空(2)處應(yīng)該填寫(xiě)Imageimp;空處需 要根據(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與圖像顯

45、示代碼分 解在不 同的類層次結(jié)構(gòu)中 ，如果不考慮中間使用的 Matrix 等類，那么最后需要設(shè)計(jì)的類包括 2 個(gè)父類，對(duì)應(yīng) 文件格式子類 ，對(duì)應(yīng)操作系統(tǒng)平臺(tái)類 ，因此 10 種圖像格 式與 5 種操作系統(tǒng)需要 17個(gè)類。參考答案(1)this- > imp (2)ImageImp (3)imp- > doPaint(m) (4)new BMP()(5) new WinImp() (6)imagel->setImp(imageImpl)(7)17 試題七 閱讀下列說(shuō)明與Java代碼，將應(yīng)填入(n)處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明 現(xiàn)欲實(shí)現(xiàn)一個(gè)圖像瀏覽系統(tǒng) ，要求該系統(tǒng)能夠顯示

46、ImageBMP、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ì),所得類圖如下圖所示。Imageimp+doPaint（）+setlmpC）*par$efle<JPECWlnknp Linuxlmp'類帕采用該設(shè)計(jì)模式的原因在于：系統(tǒng)解析BMP、GIF 與JPEG文件的代碼僅與文件格式相關(guān)，而在屏幕上顯 示像素矩陣的代碼則僅與操作系統(tǒng)相關(guān)。Java代碼class Matrix / /各種格式的文件最終都被轉(zhuǎn)化 為像素矩陣/ /此處代碼省略 ;abstract class Imageimp public abstract void doPai nt(Matrix m);/ / 顯示像素矩陣m;class Win Imp exte nds lmagelmppublic void do Paint(Matrix m)/* 調(diào)用