省考軟件設(shè)計(jì)師考試模擬題及答案從業(yè)資格考試測試題(5)

1、 軟件設(shè)計(jì)師考試模擬題及答案-試題一閱讀下列說明，回答問題1和問題2，將解答填入的對(duì)應(yīng)欄內(nèi)。說明 假設(shè)某大型商業(yè)企業(yè)由商品配送中心和連鎖超市組成，其中商品配送中心包括采購、財(cái)務(wù)、配送等部門。為實(shí)現(xiàn)高效管理，設(shè)計(jì)了商品配送中心信息管理系統(tǒng)，其主要功能描述如下： 1系統(tǒng)接收由連鎖超市提出的供貨請求，并將其記錄到供貨請求記錄文件。 2在接到供貨請求后，從商品庫存記錄文件中進(jìn)行商品庫存信息查詢。如果庫存滿足供貨請求，則給配送處理發(fā)送配送通知；否則，向采購部門發(fā)出缺貨通知。 3配送處理接到配送通知后，查詢供貨請求記錄文件，更新商品庫存記錄文件，并向配送部門發(fā)送配送單，在配送貨品的同時(shí)記錄配送信息至商品配

2、送記錄文件。 4采購部門接到缺貨通知后，與供貨商洽談，進(jìn)行商品采購處理，合格商品入庫，并記錄采購清單至采購清單記錄文件、向配送處理發(fā)出配送通知，同時(shí)通知財(cái)務(wù)部門給供貨商支付貨款。 該系統(tǒng)采用結(jié)構(gòu)化方法進(jìn)行開發(fā)，得到待修改的數(shù)據(jù)流圖如下圖所示。 1、問題1 使用說明中的詞語，給出上圖中外部實(shí)體E1至E4的名稱和數(shù)據(jù)存儲(chǔ)D1至D4的名稱。2、問題2 以上數(shù)據(jù)流圖中存在四處錯(cuò)誤數(shù)據(jù)流，請指出各自的起點(diǎn)和終點(diǎn)；若將上述四條錯(cuò)誤數(shù)據(jù)流刪除，為保證數(shù)據(jù)流圖的正確性，應(yīng)補(bǔ)充三條數(shù)據(jù)流，請給出所補(bǔ)充數(shù)據(jù)流的起點(diǎn)和終點(diǎn)。(起點(diǎn)和終點(diǎn)請采用上述數(shù)據(jù)流圖中的符號(hào)或名稱) 錯(cuò)誤數(shù)據(jù)流 補(bǔ)充的數(shù)據(jù)流 試題二閱讀下列說明

3、，回答問題1至問題3，將解答填入的對(duì)應(yīng)欄內(nèi)。說明 某集團(tuán)公司擁有多個(gè)大型連鎖商場，公司需要構(gòu)建一個(gè)數(shù)據(jù)庫系統(tǒng)以方便管理其業(yè)務(wù)運(yùn)作活動(dòng)。 需求分析結(jié)果 1商場需要記錄的信息包括商場編號(hào)(編號(hào)唯一)，商場名稱，地址和聯(lián)系電話。某商場信息如下表所示。 商場信息表 2每個(gè)商場包含有不同的部門，部門需要記錄的信息包括部門編號(hào)(集團(tuán)公司分配)，部門名稱，位置分布和聯(lián)系電話。某商場的部門信息如下表所示。 部門信息表 3每個(gè)部門雇用多名員工處理日常事務(wù)，每名員工只能隸屬于一個(gè)部門(新進(jìn)員工在培訓(xùn)期不隸屬于任何部門)。員工需要記錄的信息包括員工編號(hào)(集團(tuán)公司分配)，姓名，崗位，電話號(hào)碼和工資。員工信息如下表所示

4、。 員工信息表 4每個(gè)部門的員工中有一名是經(jīng)理，每個(gè)經(jīng)理只能管理一個(gè)部門，系統(tǒng)需要記錄每個(gè)經(jīng)理的任職時(shí)間。 概念模型設(shè)計(jì) 根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖和關(guān)系模式(不完整)如下： 實(shí)體聯(lián)系圖 關(guān)系模式設(shè)計(jì) 商場(商場編號(hào)，商場名稱，地址，聯(lián)系電話) 部門(部門編號(hào)，部門名稱，位置分布，聯(lián)系電話， (a) ) 員工(員工編號(hào)，員工姓名，崗位，電話號(hào)碼，工資， (b) ) 經(jīng)理( (c) ，任職時(shí)間)3、問題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。4、問題2 根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中

5、的空(a)(c)補(bǔ)充完整，并分別給出部門、員工和經(jīng)理關(guān)系模式的主鍵和外鍵。5、問題3 為了使商場有緊急事務(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)系模式。試題三閱讀下列說明和圖，回答問題1至問題3，將解答填入的對(duì)應(yīng)欄內(nèi)。說明 某銀行計(jì)劃開發(fā)一個(gè)自動(dòng)存提款機(jī)模擬系統(tǒng)(ATM System)。系統(tǒng)通過讀卡器 (Card Reader)讀取ATM卡；系統(tǒng)與客戶(Customer)的交互由客戶控制臺(tái)(Custom

6、er-Console)實(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卡賬戶信息。

7、一次會(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所示。 6、問題1 根據(jù)說明中的描述，給出圖3-1中A1和A2所對(duì)應(yīng)的參與者，U1至U3所對(duì)應(yīng)的用例，以及該圖中空 (1) 所對(duì)應(yīng)的關(guān)系。(U1至U3的可選用例包括：Session、Transaction、Insert Ca

8、rd、Invalid PIN Process和Transfer)7、問題2 根據(jù)說明中的描述，使用消息名稱列表中的英文名稱，給出圖3-2中69對(duì)應(yīng)的消息。8、問題3 解釋圖3-1中用例U3和用例Withdraw、Deposit等四個(gè)用例之間的關(guān)系及其內(nèi)涵。試題四閱讀下列說明，回答問題1和問題2，將解答填入的對(duì)應(yīng)欄內(nèi)。說明 現(xiàn)需在某城市中選擇一個(gè)社區(qū)建一個(gè)大型超市，使該城市的其他社區(qū)到該超市的距離總和最小。用圖模型表示該城市的地圖，其中頂點(diǎn)表示社區(qū)，邊表示社區(qū)間的路線，邊上的權(quán)重表示該路線的長度。 現(xiàn)設(shè)計(jì)一個(gè)算法來找到該大型超市的最佳位置：即在給定圖中選擇一個(gè)頂點(diǎn)，使該頂點(diǎn)到其他各頂點(diǎn)的最短路徑

9、之和最小。算法首先需要求出每個(gè)頂點(diǎn)到其他任一頂點(diǎn)的最短路徑，即需要計(jì)算任意兩個(gè)頂點(diǎn)之間的最短路徑；然后對(duì)每個(gè)頂點(diǎn)，計(jì)算其他各頂點(diǎn)到該頂點(diǎn)的最短路徑之和；最后，選擇最短路徑之和最小的頂點(diǎn)作為建大型超市的最佳位置。9、問題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)k0時(shí)，該最短路徑上所有的中間頂點(diǎn)均屬于集合1,2，k。若中間頂點(diǎn)包括頂點(diǎn)k，則；若中間頂點(diǎn)不包括頂點(diǎn)k，則。于是得到如下遞歸式。 因?yàn)閷?duì)于任意路徑，所

10、有的中間頂點(diǎn)都在集合1,2，n內(nèi)，因此矩陣給出了任意兩個(gè)頂點(diǎn)之間的最短路徑，即對(duì)所有i,jV，表示頂點(diǎn)i到頂點(diǎn)j的最短路徑。 下面是求解該問題的偽代碼，請?zhí)畛淦渲锌杖钡?1)至(6)處。偽代碼中的主要變量說明如下： W：權(quán)重矩陣 n：圖的頂點(diǎn)個(gè)數(shù) SP：最短路徑權(quán)重之和數(shù)組，SPi表示頂點(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)控制變量 LOCATE -SHOPPINGMALL (W, n) 1 D(0) = W 2 for (1) 3 for i = 1 to

11、 n 4 for j = 1 to n 6 (2) 7 else 8 (3) 9 for i = 1 to n 10 SP i = 0 11 for j = 1 to n 12 (4) 13 min_SP = SPi 14 (5) 15 for i = 2 to n 16 if min_SP SPi 17 min_SP = SPi 18 min_v = i 19 return (6) 10、問題2 問題1中偽代碼的時(shí)間復(fù)雜度為 (7) (用O符號(hào)表示)。試題五閱讀下列說明和C函數(shù)代碼，將應(yīng)填入 (n) 處的字句寫在的對(duì)應(yīng)欄內(nèi)。11、說明 對(duì)二叉樹進(jìn)行遍歷是二叉樹的一個(gè)基本運(yùn)算。遍歷是指按某種策

12、略訪問二叉樹的每個(gè)節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)僅訪問一次的過程。函數(shù)InOrder()借助棧實(shí)現(xiàn)二叉樹的非遞歸中序遍歷運(yùn)算。 設(shè)二叉樹采用二叉鏈表存儲(chǔ)，節(jié)點(diǎn)類型定義如下： typedef struct BtNode ElemType data； /*節(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é)點(diǎn)類型定義如下： typedef struct StNode /*鏈棧的節(jié)

13、點(diǎn)類型*/ BTree elem； /*棧中的元素是指向二叉鏈表節(jié)點(diǎn)的指針*/ struct StNode*link； StNode； 假設(shè)從棧頂?shù)綏５椎脑貫閑n、en-1、e1，則不含頭節(jié)點(diǎn)的鏈棧示意圖如圖5-1所示。 C函數(shù) int InOrder(BTree root) /*實(shí)現(xiàn)二叉樹的非遞歸中序遍歷*/ BTree ptr； /*ptr用于指向二叉樹中的節(jié)點(diǎn)*/ StNode*q； /*q暫存鏈棧中新創(chuàng)建或待刪除的節(jié)點(diǎn)指針*/ StNode*stacktop=NULL； /*初始化空棧的棧頂指針stacktop*/ Ptr=root； /*ptr指向二叉樹的根節(jié)點(diǎn)*/ while (

14、 (1) | | stacktop !=NULL) while (ptr!=NULL) q=(StNode*)malloc(sizeof (StNode)； if (q= =NULL) return-1； q-elem=ptr； (2) ； stacktop=q； /*stacktop指向新的棧頂*/ ptr= (3) ； /*進(jìn)入左子樹*/ q=stacktop； (4) ； /*棧頂元素出棧*/ visit(q)； /*visit是訪問節(jié)點(diǎn)的函數(shù)，其具體定義省略*/ ptr= (5) ； /*進(jìn)入右子樹*/ free(q)； /*釋放原棧頂元素的節(jié)點(diǎn)空間*/ return 0； /*Ino

15、rder*/試題六閱讀下列說明和C+代碼，將應(yīng)填入 (n) 處的字句寫在的對(duì)應(yīng)欄內(nèi)。12、說明 現(xiàn)欲實(shí)現(xiàn)一個(gè)圖像瀏覽系統(tǒng)，要求該系統(tǒng)能夠顯示BMP、3PEG和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ì)，所得類圖如下圖所示。 采用該設(shè)計(jì)模式的原因在于：系統(tǒng)解析BMP、GIF與JPEG文件的代碼僅與文件格式相關(guān)，而在屏幕上顯示像素矩陣的代碼

16、則僅與操作系統(tǒng)相關(guān)。 C+代碼 class Matrix / 各種格式的文件最終都被轉(zhuǎn)化為像素矩陣 / 此處代碼省略 ； class Imagelmp public： virtual void doPaint (Matrix m)=0； / 顯示像素矩陣m ； class WinImp ：public ImageImp public： void doPaint (Matrix m) /*調(diào)用Windows系統(tǒng)的繪制函數(shù)繪制像素矩陣*/) ； class LinuxImp : public ImageImp public: void doPaint(Matrix m) /*調(diào)用 Linux系統(tǒng)的

17、繪制函數(shù)繪制像素矩陣*/ ; class Image public: void set Imp (Image Imp *imp) (1) = imp; virtual void parse File(string file Name)=0; protected: (2) *imp; ; class BMP : public Image public: void parse File(string file Name) / 此處解析BMP文件并獲得一個(gè)像素矩陣對(duì)象m (3) ;/ 顯示像素矩陣m ; class GIF : public Image / 此處代碼省略 ; class JPEG :

18、 public Image / 此處代碼省略 ; void main() /在Windows操作系統(tǒng)上查看demo. bmp圖像文件 Image *imagel = (4) ; ImageImp *imageImpl = (5) ; (6) ; imagel-parseFile(demo.bmp)； 現(xiàn)假設(shè)該系統(tǒng)需要支持10種格式的圖像文件和5種操作系統(tǒng)，不考慮類Matrix，若采用橋接設(shè)計(jì)模式則至少需要設(shè)計(jì) (7) 個(gè)類。試題七閱讀下列說明和Java代碼，將應(yīng)填入 (n) 處的字句寫在的對(duì)應(yīng)欄內(nèi)。13、說明 現(xiàn)欲實(shí)現(xiàn)一個(gè)圖像瀏覽系統(tǒng)，要求該系統(tǒng)能夠顯示BMP、JPEG和GIF三種格式的文件，

19、并且能夠在Windows和Linux兩種操作系統(tǒng)上運(yùn)行。系統(tǒng)首先將BMP、JPEG和GIF三種格式的文件解析為像素矩陣，然后將像素矩陣顯示在屏幕上。系統(tǒng)需具有較好的擴(kuò)展性以支持新的文件格式和操作系統(tǒng)。為滿足上述需求并減少所需生成的子類數(shù)目，采用橋接(Bridge)設(shè)計(jì)模式進(jìn)行設(shè)計(jì)，所得類圖如下圖所示。 采用該設(shè)計(jì)模式的原因在于：系統(tǒng)解析BMP、GIF與JPEG文件的代碼僅與文件格式相關(guān)，而在屏幕上顯示像素矩陣的代碼則僅與操作系統(tǒng)相關(guān)。 Java代碼 class Matrix /各種格式的文件最終都被轉(zhuǎn)化為像素矩陣 /此處代碼省略 ； abstract class lmageImp public

20、 abstract void do Paint(Matrix m)； /顯示像素矩陣m ； class WinImp extends ImageImp public void do Paint(Matrix m) /*調(diào)用Windows系統(tǒng)的繪制函數(shù)繪制像素矩陣*/ ； class Linuxlmp extends ImageImp public void do Paint(Matrix m)/*調(diào)用Linux系統(tǒng)的繪制函數(shù)繪制像素矩陣*/) ； abstract class Image public void setImp(1magelmp imp) (1) =imp；) public ab

21、stract void parse File(String file Name)； protected (2) imp； ； class BMP extends Image public void parse File(String file Name) /此處解析BMP文件并獲得一個(gè)像素矩陣對(duì)象m (3) ；/顯示像素矩陣m ； class GIF extends Image /此處代碼省略 ； class JPEG extends Image /此處代碼省略 ； public class java Main public static void main(String args) /在Wi

22、ndows操作系統(tǒng)上查看demo.bmp圖像文件 Image image1= (4) ； ImageImp imageImp1= (5) ； (6) ； image1.parseFile(demo.bmp)； 現(xiàn)假設(shè)該系統(tǒng)需要支持10種格式的圖像文件和5種操作系統(tǒng)，不考慮類Matrix和類javaMain，若采用橋接設(shè)計(jì)模式則至少需要設(shè)計(jì) (7) 個(gè)類。答案:試題一1、E1：財(cái)務(wù)部門 E2：采購部門 E3：連鎖超市 E4：配送部門 D1：采購清單記錄文件 D2：商品庫存記錄文件 D3：商品配送記錄文件 D4：供貨請求記錄文件 2、錯(cuò)誤數(shù)據(jù)流 補(bǔ)充的數(shù)據(jù)流 分析 本題考查DFD的分析與設(shè)計(jì)，問題

23、一主要考查DFD中的外部實(shí)體和數(shù)據(jù)存儲(chǔ)，由于在題干中已經(jīng)提到“系統(tǒng)接收由連鎖超市提出的供貨請求，并將其記錄到供貨請求記錄文件”，因此可以明確出“連鎖超市”外部實(shí)體和“供貨請求記錄文件”數(shù)據(jù)存儲(chǔ)；對(duì)應(yīng)到DFD圖中為E3和D4。描述中的第二項(xiàng)提出“從商品庫存記錄文件中進(jìn)行商品庫存信息查詢。如果庫存滿足供貨請求，則給配送處發(fā)送配送通知；否則，向采購部門發(fā)出缺貨通知”，因?yàn)榕渌屯ㄖ枰l(fā)送到采購部門，因此采購部門將成為系統(tǒng)的外部實(shí)體；同時(shí)，商品庫存記錄文件能夠提供庫存信息，所以DFD圖中E2和D2分別為采購部門和商品配送記錄文件。第三項(xiàng)需求“配送處理接到配送通知后，查詢供貨請求記錄文件，更新商品庫存記

24、錄文件，并向配送部門發(fā)送配送單，在配送貨品的同時(shí)記錄配送信息至商品配送記錄文件”，所以配送處理需要查詢供貨請求記錄文件，更新商品庫存記錄文件與商品配送記錄文件，因此D3為商品配送記錄文件；采購處理需要記錄采購清單同時(shí)通知財(cái)務(wù)部門，所以E1應(yīng)該為財(cái)務(wù)部門，D1為采購清單記錄文件，剩下的E4則為配送部門。 DFD中出現(xiàn)的錯(cuò)誤數(shù)據(jù)流為：E1到E2，E1與E2的數(shù)據(jù)流不屬于系統(tǒng)的范圍；D3到E4，多余的數(shù)據(jù)流；D2到采購處理，數(shù)據(jù)流方向錯(cuò)誤；D4到供貨請求處理，數(shù)據(jù)流方向錯(cuò)誤。 需要補(bǔ)充的數(shù)據(jù)流為：E2到采購處理，因?yàn)镋2是采購部門，采購部門需要給采購處提供入庫商品信息；采購處到D2需要一條數(shù)據(jù)流，因

25、為采購處理需要更改庫存信息；供貨請求處理到D4需要一條數(shù)據(jù)流，因?yàn)楣┴浾埱筇幚硇枰涗浌┴浾埱笮畔ⅰＴ囶}二3、(圖中的m、n也可用*表示，對(duì)聯(lián)系名稱可不做要求，但不能出現(xiàn)重名) 解析 本題考查數(shù)據(jù)庫概念結(jié)構(gòu)設(shè)計(jì)及概念結(jié)構(gòu)向邏輯結(jié)構(gòu)轉(zhuǎn)換的過程。 此類題目要求考生認(rèn)真閱讀題目對(duì)現(xiàn)實(shí)問題的描述，經(jīng)過分類、聚集和概括等方法從中確定實(shí)體及其聯(lián)系。題目已經(jīng)給出了4個(gè)實(shí)體，需要根據(jù)需求描述給出實(shí)體間的聯(lián)系。 由“每個(gè)商場包含有不同的部門”可知商場與部門間為1:m聯(lián)系；由“每個(gè)部門雇用了多名員工處理日常事務(wù)”可知部門與員工間為1:p聯(lián)系；由“每個(gè)部門的員工中有一個(gè)經(jīng)理每個(gè)經(jīng)理只能管理一個(gè)部門”可知部門與經(jīng)理間

26、為1:1聯(lián)系，并且員工是經(jīng)理的超類型，經(jīng)理是員工的子類型。 4、(a)商場編號(hào) (b)部門編號(hào) (c)員工編號(hào) 部門關(guān)系模式的主鍵：部門編號(hào) 外鍵：商場編號(hào) 員工關(guān)系模式的主鍵：員工編號(hào) 外鍵：部門編號(hào) 經(jīng)理關(guān)系模式的主鍵：員工編號(hào) 外鍵：員工編號(hào)解析 商場的屬性信息中，商場編號(hào)由集團(tuán)公司分配，不會(huì)重復(fù)，可作為商場的主鍵屬性；部門的屬性信息中，部門編號(hào)由集團(tuán)公司分配，不會(huì)重復(fù)，可作為部門的主鍵屬性，商場與部門的聯(lián)系需要通過將商場的主鍵(商場編號(hào))加入到部門中來表達(dá)；員工的屬性信息中，員工編號(hào)由集團(tuán)公司分配，不會(huì)重復(fù)，可作為員工的主鍵屬性，部門與員工的聯(lián)系需要通過將部門的主鍵(部門編號(hào))加入到員

27、工中來表達(dá)；經(jīng)理除了包含員工的屬性信息外，還需要任職時(shí)間屬性。完整的關(guān)系模式如下： 商場(商場編號(hào)，商場名稱，地址，聯(lián)系電話) 部門(部門編號(hào)，部門名稱，位置分布，聯(lián)系電話，商場編號(hào)) 員工(員工編號(hào)，姓名，崗位，電話號(hào)碼，工資，部門編號(hào)) 經(jīng)理(員工編號(hào)，任職時(shí)間)5、(d)緊急聯(lián)系人 (e)1:n 關(guān)系模式：緊急聯(lián)系人(員工編號(hào)，姓名，聯(lián)系電話)解析 員工的緊急聯(lián)系人信息通過添加緊急聯(lián)系人關(guān)系來實(shí)現(xiàn)，由“每位員工必須且只能登記一位緊急聯(lián)系人的姓名和聯(lián)系電話”，但可能存在多位員工登記同一位家屬，可知員工與家屬間為n:1聯(lián)系；由“不同員工可以登記相同的緊急聯(lián)系人”可知，員工編號(hào)可作為家屬的主鍵

28、屬性。所以需要添加的關(guān)系模式如下： 緊急聯(lián)系人(員工編號(hào)，姓名，聯(lián)系電話)試題三6、A1：Customer A2：Bank U1：Session U2：Invalid PIN Process U3：Transaction (1)：extend解析 本題涉及面向?qū)ο笙到y(tǒng)開發(fā)時(shí)的UML用例圖、序列圖以及用例之間的關(guān)系。 構(gòu)建用例圖時(shí)，常用的方式是先識(shí)別參與者，然后確定用例以及用例之間的關(guān)系。 識(shí)別參與者時(shí)，考查和系統(tǒng)交互的人員和外部系統(tǒng)。本題中，與系統(tǒng)交互的人員包括客戶(Customer)和銀行操作員(Operator)，與本模擬系統(tǒng)交互的外部系統(tǒng)包括銀行。系統(tǒng)(Bank)。 考查用例時(shí)，通過判斷

29、哪一個(gè)特定參與者發(fā)起或者觸發(fā)了與系統(tǒng)的哪些交互，宋識(shí)別用例并建立和參與者之間的關(guān)聯(lián)?？疾橛美g的關(guān)系時(shí)，include(包含)定義了用例之間的包含關(guān)系，用于一個(gè)用例包含另一個(gè)用例的行為的建模；如果可以從一個(gè)用例的執(zhí)行中，在需要時(shí)轉(zhuǎn)向執(zhí)行另一個(gè)用例，執(zhí)行完返回之前的用例繼續(xù)執(zhí)行，用例間即存在extend關(guān)系。 本題中，客戶一旦插卡成功，系統(tǒng)就創(chuàng)建會(huì)話(Session)，會(huì)話中可以執(zhí)行用戶從菜單選擇的Withdraw、Deposit、Transfer和Inquire等事務(wù)(Transaction)。由圖中U3和 Withdraw之間的擴(kuò)展關(guān)系，可知U3為Transaction；又由U1和U3之間

30、的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ò)誤處理(1nvalid PIN Process，圖中U2)，所以(1)處應(yīng)填extend。7、6：read PIN() 7：PIN 8：creat(atm，this，card，pin) 9：perform Transaction()解析 序列圖是場景的圖形化表示，描述了以時(shí)間順序組織的對(duì)象之間的交互活動(dòng)。構(gòu)造序列圖時(shí)遵循如下指導(dǎo)原則：確定順序圖的范圍，描述這個(gè)用例場景或一個(gè)步驟；繪制參與者和接口類，如果

31、范圍包括這些內(nèi)容的話：沿左手邊列出用例步驟；對(duì)控制器類及必須在順序中協(xié)作的每個(gè)實(shí)體類，基于它擁有的屬性或已經(jīng)分配給它的行為繪制框；為持續(xù)類和系統(tǒng)類繪制框；繪制所需消息，并把每條消息指到將實(shí)現(xiàn)響應(yīng)消息的責(zé)任的類上；添加活動(dòng)條指示每個(gè)對(duì)象實(shí)例的生命期；為清晰起見，添加所需的返回消息；如果需要，為循環(huán)、可選步驟和替代步驟等添加框架。 本題中，根據(jù)說明中的描述，從ATM機(jī)判斷卡已插入(card Inserted()開始會(huì)話，即為當(dāng)前ATM創(chuàng)建會(huì)話(create(this)并開始執(zhí)行會(huì)話(perform Session()；讀卡器讀卡(read Card()獲得ATM卡信息(card)，然后從控制臺(tái)讀取

32、個(gè)人驗(yàn)證碼輸入(read PIN()，圖中標(biāo)號(hào)6處)并獲得個(gè)人驗(yàn)證碼信息(PIN，圖中標(biāo)號(hào)7處)；然后根據(jù)用戶選擇啟動(dòng)并執(zhí)行事務(wù)，即為當(dāng)前會(huì)話創(chuàng)建事務(wù)(creat(atm，this，card，pin)，圖中標(biāo)號(hào)8處)和執(zhí)行事務(wù)(perform Transaction()，圖中標(biāo)號(hào)9處)；可以選擇繼續(xù)執(zhí)行某個(gè)事務(wù)(do Again)循環(huán)，或者選擇退卡(eject Card()。8、Transaction是一個(gè)抽象泛化用例，具有其他事務(wù)類型共有的屬性和行為，每個(gè)具體的事務(wù)類型繼承它，并實(shí)現(xiàn)適合自己的特定的操作。解析 用例之間的繼承關(guān)系表示子類型“是一種”父類型。其中父類型通常是一個(gè)抽象泛化用例，具

33、有子類型共有的屬性和行為，每個(gè)具體的子類型繼承它，并實(shí)現(xiàn)適合自己的特定的操作。 本題中Transaction和Withdraw、Deposit等四個(gè)用例之間的關(guān)系即為繼承關(guān)系，Transaction即是一個(gè)抽象泛化用例，具有其他事務(wù)類型共有的屬性和行為，每個(gè)具體的事務(wù)類型繼承它，并實(shí)現(xiàn)適合自己的特定的操作。試題四9、(1)k=1 to n (2) (3) (4) SPi=SPi+ (5)min_v=1 (6)min_v解析 本題考查的是算法的設(shè)計(jì)和分析技術(shù)。 本問題考查算法流程。第(1)空表示主循環(huán)，k是循環(huán)控制變量，故第(1)空填k=1 to n。第(2)和(3)空根據(jù)題意和遞歸式，可分別得

34、到答案為和。計(jì)算了任意兩個(gè)頂點(diǎn)之間的最短路徑之后，對(duì)每個(gè)頂點(diǎn)，開始統(tǒng)計(jì)其到所有其他頂點(diǎn)的最短路徑之和，因此第(4)空填SPi=SPi+。第13和第14行初始化，假設(shè)最小的到所有其他頂點(diǎn)的最短路徑之和為第一個(gè)頂點(diǎn)的最小路徑之和，大型超市的最佳位置為第一個(gè)頂點(diǎn)，故第(5)空填min_v=1。最后要求返回大型超市的最佳位置，即到所有其他頂點(diǎn)的最短路徑之和最小的頂點(diǎn)，故第(6)空填min_v。10、(7)O(n3)解析 本問題考查問題門中的偽代碼第28行，計(jì)算任意兩點(diǎn)之間的最短路徑，有三重循環(huán)，故時(shí)間復(fù)雜度為O(n3)。第912行，計(jì)算每個(gè)點(diǎn)到任意其他點(diǎn)的最短路徑之和，有兩重循環(huán)，故時(shí)間復(fù)雜度為O(n

35、2)。第1518行，在所有點(diǎn)的最短路徑之和中找到最小的最短路徑之和，時(shí)間復(fù)雜度為O(n)。故算法總的時(shí)間復(fù)雜度為O(n3)。試題五11、(1)ptr!=NULL，或ptr!=0，或ptr (2)q-link=stacktop (3)ptr-lchild (4)smcktop=stacktop-link，或stacktop=q-link (5)q-elem-rchild解析 本題考查基本數(shù)據(jù)結(jié)構(gòu)和C語言程序設(shè)計(jì)能力。 對(duì)非空二叉樹進(jìn)行中序遍歷的方法是：先中序遍歷根節(jié)點(diǎn)的左子樹，然后訪問根節(jié)點(diǎn)，最后中序遍歷根節(jié)點(diǎn)的右子樹。用遞歸方式描述的算法如下： void In_order_Traversing

36、 (BiTree root) / / root是指向二叉樹根節(jié)點(diǎn)的指針 if (root !=NULL) In_order_Traversing(root-LeftChild)； visit(root)； In_order_Traversing(root-RightChild)； 從以上算法的執(zhí)行過程可知，從樹根出發(fā)進(jìn)行遍歷時(shí)，遞歸調(diào)用In_Order_Traversing(root-LeftChild)使得遍歷過程沿著左孩子分支一直走向下層節(jié)點(diǎn)，直到到達(dá)二叉樹中最左下方的節(jié)點(diǎn)(設(shè)為f)的空左子樹為止，然后返回f節(jié)點(diǎn)，再由遞歸調(diào)用In_Order_Traversing(root-RightCh

37、ild)進(jìn)入f的右子樹，并重復(fù)以上過程。在遞歸算法執(zhí)行過程中，輔助實(shí)現(xiàn)遞歸調(diào)用和返回處理的控制棧實(shí)際上起著保存從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑信息。 用非遞歸算法實(shí)現(xiàn)二叉樹的中序遍歷時(shí)，可以由一個(gè)循環(huán)語句實(shí)現(xiàn)從指定的根節(jié)點(diǎn)出發(fā)，沿著左孩子分支一直到頭(到達(dá)一個(gè)沒有左子樹的節(jié)點(diǎn))的處理，從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑信息(節(jié)點(diǎn)序列)可以明確構(gòu)造一個(gè)棧來保存。 本題目的難點(diǎn)在于將棧的實(shí)現(xiàn)和使用混合在一起來處理，而且棧采用單鏈表存儲(chǔ)結(jié)構(gòu)。下面分析題中給出的代碼。 空(1)是遍歷的條件之一，由于另外一個(gè)條件stacktop!=ULL初始時(shí)是不成立的，因此空(1)所表示的條件必須滿足，由于是對(duì)非空二叉樹進(jìn)行遍歷，顯然

38、該條件代表二叉樹非空，即ptr!=ULL或其等價(jià)表示形式。 臨時(shí)指針ptr初始時(shí)指向整個(gè)二叉樹的根節(jié)點(diǎn)，此后用以下代碼表示一直沿左孩子指針鏈向下走的處理，臨時(shí)指針q用于在鏈棧中加入新元素時(shí)使用。處理思路是：若當(dāng)前節(jié)點(diǎn)有左子樹，則將當(dāng)前節(jié)點(diǎn)的指針存入棧中，然后進(jìn)入當(dāng)前節(jié)點(diǎn)的左子樹。入棧時(shí)，先申請?jiān)卦阪湕Ｖ械墓?jié)點(diǎn)空間，然后設(shè)置節(jié)點(diǎn)數(shù)據(jù)域的值(即當(dāng)前節(jié)點(diǎn)的指針)，最后將新申請的節(jié)點(diǎn)加入鏈棧首部。 while (ptr!=ULL) q=(StNode *) malloc (sizeof (StNode)；/*為新入棧的元素創(chuàng)建節(jié)點(diǎn)*/ if (q= =NULL) /*若創(chuàng)建新節(jié)點(diǎn)失敗，則退出*/ r

39、eturn-1； q-elem=ptr； /*在棧頂保存指向當(dāng)前節(jié)點(diǎn)的指針*/ q-link=stacktop； /*新節(jié)點(diǎn)加入棧頂*/ stacktop=q； /*更新棧頂指針，即stacktop指向新的棧頂*/ ptr=ptr-1child /*進(jìn)入當(dāng)前節(jié)點(diǎn)的左子樹*/ 當(dāng)上述過程進(jìn)入一棵空的子樹時(shí)(ptr為空指針)，循環(huán)結(jié)束。此后，應(yīng)該從空的子樹返回其父節(jié)點(diǎn)并進(jìn)行訪問。由于進(jìn)入空的左子樹前已將其父節(jié)點(diǎn)指針壓入棧中，因此，棧頂元素即為該父節(jié)點(diǎn)，對(duì)應(yīng)的處理就是彈棧。相應(yīng)地，在鏈棧中要?jiǎng)h除表頭節(jié)點(diǎn)并釋放節(jié)點(diǎn)空間。 q=stacktop； /*q指向鏈棧中需要?jiǎng)h除的節(jié)點(diǎn)，即棧頂元素*/ stac

40、k=stacktop-link； /*棧頂元素出棧*/ visit(q)； /*訪問節(jié)點(diǎn)*/ free(q)； /*釋放節(jié)點(diǎn)空間*/ 由于還需要通過q指針進(jìn)入被刪除節(jié)點(diǎn)的右子樹，因此，釋放節(jié)點(diǎn)空間的操作free(q)操作之前，使ptr指向q所指節(jié)點(diǎn)的右子樹指針，以得到被刪除節(jié)點(diǎn)的數(shù)據(jù)域信息，即空(5)所在語句ptr=q-elem-rchild。 指針是C語言中靈活且非常強(qiáng)大的工具，是否熟練掌握C語言的判斷條件之一就是對(duì)指針的理解和使用。軟件設(shè)計(jì)師需要熟練掌握這些內(nèi)容。試題六12、(1)this-imp (2)ImageImp (3)imp-doPaint(m) (4)new BMP() (5)new WinImp() (6)imagel-setImp(imageImpl) (7)17解析 根據(jù)題目描述，在設(shè)計(jì)該圖像顯示系統(tǒng)時(shí)主要分為兩個(gè)步驟：一是讀取各種文件并將文件內(nèi)容轉(zhuǎn)換成像素矩陣，