第1題： 假設(shè)某大型商業(yè)企業(yè)由商品配送中心和連鎖超市組成，其中商品配送中心包括采購(gòu)、財(cái)務(wù)、配送等部門。為實(shí)現(xiàn)高效管理，設(shè)計(jì)了商品配送中心信息管理系統(tǒng)，其主要功能描述如下：
1．系統(tǒng)接收由連鎖超市提出的供貨請(qǐng)求，并將其記錄到供貨請(qǐng)求記錄文件。
2．在接到供貨請(qǐng)求后，從商品庫(kù)存記錄文件中進(jìn)行商品庫(kù)存信息查詢。如果庫(kù)存滿足供貨請(qǐng)求，則給配送處理發(fā)送配送通知：否則，向采購(gòu)部門發(fā)出缺貨通知。
3．配送處理接到配送通知后，查詢供貨請(qǐng)求記錄文件，更新商品庫(kù)存記錄文件，并向配送部門發(fā)送配送單，在配送貨品的同時(shí)記錄配送信息至商品配送記錄文件。
4．采購(gòu)部門接到缺貨通知后，與供貨商洽談，進(jìn)行商品采購(gòu)處理，合格商品入庫(kù)，并記錄采購(gòu)清單至采購(gòu)清單記錄文件、向配送處理發(fā)出配送通知，同時(shí)通知財(cái)務(wù)部門給供貨商支付貨款。

該系統(tǒng)采用結(jié)構(gòu)化方法進(jìn)行開發(fā)，得到待修改的數(shù)據(jù)流圖如下圖所示。

?【問(wèn)題1】使用說(shuō)明中的詞語(yǔ)，給出上圖中外部實(shí)體E1至E4的名稱和數(shù)據(jù)存儲(chǔ)D1至D4的名稱。
?【問(wèn)題2】以上數(shù)據(jù)流圖中存在四處錯(cuò)誤數(shù)據(jù)流，請(qǐng)指出各自的起點(diǎn)和終點(diǎn)；若將上述四條錯(cuò)誤數(shù)據(jù)流刪除，為保證數(shù)據(jù)流圖的正確性，應(yīng)補(bǔ)充三條數(shù)據(jù)流，請(qǐng)給出所補(bǔ)充數(shù)據(jù)流的起點(diǎn)和終點(diǎn)。(起點(diǎn)和終點(diǎn)請(qǐng)采用上述數(shù)據(jù)流圖中的符號(hào)或名稱)
答案解析與討論：m.xiexiliangjiufa.com/st/380776272.html

第2題： 閱讀下列說(shuō)明，回答問(wèn)題1至問(wèn)題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
某集團(tuán)公司擁有多個(gè)大型連鎖商場(chǎng)，公司需要構(gòu)建一個(gè)數(shù)據(jù)庫(kù)系統(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í)間）
?【問(wèn)題1】
根據(jù)問(wèn)題描述，補(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。
?【問(wèn)題2】
根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中的空（a）~（c）補(bǔ)充完整，并分別給出部門、員工和經(jīng)理關(guān)系模式的主鍵和外鍵。
?【問(wè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)系模式。

答案解析與討論：m.xiexiliangjiufa.com/st/380781422.html

第4題： 閱讀下列說(shuō)明，回答問(wèn)題1和問(wèn)題2，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
現(xiàn)需在某城市中選擇一個(gè)社區(qū)建一個(gè)大型超市，使該城市的其它社區(qū)到該超市的距離總和最小。用圖模型表示該城市的地圖，其中頂點(diǎn)表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長(zhǎng)度?，F(xiàn)設(shè)計(jì)一個(gè)算法來(lái)找到該大型超市的最佳位置：即在給定圖中選擇一個(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)作為建大型超市的最佳位置。
【問(wè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的最短路徑。
下面是求解該問(wèn)題的偽代碼，請(qǐng)?zhí)畛淦渲锌杖钡?(1)至(6)處。 偽代碼中的主要變量說(shuō)明如下：
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)控制變量

【問(wèn)題2】（3分）
【問(wèn)題1】中偽代碼的時(shí)間復(fù)雜度為（7）用Ο 符號(hào)表示）。
答案解析與討論：m.xiexiliangjiufa.com/st/380806315.html

第5題： 閱讀下列說(shuō)明和C 函數(shù)代碼，將應(yīng)填入（n）處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
對(duì)二叉樹進(jìn)行遍歷是二叉樹的一個(gè)基本運(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)類型定義如下：
typedef struct BtNode{
ElemTypedata;/*結(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ǎn)稱鏈棧），其結(jié)點(diǎn)類型定義如下：
typedef struct StNode{  /*鏈棧的結(jié)點(diǎn)類型*/
BTree elem;  /*棧中的元素是指向二叉鏈表結(jié)點(diǎn)的指針*/
struct StNode *link;
}StNode;
假設(shè)從棧頂?shù)綏５椎脑貫?en、en-1、…、e1，則不含頭結(jié)點(diǎn)的鏈棧示意圖如圖 5-1所示。

【C函數(shù)】

答案解析與討論：m.xiexiliangjiufa.com/st/3808115165.html

第6題： 閱讀下列說(shuō)明和C++代碼，將應(yīng)填入 （n） 處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
現(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ì)所得類圖如圖6-1所示。

采用該設(shè)計(jì)模式的原因在于：系統(tǒng)解析BMP、GIF與JPEG文件的代碼僅與文件格式相關(guān)，而在屏幕上顯示像素矩陣的代碼則僅與操作系統(tǒng)相關(guān)。
【C++代碼】

現(xiàn)假設(shè)該系統(tǒng)需要支持10種格式的圖像文件和5種操作系統(tǒng)，不考慮類Matrix，若采用橋接設(shè)計(jì)模式則至少需要設(shè)計(jì)（7）個(gè)類。
答案解析與討論：m.xiexiliangjiufa.com/st/3808215536.html