2024年上半年軟件設(shè)計師下午試題及答案解析

全國計算機技術(shù)與軟件專業(yè)技術(shù)資格（水平）考試

上六個月

軟件設(shè)計師

下午試卷試題壹閱讀下列闡明，回答問題1和問題2，將解答填入答題紙的對應(yīng)欄內(nèi)。[闡明]假設(shè)某大型商業(yè)企業(yè)由商品配送中心和連鎖超市構(gòu)成，其中商品配送中心包括采購、財務(wù)、配送等部門。為實現(xiàn)高效管理，設(shè)計了商品配送中心信息管理系統(tǒng)，其重要功能描述如下：1．系統(tǒng)接受由連鎖超市提出的供貨祈求，并將其記錄到供貨祈求記錄文獻。2．在接到供貨祈求後，從商品庫存記錄文獻中進行商品庫存信息查詢。假如庫存滿足供貨祈求，則給配送處剪發(fā)送配送告知：否則，向采購部門發(fā)出缺貨告知。3．配送處理接到配送告知後，查詢供貨祈求記錄文獻，更新商品庫存記錄文獻，并向配送部門發(fā)送配送單，在配送貨品的同步記錄配送信息至商品配送記錄文獻。4．采購部門接到缺貨告知後，與供貨商洽談，進行商品采購處理，合格商品入庫，并記錄采購清單至采購清單記錄文獻、向配送處剪發(fā)出配送告知，同步告知財務(wù)部門給供貨商支付貨款。該系統(tǒng)采用構(gòu)造化措施進行開發(fā)，得到待修改的數(shù)據(jù)流圖如下圖所示。[問題1]使用[闡明]中的詞語，給出上圖中外部實體E1至E4的名稱和數(shù)據(jù)存儲D1至D4的名稱。答：E1：財務(wù)部門E2：采購部門E3：連鎖超市E4：配送部門D1：采購清單記錄文獻D2：商品庫存記錄文獻D3：商品配送記錄文獻D4：供貨祈求記錄文獻[問題2]以上數(shù)據(jù)流圖中存在到處錯誤數(shù)據(jù)流，請指出各自的起點和終點；若將上述四條錯誤數(shù)據(jù)流刪除，為保證數(shù)據(jù)流圖的對的性，應(yīng)補充三條數(shù)據(jù)流，請給出所補充數(shù)據(jù)流的起點和終點。(起點和終點請采用上述數(shù)據(jù)流圖中的符號或名稱)答：錯誤數(shù)據(jù)流補充的數(shù)據(jù)流試題壹分析本題考察DFD的分析與設(shè)計，問題壹重要考察DFD中的外部實體和數(shù)據(jù)存儲，由于在題干中已經(jīng)提到“系統(tǒng)接受由連鎖超市提出的供貨祈求，并將其記錄到供貨祈求記錄文獻”，因此可以明確出“連鎖超市”外部實體和“供貨祈求記錄文獻”數(shù)據(jù)存儲：對應(yīng)到DFD圖中為E3和D4。描述中的第二項提出“從商品庫存記錄文獻中進行商品庫存信息查詢。假如庫存滿足供貨祈求，則給配送處發(fā)送配送告知；否則，向采購部門發(fā)出缺貨告知”，由于配送告知需要發(fā)送到采購部門，因此采購部門將成為系統(tǒng)的外部實體；同步，商品庫存記錄文獻可以提供庫存信息，因此DFD圖中E2和D2分別為采購部門和商品配送記錄文獻。第三項需求“配送處理接到配送告知後，查詢供貨祈求記錄文獻，更新商品庫存記錄文獻，并向配送部門發(fā)送配送單，在配送貨品的同步記錄配送信息至商品配送記錄文獻”，因此配送處理需要查詢供貨祈求記錄文獻，更新商品庫存記錄文獻與商品配送記錄文獻，因此D3為商品配送記錄文獻；采購處理需要記錄采購清單同步告知財務(wù)部門，因此E1應(yīng)當為財務(wù)部門，D1為采購清單記錄文獻，剩余的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，將解答填入答題紙的對應(yīng)欄內(nèi)。[闡明]某集團企業(yè)擁有多種大型連鎖商場，企業(yè)需要構(gòu)建壹種數(shù)據(jù)庫系統(tǒng)以以便管理其業(yè)務(wù)運作活動。[需求分析成果]1．商場需要記錄的信息包括商場編號(編號唯壹)，商場名稱，地址和聯(lián)絡(luò)電話。某商場信息如下表所示。商場信息表2．每個商場包具有不壹樣的部門，部門需要記錄的信息包括部門編號(集團企業(yè)分派)，部門名稱，位置分布和聯(lián)絡(luò)電話。某商場的部門信息如下表所示。部門信息表3．每個部門雇用多名員工處理平常事務(wù)，每名員工只能從屬于壹種部門(新進員工在培訓期不從屬于任何部門)。員工需要記錄的信息包括員工編號(集團企業(yè)分派)，姓名，崗位，電話號碼和工資。員工信息如下表所示。員工信息表4．每個部門的員工中有壹名是經(jīng)理，每個經(jīng)理只能管理壹種部門，系統(tǒng)需要記錄每個經(jīng)理的任職時間。[概念模型設(shè)計]根據(jù)需求階段搜集的信息，設(shè)計的實體聯(lián)絡(luò)圖和關(guān)系模式(不完整)如下：實體聯(lián)絡(luò)圖[關(guān)系模式設(shè)計]商場(商場編號，商場名稱，地址，聯(lián)絡(luò)電話)部門(部門編號，部門名稱，位置分布，聯(lián)絡(luò)電話，(a))//a:商場編號員工(員工編號，員工姓名，崗位，電話號碼，工資，(b))//b:部門編號經(jīng)理((c)，任職時間)//c:員工編號[問題1]根據(jù)問題描述，補充四個聯(lián)絡(luò)，完善圖2—1的實體聯(lián)絡(luò)圖。聯(lián)絡(luò)名可用聯(lián)絡(luò)1、聯(lián)絡(luò)2、聯(lián)絡(luò)3和聯(lián)絡(luò)4替代，聯(lián)絡(luò)的類型分為1:1、1:n和m:n。答：[問題2]根據(jù)實體聯(lián)絡(luò)圖，將關(guān)系模式中的空(a)～(c)補充完整，并分別給出部門、員工和經(jīng)理關(guān)系模式的主鍵和外鍵。[問題3]為了使商場有緊急事務(wù)時能聯(lián)絡(luò)到輪休的員工，規(guī)定每位員工必須且只能登記壹位緊急聯(lián)絡(luò)人的姓名和聯(lián)絡(luò)電話，不壹樣的員工可以登記相似的緊急聯(lián)絡(luò)人。則在圖2—1中還需添加的實體是(1)，該實體和圖2-1中的員工存在(2//登記)聯(lián)絡(luò)(填寫聯(lián)絡(luò)類型)。給出該實體的關(guān)系模式。答：緊急聯(lián)絡(luò)人(員工編號，姓名，聯(lián)絡(luò)電話)試題二分析本題考察數(shù)據(jù)庫概念構(gòu)造設(shè)計及概念構(gòu)造向邏輯構(gòu)造轉(zhuǎn)換的過程。此類題目規(guī)定考生認真閱讀題目對現(xiàn)實問題的描述，通過度類、匯集和概括等措施從中確定實體及其聯(lián)絡(luò)。題目已經(jīng)給出了4個實體，需要根據(jù)需求描述給出實體間的聯(lián)絡(luò)。[問題1]由“每個商場包具有不壹樣的部門”可知商場與部門間為1:m聯(lián)絡(luò)；由“每個部門雇用了多名員工處理平常事務(wù)”可知部門與員工間為1:p聯(lián)絡(luò)；由“每個部門的員工中有壹種經(jīng)理……每個經(jīng)理只能管理壹種部門”可知部門與經(jīng)理間為1:1聯(lián)絡(luò)，并且員工是經(jīng)理的超類型，經(jīng)理是員工的子類型。[問題2]商場的屬性信息中，商場編號由集團企業(yè)分派，不會反復，可作為商場的主鍵屬性；部門的屬性信息中，部門編號由集團企業(yè)分派，不會反復，可作為部門的主鍵屬性，商場與部門的聯(lián)絡(luò)需要通過將商場的主鍵(商場編號)加入到部門中來體現(xiàn)；員工的屬性信息中，員工編號由集團企業(yè)分派，不會反復，可作為員工的主鍵屬性，部門與員工的聯(lián)絡(luò)需要通過將部門的主鍵(部門編號)加入到員工中來體現(xiàn)；經(jīng)理除了包括員工的屬性信息外，還需要任職時間屬性。完整的關(guān)系模式如下：商場(商場編號，商場名稱，地址，聯(lián)絡(luò)電話)部門(部門編號，部門名稱，位置分布，聯(lián)絡(luò)電話，商場編號)員工(員工編號，姓名，崗位，電話號碼，工資，部門編號)經(jīng)理(員工編號，任職時間)[問題3]員工的緊急聯(lián)絡(luò)人信息通過添加緊急聯(lián)絡(luò)人關(guān)系來實現(xiàn)，由“每位員工必須且只能登記壹位緊急聯(lián)絡(luò)人的姓名和聯(lián)絡(luò)電話”，但也許存在多位員工登記同壹位家眷，可知員工與家眷間為n:1聯(lián)絡(luò)：由“不壹樣員工可以登記相似的緊急聯(lián)絡(luò)人”可知，員工編號可作為家眷的主鍵屬性。因此需要添加的關(guān)系模式如下：緊急聯(lián)絡(luò)人(員工編號，姓名，聯(lián)絡(luò)電話)參照答案[問題1](圖中的m、n也可用*表達，對聯(lián)絡(luò)名稱可不做規(guī)定，但不能出現(xiàn)重名)[問題2](a)商場編號(b)部門編號(c)員工編號部門關(guān)系模式的主鍵：部門編號外鍵：商場編號員工關(guān)系模式的主鍵：員工編號外鍵：部門編號經(jīng)理關(guān)系模式的主鍵：員工編號外鍵：員工編號[問題3](d)緊急聯(lián)絡(luò)人(e)1:n關(guān)系模式：緊急聯(lián)絡(luò)人(員工編號，姓名，聯(lián)絡(luò)電話)試題三閱讀下列闡明和圖，回答問題1至問題3，將解答填入答題紙的對應(yīng)欄內(nèi)。[闡明]某銀行計劃開發(fā)壹種自動存提款機模擬系統(tǒng)(ATMSystem)。系統(tǒng)通過讀卡器(CardReader)讀取ATM卡；系統(tǒng)與客戶(Customer)的交互由客戶控制臺(Customer-Console)實現(xiàn)；銀行操作員(Operator)可控制系統(tǒng)的啟動(SystemStartup)和停止(SystemShutdown)：系統(tǒng)通過網(wǎng)絡(luò)和銀行系統(tǒng)(Bank)實現(xiàn)通信。當讀卡器判斷顧客已將ATM卡插入後，創(chuàng)立會話(Session)。會話開始後，讀卡器進行讀卡，并規(guī)定客戶輸入個人驗證碼(PIN)。系統(tǒng)將卡號和個人驗證碼信息送到銀行系統(tǒng)進行驗證。驗證通過後，客戶可從菜單項選擇擇如下事務(wù)(Transaction)：1．從ATM卡賬戶取款(Withdraw)；2．向ATM卡賬尸存款(Deposit)；3．進行轉(zhuǎn)賬(Transfer)：4．查詢(Inquire)ATM卡賬戶信息。壹次會話可以包括多種事務(wù)，每個事務(wù)處理也會將卡號和個人驗證碼信息送到銀行系統(tǒng)進行驗證。若個人驗證碼錯誤，則轉(zhuǎn)個人驗證碼錯誤處理(InvalidPINProcess)。每個事務(wù)完畢後，客戶可選擇繼續(xù)上述事務(wù)或退卡。選擇退卡時，系統(tǒng)彈出ATM卡，會話結(jié)束。系統(tǒng)采用面向?qū)ο蟠胧╅_發(fā)，使用UML進行建模。系統(tǒng)的頂層用例圖如圖3-1所示，壹次會話的序列圖(不考慮驗證)如圖3-2所示。[問題1]根據(jù)[闡明]中的描述，給出圖3-1中A1和A2所對應(yīng)的參與者，U1至U3所對應(yīng)的用例，以及該圖中空(1)所對應(yīng)的關(guān)系。(U1至U3的可選用例包括：Session、Transaction、InsertCard、InvalidPINProcess和Transfer)答：A1：CustomerA2：BankU1：SessionU2：InvalidPINProcessU3：Transaction(1)：＜＜extend＞＞[問題2]根據(jù)[闡明]中的描述，使用消息名稱列表中的英文名稱，給出圖3-2中6～9對應(yīng)的消息。答：6：readPIN()7:PIN8:creat(atm,this,card,pin)9:preformTransaction()[問題3]解釋圖3-1中用例U3和用例Withdraw、Deposit等四個用例之間的關(guān)系及其內(nèi)涵。答：Transaction是壹種抽象泛化用例，具有其他事務(wù)類型共有的屬性和行為，每個詳細的事務(wù)類型繼承它，并實現(xiàn)適合自已的特定的操作。試題三分析本題波及面向?qū)ο笙到y(tǒng)開發(fā)時的UML用例圖、序列圖以及用例之間的關(guān)系。[問題1]構(gòu)建用例圖時，常用的方式是先識別參與者，然後確定用例以及用例之間的關(guān)系。識別參與者時，考察和系統(tǒng)交互的人員和外部系統(tǒng)。本題中，與系統(tǒng)交互的人員包括客戶(Customer)和銀行操作員(Operator)，與本模擬系統(tǒng)交互的外部系統(tǒng)包括銀行。系統(tǒng)(Bank)?？疾煊美龝r，通過判斷哪壹種特定參與者發(fā)起或者觸發(fā)了與系統(tǒng)的哪些交互，宋識別用例并建立和參與者之間的關(guān)聯(lián)?？疾煊美g的關(guān)系時，＜＜include＞＞(包括)定義了用例之間的包括關(guān)系，用于壹種用例包括另壹種用例的行為的建模；假如可以從壹種用例的執(zhí)行中，在需要時轉(zhuǎn)向執(zhí)行另壹種用例，執(zhí)行完返回之前的用例繼續(xù)執(zhí)行，用例間即存在＜＜extend＞＞關(guān)系。本題中，客戶壹旦插卡成功，系統(tǒng)就創(chuàng)立會話(Session)，會話中可以執(zhí)行顧客從菜單項選擇擇的Withdraw、Deposit、Transfer和Inquire等事務(wù)(Transaction)。由圖中U3和Withdraw之間的擴展關(guān)系，可知U3為Transaction；又由U1和U3之間的＜＜include＞＞關(guān)系，得知U1為Session，進而鑒定圖中A1為Customer，A2為Bank。每個事務(wù)處理也會將卡號和個人驗證碼信息送到銀行系統(tǒng)進行驗證，若個人驗證碼錯誤，則轉(zhuǎn)個人驗證碼錯誤處理(1nvalidPINProcess，圖中U2)，因此(1)處應(yīng)填＜＜extend＞＞。[問題2]序列圖是場景的圖形化表達，描述了以時間次序組織的對象之間的交互活動。構(gòu)造序列圖時遵照如下指導原則：確定次序圖的范圍，描述這個用例場景或壹種環(huán)節(jié)；繪制參與者和接口類，假如范圍包括這些內(nèi)容的話：沿左手邊列出用例環(huán)節(jié)；對控制器類及必須在次序中協(xié)作的每個實體類，基于它擁有的屬性或已經(jīng)分派給它的行為繪制框；為持續(xù)類和系統(tǒng)類繪制框；繪制所需消息，并把每條消息指到將實現(xiàn)響應(yīng)消息的責任的類上；添加活動條指示每個對象實例的生命期；為清晰起見，添加所需的返回消息；假如需要，為循環(huán)、可選環(huán)節(jié)和替代環(huán)節(jié)等添加框架。本題中，根聽闡明中的描述，從ATM機判斷卡已插入(cardInserted())開始會話，即為目前ATM創(chuàng)立會話(create(this))并開始執(zhí)行會話(performSession())：讀卡器讀卡(readCard())獲得ATM卡信息(card)，然後從控制臺讀取個人驗證碼輸入(readPIN()，圖中標號6處)并獲得個人驗證碼信息(PIN，圖中標號7處)：然後根據(jù)顧客選擇啟動并執(zhí)行事務(wù)，即為目前會話創(chuàng)立事務(wù)(creat(atm，this，card，pin)，圖中標號8處)和執(zhí)行事務(wù)(performTransaction()，圖中標號9處)：可以選擇繼續(xù)執(zhí)行某個事務(wù)(doAgain)循環(huán)，或者選擇退卡(ejectCard())。[問題3]用例之間的繼承關(guān)系表達子類型“是壹種”父類型。其中父類型壹般是壹種抽象泛化用例，具有子類型共有的屬性和行為，每個詳細的子類型繼承它，并實現(xiàn)適合自已的特定的操作。本題中Transaction和Withdraw、Deposit等四個用例之間的關(guān)系即為繼承關(guān)系，Transaction即是壹種抽象泛化用例，具有其他事務(wù)類型共有的屬性和行為，每個詳細的事務(wù)類型繼承它，并實現(xiàn)適合自已的特定的操作。參照答案[問題1]A1：CustomerA2：BankU1：SessionU2：InvalidPINProcessU3：Transaction(1)：＜＜extend＞＞[問題2]6：readPIN()7：PIN8：creat(atm，this，card，pin)9：performTransaction()[問題3]Transaction是壹種抽象泛化用例，具有其他事務(wù)類型共有的屬性和行為，每個詳細的事務(wù)類型繼承它，并實現(xiàn)適合自已的特定的操作。試題四閱讀下列闡明，回答問題1和問題2，將解答填入答題紙的對應(yīng)欄內(nèi)。[闡明]現(xiàn)需在某都市中選擇壹種小區(qū)建壹種大型超市，使該都市的其他小區(qū)到該超市的距離總和最小。用圖模型表達該都市的地圖，其中頂點表達小區(qū)，邊表達小區(qū)間的路線，邊上的權(quán)重表達該路線的長度。現(xiàn)設(shè)計壹種算法來找到該大型超市的最佳位置：即在給定圖中選擇壹種頂點，使該頂點到其他各頂點的最短途徑之和最小。算法首先需規(guī)定出每個頂點到其他任壹頂點的最短途徑，即需要計算任意兩個頂點之間的最短途徑；然後對每個頂點，計算其他各頂點到該頂點的最短途徑之和；最終，選擇最短途徑之和最小的頂點作為建大型超市的最佳位置。[問題1]本題采用F10y-Warshall算法求解任意兩個頂點之間的最短途徑。已知圖G的頂點集合為V={1,2，…，n)，W={Wjj}n*n。為權(quán)重矩陣。設(shè)為從頂點i到頂點j的壹條最短途徑的權(quán)重。當k=0時，不存在中間頂點，因此=Wij：當k＞0時，該最短途徑上所有的中間頂點均屬于集合{1,2，…，k}。若中間頂點包括頂點k，則；若中間頂點不包括頂點k，則。于是得到如下遞歸式。由于對于任意途徑，所有的中間頂點都在集合{1,2，…，n}內(nèi)，因此矩陣給出了任意兩個頂點之間的最短途徑，即對所有I,j∈V，表達頂點i到頂點j的最短途徑。下面是求解該問題的偽代碼，請?zhí)畛淦渲锌杖钡?1)至(6)處。偽代碼中的重要變量闡明如下：W：權(quán)重矩陣n：圖的頂點個數(shù)SP：最短途徑權(quán)重之和數(shù)組，SP[i]表達頂點i到其他各頂點的最短途徑權(quán)重之和，i從1到nmin_SP：最小的最短途徑權(quán)重之和min_V：具有最小的最短途徑權(quán)重之和的頂點i：循環(huán)控制變量j：循環(huán)控制變量k：循環(huán)控制變量LOCATE-SHOPPINGMALL(W,n)1D(0)=W2for(1)//k=1ton3fori=1ton4forj=1ton6(2)//7else8(3)//9fori=1ton10SP[i]=011forj=1ton12(4)//SP[i]=SP[i]+13minSP=SP[1]14(5)//minv=115fori=2ton16ifminSP＞SP[i]17minSP=SP[i]18minv=i19return(6)//minv[問題2][問題1]中偽代碼的時間復雜度為(7)(用O符號表達)。//(7)O(n3)試題四分析本題考察的是算法的設(shè)計和分析技術(shù)。[問題1]本問題考察算法流程。第(1)空表達主循環(huán)，k是循環(huán)控制變量，故第(1)空填k=1ton。第(2)和(3)空根據(jù)題意和遞歸式，可分別得到答案為)和。計算了任意兩個頂點之間的最短途徑之後，對每個頂點，開始記錄其到所有其他頂點的最短途徑之和，因此第(4)空填SP[i]=SP[i]+。第13和第14行初始化，假設(shè)最小的到所有其他頂點的最短途徑之和為第壹種頂點的最小途徑之和，大型超市的最佳位置為第壹種頂點，故第(5)空填minv=1。最終規(guī)定返回大型超市的最佳位置，即到所有其他頂點的最短途徑之和最小的頂點，故第(6)空填minv。[問題2]本問題考察[問題門中的偽代碼第2～8行，計算任意兩點之間的最短途徑，有三重循環(huán)，故時間復雜度為O(n3)。第9～12行，計算每個點到任意其他點的最短途徑之和，有兩重循環(huán)，故時間復雜度為O(n2)。第15～18行，在所有點的最短途徑之和中找到最小的最短途徑之和，時間復雜度為O(n)。故算法總的時間復雜度為O(n3)。參照答案[問題1](1)k=1ton(2)(3)(4)SP[i]=SP[i]+(5)min_v=1(6)min_v[問題2](7)O(n3)試題五閱讀下列闡明和C函數(shù)代碼，將應(yīng)填入(n)處的字句寫在答題紙的對應(yīng)欄內(nèi)。[闡明]對二叉樹進行遍歷是二叉樹的壹種基本運算。遍歷是指按某種方略訪問二叉樹的每個節(jié)點，且每個節(jié)點僅訪問壹次的過程。函數(shù)InOrder()借助棧實現(xiàn)二叉樹的非遞歸中序遍歷運算。設(shè)二叉樹采用二叉鏈表存儲，節(jié)點類型定義如下：typedefstructBtNode{ElemTypedata；/*節(jié)點的數(shù)據(jù)域，ElemType的詳細定義省略*/structBtNode*lchild*rchild；/*節(jié)點的左、右孩子指針域*/}BtNode，*BTree；在函數(shù)InOrder()中，用棧暫存二叉樹中各個節(jié)點的指針，并將棧表達為不含頭節(jié)點的單向鏈表(簡稱鏈棧)，其節(jié)點類型定義如下：typedefstructStNode{/*鏈棧的節(jié)點類型*/BTreeelem；/*棧中的元素是指向二叉鏈表節(jié)點的指針*/structStNode*link；}StNode；假設(shè)從棧頂?shù)綏５椎脑貫閑n、en-1…、e1，則不含頭節(jié)點的鏈棧示意圖如圖5-1所示。圖5-1鏈棧示意圖[C函數(shù)]intInOrder(BTreeroot)/*實現(xiàn)二叉樹的非遞歸中序遍歷*/{BTreeptr；/*ptr用于指向二叉樹中的節(jié)點*/StNode*q；/*q暫存鏈棧中新創(chuàng)立或待刪除的節(jié)點指針*/StNode*stacktop=NULL；/*初始化空棧的棧頂指針stacktop*/Ptr=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；/*棧頂元素出棧*/visit(q)；/*visit是訪問節(jié)點的函數(shù)，其詳細定義省略*/ptr=(5)q-＞elem-＞rchild；/*進入右子樹*/free(q)；/*釋放原棧頂元素的節(jié)點空間*/}return0；}/*Inorder*/試題五分析本題考察基本數(shù)據(jù)構(gòu)造和C語言程序設(shè)計能力。對非空二叉樹進行中序遍歷的措施是：先中序遍歷根節(jié)點的左子樹，然後訪問根節(jié)點，最終中序遍歷根節(jié)點的右子樹。用遞歸方式描述的算法如下：voidIn_order_Traversing(BiTreeroot){//root是指向二叉樹根節(jié)點的指針if(root!=NULL){In_order_Traversing(root-＞LeftChild)；visit(root)；In_order_Traversing(root—＞RightChild)；}}從以上算法的執(zhí)行過程可知，從樹根出發(fā)進行遍歷時，遞歸調(diào)用In_Order_Traversing(root-＞LeftChild)使得遍歷過程沿著左孩子分支壹直走向下層節(jié)點，直到抵達二叉樹中最左下方的節(jié)點(設(shè)為f)的空左子樹為止，然後返回f節(jié)點，再由遞歸調(diào)用In_Order_Traversing(root-＞RightChild)進入f的右子樹，并反復以上過程。在遞歸算法執(zhí)行過程中，輔助實現(xiàn)遞歸調(diào)用和返回處理的控制棧實際上起著保留從根節(jié)點到目前節(jié)點的途徑信息。用非遞歸算法實現(xiàn)二叉樹的中序遍歷時，可以由壹種循環(huán)語句實現(xiàn)從指定的根節(jié)點出發(fā)，沿著左孩子分支壹直到頭(抵達壹種沒有左子樹的節(jié)點)的處理，從根節(jié)點到目前節(jié)點的途徑信息(節(jié)點序列)可以明確構(gòu)造壹種棧來保留。本題目的難點在于將棧的實現(xiàn)和使用混合在壹起來處理，并且棧采用單鏈表存儲構(gòu)造。下面分析題中給出的代碼?？?1)是遍歷的條件之壹，由于此外壹種條件stacktop!=ULL初始時是不成立的，因此空(1)所示的條件必須滿足，由于是對非空二叉樹進行遍歷，顯然該條件代表二叉樹非空，即ptr!=ULL或其等價表達形式。臨時指針ptr初始時指向整個二叉樹的根節(jié)點，此後用如下代碼表達壹直沿左孩子指針鏈向下走的處理，臨時指針q用于在鏈棧中加入新元素時使用。處理思緒是：若目前節(jié)點有左子樹，則將目前節(jié)點的指針存入棧中，然後進入目前節(jié)點的左子樹。入棧時，先申請元素在鏈棧中的節(jié)點空間，然後設(shè)置節(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=stacktop；/*新節(jié)點加入棧頂*/stacktop=q；/*更新棧頂指針，即stacktop指向新的棧頂*/ptr=ptr-＞1child/*進入目前節(jié)點的左子樹*/}當上述過程進入壹棵空的子樹時(ptr為空指針)，循環(huán)結(jié)束。此後，應(yīng)當從空的子樹返回其父節(jié)點并進行訪問。由于進入空的左子樹前已將其父節(jié)點指針壓入棧中，因此，棧頂元素即為該父節(jié)點，對應(yīng)的處理就是彈棧。對應(yīng)地，在鏈棧中要刪除表頭節(jié)點并釋放節(jié)點空間。q=stacktop；/*q指向鏈棧中需要刪除的節(jié)點，即棧頂元素*/stack=stacktop-＞link；/*棧頂元素出棧*/visit(q)；/*訪問節(jié)點*/free(q)；/*釋放節(jié)點空間*/由于還需要通過q指針進入被刪除節(jié)點的右子樹，因此，釋放節(jié)點空間的操作free(q)操作之前，使ptr指向q所指節(jié)點的右子樹指針，以得到被刪除節(jié)點的數(shù)據(jù)域信息，即空(5)所在語句ptr=q-＞elem-＞rchild。指針是C語言中靈活且非常強大的工具，與否純熟掌握C語言的判斷條件之壹就是對指針的理解和使用。軟件設(shè)計師需要純熟掌握這些內(nèi)容。參照答案(1)ptr!=NULL，或ptr!=0，或ptr(2)q-＞link=stacktop(3)ptr-＞lchild(4)smcktop=stacktop-＞link，或stacktop=q-＞link(5)q-＞elem-＞rchild試題六閱讀下列闡明和C++代碼，將應(yīng)填入(n)處的字句寫在答題紙的對應(yīng)欄內(nèi)。[闡明]現(xiàn)欲實現(xiàn)壹種圖像瀏覽系統(tǒng)，規(guī)定該系統(tǒng)可以顯示BMP、JPEG和GIF三種格式的文獻，并且可以在Windows和Linux兩種操作系統(tǒng)上運行。系統(tǒng)首先將BMP、JPEG和GIF三種格式的文獻解析為像素矩陣，然後將像素矩陣顯示在屏幕上。系統(tǒng)需具有很好的擴展性以支持新的文獻格式和操作系統(tǒng)。為滿足上述需求并減少所需生成的子類數(shù)目，采用橋接(Bridge)設(shè)計模式進行設(shè)計，所得類圖如下圖所示。采用該設(shè)計模式的原因在于：系統(tǒng)解析BMP、GIF與JPEG文獻的代碼僅與文獻格式有關(guān)，而在屏幕上顯示像素矩陣的代碼則僅與操作系統(tǒng)有關(guān)。[C++代碼]classMatrix{//多種格式的文獻最終都被轉(zhuǎn)化為像素矩陣//此處代碼省略}；classImagelmp{public：virtualvoiddoPaint(Matrixm)=0；//顯示像素矩陣m}；classWinImp：publicImageImp{public：voiddoPaint(Matrixm){/*調(diào)用Windows系統(tǒng)的繪制函數(shù)繪制像素矩陣*/)}；classLinuxImp:publicImageImp{public:voiddoPaint(Matrixm){/*調(diào)用Linux系統(tǒng)的繪制函數(shù)繪制像素矩陣*/}};classImage{public:voidsetImp(ImageImp*imp){(1)thisimp=imp;}virtualvoidparseFile(stringfileName)=0;protected:(2)ImageImp*imp;};classBMP:publicImage{public:voidparseFile(stringfileName){//此處解析BMP文獻并獲得壹種像素矩陣對象m(3)imp-＞doPaint(m);//顯示像素矩陣m}};classGIF:publicImage{//此處代碼省略};classJPEG:publicImage{//此處代碼省略};voidmain(){//在Windows操作系統(tǒng)上查看demo.bmp圖像文獻Image*imagel=(4)newBMP();ImageImp*imageImpl=(5)newWinImp();(6)imagel-＞setImp(imageImpl);imagel-＞parseFile("demo.bmp")；}(7)17現(xiàn)假設(shè)該系統(tǒng)需要支持10種格式的圖像文獻和5種操作系統(tǒng)，不考慮類Matrix，若采用橋接設(shè)計模式則至少需要設(shè)計(7)個類。//(7)17試題六分析根據(jù)題目描述，在設(shè)計該圖像顯示系統(tǒng)時重要分為兩個環(huán)節(jié)：壹是讀取多種文獻并將文獻內(nèi)容轉(zhuǎn)換成像素矩陣，由于多種圖片格式不壹樣，因此需要針對每壹種圖片格式編寫文獻讀取代碼，而該代碼與操作系統(tǒng)平臺無關(guān)。將像素矩陣顯示到屏幕上時，由于和操作系統(tǒng)有關(guān)，因此需要把該代碼和讀取文獻代碼相分離。設(shè)計中的Image類表達抽象的圖像概念，Image類中就包括了讀取文獻接口和設(shè)置實現(xiàn)平臺接口：Image的子類BMP、GIF和JPEG分別負責讀取多種不壹樣格式的文獻：ImageImp的重要任務(wù)是將像素矩陣顯示在屏幕上，因此，它存在兩個子類，分別實現(xiàn)Windows系統(tǒng)和Linux系統(tǒng)上的圖像顯示代碼?？杖?1)處重要是設(shè)置將在哪個平臺上進行實現(xiàn)，因此該處應(yīng)當存儲參數(shù)所傳遞的對象，由于該類的組員變量也是imp，與參數(shù)相似，因此需要填寫this-＞imp；同理，該組員變量的類型和參數(shù)的類型應(yīng)當保持相似，空(2)處應(yīng)當填寫ImageImp；空(3)處需要根據(jù)imp組員變量存儲的實現(xiàn)對象來顯示圖像：在空(4)處需要生成壹種BMP對象；由于需要在Windows平臺上實現(xiàn)，因此空(5)處需要生成壹種WinImp對象，同步，還需設(shè)置該BMP對象，應(yīng)采用WinImp對象來實現(xiàn)顯示。采用橋接模式可以將文獻分析代碼和圖像顯示代碼分解在不壹樣的類層次構(gòu)造中，假如不考慮中間使用的Matrix等類，那么最終需要設(shè)計的類包括2個父類，對應(yīng)文獻格式子類，對應(yīng)操作系統(tǒng)平臺類，因此10種圖像格式和5種操作系統(tǒng)需要17個類。參照答案(1)this-＞imp(2)ImageImp(3)imp-＞doPaint(m)(4)newBMP()(5)newWinImp()(6)imagel-＞setImp(imageImpl)(7)17試題七閱讀下列闡明和Java代碼，將應(yīng)填入(n)處的字句寫在答題紙的對應(yīng)欄內(nèi)。[闡明]現(xiàn)欲實現(xiàn)壹種圖像瀏覽系統(tǒng)，規(guī)定該系統(tǒng)可以顯示BMP、JPEG和GIF三種格式的文獻，并且可以在Windows和Linux兩種操作系統(tǒng)上運行。系統(tǒng)首先將BMP、JPEG和GIF三種格式的文獻解析為像素矩陣，然後將像素矩陣顯示在屏幕上。系統(tǒng)需具有很好的擴展性以支持新的文獻格式和操作系統(tǒng)。為滿足上述需求并減少所需生成的子類數(shù)目，采用橋接(Bridge)設(shè)計模式進行設(shè)計，所得類圖如下圖所示。采用該設(shè)計模式的原因在于：系統(tǒng)解析BMP、GIF與JPEG文獻的代碼僅與文獻格式有關(guān)，而在屏幕上顯示像素矩陣的代碼則僅與操作系統(tǒng)有關(guān)。[Java代碼]classMatrix{//多種格式的文獻最終都被轉(zhuǎn)化為像素矩陣//此處代碼省略}；abstractclasslmageImp{publicabstractvoiddoPaint(Matrixm)；//顯示像素矩陣m}；classWinImpextendsImageImp{publicvoiddoPaint(Matrixm){/*調(diào)用Windows系統(tǒng)的繪制函數(shù)繪制像素矩陣*/}}；classLinuxlmpextendsImageImp{publicvoiddoPaint(Matrixm){/*調(diào)用Linux系統(tǒng)的繪制函數(shù)繪制像素矩