上半年軟件設計師下午試題及答案

1、 全國計算機技術與軟件專業(yè)技術資格（水平）考試  2009年上半年  軟件設計師  下午試卷 試題一 閱讀下列說明，回答問題1和問題2，將解答填入答題紙的對應欄內。 說明 假設某大型商業(yè)企業(yè)由商品配送中心和連鎖超市組成，其中商品配送中心包括采購、財務、配送等部門。為實現(xiàn)高效管理，設計了商品配送中心信息管理系統(tǒng)，其主要功能描述如下： 1系統(tǒng)接收由連鎖超市提出的供貨請求，并將其記錄到供貨請求記錄文件。 2在接到供貨請求后，從商品庫存記錄文件中進行商品庫存信息查詢。如果庫存滿足供貨請求，則給配送處理發(fā)送配送通知：否則，向采購部門發(fā)出缺貨通知

2、。 3配送處理接到配送通知后，查詢供貨請求記錄文件，更新商品庫存記錄文件，并向配送部門發(fā)送配送單，在配送貨品的同時記錄配送信息至商品配送記錄文件。 4采購部門接到缺貨通知后，與供貨商洽談，進行商品采購處理，合格商品入庫，并記錄采購清單至采購清單記錄文件、向配送處理發(fā)出配送通知，同時通知財務部門給供貨商支付貨款。 該系統(tǒng)采用結構化方法進行開發(fā)，得到待修改的數(shù)據(jù)流圖如下圖所示。 問題1使用說明中的詞語，給出上圖中外部實體E1至E4的名稱和數(shù)據(jù)存儲D1至D4的名稱。答：E1：財務部門 E2：采購部門 E3：連鎖超市 E4：配送部門 D1：采購清單記錄文件 D2：商品庫存記錄文件 D3：商品配送記錄文

3、件 D4：供貨請求記錄文件 問題2以上數(shù)據(jù)流圖中存在四處錯誤數(shù)據(jù)流，請指出各自的起點和終點；若將上述四條錯誤數(shù)據(jù)流刪除，為保證數(shù)據(jù)流圖的正確性，應補充三條數(shù)據(jù)流，請給出所補充數(shù)據(jù)流的起點和終點。(起點和終點請采用上述數(shù)據(jù)流圖中的符號或名稱)答： 錯誤數(shù)據(jù)流 補充的數(shù)據(jù)流 試題一分析 本題考查DFD的分析與設計，問題一主要考查DFD中的外部實體和數(shù)據(jù)存儲，由于在題干中已經(jīng)提到“系統(tǒng)接收由連鎖超市提出的供貨請求，并將其記錄到供貨請求記錄文件”，因此可以明確出“連鎖超市”外部實體和“供貨請求記錄文件”數(shù)據(jù)存儲：對應到DFD圖中為E3和D4。描述中的第二項提出“從商品庫存記錄文件中進行商品庫存信息查詢

4、。如果庫存滿足供貨請求，則給配送處發(fā)送配送通知；否則，向采購部門發(fā)出缺貨通知”，因為配送通知需要發(fā)送到采購部門，因此采購部門將成為系統(tǒng)的外部實體；同時，商品庫存記錄文件能夠提供庫存信息，所以DFD圖中E2和D2分別為采購部門和商品配送記錄文件。第三項需求“配送處理接到配送通知后，查詢供貨請求記錄文件，更新商品庫存記錄文件，并向配送部門發(fā)送配送單，在配送貨品的同時記錄配送信息至商品配送記錄文件”，所以配送處理需要查詢供貨請求記錄文件，更新商品庫存記錄文件與商品配送記錄文件，因此D3為商品配送記錄文件；采購處理需要記錄采購清單同時通知財務部門，所以E1應該為財務部門，D1為采購清單記錄文件，剩下的

5、E4則為配送部門。 DFD中出現(xiàn)的錯誤數(shù)據(jù)流為：E1到E2，E1與E2的數(shù)據(jù)流不屬于系統(tǒng)的范圍；D3到E4，多余的數(shù)據(jù)流；D2到采購處理，數(shù)據(jù)流方向錯誤；D4到供貨請求處理，數(shù)據(jù)流方向錯誤。 需要補充的數(shù)據(jù)流為：E2到采購處理，因為E2是采購部門，采購部門需要給采購處提供入庫商品信息；采購處到D2需要一條數(shù)據(jù)流，因為采購處理需要更改庫存信息；供貨請求處理到D4需要一條數(shù)據(jù)流，因為供貨請求處理需要記錄供貨請求信息。 試題二 閱讀下列說明，回答問題1至問題3，將解答填入答題紙的對應欄內。 說明 某集團公司擁有多個大型連鎖商場，公司需要構建一個數(shù)據(jù)庫系統(tǒng)以方便管理其業(yè)務運作活動。 需求分析結果 1商

6、場需要記錄的信息包括商場編號(編號唯一)，商場名稱，地址和聯(lián)系電話。某商場信息如下表所示。商場信息表 2每個商場包含有不同的部門，部門需要記錄的信息包括部門編號(集團公司分配)，部門名稱，位置分布和聯(lián)系電話。某商場的部門信息如下表所示。 部門信息表 3每個部門雇用多名員工處理日常事務，每名員工只能隸屬于一個部門(新進員工在培訓期不隸屬于任何部門)。員工需要記錄的信息包括員工編號(集團公司分配)，姓名，崗位，電話號碼和工資。員工信息如下表所示。 員工信息表 4每個部門的員工中有一名是經(jīng)理，每個經(jīng)理只能管理一個部門，系統(tǒng)需要記錄每個經(jīng)理的任職時間。 概念模型設計 根據(jù)需求階段收集的信息，設計的實體

7、聯(lián)系圖和關系模式(不完整)如下：實體聯(lián)系圖 關系模式設計 商場(商場編號，商場名稱，地址，聯(lián)系電話) 部門(部門編號，部門名稱，位置分布，聯(lián)系電話， (a) ) / a: 商場編號 員工(員工編號，員工姓名，崗位，電話號碼，工資， (b) ) /b:部門編號 經(jīng)理( (c) ，任職時間) /c:員工編號 問題1根據(jù)問題描述，補充四個聯(lián)系，完善圖21的實體聯(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根據(jù)實體聯(lián)系圖，將關系模式中的空(a)(c)補充完整，并分別給出部門、員工和經(jīng)理關系模式的主鍵和外鍵。 問題3為了使商場有緊急事務時能聯(lián)系到

8、輪休的員工，要求每位員工必須且只能登記一位緊急聯(lián)系人的姓名和聯(lián)系電話，不同的員工可以登記相同的緊急聯(lián)系人。則在圖21中還需添加的實體是 (1) ，該實體和圖2-1中的員工存在 (2/登記) 聯(lián)系(填寫聯(lián)系類型)。給出該實體的關系模式。答：緊急聯(lián)系人(員工編號，姓名，聯(lián)系電話) 試題二分析 本題考查數(shù)據(jù)庫概念結構設計及概念結構向邏輯結構轉換的過程。 此類題目要求考生認真閱讀題目對現(xiàn)實問題的描述，經(jīng)過分類、聚集和概括等方法從中確定實體及其聯(lián)系。題目已經(jīng)給出了4個實體，需要根據(jù)需求描述給出實體間的聯(lián)系。 問題1由“每個商場包含有不同的部門”可知商場與部門間為1:m聯(lián)系；由“每個部門雇用了多名員工處理

9、日常事務”可知部門與員工間為1:p聯(lián)系；由“每個部門的員工中有一個經(jīng)理每個經(jīng)理只能管理一個部門”可知部門與經(jīng)理間為1:1聯(lián)系，并且員工是經(jīng)理的超類型，經(jīng)理是員工的子類型。 問題2 商場的屬性信息中，商場編號由集團公司分配，不會重復，可作為商場的主鍵屬性；部門的屬性信息中，部門編號由集團公司分配，不會重復，可作為部門的主鍵屬性，商場與部門的聯(lián)系需要通過將商場的主鍵(商場編號)加入到部門中來表達；員工的屬性信息中，員工編號由集團公司分配，不會重復，可作為員工的主鍵屬性，部門與員工的聯(lián)系需要通過將部門的主鍵(部門編號)加入到員工中來表達；經(jīng)理除了包含員工的屬性信息外，還需要任職時間屬性。完整的關系模

10、式如下： 商場(商場編號，商場名稱，地址，聯(lián)系電話) 部門(部門編號，部門名稱，位置分布，聯(lián)系電話，商場編號) 員工(員工編號，姓名，崗位，電話號碼，工資，部門編號) 經(jīng)理(員工編號，任職時間) 問題3 員工的緊急聯(lián)系人信息通過添加緊急聯(lián)系人關系來實現(xiàn)，由“每位員工必須且只能登記一位緊急聯(lián)系人的姓名和聯(lián)系電話”，但可能存在多位員工登記同一位家屬，可知員工與家屬間為n:1聯(lián)系：由“不同員工可以登記相同的緊急聯(lián)系人”可知，員工編號可作為家屬的主鍵屬性。所以需要添加的關系模式如下： 緊急聯(lián)系人(員工編號，姓名，聯(lián)系電話) 參考答案 問題1 (圖中的m、n也可用*表示，對聯(lián)系名稱可不做要求，但不能出現(xiàn)

11、重名) 問題2 (a)商場編號 (b)部門編號 (c)員工編號 部門關系模式的主鍵：部門編號 外鍵：商場編號 員工關系模式的主鍵：員工編號 外鍵：部門編號 經(jīng)理關系模式的主鍵：員工編號 外鍵：員工編號 問題3 (d)緊急聯(lián)系人 (e)1:n 關系模式：緊急聯(lián)系人(員工編號，姓名，聯(lián)系電話) 試題三 閱讀下列說明和圖，回答問題1至問題3，將解答填入答題紙的對應欄內。 說明 某銀行計劃開發(fā)一個自動存提款機模擬系統(tǒng)(ATM System)。系統(tǒng)通過讀卡器 (CardReader)讀取ATM卡；系統(tǒng)與客戶(Customer)的交互由客戶控制臺(Customer-Console)實現(xiàn)；銀行操作員(Ope

12、rator)可控制系統(tǒng)的啟動(System Startup)和停止(System Shutdown)：系統(tǒng)通過網(wǎng)絡和銀行系統(tǒng)(Bank)實現(xiàn)通信。 當讀卡器判斷用戶已將ATM卡插入后，創(chuàng)建會話(Session)。會話開始后，讀卡器進行讀卡，并要求客戶輸入個人驗證碼(PIN)。系統(tǒng)將卡號和個人驗證碼信息送到銀行系統(tǒng)進行驗證。驗證通過后，客戶可從菜單選擇如下事務(Transaction)： 1從ATM卡賬戶取款(Withdraw)； 2向ATM卡賬尸存款(Deposit)； 3進行轉賬(Transfer)： 4查詢(Inquire)ATM卡賬戶信息。 一次會話可以包含多個事務，每個事務處理也會將卡

13、號和個人驗證碼信息送到銀行系統(tǒng)進行驗證。若個人驗證碼錯誤，則轉個人驗證碼錯誤處理(Invalid PIN Process)。每個事務完成后，客戶可選擇繼續(xù)上述事務或退卡。選擇退卡時，系統(tǒng)彈出ATM卡，會話結束。 系統(tǒng)采用面向對象方法開發(fā)，使用UML進行建模。系統(tǒng)的頂層用例圖如圖3-1所示，一次會話的序列圖(不考慮驗證)如圖3-2所示。 問題1根據(jù)說明中的描述，給出圖3-1中A1和A2所對應的參與者，U1至U3所對應的用例，以及該圖中空 (1) 所對應的關系。(U1至U3的可選用例包括：Session、Transaction、Insert Card、Invalid PIN Process和Tra

14、nsfer)答：A1：Customer A2：Bank U1：Session U2：Invalid PIN Process U3：Transaction (1)：extend 問題2 根據(jù)說明中的描述，使用消息名稱列表中的英文名稱，給出圖3-2中69對應的消息。答： 6：readPIN() 7:PIN 8:creat(atm,this,card,pin) 9:preformTransaction() 問題3 解釋圖3-1中用例U3和用例Withdraw、Deposit等四個用例之間的關系及其內涵。答：Transaction是一個抽象泛化用例，具有其他事務類型共有的屬性和行為，每個具體的事務類型

15、繼承它，并實現(xiàn)適合自己的特定的操作。 試題三分析 本題涉及面向對象系統(tǒng)開發(fā)時的UML用例圖、序列圖以及用例之間的關系。 問題1 構建用例圖時，常用的方式是先識別參與者，然后確定用例以及用例之間的關系。 識別參與者時，考查和系統(tǒng)交互的人員和外部系統(tǒng)。本題中，與系統(tǒng)交互的人員包括客戶(Customer)和銀行操作員(Operator)，與本模擬系統(tǒng)交互的外部系統(tǒng)包括銀行。系統(tǒng)(Bank)。 考查用例時，通過判斷哪一個特定參與者發(fā)起或者觸發(fā)了與系統(tǒng)的哪些交互，宋識別用例并建立和參與者之間的關聯(lián)?？疾橛美g的關系時，include(包含)定義了用例之間的包含關系，用于一個用例包含另一個用例的行為的建

16、模；如果可以從一個用例的執(zhí)行中，在需要時轉向執(zhí)行另一個用例，執(zhí)行完返回之前的用例繼續(xù)執(zhí)行，用例間即存在extend關系。 本題中，客戶一旦插卡成功，系統(tǒng)就創(chuàng)建會話(Session)，會話中可以執(zhí)行用戶從菜單選擇的Withdraw、Deposit、Transfer和Inquire等事務(Transaction)。由圖中U3和 Withdraw之間的擴展關系，可知U3為Transaction；又由U1和U3之間的include關系，得知U1為Session，進而判定圖中A1為Customer，A2為Bank。每個事務處理也會將卡號和個人驗證碼信息送到銀行系統(tǒng)進行驗證，若個人驗證碼錯誤，則轉個人驗證

17、碼錯誤處理(1nvalid PIN Process，圖中U2)，所以(1)處應填extend。 問題2 序列圖是場景的圖形化表示，描述了以時間順序組織的對象之間的交互活動。構造序列圖時遵循如下指導原則：確定順序圖的范圍，描述這個用例場景或一個步驟；繪制參與者和接口類，如果范圍包括這些內容的話：沿左手邊列出用例步驟；對控制器類及必須在順序中協(xié)作的每個實體類，基于它擁有的屬性或已經(jīng)分配給它的行為繪制框；為持續(xù)類和系統(tǒng)類繪制框；繪制所需消息，并把每條消息指到將實現(xiàn)響應消息的責任的類上；添加活動條指示每個對象實例的生命期；為清晰起見，添加所需的返回消息；如果需要，為循環(huán)、可選步驟和替代步驟等添加框架。

18、 本題中，根據(jù)說明中的描述，從ATM機判斷卡已插入(card Inserted()開始會話，即為當前ATM創(chuàng)建會話(create(this)并開始執(zhí)行會話(perform Session()：讀卡器讀卡(read Card()獲得ATM卡信息(card)，然后從控制臺讀取個人驗證碼輸入(read PIN()，圖中標號6處)并獲得個人驗證碼信息(PIN，圖中標號7處)：然后根據(jù)用戶選擇啟動并執(zhí)行事務，即為當前會話創(chuàng)建事務(creat(atm，this，card，pin)，圖中標號8處)和執(zhí)行事務(perform Transaction()，圖中標號9處)：可以選擇繼續(xù)執(zhí)行某個事務(do Agai

19、n)循環(huán)，或者選擇退卡(eject Card()。 問題3 用例之間的繼承關系表示子類型“是一種”父類型。其中父類型通常是一個抽象泛化用例，具有子類型共有的屬性和行為，每個具體的子類型繼承它，并實現(xiàn)適合自己的特定的操作。 本題中Transaction和Withdraw、Deposit等四個用例之間的關系即為繼承關系， Transaction即是一個抽象泛化用例，具有其他事務類型共有的屬性和行為，每個具體的事務類型繼承它，并實現(xiàn)適合自己的特定的操作。 參考答案 問題1 A1：Customer A2：Bank U1：Session U2：Invalid PIN Process U3：Transac

20、tion (1)：extend 問題2 6：read PIN() 7：PIN 8：creat(atm，this，card，pin) 9：perform Transaction() 問題3 Transaction是一個抽象泛化用例，具有其他事務類型共有的屬性和行為，每個具體的事務類型繼承它，并實現(xiàn)適合自己的特定的操作。 試題四 閱讀下列說明，回答問題1和問題2，將解答填入答題紙的對應欄內。 說明 現(xiàn)需在某城市中選擇一個社區(qū)建一個大型超市，使該城市的其他社區(qū)到該超市的距離總和最小。用圖模型表示該城市的地圖，其中頂點表示社區(qū)，邊表示社區(qū)間的路線，邊上的權重表示該路線的長度。 現(xiàn)設計一個算法來找到該大

21、型超市的最佳位置：即在給定圖中選擇一個頂點，使該頂點到其他各頂點的最短路徑之和最小。算法首先需要求出每個頂點到其他任一頂點的最短路徑，即需要計算任意兩個頂點之間的最短路徑；然后對每個頂點，計算其他各頂點到該頂點的最短路徑之和；最后，選擇最短路徑之和最小的頂點作為建大型超市的最佳位置。 問題1 本題采用F10y-Warshall算法求解任意兩個頂點之間的最短路徑。已知圖G的頂點集合為V=1,2，n)，W=Wjj n*n。為權重矩陣。設為從頂點i到頂點j的一條最短路徑的權重。當k=0時，不存在中間頂點，因此=Wij：當k0時，該最短路徑上所有的中間頂點均屬于集合1,2，k。若中間頂點包括頂點k，則

22、；若中間頂點不包括頂點k，則。于是得到如下遞歸式。 因為對于任意路徑，所有的中間頂點都在集合1,2，n內，因此矩陣給出了任意兩個頂點之間的最短路徑，即對所有I,jV，表示頂點i到頂點j的最短路徑。 下面是求解該問題的偽代碼，請?zhí)畛淦渲锌杖钡?1)至(6)處。偽代碼中的主要變量說明如下： W：權重矩陣 n：圖的頂點個數(shù) SP：最短路徑權重之和數(shù)組，SPi表示頂點i到其他各頂點的最短路徑權重之和，i從1到n min_SP：最小的最短路徑權重之和 min_V：具有最小的最短路徑權重之和的頂點 i：循環(huán)控制變量 j：循環(huán)控制變量 k：循環(huán)控制變量 LOCATE -SHOPPINGMALL (W, n)

23、 1 D(0) = W 2 for (1) /k = 1 to n 3 for i = 1 to n 4 for j = 1 to n 6 (2) / 7 else 8 (3) / 9 for i = 1 to n 10 SP i = 0 11 for j = 1 to n 12 (4) / SPi=SPi+ 13 min SP = SP1 14 (5) / min v=1 15 for i = 2 to n 16 if min SP SPi 17 min SP = SPi 18 min v = i 19 return (6) / min v 問題2 問題1中偽代碼的時間復雜度為 (7) (用

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

25、(6)空填min v。 問題2 本問題考查問題門中的偽代碼第28行，計算任意兩點之間的最短路徑，有三重循環(huán)，故時間復雜度為O(n3)。第912行，計算每個點到任意其他點的最短路徑之和，有兩重循環(huán)，故時間復雜度為O(n2)。第1518行，在所有點的最短路徑之和中找到最小的最短路徑之和，時間復雜度為O(n)。故算法總的時間復雜度為O(n3)。 參考答案 問題1 (1)k=1 to n (2) (3) (4) SPi=SPi+ (5)min_v=1 (6)min_v 問題2 (7) O(n3) 試題五 閱讀下列說明和C函數(shù)代碼，將應填入 (n) 處的字句寫在答題紙的對應欄內。 說明 對二叉樹進行遍歷

26、是二叉樹的一個基本運算。遍歷是指按某種策略訪問二叉樹的每個節(jié)點，且每個節(jié)點僅訪問一次的過程。函數(shù)InOrder()借助棧實現(xiàn)二叉樹的非遞歸中序遍歷運算。 設二叉樹采用二叉鏈表存儲，節(jié)點類型定義如下： typedef struct BtNode ElemType data； /*節(jié)點的數(shù)據(jù)域，ElemType的具體定義省略*/ struct BtNode * lchild * rchild； /*節(jié)點的左、右孩子指針域*/ BtNode，*BTree； 在函數(shù)InOrder()中，用棧暫存二叉樹中各個節(jié)點的指針，并將棧表示為不含頭節(jié)點的單向鏈表(簡稱鏈棧)，其節(jié)點類型定義如下： typedef

27、struct StNode /*鏈棧的節(jié)點類型*/ BTree elem； /*棧中的元素是指向二叉鏈表節(jié)點的指針*/ struct StNode*link； StNode； 假設從棧頂?shù)綏５椎脑貫閑n、en-1、e1，則不含頭節(jié)點的鏈棧示意圖如圖5-1所示。 圖5-1 鏈棧示意圖 C函數(shù) int InOrder(BTree root) /*實現(xiàn)二叉樹的非遞歸中序遍歷*/ BTree ptr； /*ptr用于指向二叉樹中的節(jié)點*/ StNode*q； /*q暫存鏈棧中新創(chuàng)建或待刪除的節(jié)點指針*/ StNode*stacktop=NULL； /*初始化空棧的棧頂指針stacktop*/ Ptr

28、=root； /*ptr指向二叉樹的根節(jié)點*/ while ( (1) ptr!=NULL | | stacktop !=NULL) while (ptr!=NULL) q= (StNode*)malloc(sizeof (StNode)； if (q= =NULL) return-1； q-elem=ptr； (2) q-link=stacktop ； stacktop=q； /*stacktop指向新的棧頂*/ ptr= (3) ptr-lchild ； /*進入左子樹*/ q=stacktop； (4) smcktop=stacktop-link，或stacktop=q-link ； /

29、*棧頂元素出棧*/ visit(q)； /*visit是訪問節(jié)點的函數(shù)，其具體定義省略*/ ptr= (5)q-elem-rchild ； /*進入右子樹*/ free(q)； /*釋放原棧頂元素的節(jié)點空間*/ return 0； /*Inorder*/ 試題五分析 本題考查基本數(shù)據(jù)結構和C語言程序設計能力。 對非空二叉樹進行中序遍歷的方法是：先中序遍歷根節(jié)點的左子樹，然后訪問根節(jié)點，最后中序遍歷根節(jié)點的右子樹。用遞歸方式描述的算法如下： void In_order_Traversing (BiTree root) / / root是指向二叉樹根節(jié)點的指針 if (root !=NULL) I

30、n_order_Traversing(root-LeftChild)； visit(root)； In_order_Traversing(rootRightChild)； 從以上算法的執(zhí)行過程可知，從樹根出發(fā)進行遍歷時，遞歸調用In_Order_Traversing(root-LeftChild)使得遍歷過程沿著左孩子分支一直走向下層節(jié)點，直到到達二叉樹中最左下方的節(jié)點(設為f)的空左子樹為止，然后返回f節(jié)點，再由遞歸調用 In_Order_Traversing(root-RightChild)進入f的右子樹，并重復以上過程。在遞歸算法執(zhí)行過程中，輔助實現(xiàn)遞歸調用和返回處理的控制棧實際上起著保

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

32、用以下代碼表示一直沿左孩子指針鏈向下走的處理，臨時指針q用于在鏈棧中加入新元素時使用。處理思路是：若當前節(jié)點有左子樹，則將當前節(jié)點的指針存入棧中，然后進入當前節(jié)點的左子樹。入棧時，先申請元素在鏈棧中的節(jié)點空間，然后設置節(jié)點數(shù)據(jù)域的值(即當前節(jié)點的指針)，最后將新申請的節(jié)點加入鏈棧首部。 while (ptr!=ULL) q=(StNode *) malloc (sizeof (StNode)；/*為新入棧的元素創(chuàng)建節(jié)點*/ if (q= =NULL) /*若創(chuàng)建新節(jié)點失敗，則退出*/ return-1； q-elem=ptr； /*在棧頂保存指向當前節(jié)點的指針*/ q-link=stackto

33、p； /*新節(jié)點加入棧頂*/ stacktop=q； /*更新棧頂指針，即stacktop指向新的棧頂*/ ptr=ptr-1child /*進入當前節(jié)點的左子樹*/ 當上述過程進入一棵空的子樹時(ptr為空指針)，循環(huán)結束。此后，應該從空的子樹返回其父節(jié)點并進行訪問。由于進入空的左子樹前已將其父節(jié)點指針壓入棧中，因此，棧頂元素即為該父節(jié)點，對應的處理就是彈棧。相應地，在鏈棧中要刪除表頭節(jié)點并釋放節(jié)點空間。 q=stacktop； /*q指向鏈棧中需要刪除的節(jié)點，即棧頂元素*/ stack=stacktop-link； /*棧頂元素出棧*/ visit(q)； /*訪問節(jié)點*/ free(q)

34、； /*釋放節(jié)點空間*/ 由于還需要通過q指針進入被刪除節(jié)點的右子樹，因此，釋放節(jié)點空間的操作free(q)操作之前，使ptr指向q所指節(jié)點的右子樹指針，以得到被刪除節(jié)點的數(shù)據(jù)域信息，即空(5)所在語句ptr=q-elem-rchild。 指針是C語言中靈活且非常強大的工具，是否熟練掌握C語言的判斷條件之一就是對指針的理解和使用。軟件設計師需要熟練掌握這些內容。 參考答案 (1)ptr!=NULL，或ptr!=0，或ptr (2)q-link=stacktop (3)ptr-lchild (4)smcktop=stacktop-link，或stacktop=q-link (5)q-elem-r

35、child 試題六 閱讀下列說明和C+代碼，將應填入 (n) 處的字句寫在答題紙的對應欄內。 說明 現(xiàn)欲實現(xiàn)一個圖像瀏覽系統(tǒng)，要求該系統(tǒng)能夠顯示BMP、JPEG和GIF三種格式的文件，并且能夠在Windows和Linux兩種操作系統(tǒng)上運行。系統(tǒng)首先將BMP、JPEG和 GIF三種格式的文件解析為像素矩陣，然后將像素矩陣顯示在屏幕上。系統(tǒng)需具有較好的擴展性以支持新的文件格式和操作系統(tǒng)。為滿足上述需求并減少所需生成的子類數(shù)目，采用橋接(Bridge)設計模式進行設計，所得類圖如下圖所示。 采用該設計模式的原因在于：系統(tǒng)解析BMP、GIF與JPEG文件的代碼僅與文件格式相關，而在屏幕上顯示像素矩陣的

36、代碼則僅與操作系統(tǒng)相關。 C+代碼 class Matrix / / 各種格式的文件最終都被轉化為像素矩陣 / / 此處代碼省略 ； class Imagelmp public： virtual void doPaint (Matrix m)=0； / / 顯示像素矩陣m ； class WinImp ：public ImageImp public： void doPaint (Matrix m) /*調用Windows系統(tǒng)的繪制函數(shù)繪制像素矩陣*/) ； class LinuxImp : public ImageImp public: void doPaint(Matrix m) /*調用

37、Linux系統(tǒng)的繪制函數(shù)繪制像素矩陣*/ ; class Image public: void setImp (ImageImp *imp) (1)this imp = imp; virtual void parse File(string file Name) = 0; protected: (2) ImageImp *imp; ; class BMP : public Image public:void parse File(string file Name) / / 此處解析BMP文件并獲得一個像素矩陣對象m (3) imp-doPaint(m) ;/ / 顯示像素矩陣m ; class

38、 GIF : public Image / / 此處代碼省略 ; class JPEG : public Image / / 此處代碼省略 ; void main() /在Windows操作系統(tǒng)上查看demo. bmp圖像文件 Image *imagel = (4)new BMP() ; ImageImp *imageImpl = (5) new WinImp() ; (6) imagel-setImp(imageImpl) ; imagel-parseFile("demo.bmp")； (7)17 現(xiàn)假設該系統(tǒng)需要支持10種格式的圖像文件和5種操作系統(tǒng)，不考慮類Matri

39、x，若采用橋接設計模式則至少需要設計 (7) 個類。/(7)17 試題六分析 根據(jù)題目描述，在設計該圖像顯示系統(tǒng)時主要分為兩個步驟：一是讀取各種文件并將文件內容轉換成像素矩陣，因為各種圖片格式不同，因此需要針對每一種圖片格式編寫文件讀取代碼，而該代碼與操作系統(tǒng)平臺無關。將像素矩陣顯示到屏幕上時，由于和操作系統(tǒng)相關，因此需要把該代碼和讀取文件代碼相分離。設計中的Image類表示抽象的圖像概念，Image類中就包含了讀取文件接口和設置實現(xiàn)平臺接口：Image的子類BMP、 GIF和JPEG分別負責讀取各種不同格式的文件：ImageImp的主要任務是將像素矩陣顯示在屏幕上，因此，它存在兩個子類，分別

40、實現(xiàn)Windows系統(tǒng)和Linux系統(tǒng)上的圖像顯示代碼?？杖?1)處主要是設置將在哪個平臺上進行實現(xiàn)，因此該處應該存儲參數(shù)所傳遞的對象，由于該類的成員變量也是imp，與參數(shù)相同，因此需要填寫this-imp；同理，該成員變量的類型和參數(shù)的類型應該保持相同，空(2)處應該填寫ImageImp；空(3)處需要根據(jù)imp成員變量存儲的實現(xiàn)對象來顯示圖像：在空(4)處需要生成一個BMP對象；由于需要在Windows平臺上實現(xiàn)，因此空(5)處需要生成一個WinImp對象，同時，還需設置該BMP對象，應采用WinImp對象來實現(xiàn)顯示。采用橋接模式能夠將文件分析代碼和圖像顯示代碼分解在不同的類層次結構中，如

41、果不考慮中間使用的Matrix等類，那么最后需要設計的類包括2個父類，對應文件格式子類，對應操作系統(tǒng)平臺類，因此10種圖像格式和5種操作系統(tǒng)需要17個類。 參考答案 (1)this-imp (2)ImageImp (3)imp-doPaint(m) (4)new BMP() (5)new WinImp() (6)imagel-setImp(imageImpl) (7)17試題七閱讀下列說明和Java代碼，將應填入 (n) 處的字句寫在答題紙的對應欄內。 說明 現(xiàn)欲實現(xiàn)一個圖像瀏覽系統(tǒng)，要求該系統(tǒng)能夠顯示BMP、JPEG和GIF三種格式的文件，并且能夠在Windows和Linux兩種操作系統(tǒng)上運

42、行。系統(tǒng)首先將BMP、JPEG和 GIF三種格式的文件解析為像素矩陣，然后將像素矩陣顯示在屏幕上。系統(tǒng)需具有較好的擴展性以支持新的文件格式和操作系統(tǒng)。為滿足上述需求并減少所需生成的子類數(shù)目，采用橋接(Bridge)設計模式進行設計，所得類圖如下圖所示。 采用該設計模式的原因在于：系統(tǒng)解析BMP、GIF與JPEG文件的代碼僅與文件格式相關，而在屏幕上顯示像素矩陣的代碼則僅與操作系統(tǒng)相關。 Java代碼 class Matrix / /各種格式的文件最終都被轉化為像素矩陣 / /此處代碼省略 ； abstract class lmageImp public abstract void doPaint(Matrix m)； / /顯示像素矩陣m ； class WinImp extends ImageImp public void do Paint(Matrix m) /*調用Windows系統(tǒng)的繪制函數(shù)繪制像素矩陣*/ ； class Linuxlmp extends ImageImp public void do Paint(Matrix m)/*調用Linux系統(tǒng)的繪制函數(shù)繪制像素矩陣*/) ； abstract