第4題： 閱讀下列說明，回答問題1和問題2，將解答填入答題紙的對應(yīng)欄內(nèi)。
【說明】
現(xiàn)需在某城市中選擇一個社區(qū)建一個大型超市，使該城市的其它社區(qū)到該超市的距離總和最小。用圖模型表示該城市的地圖，其中頂點表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長度。現(xiàn)設(shè)計一個算法來找到該大型超市的最佳位置：即在給定圖中選擇一個頂點，使該頂點到其它各頂點的最短路徑之和最小。算法首先需要求出每個頂點到其它任一頂點的最短路徑，即需要計算任意兩個頂點之間的最短路徑；然后對每個頂點，計算其它各頂點到該頂點的最短路徑之和；最后，選擇最短路徑之和最小的頂點作為建大型超市的最佳位置。
?【問題1】（12分）
本題采用Floyd-Warshall算法求解任意兩個頂點之間的最短路徑。 已知圖G 的頂點集合為V= {1，2，...，n } ，W= ｛Wij｝n*n 為權(quán)重矩陣。設(shè) d (k)ij=為從頂點i到頂點 j的一條最短路徑的權(quán)重。當(dāng)k = 0時，不存在中間頂點，因此d(0)ij=wij當(dāng)k >0 時，該最短路徑上所有的中間頂點均屬于集合 {1，2， ...， k｝若中間頂點包括頂點 k ，則d(k)ij=d(k-1)ik+d(k-1)kj若中間頂點不包括頂點則d(k-1)ij=d(k-1)i于是得到如下遞歸式

因為對于任意路徑，所有的中間頂點都在集合{1，2， ...， n｝ 內(nèi)，因此矩陣D(n)=｛d(n)ij｝n*n 給出了任意兩個頂點之間的最短路徑，即對所有i， j ∈V，d(n)ij表示頂點i到頂點 j的最短路徑。
下面是求解該問題的偽代碼，請?zhí)畛淦渲锌杖钡?(1)至(6)處。 偽代碼中的主要變量說明如下：
W：權(quán)重矩陣
n： 圖的頂點個數(shù)
SP：最短路徑權(quán)重之和數(shù)組，SP[i]表示頂點i到其它各頂點的最短路徑權(quán)重之和，i從1到n
min_SP：最小的最短路徑權(quán)重之和
min_v：具有最小的最短路徑權(quán)重之和的頂點
i：循環(huán)控制變量
j：循環(huán)控制變量
k：循環(huán)控制變量

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

第5題： 閱讀下列說明和C 函數(shù)代碼，將應(yīng)填入（n）處的字句寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
對二叉樹進(jìn)行遍歷是二叉樹的一個基本運算。遍歷是指按某種策略訪問二叉樹的每個結(jié)點，且每個結(jié)點僅訪問一次的過程。函數(shù)InOrder()借助棧實現(xiàn)二叉樹的非遞歸中序遍歷運算。
設(shè)二叉樹采用二叉鏈表存儲，結(jié)點類型定義如下：
typedef struct BtNode{
ElemTypedata;/*結(jié)點的數(shù)據(jù)域，ElemType的具體定義省略*/
struct BtNode *lchild，*rchild;/*結(jié)點的左、右孩子指針域*/
}BtNode， *BTree;

在函數(shù)InOrder()中，用棧暫存二叉樹中各個結(jié)點的指針，并將棧表示為不含頭結(jié)點的單向鏈表（簡稱鏈棧），其結(jié)點類型定義如下：
typedef struct StNode{  /*鏈棧的結(jié)點類型*/
BTree elem;  /*棧中的元素是指向二叉鏈表結(jié)點的指針*/
struct StNode *link;
}StNode;
假設(shè)從棧頂?shù)綏５椎脑貫?en、en-1、…、e1，則不含頭結(jié)點的鏈棧示意圖如圖 5-1所示。

【C函數(shù)】

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

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

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

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