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

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

2、過網(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)將卡號和個(gè)人驗(yàn)證碼信息送到銀行系統(tǒng)進(jìn)行驗(yàn)證。驗(yàn)證通過后，客戶可從菜單選擇如下事務(wù)（Transaction）： 1.從ATM卡賬戶取款（Withdraw）； 2.向ATM卡賬戶存款（Deposit）； 3.進(jìn)行轉(zhuǎn)賬（Transfer）； 4.查詢（Inquire）ATM卡賬戶信息。 一次會(huì)話可以包含多個(gè)事務(wù)，每個(gè)事務(wù)處理也會(huì)將卡號和個(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。 可能的消息名稱列表 【問題1】（7分） 根據(jù)中的描述，給出圖3-1中A1和A2所對應(yīng)的參與者，U1至U3所對應(yīng)的用例，以及該圖中空（1）所對應(yīng)的關(guān)系。（U1至U3的可選用例包括：Session、Transaction、Insert?Card．Invalid?PIN?Process和Transfer） 【問題2】（

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

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

6、或者觸發(fā)了與系統(tǒng)的哪些交互，來識別用例并建立和參與者之間的關(guān)聯(lián)?？疾橛美g的關(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ì)將卡號和個(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>>。 【問題2】 序列圖是場景的圖形化表示，描述了以時(shí)間順序組織的對象之間的交互活動(dòng)。構(gòu)造序列圖時(shí)遵循如下指導(dǎo)原則：確定順序圖的范圍，描述這個(gè)用例場景或一個(gè)步驟；繪制參與者和接口類，如果范圍包括這些內(nèi)容的話；沿左手邊列出用例步驟；對控制器類及必須在順序中協(xié)作的每個(gè)實(shí)體類，基于它擁有的屬性或己經(jīng)分配給它

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

9、啟動(dòng)并執(zhí)行事務(wù)，即為當(dāng)前會(huì)話創(chuàng)建事務(wù)（creat(atm，this，card，pin)，圖中標(biāo)號8處）和執(zhí)行事務(wù)（performTransaction()，圖中標(biāo)號9處）；可以選擇繼續(xù)執(zhí)行某個(gè)事務(wù)（doAgain）循環(huán)，或者選擇退卡（ejectCard()）。 【問題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è)由商品配送中心和連鎖超市組成，其中商品配送中心包括采購、財(cái)務(wù)、配送等部門。為實(shí)現(xiàn)高效管理，設(shè)計(jì)了商品配送中心信息管理系統(tǒng)，其主要功能描述如下： 1.系統(tǒng)接收由連鎖超市提出的供貨請求，并將其記錄到供貨請求記錄文件。 2.在接到供貨請求后，從商品庫存記錄文件中進(jìn)行商品庫存信息查詢。如果庫存滿足供貨請求，則給配送處理發(fā)送配送通知；否則，向采購部門發(fā)出缺貨通知。 3.配送處理接到配送通知后，查詢供貨請求記錄文件，更新商品庫存記錄文件，并向配送部門發(fā)送配送單，在配送貨品的同

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

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

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

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

15、需求分析結(jié)果】 1.商場需要記錄的信息包括商場編號（編號唯一），商場名稱，地址和聯(lián)系電話。某商場信息如表2-1所示。 2.每個(gè)商場包含有不同的部門，部門需要記錄的信息包括部門編號（集團(tuán)公司分配），部門名稱，位置分布和聯(lián)系電話。某商場的部門信息如表2-2所示。 3.每個(gè)部門雇用多名員工處理日常事務(wù)，每名員工只能隸屬于一個(gè)部門（新進(jìn)員工在培訓(xùn)期不隸屬于任何部門）。員工需要記錄的信息包括員工編號（集團(tuán)公司分配），姓名，崗位，電話號碼和工資。員工信息如表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ì)】 商場（商場編號，商場名稱，地址，聯(lián)系電話） 部門（部門編號，部門名稱，位置分布，聯(lián)系電話，（a）） 員工（員工編號，員工姓名，崗位，電話號碼，工資，（b）） 經(jīng)理（（c），任職時(shí)間） 【問題1】（6分） 根據(jù)問題描述，補(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。 【問題2】（6分） 根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中的空（a）~（c）補(bǔ)充完整，并分別給出部門、員工和經(jīng)理關(guān)系模式的主鍵和外鍵。 【問題3】（3分）

17、 為了使商場有緊急事務(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)系模式。 正確答案： 本題解析： 【問題1】（圖中的m、n也可用*表示，對聯(lián)系名稱可不做要求，但不能出現(xiàn)重名） 【問題2】 （a）商場編號 （b）部門編號 （c）員工編號 部門關(guān)系模式的主鍵：部門編號 外鍵：商場編號 員工關(guān)系模式的主鍵：員工編

18、號 外鍵：部門編號 經(jīng)理關(guān)系模式的主鍵：員工編號 外鍵：員工編號 【問題3】 （d）緊急聯(lián)系人（e）1:n 關(guān)系模式：緊急聯(lián)系人（員工編號，姓名，聯(lián)系電話） 本題考查數(shù)據(jù)庫概念結(jié)構(gòu)設(shè)計(jì)及概念結(jié)構(gòu)向邏輯結(jié)構(gòu)轉(zhuǎn)換的過程。 此類題目要求考生認(rèn)真閱讀題目對現(xiàn)實(shí)問題的描述，經(jīng)過分類、聚集和概括等方法從中確定實(shí)體及其聯(lián)系。題目已經(jīng)給出了4個(gè)實(shí)體，需要根據(jù)需求描述給出實(shí)體間的聯(lián)系。 【問題1】 由“每個(gè)商場包含有不同的部門”可知商場與部門間為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)理是員工的子類型。 【問題2】 商場的屬性信息中，商場編號由集團(tuán)公司分配，不會(huì)重復(fù)，可作為商場的主鍵屬性：部門的屬性信息中，部門編號由集團(tuán)公司分配，不會(huì)重復(fù)，可作為部門的主鍵屬性，商場與部門的聯(lián)系需要通過將商場的主鍵（商場編號）加入到部門中來表達(dá)；員工的屬性信息中，員工編號由集團(tuán)公司分配，不會(huì)重復(fù)，可作為員工的主鍵屬性，部門與員工的聯(lián)系需要通過將部門的主鍵（部門編號）加入到員工中來表達(dá)；經(jīng)理除了包含員工的屬性信息外，還需要任職時(shí)間屬性。完整的關(guān)系模式如下： 商場（商場編號，商場名稱，地址，聯(lián)系電話） 部門（部門編號，部門名稱，位置分

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

21、該城市的地圖，其中頂點(diǎn)表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長度。現(xiàn)設(shè)計(jì)一個(gè)算法來找到該大型超市的最佳位置：即在給定圖中選擇一個(gè)頂點(diǎn)，使該頂點(diǎn)到其它各頂點(diǎn)的最短路徑之和最小。算法首先需要求出每個(gè)頂點(diǎn)到其它任一頂點(diǎn)的最短路徑，即需要計(jì)算任意兩個(gè)頂點(diǎn)之間的最短路徑；然后對每個(gè)頂點(diǎn)，計(jì)算其它各頂點(diǎn)到該頂點(diǎn)的最短路徑之和；最后，選擇最短路徑之和最小的頂點(diǎ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)閷τ谌我饴窂剑械闹虚g頂點(diǎn)都在集合{1，2，...，n｝內(nèi)，因此矩陣D(n)=｛d(n)ij｝n*n給出了任意兩個(gè)頂點(diǎn)之間的最短路徑，即對所有i，j∈V，d(n)ij表示頂點(diǎn)i到頂點(diǎn)j的最短路徑。 下面是求解該問題的偽代碼，請?zhí)畛淦渲锌杖钡?1)至(6)處。偽代碼中的主要變量說明如下： 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)控制變量 【問題2】（3分） 【問題1】中偽代碼的時(shí)間復(fù)雜度為（7）（用Ο符號表示）。 正確答案： 本題解析： 【問題1】 （1）k=1 to n （2） （3） （4） （5）min_v=1 （6）min_v 【問題

24、2】 （7）O(n3) 本題考查的是算法的設(shè)計(jì)和分析技術(shù)。 【問題1】 本問題考查算法流程。第（1）空表示主循環(huán)，k是循環(huán)控制變量，故第（1）空填k=1?to?n。第（2）和（3）空根據(jù)題意和遞歸式，可分別得到答案為和。計(jì)算了任意兩個(gè)頂點(diǎn)之間的最短路徑之后，對每個(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。 【問題2

25、】 本問題考查【問題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.對二叉樹進(jìn)行遍歷是二叉樹的一個(gè)基本運(yùn)算。遍歷是指按某種策略訪問二叉樹的每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)僅訪問一次的過程。函數(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é)點(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是訪問節(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語言程序設(shè)計(jì)能力。 對非空二叉樹進(jìn)行中序遍歷的方法是：先中序遍根節(jié)點(diǎ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í)行過程中可知，從樹根出發(fā)進(jìn)行遍歷時(shí)，遞歸調(diào)用In_Order_Traversing(root->LeftChild）使得遍歷過程沿著左孩子分支直走向下層節(jié)點(diǎn)，直到到達(dá)二叉樹中最左下方的節(jié)點(diǎn)（設(shè)為f）的空左子樹為止，然后返回f節(jié)點(diǎn)，再由遞歸調(diào)用In_Order_Traversing(root->RightChild)進(jìn)入f的右子樹，并重復(fù)以上過程。在遞歸算法執(zhí)行過程中，輔助實(shí)現(xiàn)遞歸調(diào)用和返回處理的

31、控制棧實(shí)際上起著保存從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑信息。 用非遞歸算法實(shí)現(xiàn)二叉樹的中序遍歷時(shí)，可以由一個(gè)循環(huán)語句實(shí)現(xiàn)從指定的根節(jié)點(diǎn)出發(fā)，沿著左孩子分支一直到頭（到達(dá)一個(gè)沒有左子樹的節(jié)點(diǎn)）的處理，從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑信息（節(jié)點(diǎn)序列）可以明確構(gòu)造一個(gè)棧來保存。 本題目的難點(diǎn)在于將棧的實(shí)現(xiàn)和使用混合在一起來處理，而且棧采用單鏈表存儲(chǔ)結(jié)構(gòu)。下面分析題中給出的代碼。 空（1）是遍歷的條件之一，由于另外個(gè)條件stacktop!=NULL初始時(shí)是不成立的，因此空（1）所表示的條件必須滿足，由于是對非空二叉樹進(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í)，先申請?jiān)卦阪湕Ｖ械墓?jié)點(diǎn)空間，然后設(shè)置節(jié)點(diǎn)數(shù)據(jù)域的值（即當(dāng)前節(jié)點(diǎn)的指針），最后將新申請的節(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)上述過程進(jìn)入一棵空的子樹時(shí)（ptr為空指針），循環(huán)結(jié)束。此后，應(yīng)該從空的子樹返回其父節(jié)點(diǎn)并進(jìn)行訪問。由于進(jìn)入空的左子樹前已將其父節(jié)點(diǎn)指針壓入棧中，因此，棧頂元素即為該父節(jié)點(diǎn)，對應(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);/*訪問節(jié)點(diǎn)* free(q);/*釋放節(jié)點(diǎn)空間*/ 由于還需要通過q指針進(jìn)入被刪除節(jié)點(diǎn)的右子樹，因此，釋放節(jié)點(diǎn)空間的操作free(q)操作之前，使ptr抬向q所指節(jié)點(diǎn)的右子樹指針，以得到被刪除節(jié)點(diǎn)的數(shù)據(jù)域信息，即空（5）所在語句ptr=q->elem->rchild。 指針是C語言中靈活且非常強(qiáng)大的工具，是否熱練掌握C語言的判斷條件之一就是對指針的理解和使用。軟件設(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è)像素矩陣對象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圖片格式不同，因此需要針對每一種圖片格式編寫文件讀取代碼，而該代碼與操作系統(tǒng)平臺無關(guān)。將像素矩陣顯示到屏幕上時(shí)，由于和操作系統(tǒng)相關(guān)，因此需要把該代碼和讀取文件代碼相分離。設(shè)計(jì)中的Image類表示抽象的圖像概念，Image類中就包含了讀取文件接口和設(shè)置實(shí)現(xiàn)平臺接口；Image的子類BMP、GIF和JPEG分別負(fù)責(zé)讀取各種不同格式的文件；ImageImp的主要任務(wù)是將像素矩陣顯示在屏幕上，因此，它存在兩個(gè)子類，分別實(shí)現(xiàn)Windows系統(tǒng)和Linux系統(tǒng)上的圖像顯示代碼?？杖保?/p>

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

41、2個(gè)父類，對應(yīng)文件格式子類，對應(yīng)操作系統(tǒng)平臺類，因此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è)像素矩陣對象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圖片格式不同，因此需要針對每一種圖片格式編寫文件讀取代碼，而該代碼與操作

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