軟件設(shè)計(jì)師考試歷年試題

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

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

3、數(shù)據(jù)流的起點(diǎn)和終點(diǎn)。（起點(diǎn)和終點(diǎn)請采用數(shù)據(jù)流圖 1-1 中的符號或名稱）錯(cuò)誤數(shù)據(jù)流起點(diǎn)終點(diǎn)補(bǔ)充的數(shù)據(jù)流起點(diǎn)終點(diǎn)試題二（共 15 分）閱讀下列說明，回答問題 1 至問題 3，將解答填入答題紙的對應(yīng)欄內(nèi)?！菊f明】某集團(tuán)公司擁有多個(gè)大型連鎖商場，公司需要構(gòu)建一個(gè)數(shù)據(jù)庫系統(tǒng)以方便管理其業(yè)務(wù)運(yùn)作活動?！拘枨蠓治鼋Y(jié)果】1.商場需要記錄的信息包括商場編號（編號唯一），商場名稱，地址和聯(lián)系電話。某商場信息如表 2-1 所示。表 2-1 商場信息表商場編號商場名稱地址聯(lián)系電話PS2101淮海商場淮海中路 918 號021-PS2902西大街商場西大街時(shí)代盛典大廈029-PS2903東大街商場碑林區(qū)東大街 239

4、 號029-PS2901長安商場雁塔區(qū)長安中路 38 號029-2. 每個(gè)商場包含有不同的部門，部門需要記錄的信息包括部門編號（集團(tuán)公司分配），部門名稱，位置分布和聯(lián)系電話。某商場的部門信息如表 2-2 所示。表 2-2 部門信息表部門編號部門名稱位置分布聯(lián)系電話DT002財(cái)務(wù)部商場大樓六層DT007后勤部商場地下副一層DT021安保部商場地下副一層DT005人事部商場大樓六層DT001管理部商場裙樓三層3. 每個(gè)部門雇用多名員工處理日常事務(wù)，每名員工只能隸屬于一個(gè)部門（新進(jìn)員工在培訓(xùn)期不隸屬于任何部門）。員工需要記錄的信息包括員工編號（集團(tuán)公司分配），姓名，崗位，電話號碼和工資。員工信息如表

5、 2-3 所示。表 2-3 員工信息表員工編號姓名崗位電話號碼工資XA3310周超理貨員1500.00SH1075劉飛防損員1500.00XA0048江雪花廣播員1428.00BJ3123張正華部門主管1876.004. 每個(gè)部門的員工中有一名是經(jīng)理，每個(gè)經(jīng)理只能管理一個(gè)部門，系統(tǒng)需要記錄每個(gè)經(jīng)理的任職時(shí)間?！靖拍钅Ｐ驮O(shè)計(jì)】根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖和關(guān)系模式（不完整）如下：商場部門經(jīng)理員工 圖 2-1 實(shí)體聯(lián)系圖【關(guān)系模式設(shè)計(jì)】商場（商場編號，商場名稱，地址，聯(lián)系電話）部門（部門編號，部門名稱，位置分布，聯(lián)系電話，（a）員工（員工編號，員工姓名，崗位，電話號碼，工資，（b）經(jīng)理

6、（c），任職時(shí)間）【問題 1】（6 分）根據(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】（6 分）根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中的空（a）（c）補(bǔ)充完整，并分別給出部門、員工和經(jīng)理關(guān)系模式的主鍵和外鍵?！締栴} 3】（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)系

7、模式。 試題三（共 15 分）閱讀下列說明和圖，回答問題 1 至問題 3，將解答填入答題紙的對應(yīng)欄內(nèi)?！菊f明】某銀行計(jì)劃開發(fā)一個(gè)自動存提款機(jī)模擬系統(tǒng)（ATM System）。系統(tǒng)通過讀卡器CardReader）讀取ATM卡 ； 系統(tǒng)與客戶（Customer ）的交互由客戶控制臺（CustomerConsole）實(shí)現(xiàn)；銀行操作員（Operator）可控制系統(tǒng)的啟動（System Startup）和停止（System Shutdown）；系統(tǒng)通過網(wǎng)絡(luò)和銀行系統(tǒng)（Bank）實(shí)現(xiàn)通信。當(dāng)讀卡器判斷用戶已將 ATM 卡插入后，創(chuàng)建會話（Session）。會話開始后，讀卡器進(jìn)行讀卡，并要求客戶輸入個(gè)人驗(yàn)證

8、碼（PIN）。系統(tǒng)將卡號和個(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 卡賬戶信息。一次會話可以包含多個(gè)事務(wù)，每個(gè)事務(wù)處理也會將卡號和個(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卡，會話結(jié)束。系統(tǒng)采用面向?qū)ο蠓椒ㄩ_發(fā)，使用 U

9、ML 進(jìn)行建模。系統(tǒng)的頂層用例圖如圖 3-1 所示，一次會話的序列圖（不考慮驗(yàn)證）如圖 3-2 所示。消息名稱參見表 3-1。表 3-1 可能的消息名稱列表名稱說明名稱說明cardInserted( )ATM 卡已插入performTransaction( )執(zhí)行事務(wù)performSession( )執(zhí)行會話readCard( )讀卡readPIN( )讀取個(gè)人驗(yàn)證碼PIN個(gè)人驗(yàn)證碼信息creat(atm, this, card, pin)為當(dāng)前會話創(chuàng)建事務(wù)create(this)為當(dāng)前 ATM 創(chuàng)建會話cardATM 卡信息doAgain執(zhí)行下一個(gè)事務(wù)ejectCard( )彈出 ATM 卡

10、【問題 1】（7 分）根據(jù)【說明】中的描述，給出圖 3-1 中 A1 和 A2 所對應(yīng)的參與者，U1 至 U3 所對應(yīng)的用例，以及該圖中空（1）所對應(yīng)的關(guān)系。（U1 至 U3 的可選用例包括：Session、Transaction、Insert Card、Invalid PIN Process 和 Transfer）【問題 2】（6 分）根據(jù)【說明】中的描述，使用表 3-1 中的英文名稱，給出圖 3-2 中 69 對應(yīng)的消息。【問題 3】（2 分）解釋圖 3-1 中用例 U3 和用例 Withdraw、Deposit 等四個(gè)用例之間的關(guān)系及其內(nèi)涵。圖 3-1 ATM 系統(tǒng)頂層用例圖圖 3-2

11、一次會話的序列圖（無驗(yàn)證消息）試題四（共 15 分）閱讀下列說明，回答問題 1 和問題 2，將解答填入答題紙的對應(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)的最短路徑之和最小。算法首先需要求出每個(gè)頂點(diǎn)到其它任一頂點(diǎn)的最短路徑，即需要計(jì)算任意兩個(gè)頂點(diǎn)之間的最短路徑；然后對每個(gè)頂點(diǎn)，計(jì)算其它各頂點(diǎn)到該頂點(diǎn)的最短路徑之和；最后，選擇最短路徑之和最小的頂點(diǎn)作為建大型

12、超市的最佳位置。 【問題 1】（12 分） 本題采用 Floyd-Warshall 算法求解任意兩個(gè)頂點(diǎn)之間的最短路徑。已知圖 G 的頂點(diǎn)集合為V= 1, 2,., ，W = wij*為權(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,., 。 若中間頂點(diǎn)包括頂點(diǎn)k，則=+；若中間頂點(diǎn)不包括頂點(diǎn)k ，則=。于是得到如下遞歸式。 = Wij k=0min()，+ k>0 因?yàn)閷τ谌我饴窂?，所有的中間頂點(diǎn)都在集合1, 2,., 內(nèi)，因此矩陣D(n)=n*n給出了

13、任意兩個(gè)頂點(diǎn)之間的最短路徑，即對所有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 到 nmin_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 n4 for j = 1 to n5 if +6 （2

14、） 7 else 8 （3） 9 for i = 1 to n10 SPi = 011 for j = 1 to n 12 （4） 13 min_SP = SP1 14 （5） 15 for i = 2 to n16 if min_SP > SPi 17 min_SP = SPi 18 min_v = i 19return （6） 【問題 2】（3 分）【問題 1】中偽代碼的時(shí)間復(fù)雜度為（7）（用符號表示）。從下列的 3 道試題（試題五至試題七）中任選 1 道解答。如果解答的試題數(shù)超過 1 道，則題號小的 1 道解答有效。試題五（共 15 分）閱讀下列說明和 C 函數(shù)代碼，將應(yīng)填入（n）

15、處的字句寫在答題紙的對應(yīng)欄內(nèi)?！菊f明】 對二叉樹進(jìn)行遍歷是二叉樹的一個(gè)基本運(yùn)算。遍歷是指按某種策略訪問二叉樹的每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)僅訪問一次的過程。函數(shù) InOrder()借助棧實(shí)現(xiàn)二叉樹的非遞歸中序遍歷運(yùn)算。設(shè)二叉樹采用二叉鏈表存儲，結(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)的單向

16、鏈表（簡稱鏈棧），其結(jié)點(diǎn)類型定義如下：typedef struct StNode BTree elem; /*鏈棧的結(jié)點(diǎn)類型*/ struct StNode *link; /*棧中的元素是指向二叉鏈表結(jié)點(diǎn)的指針*/StNode; 假設(shè)從棧頂?shù)綏５椎脑貫?en、en-1、e1，則不含頭結(jié)點(diǎn)的鏈棧示意圖如圖 5-1所示。 圖 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 *s

17、tacktop = NULL; /* 初始化空棧的棧頂指針 stacktop */ ptr = root; /* ptr 指向二叉樹的根結(jié)點(diǎn) */ while ( （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） ; /*棧頂元素出棧*/ v

18、isit(q); /*visit 是訪問結(jié)點(diǎn)的函數(shù)，其具體定義省略*/ ptr = （5） ; /*進(jìn)入右子樹*/ free(q); /*釋放原棧頂元素的結(jié)點(diǎn)空間*/ return 0; /*InOrder*/ 試題六（共 15 分）閱讀下列說明和 C+代碼，將應(yīng)填入（n）處的字句寫在答題紙的對應(yīng)欄內(nèi)。【說明】現(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ò)展性以支持新的文

19、件格式和操作系統(tǒng)。為滿足上述需求并減少所需生成的子類數(shù)目，采用橋接（Bridge）設(shè)計(jì)模式進(jìn)行設(shè)計(jì)所得類圖如圖 6-1 所示。圖 6-1類圖采用該設(shè)計(jì)模式的原因在于：系統(tǒng)解析 BMP、GIF 與 JPEG 文件的代碼僅與文件格式相關(guān)，而在屏幕上顯示像素矩陣的代碼則僅與操作系統(tǒng)相關(guān)?！綜+代碼】class Matrix /各種格式的文件最終都被轉(zhuǎn)化為像素矩陣/此處代碼省略; class ImageImp public: virtual void doPaint(Matrix m) = 0; /顯示像素矩陣 m ; class WinImp : public ImageImp public: vo

20、id doPaint(Matrix m) /*調(diào)用 windows 系統(tǒng)的繪制函數(shù)繪制像素矩陣*/ ; class LinuxImp : public ImageImp public: void doPaint(Matrix m) /*調(diào)用 Linux 系統(tǒng)的繪制函數(shù)繪制像素矩陣*/ ; class Image public: void setImp(ImageImp *imp) （1） = imp; virtual void parseFile(string fileName) = 0; protected: （2） *imp; ; class BMP : public Image publ

21、ic: void parseFile(string fileName) /此處解析 BMP 文件并獲得一個(gè)像素矩陣對象 m （3） ;/顯示像素矩陣 m ; class GIF : public Image /此處代碼省略; class JPEG : public Image /此處代碼省略; void main() /在 windows 操作系統(tǒng)上查看 demo.bmp 圖像文件Image *image1 = （4） ; ImageImp *imageImp1 = （5） ; （6） image1->parseFile("demo.bmp"); 現(xiàn)假設(shè)該系統(tǒng)需要支持

22、 10 種格式的圖像文件和 5 種操作系統(tǒng)，不考慮類 Matrix，若采用橋接設(shè)計(jì)模式則至少需要設(shè)計(jì)（7）個(gè)類。試題七（共 15 分）閱讀下列說明和 Java 代碼，將應(yīng)填入（n）處的字句寫在答題紙的對應(yīng)欄內(nèi)?！菊f明】現(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ì)所得類圖如圖 7-1 所示。圖 7-1類圖采用該設(shè)計(jì)模式的原因在于：系統(tǒng)解析 BMP、GIF 與 JPEG 文件的代碼僅與文件格式相關(guān)，而在屏幕上顯示像素矩陣的代碼則僅與操作系統(tǒng)相關(guān)?！綣ava 代碼】class Matrix /各種格式的文件最終都被轉(zhuǎn)化為像素矩陣/此處代碼省略; abstract class ImageImp public abstract void doPaint(Matrix