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

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

上六個(gè)月

軟件設(shè)計(jì)師

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