2013年下半年軟件設(shè)計(jì)師考試真題(下午)

1、2013 年下半年軟件設(shè)計(jì)師考試真題（下午）一、閱讀下列說明和圖，回答問題1至問題 4 ，將解答填入答題紙的對應(yīng)欄內(nèi)?！菊f明】某大學(xué)欲開發(fā)一個(gè)基于Web 的課程注冊系統(tǒng)。該系統(tǒng)的主要功能如下：1、驗(yàn)證輸入信息（ 1）檢查學(xué)生信息：檢查學(xué)生輸入的所有注冊所需信息。如果信息不合法，返回學(xué)生信息 不合法提示；如果合法，輸出合法學(xué)生信息。（ 2）檢查學(xué)位考試信息：檢查學(xué)生提供的學(xué)位考試結(jié)果。如果不合法，返回學(xué)位考試結(jié)果 不合法提示；如果合法，檢查該學(xué)生注冊資格。（ 3）檢查學(xué)生資格：根據(jù)合法學(xué)生信息和合法學(xué)位考試結(jié)果，檢查該學(xué)生對欲選課程的注冊資格。如果無資格，返回?zé)o注冊資格提示；如果有注冊資格，則輸

2、出注冊學(xué)生信息（包含選課學(xué)生標(biāo)識）和欲注冊課程信息。2、處理注冊申請（ 1）存儲注冊信息：將注冊學(xué)生信息記錄在學(xué)生庫。（ 2）存儲所注冊課程：將選課學(xué)生標(biāo)識與欲注冊課程進(jìn)行關(guān)聯(lián)，然后存入課程庫。（ 3）發(fā)送注冊通知：從學(xué)生庫中讀取注冊學(xué)生信息，從課程庫中讀取所注冊課程信息，給 學(xué)生發(fā)送接受提示；給教務(wù)人員發(fā)送所注冊課程信息和已注冊學(xué)生信息?，F(xiàn)采用結(jié)構(gòu)化方法對課程注冊系統(tǒng)進(jìn)行分析和設(shè)計(jì)，獲得如圖1-1所示的 0層數(shù)據(jù)流圖和圖1-2 所示的 1層數(shù)據(jù)流圖。圖 1-1 0 層數(shù)據(jù)流圖 1-2 1 層數(shù)據(jù)流圖【問題 1 】（2 分）使用說明中的詞語，給出圖1-1中的實(shí)體 E1 和 E2 的名稱?！締栴}

3、 2 】（2 分）使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲 D1 和 D2 的名稱。【問題 3 】（8 分）根據(jù)說明和圖中術(shù)語，補(bǔ)充圖1-2中缺失的數(shù)據(jù)流及其起點(diǎn)和終點(diǎn)。【問題 4 】（3 分）根據(jù)補(bǔ)充完整的圖 1-1 和圖 1-2 ，說明上層的哪些數(shù)據(jù)流是由下層的哪些數(shù)據(jù)流組合而成。二、閱讀下列說明，回答問題1至問題 3 ，將解答填入答題紙的對應(yīng)欄內(nèi)?！菊f明】某快遞公司為了方便管理公司物品運(yùn)送的各項(xiàng)業(yè)務(wù)活動，需要構(gòu)建一個(gè)物品運(yùn)送信息管理系統(tǒng)?！拘枨蠓治鼋Y(jié)果】（ 1）快遞公司有多個(gè)分公司，分公司信息包括分公司編號、名稱、經(jīng)理、辦公電話和地址。每個(gè)分公司可以有多名員工處理分公司的日常業(yè)務(wù)，每位

4、員工只能在一個(gè)分公司工作。每個(gè)分公司由一名經(jīng)理負(fù)責(zé)管理分公司的業(yè)務(wù)和員工，系統(tǒng)需要記錄每個(gè)經(jīng)理的任職時(shí)間。（ 2）員工信息包括員工號、姓名、崗位、薪資、手機(jī)號和家庭地址。其中，員工號唯一標(biāo)識員工信息的每一個(gè)元組。崗位包括經(jīng)理、調(diào)度員、業(yè)務(wù)員等。業(yè)務(wù)員根據(jù)客戶提交的快件申 請單進(jìn)行快件受理事宜，一個(gè)業(yè)務(wù)員可以受理多個(gè)客戶的快件申請，一個(gè)快件申請只能由一個(gè)業(yè)務(wù)員受理。調(diào)度員根據(jù)已受理的申請單安排快件的承運(yùn)事宜，例如：執(zhí)行承運(yùn)的業(yè)務(wù)員、運(yùn)達(dá)時(shí)間等。一個(gè)業(yè)務(wù)員可以執(zhí)行調(diào)度員安排的多個(gè)快件的承運(yùn)業(yè)務(wù)。（ 3）客戶信息包括客戶號、單位名稱、通信地址、所屬省份、聯(lián)系人、聯(lián)系電話、銀行賬號。其中，客戶號唯一標(biāo)

5、識客戶信息的每一個(gè)元組。當(dāng)客戶要寄快件時(shí)，先要提交快件申請 單，申請?zhí)栍上到y(tǒng)自動生成?？旒暾埿畔ㄉ暾?zhí)?、客戶號、發(fā)件人、發(fā)件人電話、快件 名稱、運(yùn)費(fèi)、發(fā)出地、收件人、收件人電話、收件地址。其中，一個(gè)申請?zhí)枌?yīng)唯一的一個(gè)快件申請，一個(gè)客戶可以提交多個(gè)快件申請，但一個(gè)快件申請由唯一的一個(gè)客戶提交?！靖拍钅Ｐ驮O(shè)計(jì)】根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖（圖2-1 ）和關(guān)系模型（不完整）如下：【關(guān)系模型設(shè)計(jì)】分公司（分公司編號，名稱，經(jīng)理，辦公電話，地址）員工（員工號，姓名，（a） ，崗位，薪資，手機(jī)號，家庭地址）客戶（客戶號，單位名稱，通信地址，所屬省份，聯(lián)系人，聯(lián)系電話，銀行賬號）申請單（

6、 b） ，發(fā)件人，發(fā)件人電話，發(fā)件人地址，快件名稱，運(yùn)費(fèi)，收件人，收件人電話，收件地址，受理標(biāo)志，業(yè)務(wù)員）安排承運(yùn)（c） ，實(shí)際完成時(shí)間，調(diào)度員）【問題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)系5代替，聯(lián)系的類型分為1:1、 1:n和 m:n （或1:1、1:*和*:*）?！締栴}2 】（ 1）根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中的空（ a）(c) 補(bǔ)充完整；（ 2）給出員工、申請單和安排承運(yùn)關(guān)系模式的主鍵和外鍵?！締栴} 3】（1）客戶關(guān)系的通信地址可以進(jìn)一步分為郵編、省、市、街道，那么該屬性是否屬于簡單屬性，為什么？請用100 字以內(nèi)

7、的文字說明。（2）假設(shè)分公司需要增設(shè)一位經(jīng)理的職位，那么分公司與經(jīng)理之間的聯(lián)系類型應(yīng)修改為（ d），分公司的主鍵應(yīng)修改為（e）。三、閱讀下列說明和圖，回答問題1至問題 3 ，將解答填入答題紙的對應(yīng)欄內(nèi)。【說明】某航空公司會員積分系統(tǒng)（CFrequentFlyer ）的主要功能描述如下：乘客只要辦理該航空公司的會員卡，即可成為普卡會員（CBasic）。隨著飛行里程數(shù)的積累，可以從普卡會員升級到銀卡會員（CSilver ）或金卡會員（ CGold）。非會員（ CNonMember）不能積累里程數(shù)。每年年末，系統(tǒng)根據(jù)會員在本年度累積的里程數(shù)對下一年會員等級進(jìn)行調(diào)整。普卡會員在一年內(nèi)累積的里程數(shù)若滿

8、25000 英里但不足 50000 英里，則自動升級為銀卡會員；若累積的里程數(shù)在50000 英里以上，則自動升級為金卡會員。銀卡會員在一年內(nèi)累積的里程數(shù)若在 50000 英里以上，則自動升級為金卡會員。若一年內(nèi)沒有達(dá)到對應(yīng)級別要求的里程數(shù)，則自動降低會員等級。金卡會員一年內(nèi)累積的里程數(shù)若不足 25000 英里，則自動降級為普卡會員；若累積的里程數(shù)達(dá)到25000 英里，但是不足50000 英里，則自動降級為銀卡會員。銀卡會員一年內(nèi)累積的里程數(shù)若不足25000英里，則自動降級為普卡會員。采用面向?qū)ο蠓椒▽T積分系統(tǒng)進(jìn)行分析與設(shè)計(jì)，得到如圖3-1所示的狀態(tài)圖和圖 3-2所示的類圖。3-1 狀態(tài)圖圖

9、 3-2 的類圖【問題 1 】（6 分）根據(jù)說明中的描述，給出圖3-1中 S1S3 處所對應(yīng)的狀態(tài)以及T1T3 處所對應(yīng)的遷移的名稱?！締栴} 2 】（4 分）根據(jù)說明中的描述，給出圖3-2中 C1C4 所對應(yīng)的類名（類名使用說明中給出的英文詞匯）?！締栴} 3 】（5 分）圖 3-2所示的類圖中使用了哪種設(shè)計(jì)模式？在這種設(shè)計(jì)模式下，類CFrequentFlyer必須具有的屬性是什么？C1C4 中的 travel方法應(yīng)具有什么功能？四、閱讀下列說明和C 代碼，回答問題1至問題 3 ，將解答填入答題紙的對應(yīng)欄內(nèi)?！菊f明】某工程計(jì)算中要完成多個(gè)矩陣相乘（鏈乘）的計(jì)算任務(wù)。兩個(gè)矩陣相乘要求第一個(gè)矩陣的列

10、數(shù)等于第二個(gè)矩陣的行數(shù)，計(jì)算量主要由進(jìn)行乘法運(yùn)算的 次數(shù)決定。采用標(biāo)準(zhǔn)的矩陣相乘算法，計(jì)算 Amn*Bnp，需要 m*n*p 次乘法運(yùn)算。矩陣相乘滿足結(jié)合律，多個(gè)矩陣相乘，不同的計(jì)算順序會產(chǎn)生不同的計(jì)算量。以矩陣A110100，A21005，A3550 三個(gè)矩陣相乘為例，若按（A1*A2） *A3 計(jì)算，則需要進(jìn)行10*100*5+10*5*50=7500次乘法運(yùn)算；若按A1* （A2*A3）計(jì)算，則需要進(jìn)行100*5*50+10*100*50=75000 次乘法運(yùn)算。可見不同的計(jì)算順序?qū)τ?jì)算量有很大的影響。矩陣鏈乘問題可描述為：給定n個(gè)矩陣 ，矩陣 Ai的維數(shù)為 pi-1pi ，其中i =

11、1,2,.n 。確定一種乘法順序，使得這n 個(gè)矩陣相乘時(shí)進(jìn)行乘法的運(yùn)算次數(shù)最少。由于可能的計(jì)算順序數(shù)量非常龐大，對較大的 n ，用蠻力法確定計(jì)算順序是不實(shí)際的。經(jīng)過對問題進(jìn)行分析，發(fā)現(xiàn)矩陣鏈乘問題具有最優(yōu)子結(jié)構(gòu)，即若 A1*A2* *An 的一個(gè)最優(yōu)計(jì)算順序從第 k 個(gè)矩陣處斷開，即分為 A1*A2* .Ak 和 Ak+1*Ak+2* *An 兩個(gè)子問題，則該最優(yōu)解應(yīng)該包含 A1*A2* *Ak 的一個(gè)最優(yōu)計(jì)算順序和 Ak+1*Ak+2* An 的一個(gè)最優(yōu)計(jì)算順序。據(jù)此構(gòu)造遞歸式，其中， costij表示 Ai+1*Ai+2*.Aj+1的最優(yōu)計(jì)算的計(jì)算代價(jià)。最終需要求解cost0n-1?！綜

12、代碼】算法實(shí)現(xiàn)采用自底向上的計(jì)算過程。首先計(jì)算兩個(gè)矩陣相乘的計(jì)算量，然后依次計(jì)算 3 個(gè)矩陣、 4 個(gè)矩陣、 、 n 個(gè)矩陣相乘的最小計(jì)算量及最優(yōu)計(jì)算順序。下面是算法的 C 語言實(shí)現(xiàn)。（ 1）主要變量說明n：矩陣數(shù)seq ：矩陣維數(shù)序列cost：二維數(shù)組，長度為n*n ，其中元素 costij表示 Ai+1*Ai+2*Aj+1的最優(yōu)計(jì)算的計(jì)算代價(jià)trace：二維數(shù)組，長度為n*n ，其中元素 traceij表示 Ai+1*Ai+2*Aj+1的最優(yōu)計(jì)算對應(yīng)的劃分位置，即k（ 2）函數(shù) cmm #define N 100 int costNN; int traceNN;int cmm(int n,

13、int seq) int tempCost; int tempTrace; int i,j,k,p;int temp;for( i=0;in;i+) costii = 0; for(p=1;pn;p+) for(i=0; （ 1） ;i+)（2） ; tempCost = -1; for(k = i;ktemp) tempCost = temp;（4） ;costij = tempCost; traceij = tempTrace;return cost0n-1;【問題1】（ 8 分）根據(jù)以上說明和C 代碼，填充 C 代碼中的空（ 1）（4）?！締栴} 2 】（4 分）根據(jù)以上說明和C 代碼，該

14、問題采用了（5） 算法設(shè)計(jì)策略，時(shí)間復(fù)雜度（6） 。（用 O 符號表示）【問題 3 】（3 分）考慮實(shí)例 n=6 ，各個(gè)矩陣的維數(shù)： A1 為 5*10 ，A2 為 10*3 ， A3 為 3*12 ， A4 為12*5， A5 為 5*50 ， A6 為 50*6 ，即維數(shù)序列為5,10,3,12,5,50,6。則根據(jù)上述 C 代碼得到的一個(gè)最優(yōu)計(jì)算順序?yàn)椋?7） （用加括號方式表示計(jì)算順序），所需要的乘法運(yùn)算次數(shù)為（8） 。五、閱讀下列說明和C+代碼，將應(yīng)填入（ n）處的字句寫在答題紙的對應(yīng)欄內(nèi)?！菊f明】欲開發(fā)一個(gè)繪圖軟件，要求使用不同的繪圖程序繪制不同的圖形。以繪制直線和圓形為例，對應(yīng)的

15、繪圖程序如表5-1所示。該繪圖軟件的擴(kuò)展性要求，將不斷擴(kuò)充新的圖形和新的繪圖程序。為了避免出現(xiàn)類爆炸的情況，現(xiàn)采用橋接（ Bridge ）模式來實(shí)現(xiàn)上述要求，得到如圖5-1所示的類圖。圖5-1類圖【C+ 代碼】class DP1 public:static void draw_a_line(double x1,double y1,double x2,double y2)/*代碼省略*/ static void draw_a_circle(double x,double y,double r) /*代碼省略 */;class DP2 public:static void drawline(dou

16、ble x1,double x2,double y1,double y2)/*代碼省略*/ static void drawcircle(double x,double y,double r)/*;class Drawing public:（1）;（2）;代碼省略 */;class V1Drawing:public Drawing public:void drawLine(double x1,double y1,double x2, double y2)/*代碼省略*/void drawCircle(double x, double y, double r)（3）;class V2Drawin

17、g:public Drawing public:void drawLine(double x1,double y1,double x2, double y2)/*void drawCircle(double x, doubley, double r)（4）;代碼省略*/;class Shape public:（5） ;Shape(Drawing * dp) _dp = dp;void drawLine(double x1, double y1,double x2, double y2)_dp-drawLine(x1,y1,x2,y2); void drawCircle(double x, do

18、uble y, double r)_dp-drawCircle(x,y,r);private: Drawing * _dp;class Rectangle:public Shape public:void draw (17) /*代碼省略 */ 其余代碼省略;class Circle:public Shape private: double _x,_y,_r; public:Circle(Drawing * dp, double x, double y, double r):（6） _x = x; _y= y; _r = r; void draw (18) drawCircle(_x, _y,

19、 _r); ;六、閱讀下列說明和 Java 代碼，將應(yīng)填入（ n）處的字句寫在答題紙的對應(yīng)欄內(nèi)?！菊f明】欲開發(fā)一個(gè)繪圖軟件，要求使用不同的繪圖程序繪制不同的圖形。以繪制直線和圓形為例， 對應(yīng)的繪圖程序如表 6-1 所示。該繪圖軟件的擴(kuò)展性要求，將不斷擴(kuò)充新的圖形和新的繪圖程序。為了避免出現(xiàn)類爆炸的情 況，現(xiàn)采用橋接（ Bridge ）模式來實(shí)現(xiàn)上述要求，得到如圖 6-1 所示的類圖。圖 6-1 類圖【 Java 代碼】（1） Drawing（2） ;（3） ;class DP1static public void draw_a_line(double x1, double y1, double

20、 x2, double y2) /* 代碼省略 */ static public void draw_a_circle(double x, double y, double r) /* 代碼省略 */class DP2static public void drawline(double x1, double y1, double x2 ,double y2)/* 代碼省略 */ static public void drawcircle (double x, double y, double r)/* 代碼省略 */class V1Drawing implements Drawingpublic void drawLine(double x1, double y1, double x2 ,double y2)/*代碼省略*/ public void drawCircle(double x, double y, double r)（4）;class V2Drawing implements Drawingpublic void draw