下半下午真題

1、2008年下半年軟件設(shè)計(jì)師下午試卷試題一(共 15 分)閱讀下列說(shuō)明和圖,回答問(wèn)題 1 至問(wèn)題 3,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。【說(shuō)明】某營(yíng)銷(xiāo)企業(yè)擬開(kāi)發(fā)一個(gè)銷(xiāo)售管理系統(tǒng),其主要功能描述如下:1.接受客戶(hù)訂單,檢查庫(kù)存貨物是否滿(mǎn)足訂單要求。如果滿(mǎn)足,進(jìn)行供貨處理:即修改庫(kù)存記錄文件,給庫(kù)房開(kāi)具備貨單并且保留客戶(hù)訂單至訂單記錄文件;否則進(jìn)行缺貨處理:將缺貨訂單錄入缺貨記錄文件。2.根據(jù)缺貨記錄文件進(jìn)行缺貨統(tǒng)計(jì),將缺貨通知單發(fā)給采購(gòu)部門(mén)。3.根據(jù)采購(gòu)部門(mén)提供的進(jìn)貨通知單進(jìn)行進(jìn)貨處理:即修改庫(kù)存記錄文件,并從缺貨記錄文件中取出缺貨訂單進(jìn)行供貨處理。4.根據(jù)保留的客戶(hù)訂單進(jìn)行銷(xiāo)售統(tǒng)計(jì),打印統(tǒng)計(jì)報(bào)表給經(jīng)理

2、?，F(xiàn)采用結(jié)構(gòu)化方法對(duì)銷(xiāo)售管理系統(tǒng)進(jìn)行分析與設(shè)計(jì),獲得如圖 1-1 所示的頂層數(shù)據(jù)流圖和圖 1-2 所示的 0 層數(shù)據(jù)流圖。【問(wèn)題 1】(4 分)使用說(shuō)明中的詞語(yǔ),給出圖 1-1 的外部實(shí)體 E1E4 的名稱(chēng)?！締?wèn)題 2】(3 分)使用說(shuō)明中的詞語(yǔ),給出圖 1-2 的數(shù)據(jù)存儲(chǔ) D1D3 的名稱(chēng)?！締?wèn)題 3】(8 分)數(shù)據(jù)流圖 1-2 缺少了四條數(shù)據(jù)流,根據(jù)說(shuō)明及數(shù)據(jù)流圖 1-1 提供的信息,分別指出這四條數(shù)據(jù)流的起點(diǎn)和終點(diǎn)。起點(diǎn)終點(diǎn)試題二(共 15 分)閱讀下列說(shuō)明和圖,回答問(wèn)題 1 至問(wèn)題 4,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。【說(shuō)明】某賓館擬開(kāi)發(fā)一個(gè)賓館客房預(yù)訂子系統(tǒng),主要是針對(duì)客房的預(yù)訂和入住等

3、情況進(jìn)行管理。【需求分析結(jié)果】1.員工信息主要包括:員工號(hào)、姓名、出生年月、性別、部門(mén)、崗位、住址、聯(lián)系電話(huà)和密碼等信息。崗位有管理和服務(wù)兩種。崗位為”管理”的員工可以更改(添加、刪除和修改)員工表中的本部門(mén)員工的崗位和密碼,要求將每一次更改前的信息保留;崗位為”服務(wù)”的員工只能修改員工表中本人的密碼,且負(fù)責(zé)多個(gè)客房的清理等工作。2.部門(mén)信息主要包括:部門(mén)號(hào)、部門(mén)名稱(chēng)、部門(mén)負(fù)責(zé)人、電話(huà)等信息;一個(gè)員工只能屬于一個(gè)部門(mén),一個(gè)部門(mén)只有一位負(fù)責(zé)人。 3.客房信息包括:客房號(hào)、類(lèi)型、價(jià)格、狀態(tài)等信息。其中類(lèi)型是指單人間、三人間、普通標(biāo)準(zhǔn)間、豪華標(biāo)準(zhǔn)間等;狀態(tài)是指空閑、入住和維修。4.客戶(hù)信息包括:身份

4、證號(hào)、姓名、性別、單位和聯(lián)系電話(huà)。5.客房預(yù)定情況包括:客房號(hào)、預(yù)定日期、預(yù)定入住日期、預(yù)定入住天數(shù)、身份證號(hào)等信息。一條預(yù)定信息必須且僅對(duì)應(yīng)一位客戶(hù),但一位客戶(hù)可以有多條預(yù)定信息?！靖拍钅Ｐ驮O(shè)計(jì)】根據(jù)需求階段收集的信息,設(shè)計(jì)的實(shí)體聯(lián)系圖(不完整)如圖 2-1 所示:【邏輯結(jié)構(gòu)設(shè)計(jì)】邏輯結(jié)構(gòu)設(shè)計(jì)階段設(shè)計(jì)的部分關(guān)系模式(不完整)如下:員工( (4),姓名,出生年月,性別,崗位,住址,聯(lián)系電話(huà),密碼) 權(quán)限(崗位,操作權(quán)限)部門(mén)(部門(mén)號(hào),部門(mén)名稱(chēng),部門(mén)負(fù)責(zé)人,電話(huà))客房( (5),類(lèi)型,價(jià)格,狀態(tài),入住日期,入住時(shí)間,員工號(hào))客戶(hù)( (6),姓名,性別,單位,聯(lián)系電話(huà)) 更改權(quán)限(員工號(hào),(7),

5、密碼,更改日期,更改時(shí)間,管理員號(hào)) 預(yù)定情況( (8) ,預(yù)定日期,預(yù)定入住日期,預(yù)定入住天數(shù)) 【問(wèn)題 1】(3 分)根據(jù)問(wèn)題描述,填寫(xiě)圖 2-1 中(1)(3)處聯(lián)系的類(lèi)型。聯(lián)系類(lèi)型分為一對(duì)一、一對(duì)多和多對(duì)多三種,分別使用 1 : 1,1 : n或 1 : *,m : n或 * : *表示?！締?wèn)題 2】(2 分)補(bǔ)充圖 2-1 中的聯(lián)系并指明其聯(lián)系類(lèi)型?！締?wèn)題 3】(7 分)根據(jù)需求分析結(jié)果和圖2-1,將邏輯結(jié)構(gòu)設(shè)計(jì)階段生成的關(guān)系模式中的空(4)(8)補(bǔ)充完整。(注:一個(gè)空可能需要填多個(gè)屬性)【問(wèn)題 4】(3 分)若去掉權(quán)限表,并將權(quán)限表中的操作權(quán)限屬性放在員工表中(仍保持管理和服務(wù)崗位

6、的操作權(quán)限規(guī)定),則與原有設(shè)計(jì)相比有什么優(yōu)缺點(diǎn)(請(qǐng)從數(shù)據(jù)庫(kù)設(shè)計(jì)的角度進(jìn)行說(shuō)明)? 試題三(共 15 分)閱讀下列說(shuō)明和圖,回答問(wèn)題 1 至問(wèn)題 4,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】在線(xiàn)會(huì)議審稿系統(tǒng)(ORS:Online Reviewing System)主要處理會(huì)議前期的投稿和審稿事務(wù),其功能描述如下:1.用戶(hù)在初始使用系統(tǒng)時(shí),必須在系統(tǒng)中注冊(cè)(register)成為作者或?qū)徃迦恕?.作者登錄(login)后提交稿件和瀏覽稿件審閱結(jié)果。提交稿件必須在規(guī)定提交時(shí)間范圍內(nèi),其過(guò)程為先輸入標(biāo)題和摘要、選擇稿件所屬主題類(lèi)型、選擇稿件所在位置(存儲(chǔ)位置)。上述幾步若未完成,則重復(fù);若完成,則上傳稿件

7、至數(shù)據(jù)庫(kù)中,系統(tǒng)發(fā)送通知。3.審稿人登錄后可設(shè)置興趣領(lǐng)域、審閱稿件給出意見(jiàn)以及羅列錄用和(或)拒絕的稿件。4.會(huì)議委員會(huì)主席是一個(gè)特殊審稿人,可以瀏覽提交的稿件、給審稿人分配稿件、羅列錄用和(或)拒絕的稿件以及關(guān)閉審稿過(guò)程。其中關(guān)閉審稿過(guò)程須包括羅列錄用和(或)拒絕的稿件。系統(tǒng)采用面向?qū)ο蠓椒ㄩ_(kāi)發(fā),使用 UML 進(jìn)行建模。在建模用例圖時(shí),常用的方式是先識(shí)別參與者,然后確定參與者如何使用系統(tǒng)來(lái)確定用例,每個(gè)用例可以構(gòu)造一個(gè)活動(dòng)圖。參與者名稱(chēng)、用例和活動(dòng)名稱(chēng)分別參見(jiàn)表 3-1、表 3-2 和表 3-3。系統(tǒng)的部分用例圖和提交稿件的活動(dòng)圖分別如圖 3-1 和圖 3-2 所示。表 3-1 參與者列表名

8、稱(chēng)說(shuō)明名稱(chēng)說(shuō)明User用戶(hù)Author作者Reviewer審稿人Pcchair委員會(huì)主席表 3-2 用例名稱(chēng)列表名稱(chēng)說(shuō)明名稱(chēng)說(shuō)明login登錄系統(tǒng)register注冊(cè)submit paper提交稿件browse review results瀏覽稿件審閱結(jié)果close reviewing process關(guān)閉審稿過(guò)程assiagn paper to reviewer分配稿件給出意見(jiàn)set preferences高定興趣領(lǐng)域enter review審閱稿件給出意見(jiàn)list accepted/rejected papers羅列錄用或/扣拒絕的稿件browse submitted papers瀏覽提交的

9、稿件表 3-3 活動(dòng)名稱(chēng)列表名稱(chēng)說(shuō)明名稱(chēng)說(shuō)明select paper location選擇稿件位置upload paper上傳稿件elect subject group選擇主題類(lèi)型send notification發(fā)送通知enter title and abstract輸入標(biāo)題和摘要圖 3-1 ORS 用例圖圖 3-2 提交稿件過(guò)程的活動(dòng)圖【問(wèn)題 1】(4 分) 根據(jù)【說(shuō)明】中的描述,使用表 3-1 中的英文名稱(chēng),給出圖 3-1 中 A1A4 所對(duì)應(yīng)的參與者?！締?wèn)題 2】(3 分)根據(jù)【說(shuō)明】中的描述,使用表 3-2 中的英文名稱(chēng),給出圖 3-1 中 U1U3 所對(duì)應(yīng)的用例?！締?wèn)題 3】(4

10、分) 根據(jù)【說(shuō)明】中的描述,給出圖 3-1 中(1)和(2)所對(duì)應(yīng)的關(guān)系。 【問(wèn)題 4】(4 分) 根據(jù)【說(shuō)明】中的描述,使用表 3-2 和表 3-3 中的英文名稱(chēng),給出圖 3-2 中 Action1Action4 對(duì)應(yīng)的活動(dòng)。試題四(共 15 分)閱讀下列說(shuō)明,回答問(wèn)題 1 至問(wèn)題 3,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。 【說(shuō)明】某餐廳供應(yīng)各種標(biāo)準(zhǔn)的營(yíng)養(yǎng)套餐。假設(shè)菜單上共有n項(xiàng)食物 m1,m2,mn,每項(xiàng)食物 mi的營(yíng)養(yǎng)價(jià)值為vi,價(jià)格為pi,其中i=1,2,n,套餐中每項(xiàng)食物至多出現(xiàn)一次。客人常需要一個(gè)算法來(lái)求解總價(jià)格不超過(guò)M的營(yíng)養(yǎng)價(jià)值最大的套餐。【問(wèn)題 1】(9 分) 下面是用動(dòng)態(tài)規(guī)劃策略求解

11、該問(wèn)題的偽代碼,請(qǐng)?zhí)畛淦渲械目杖?1)、(2)和(3)處。偽代碼中的主要變量說(shuō)明如下:n:總的食物項(xiàng)數(shù);v:營(yíng)養(yǎng)價(jià)值數(shù)組,下標(biāo)從 1 到 n,對(duì)應(yīng)第 1 到第 n 項(xiàng)食物的營(yíng)養(yǎng)價(jià)值;p:價(jià)格數(shù)組,下標(biāo)從 1 到 n,對(duì)應(yīng)第 1 到第 n 項(xiàng)食物的價(jià)格;M:總價(jià)格標(biāo)準(zhǔn),即套餐的價(jià)格不超過(guò) M;x: 解向量(數(shù)組),下標(biāo)從 1 到 n,其元素值為 0 或 1,其中元素值為 0 表示對(duì)應(yīng)的食物不出現(xiàn)在套餐中,元素值為 1 表示對(duì)應(yīng)的食物出現(xiàn)在套餐中;nv:n+1 行 M+1 列的二維數(shù)組,其中行和列的下標(biāo)均從 0 開(kāi)始,nvij表示由前 i 項(xiàng)食物組合且價(jià)格不超過(guò) j 的套餐的最大營(yíng)養(yǎng)價(jià)值。問(wèn)題最終

12、要求的套餐的最大營(yíng)養(yǎng)價(jià)值為nvnM。偽代碼如下:MaxNutrientValue(n, v, p, M, x) 1 for i = 0 to n2 nvi0 = 03 for j = 1 to M 4 nv0j = 05 for i = 1 to n6 for j = 1 to M 7 if j < pi /若食物 mi不能加入到套餐中8 nvij = nvi - 1j 9 else if (1)10 nvij = nvi - 1j 11 else 12 nvij = nvi - 1j pi + vi 13 j = M 14 for i = n downto 115 if (2)16 x

13、i = 0 17 else 18 xi = 119 (3)20 return x and nvnM 【問(wèn)題 2】(4 分) 現(xiàn)有 5 項(xiàng)食物,每項(xiàng)食物的營(yíng)養(yǎng)價(jià)值和價(jià)格如表 4-1 所示。表 4-1 食物營(yíng)養(yǎng)價(jià)值及價(jià)格表編 碼營(yíng)養(yǎng)價(jià)值價(jià) 格m120050m218030m322545m420025m5505若要求總價(jià)格不超過(guò) 100 的營(yíng)養(yǎng)價(jià)值最大的套餐,則套餐應(yīng)包含的食物有(4)(用食物項(xiàng)的編碼表示),對(duì)應(yīng)的最大營(yíng)養(yǎng)價(jià)值為(5)?！締?wèn)題 3】(2 分) 【問(wèn)題 1】中偽代碼的時(shí)間復(fù)雜度為(6)(用符號(hào)表示)。試題五(共 15 分)閱讀下列說(shuō)明和 C 函數(shù),將應(yīng)填入 (n) 處的字句寫(xiě)在答題紙的對(duì)

14、應(yīng)欄內(nèi)。 【說(shuō)明】已知集合 A 和 B 的元素分別用不含頭結(jié)點(diǎn)的單鏈表存儲(chǔ),函數(shù) Difference()用于求解集合 A 與 B 的差集,并將結(jié)果保存在集合 A 的單鏈表中。例如,若集合 A=5,10,20,15,25,30,集合 B=5,15,35,25,如圖 5-1(a)所示,運(yùn)算完成后的結(jié)果如圖 5-1(b)所示。圖5-1 集合A、B運(yùn)算前后示意圖鏈表結(jié)點(diǎn)的結(jié)構(gòu)類(lèi)型定義如下:typedef struct Node ElemType elem; struct Node *next; NodeType; 【C 函數(shù)】void Difference(NodeType *LA, NodeTyp

15、e *LB) NodeType *pa, *pb, *pre, *q; pre = NULL; (1) ;while (pa) pb = LB; while ( (2) ) pb = pb->next; if ( (3) ) if (!pre) *LA = (4) ; else (5) = pa->next; q = pa; pa = pa->next; free(q); Else (6);pa = pa->next; 試題六(共 15 分)閱讀下列說(shuō)明和 C+代碼,將應(yīng)填入 (n) 處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。 【說(shuō)明】 已知某類(lèi)庫(kù)開(kāi)發(fā)商提供了一套類(lèi)庫(kù),類(lèi)庫(kù)中定義了

16、Application 類(lèi)和 Document 類(lèi),它們之間的關(guān)系如圖6-1所示,其中,Application 類(lèi)表示應(yīng)用程序自身,而 Document 類(lèi)則表示應(yīng)用程序打開(kāi)的文檔。Application 類(lèi)負(fù)責(zé)打開(kāi)一個(gè)已有的以外部形式存儲(chǔ)的文檔,如一個(gè)文件,一旦從該文件中讀出信息后,它就由一個(gè) Document 對(duì)象表示。圖 6-1 Application 與 Document 關(guān)系圖當(dāng)開(kāi)發(fā)一個(gè)具體的應(yīng)用程序時(shí),開(kāi)發(fā)者需要分別創(chuàng)建自己的 Application 和 Document子類(lèi),例如圖6-1中的類(lèi)MyApplication和類(lèi) MyDocument,并分別實(shí)現(xiàn)Application和

17、Document 類(lèi)中的某些方法。已知 Application 類(lèi)中的 openDocument 方法采用了模板方法(Template Method設(shè)計(jì)模式,該方法定義了打開(kāi)文檔的每一個(gè)主要步驟,如下所示:1.首先檢查文檔是否能夠被打開(kāi),若不能打開(kāi),則給出出錯(cuò)信息并返回;2.創(chuàng)建文檔對(duì)象;3.通過(guò)文檔對(duì)象打開(kāi)文檔;4.通過(guò)文檔對(duì)象讀取文檔信息;5.將文檔對(duì)象加入到 Application 的文檔對(duì)象集合中。【C+代碼】 #include <iostream> #include <vector> using namespace std; class Document pu

18、blic: void save() /*存儲(chǔ)文檔數(shù)據(jù),此處代碼省略*/ ; void open(string docName) /* 打開(kāi)文檔,此處代碼省略 */ void close() /* 關(guān)閉文檔,此處代碼省略*/ virtual void read(string docName) = 0; class Appplication private: vector < (1) > docs; /*文檔對(duì)象集合*/ public: bool canOpenDocument(string docName) /*判斷是否可以打開(kāi)指定文檔,返回真值時(shí)表示可以打開(kāi),返回假值表示不可打開(kāi),

19、此處代碼省略*/ void addDocument(Document * aDocument) /*將文檔對(duì)象添加到文檔對(duì)象集合中*/ docs.push_back( (2) ); virtual Document * doCreateDocument() = 0; /*創(chuàng)建一個(gè)文檔對(duì)象*/ void openDocument(string docName) /*打開(kāi)文檔*/ if ( (3) ) cout << "文檔無(wú)法打開(kāi)!" << endl; return; (4) adoc = (5) ; (6) ; (7) ; (8) ; ; 試題七(共 15 分)閱讀下列說(shuō)明和 Java 代碼,將應(yīng)填入 (n) 處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。 說(shuō)明及提示均與上題相同。【Java 代碼】 abstract