第2題： 閱讀下列說明，回答問題1至問題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
某集團(tuán)公司擁有多個(gè)大型連鎖商場(chǎng)，公司需要構(gòu)建一個(gè)數(shù)據(jù)庫系統(tǒng)以方便管理其業(yè)務(wù)運(yùn)作活動(dòng)。
【需求分析結(jié)果】
1. 商場(chǎng)需要記錄的信息包括商場(chǎng)編號(hào)（編號(hào)唯一），商場(chǎng)名稱，地址和聯(lián)系電話。某商場(chǎng)信息如表2-1所示。
2-1商場(chǎng)信息表

2. 每個(gè)商場(chǎng)包含有不同的部門，部門需要記錄的信息包括部門編號(hào)（集團(tuán)公司分配），部門名稱，位置分布和聯(lián)系電話。某商場(chǎng)的部門信息如表2-2所示。
2-2部門信息表

3. 每個(gè)部門雇用多名員工處理日常事務(wù)，每名員工只能隸屬于一個(gè)部門（新進(jìn)員工在培訓(xùn)期不隸屬于任何部門）。員工需要記錄的信息包括員工編號(hào)（集團(tuán)公司分配），姓名，崗位，電話號(hào)碼和工資。員工信息如表2-3所示。
2-3員工信息表

4. 每個(gè)部門的員工中有一名是經(jīng)理，每個(gè)經(jīng)理只能管理一個(gè)部門，系統(tǒng)需要記錄每個(gè)經(jīng)理的任職時(shí)間。
【概念模型設(shè)計(jì)】
根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖和關(guān)系模式（不完整）如下：

【關(guān)系模式設(shè)計(jì)】
商場(chǎng)（商場(chǎng)編號(hào)，商場(chǎng)名稱，地址，聯(lián)系電話）
部門（部門編號(hào)，部門名稱，位置分布，聯(lián)系電話，（a）  ）
員工（員工編號(hào)，員工姓名，崗位，電話號(hào)碼，工資， （b）  ）

經(jīng)理（  （c）  ，任職時(shí)間）
【問題1】
根據(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】
根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中的空（a）~（c）補(bǔ)充完整，并分別給出部門、員工和經(jīng)理關(guān)系模式的主鍵和外鍵。
【問題3】
為了使商場(chǎng)有緊急事務(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)系模式。

答案解析與討論：www.jazzmuze.com/st/380781422.html

第3題： 閱讀下列說明和圖，回答問題1至問題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
某銀行計(jì)劃開發(fā)一個(gè)自動(dòng)存提款機(jī)模擬系統(tǒng)（ATM  System）。系統(tǒng)通過讀卡器（CardReader）讀取 ATM 卡；系統(tǒng)與客戶（Customer）的交互由客戶控制臺(tái)（CustomerConsole）實(shí)現(xiàn)；銀行操作員（Operator）可控制系統(tǒng)的啟動(dòng)（System Startup）和停止（System Shutdown）；系統(tǒng)通過網(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)將卡號(hào)和個(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ì)將卡號(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)彈出 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 所對(duì)應(yīng)的參與者，U1 至 U3 所對(duì)應(yīng)的用例，以及該圖中空 （1） 所對(duì)應(yīng)的關(guān)系。（U1至U3的可選用例包括：Session、Transaction、Insert CarD．Invalid PIN Process和Transfer）
【問題2】（6分）
根據(jù)【說明 】中的描述，使用表3-1中的英文名稱，給出圖3-2中6～9對(duì)應(yīng)的消息。
【問題3】（2分）

解釋圖3-1中用例U3和用例Withdraw、Deposit等四個(gè)用例之間的關(guān)系及其內(nèi)涵。

答案解析與討論：www.jazzmuze.com/st/380796383.html

第4題： 閱讀下列說明，回答問題1和問題2，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
現(xiàn)需在某城市中選擇一個(gè)社區(qū)建一個(gè)大型超市，使該城市的其它社區(qū)到該超市的距離總和最小。用圖模型表示該城市的地圖，其中頂點(diǎn)表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長(zhǎng)度?，F(xiàn)設(shè)計(jì)一個(gè)算法來找到該大型超市的最佳位置：即在給定圖中選擇一個(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)作為建大型超市的最佳位置。
【問題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的一條最短路徑的權(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)則d(k-1)ij=d(k-1)i于是得到如下遞歸式

因?yàn)閷?duì)于任意路徑，所有的中間頂點(diǎn)都在集合{1，2， ...， n｝ 內(nèi)，因此矩陣D(n)=｛d(n)ij｝n*n 給出了任意兩個(gè)頂點(diǎn)之間的最短路徑，即對(duì)所有i， j ∈V，d(n)ij表示頂點(diǎn)i到頂點(diǎn) j的最短路徑。
下面是求解該問題的偽代碼，請(qǐng)?zhí)畛淦渲锌杖钡?(1)至(6)處。 偽代碼中的主要變量說明如下：
W：權(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）用Ο 符號(hào)表示）。
答案解析與討論：www.jazzmuze.com/st/380806315.html