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

1、 軟件設(shè)計(jì)師考試模擬題及答案-試題一 閱讀下列說明和圖，回答問題1至問題3，將解答填入對應(yīng)欄內(nèi)。【說明】 某營銷企業(yè)擬開發(fā)一個(gè)銷售管理系統(tǒng)，其主要功能描述如下： 1接受客戶訂單，檢查庫存貨物是否滿足訂單要求。如果滿足，進(jìn)行供貨處理：修改庫存記錄文件，給庫房開具備貨單并且保留客戶訂單至訂單記錄文件；否則進(jìn)行缺貨處理：將缺貨訂單錄入缺貨記錄文件。 2根據(jù)缺貨記錄文件進(jìn)行缺貨統(tǒng)計(jì)，將缺貨通知單發(fā)給采購部門。 3根據(jù)采購部門提供的進(jìn)貨通知單進(jìn)行進(jìn)貨處理：修改庫存記錄文件，并從缺貨記錄文件中取出缺貨訂單進(jìn)行供貨處理。 4根據(jù)保留的客戶訂單進(jìn)行銷售統(tǒng)計(jì)，打印統(tǒng)計(jì)報(bào)表給經(jīng)理。 現(xiàn)采用結(jié)構(gòu)化方法對銷售管理系統(tǒng)

2、進(jìn)行分析與設(shè)計(jì)，獲得如下圖所示的頂層數(shù)據(jù)流圖和0層數(shù)據(jù)流圖。 1、【問題1】 使用說明中的詞語，給出上述頂層數(shù)據(jù)流圖中的外部實(shí)體E1E4的名稱。2、【問題2】 使用說明中的詞語，給出上述0層數(shù)據(jù)流圖中的數(shù)據(jù)存儲(chǔ)D1D3的名稱。3、【問題3】 上述0層數(shù)據(jù)流圖中缺少了4條數(shù)據(jù)流，根據(jù)說明及頂層數(shù)據(jù)流圖提供的信息，分別指出這4條數(shù)據(jù)流的起點(diǎn)和終點(diǎn)。起點(diǎn)終點(diǎn)試題二 閱讀下列說明和圖，回答問題1至問題4，將解答填入對應(yīng)欄內(nèi)?！菊f明】 某賓館擬開發(fā)一個(gè)賓館客房預(yù)訂子系統(tǒng)，主要是針對客房的預(yù)訂和入住等情況進(jìn)行管理。【需求分析結(jié)果】 1員工信息主要包括：員工號(hào)、姓名、出生年月、性別、部門、崗位、住址、聯(lián)系電

3、話和密碼等信息。崗位有管理和服務(wù)兩種。崗位為“管理”的員工可以更改(添加、刪除和修改)員工表中本部門員工的崗位和密碼，要求將每一次更改前的信息保留；崗位為“服務(wù)”的員工只能修改員工表中本人的密碼，且負(fù)責(zé)多個(gè)客房的清理等工作。 2部門信息主要包括：部門號(hào)、部門名稱、部門負(fù)責(zé)人、電話等信息。一個(gè)員工只能屬于一個(gè)部門，一個(gè)部門只有一位負(fù)責(zé)人。 3客房信息包括：客房號(hào)、類型、價(jià)格、狀態(tài)等信息。其中類型是指單人間、三人間、普通標(biāo)準(zhǔn)間、豪華標(biāo)準(zhǔn)間等；狀態(tài)是指空閑、入住和維修。 4客戶信息包括：身份證號(hào)、姓名、性別、單位和聯(lián)系電話。 5客房預(yù)定情況包括：客房號(hào)、預(yù)定日期、預(yù)定入住日期、預(yù)定入住天數(shù)、身份證號(hào)

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

5、根據(jù)問題描述，填寫上圖中(1)(3)處聯(lián)系的類型。聯(lián)系類型分為一對一、一對多和多對多三種，分別使用1:1，1:n或1:*，m:n或*:*表示。5、【問題2】 補(bǔ)充上圖中的聯(lián)系并指明其聯(lián)系類型。6、【問題3】 根據(jù)需求分析結(jié)果和上圖，將邏輯結(jié)構(gòu)設(shè)計(jì)階段生成的關(guān)系模式中的空(4)(8)補(bǔ)充完整。(注：一個(gè)空可能需要填多個(gè)屬性)7、【問題4】 若去掉權(quán)限表，并將權(quán)限表中的操作權(quán)限屬性放在員工表中(仍保持管理和服務(wù)崗位的操作權(quán)限規(guī)定)，則與原有設(shè)計(jì)相比有什么優(yōu)缺點(diǎn)(請從數(shù)據(jù)庫設(shè)計(jì)的角度進(jìn)行說明)。試題三 閱讀下列說明和圖，回答問題1至問題4，將解答填入對應(yīng)欄內(nèi)?！菊f明】 在線會(huì)議審稿系統(tǒng)(Online

6、 Reviewing System，ORS)主要處理會(huì)議前期的投稿和審稿事務(wù)，其功能描述如下： 1用戶在初始使用系統(tǒng)時(shí)，必須在系統(tǒng)中注冊(register)成為作者或?qū)徃迦恕?2作者登錄(login)后提交稿件和瀏覽稿件審閱結(jié)果。提交稿件必須在規(guī)定提交時(shí)間范圍內(nèi)，其過程為先輸入標(biāo)題和摘要、選擇稿件所屬主題類型、選擇稿件所在位置 (存儲(chǔ)位置)。上述幾步若未完成，則重復(fù)；若完成，則上傳稿件至數(shù)據(jù)庫中，系統(tǒng)發(fā)送通知。 3審稿人登錄后可設(shè)置興趣領(lǐng)域、審閱稿件給出意見以及羅列錄用和(或)拒絕的稿件。 4會(huì)議委員會(huì)主席是一個(gè)特殊審稿人，可以瀏覽提交的稿件、給審稿人分配稿件、羅列錄用和(或)拒絕的稿件以及關(guān)

7、閉審稿過程。其中，關(guān)閉審稿過程須包括羅列錄用和(或)拒絕的稿件。 系統(tǒng)采用面向?qū)ο蠓椒ㄩ_發(fā)，使用UMi進(jìn)行建模。在建模用例圖時(shí)，常用的方式是先識(shí)別參與者，然后確定參與者如何使用系統(tǒng)來確定用例，每個(gè)用例可以構(gòu)造一個(gè)活動(dòng)圖。參與者名稱、用例和活動(dòng)名稱分別參見以下各表。參與者列表名稱說明名稱說明User用戶Author作者Reviewer審稿人PCChair委員會(huì)主席 用例名稱列表 名稱說明名稱說明login登錄系統(tǒng)register注冊submit paper 提交稿件browse review results 瀏覽稿件審閱結(jié)果close reviewing procss 關(guān)閉審稿過程assign

8、paper to reviewer 分配稿件給審稿人set preferences 設(shè)定興趣領(lǐng)域enter review 審閱稿件給出意見listaccepted/rejected papers羅列錄用或/和拒 絕的稿件browsesubmitted papers瀏覽提交的稿件活動(dòng)名稱列表名稱說明名稱說明select paper location 選擇稿件位置upload paper 上傳稿件select subject group 選擇主題類型send notification 發(fā)送通知enter title and abstract 輸入標(biāo)題和摘要系統(tǒng)的部分用例圖和提交稿件的活動(dòng)圖分別見下

9、圖。 8、【問題1】 根據(jù)說明中的描述，使用參與者列表的英文名稱，給出ORS用例圖中A1A4所對應(yīng)的參與者。9、【問題2】 根據(jù)說明中的描述，使用用例名稱列表中的英文名稱，給出ORS用例圖中U1一 U3所對應(yīng)的用例。10、【問題3】 根據(jù)說明中的描述，給出ORS用例圖中 (1) 和 (2) 所對應(yīng)的關(guān)系。11、【問題4】 根據(jù)說明中的描述，使用用例名稱列表和活動(dòng)名稱列表中的英文名稱，給出提交稿件過程的活動(dòng)圖中ActionlAction4對應(yīng)的活動(dòng)。試題四 閱讀下列說明，回答問題1至問題3，將解答填入對應(yīng)欄內(nèi)?！菊f明】 某餐廳供應(yīng)各種標(biāo)準(zhǔn)的營養(yǎng)套餐。假設(shè)菜單上共有n項(xiàng)食物m1，m2，mn，每項(xiàng)食

10、物mi的營養(yǎng)價(jià)值為vi，價(jià)格為pi其中i1，2，n，套餐中每項(xiàng)食物至多出現(xiàn)一次。客人常需要一個(gè)算法來求解總價(jià)格不超過M的營養(yǎng)價(jià)值最大的套餐。12、【問題1】 下面是用動(dòng)態(tài)規(guī)劃策略求解該問題的偽代碼，請?zhí)畛淦渲械目杖?1)、(2)和(3)處。 偽代碼中的主要變量說明如下。 n：總的食物項(xiàng)數(shù)； v：營養(yǎng)價(jià)值數(shù)組，下標(biāo)從1到n，對應(yīng)第1到第n項(xiàng)食物的營養(yǎng)價(jià)值； p：價(jià)格數(shù)組，下標(biāo)從1到n，對應(yīng)第1到第n項(xiàng)食物的價(jià)格； M：總價(jià)格標(biāo)準(zhǔn)，即套餐的價(jià)格不超過M； x：解向量(數(shù)組)，下標(biāo)從1到n，其元素值為0或1，其中元素值為0表示對應(yīng)的食物不出現(xiàn)在套餐中，元素值為1表示對應(yīng)的食物出現(xiàn)在套餐中； nv：n

11、+1行M+1列的二維數(shù)組，其中行和列的下標(biāo)均從0開始，nvij表示由前i項(xiàng)食物組合且價(jià)格不超過j的套餐的最大營養(yǎng)價(jià)值。問題最終要求的套餐的最大營養(yǎng)價(jià)值為nvnM。 偽代碼如下： MaxNutrientValue(n，v，p，M，x) 1 for i0 to n 2 nvi0 0 3 for j1 to M 4 nv0j0 5 for i1 to n 6 for j1 to M 7 if jpi /若食物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 fo

12、r in downto 1 15 if (2) 16 xi 0 17 else 18 xi 1 19 (3) 20 return x and nvnM13、【問題2】 現(xiàn)有5項(xiàng)食物，每項(xiàng)食物的營養(yǎng)價(jià)值和價(jià)格如下表所示。編碼營養(yǎng)價(jià)值價(jià)格m120050m218030m322545m420025m5505食物營養(yǎng)價(jià)值及價(jià)格表若要求總價(jià)格不超過100的營養(yǎng)價(jià)值最大的套餐，則套餐應(yīng)包含的食物有 (4) (用食物項(xiàng)的編碼表示)，對應(yīng)的最大營養(yǎng)價(jià)值為 (5) 。14、【問題3】 問題1中偽代碼的時(shí)間復(fù)雜度為 (6) (用O符號(hào)表示)。試題五 閱讀下列說明和C函數(shù)，將應(yīng)填入 (n) 處的字句寫在對應(yīng)欄內(nèi)。15

13、、【說明】 已知集合A和B的元素分別用不含頭結(jié)點(diǎn)的單鏈表存儲(chǔ)，函數(shù)Difference()用于求解集合A與B的差集，并將結(jié)果保存在集合A的單鏈表中。例如，若集合A5，10， 20，15，25，30，集合B5，15，35，25，如圖(a)所示，運(yùn)算完成后的結(jié)果如圖(b)所示。 鏈表結(jié)點(diǎn)的結(jié)構(gòu)類型定義如下： typedef struct Node ElemType elem； struct Node *next； NodeType；【C函數(shù)】 void Difference(NodeType *LA，NodeType *LB. NodeType *pa， *pb， *pre， *q； preNUL

14、L； (1) ； while (pa) pbLB； while( (2) ) pbpb-next； if( (3) ) if(!pre) *LA (4) ； else (5) pa-next； q pa； papa-next； free(q)； else (6) ； papa-next； 試題六 閱讀下列說明和C+代碼，將應(yīng)填入 (n) 處的字句寫在對應(yīng)欄內(nèi)。16、【說明】 已知某類庫開發(fā)商提供了一套類庫，類庫中定義了Application類和Document類，它們之間的關(guān)系如下圖所示。其中，Application類表示應(yīng)用程序自身，而Document類則表示應(yīng)用程序打開的文檔。Applic

15、ation類負(fù)責(zé)打開一個(gè)已有的以外部形式存儲(chǔ)的文檔，如一個(gè)文件，一旦從該文件中讀出信息后，它就由一個(gè)Document對象表示。 當(dāng)開發(fā)一個(gè)具體的應(yīng)用程序時(shí)，開發(fā)者需要分別創(chuàng)建自己的Application和Document子類，例如上圖中的類MyApplication和類MyDocument，并分別實(shí)現(xiàn)Application和 Document類中的某些方法。 已知Application類中的openDocument方法采用了模板方法(Template Method)設(shè)計(jì)模式，該方法定義了打開文檔的每一個(gè)主要步驟，如下所示： 1首先檢查文檔是否能夠被打開，若不能打開，則給出出錯(cuò)信息并返回； 2創(chuàng)

16、建文檔對象； 3通過文檔對象打開文檔； 4通過文檔對象讀取文檔信息； 5將文檔對象加入到Application的文檔對象集合中?！綜+代碼】 #includeiostream #includevector using namespace std； class Document public： void save()/*存儲(chǔ)文檔數(shù)據(jù)，此處代碼省略*/) void open(string docName) /*打開文檔，此處代碼省略*/) void close() /*關(guān)閉文檔，此處代碼省略*/) virtual void read(string docName) 0； ； class Apppl

17、ication private： vector (1) docs； /*文檔對象集合*/ public： bool canOpenDocument(string docName) /*判斷是否可以打開指定文檔，返回真值時(shí)表示可以打開， 返回假值表示不可打開，此處代碼省略*/ void addDocument(Document * aDocument) /*將文檔對象添加到文檔對象集合中*/ docs.push_back( (2) )； virtual Document * doCreateDocument()0；/*創(chuàng)建一個(gè)文檔對象*/ void openDocument(string doc

18、Name)/*打開文檔*/ if ( (3) ) cout“文檔無法打開!”endl； return； (4) adoc (5) ； (6) ； (7) ； (8) ； ；試題七 閱讀下列說明和Java代碼，將應(yīng)填入 (n) 處的字句寫在對應(yīng)欄內(nèi)。17、【說明】 已知某類庫開發(fā)商捉供了一套類庫，類庫中定義了Application類和Document類，它們之間的關(guān)系如下圖所示，其中，Application類表示應(yīng)用程序自身，而Document類則表示應(yīng)用程序打開的文檔。Application類負(fù)責(zé)打開一個(gè)已有的以外部形式存儲(chǔ)的文檔，如一個(gè)文件，一旦從該文件中讀出信息后，它就由一個(gè)Documen

19、t對象表示。 當(dāng)開發(fā)一個(gè)具體的應(yīng)用程序時(shí)，開發(fā)者需要分別創(chuàng)建自己的Application和Document子類，例如上圖中的類MyApplication和類MyDocument，并分別實(shí)現(xiàn)Application和 Document類中的某些方法。 已知Application類中的openDocument方法采用了模板方法(Template Method)設(shè)計(jì)模式，該方法定義了打開文檔的每一個(gè)主要步驟，如下所示： 1首先檢查文檔是否能夠被打開，若不能打開，則給出出錯(cuò)信息并返回； 2創(chuàng)建文檔對象； 3通過文檔對象打開文檔； 4通過文檔對象讀取文檔信息； 5將文檔對象加入到Application的文

20、檔對象集合中?！綣ava代碼】 abstract class Document public void save()/*存儲(chǔ)文檔數(shù)據(jù)，此處代碼省略*/ ) public void open(String docName) /*打開文檔，此處代碼省略*/) public void close() /*關(guān)閉文檔，此處代碼省略*/) public abstract void read(String docName)； ； abstract class Appplication private Vector (1) docs； /*文檔對象集合*/ public boolean canOpenDocu

21、ment(String docName) /*判斷是否可以打開指定文檔，返回真值時(shí)表示可以打開，返回假值表示不可打開，此處代碼省略*/ public void addDocument(Document aDocument) /*將文檔對象添加到文檔對象集合中*/ docsadd( (2) )； public abstract Document doCreateDocument()；/*創(chuàng)建一個(gè)文檔對象*/ public void openDocument(String docName)/*打開文檔*/ if ( (3) ) Systemoutprintln(“文檔無法打開!”)； return

22、； (4) adoc (5) ； (6) ； (7) ； (8) ； ；答案:試題一1、E1：客戶 E2：采購部門 E3：庫房 E4：經(jīng)理 2、D1：缺貨記錄文件 D2：庫存記錄文件 D3：訂單記錄文件 3、起點(diǎn)終點(diǎn)庫存記錄文件或D2處理訂單進(jìn)貨處理供貨處理訂單記錄文件或D3銷售統(tǒng)計(jì)缺貨記錄文件或D1進(jìn)貨處理注：數(shù)據(jù)流之間沒有順序關(guān)系試題一分析 本題考查DFD的應(yīng)用，屬于比較傳統(tǒng)的題目，需要細(xì)心分析題目中所描述的內(nèi)容。 數(shù)據(jù)流圖(Data Flow Diagram，DFD)是一種便于用戶理解、分析系統(tǒng)數(shù)據(jù)流程的圖形工具。它擺脫了系統(tǒng)的物理內(nèi)容，精確地在邏輯上描述系統(tǒng)的功能、輸入、輸出和數(shù)據(jù)存儲(chǔ)

23、等，是系統(tǒng)邏輯模型的重要組成部分。問題1 考查頂層DFD。頂層DFD通常用來確定系統(tǒng)邊界，其中只包含一個(gè)唯一的加工(即待開發(fā)的系統(tǒng))、外部實(shí)體以及外部實(shí)體與系統(tǒng)之間的輸入輸出數(shù)據(jù)流。題目要求根據(jù)描述確定圖中的外部實(shí)體。分析題干中描述并結(jié)合已給出的頂層數(shù)據(jù)流圖，可知該銷售管理系統(tǒng)中有客戶、采購部門、庫房、經(jīng)理。題干中提供的關(guān)鍵信息如下：接受客戶訂單；給庫房開具備貨單；將缺貨通知單發(fā)給采購部門；打印統(tǒng)計(jì)報(bào)表給經(jīng)理。問題2 考查0層DFD，要求確定0層數(shù)據(jù)流圖中的數(shù)據(jù)存儲(chǔ)，題目中提到的數(shù)據(jù)存儲(chǔ)有訂單記錄文件、庫存記錄文件和缺貨記錄文件。在題中給出的0層DFD中，與數(shù)據(jù)存儲(chǔ) D1相關(guān)的數(shù)據(jù)流有兩條，來

24、自“處理訂單”；到達(dá)“缺貨統(tǒng)計(jì)”，分析“1接受客戶訂單，檢查庫存貨物是否滿足訂單要求。如果滿足，進(jìn)行供貨處理：修改庫存記錄文件，給庫房開具備貨單并且保留客戶訂單至訂單記錄文件；否則進(jìn)行缺貨處理：將缺貨訂單錄入缺貨記錄文件?！保_定D1應(yīng)是“缺貨記錄文件”。 分析0層數(shù)據(jù)流圖，到達(dá)D2的數(shù)據(jù)流分別來自“供貨處理”和“進(jìn)貨處理”，由“3根據(jù)采購部門提供的進(jìn)貨通知單進(jìn)行進(jìn)貨處理：修改庫存記錄文件，并從缺貨記錄文件中取出缺貨訂單進(jìn)行供貨處理?！?，確定D2為“庫存記錄文件”。由描述“給庫房開具備貨單并且保留客戶訂單至訂單記錄文件”，確定D3為“訂單記錄文件”。問題3 考查缺失的數(shù)據(jù)流。比較頂層和0層數(shù)據(jù)

25、流圖可知，頂層數(shù)據(jù)流圖中的數(shù)據(jù)流已全部體現(xiàn)在0層數(shù)據(jù)流圖中。圖中缺失數(shù)據(jù)流最明顯的地方是“銷售統(tǒng)計(jì)”加工只有流出的數(shù)據(jù)流而沒有流入的數(shù)據(jù)流，由“給庫房開具備貨單并且保留客戶訂單至訂單記錄文件，根據(jù)保留的客戶訂單進(jìn)行銷售統(tǒng)計(jì)”可知，應(yīng)存在一條從D3(訂單記錄文件)至銷售統(tǒng)計(jì)的數(shù)據(jù)流。 由“接受客戶訂單，檢查庫存貨物是否滿足訂單要求”可知，處理訂單時(shí)需要來自庫存記錄文件的數(shù)據(jù)流。當(dāng)發(fā)生缺貨情況時(shí)，除了“根據(jù)缺貨記錄文件進(jìn)行缺貨統(tǒng)計(jì)，將缺貨通知單發(fā)給采購部門”，采購部門還需根據(jù)缺貨記錄文件進(jìn)行進(jìn)貨處理。一旦進(jìn)貨成功，就可進(jìn)行供貨處理。試題二4、(1)n，或m，或， (2)n，或m，或： (3)n，或

26、m，或。 5、需要增加員工和權(quán)限之間m：1的聯(lián)系。 或者 6、問題3 (4)員工號(hào)，部門號(hào) (5)客房號(hào) (6)身份證號(hào) (7)崗位 (8)客房號(hào)，身份證號(hào) 7、若將權(quán)限表中的操作權(quán)限屬性放在員工表中，則相同崗位的操作權(quán)限在員工表中重復(fù)存儲(chǔ)，存在數(shù)據(jù)冗余。試題二分析 本題考查數(shù)據(jù)庫系統(tǒng)中實(shí)體聯(lián)系模型(E-R模型)的設(shè)計(jì)和關(guān)系模式的設(shè)計(jì)。 兩個(gè)實(shí)體型之間的聯(lián)系可以分為三類：一對一聯(lián)系(1:1)、一對多聯(lián)系(1:n)和多對多聯(lián)系(m:n)。 本題中員工和部門之間的所屬聯(lián)系類型為m:1，因?yàn)轭}中一個(gè)員工只能屬于一個(gè)部門，一個(gè)部門可以有多名員工。所以空(1)應(yīng)填m。 本題中客戶和客房之間的預(yù)定聯(lián)系類型

27、為m:n，因?yàn)轭}中一位客戶可以預(yù)訂多間客房，而客房在不同的時(shí)間段可以被多個(gè)客戶預(yù)訂。所以空(2)、空(3)應(yīng)分別填m和n。 根據(jù)題意，崗位有管理和服務(wù)兩種。崗位為“管理”的員工可以更改(添加、刪除和修改)員工表中本部門員工的崗位和密碼，要求將每一次更改前的信息保留；崗位為“服務(wù)”的員工只能修改員工表中本人的密碼，且負(fù)責(zé)多個(gè)客房的清理等工作。所以，需要增加管理員和權(quán)限之間m:1的聯(lián)系。 或者表示為 主鍵也稱為主碼，是關(guān)系中的一個(gè)或一組屬性，其值能唯一標(biāo)識(shí)一個(gè)元組。根據(jù)題意，該賓館客房預(yù)訂子系統(tǒng)中，邏輯結(jié)構(gòu)設(shè)計(jì)階段設(shè)計(jì)的部分不完整關(guān)系模式空(4) (8)應(yīng)補(bǔ)充的內(nèi)容分析如下。 空(4)應(yīng)增加一個(gè)主

28、鍵“員工號(hào)”和一個(gè)外鍵“部門號(hào)”。因?yàn)椤皢T工號(hào)”能唯一標(biāo)識(shí)員工關(guān)系中的每一個(gè)元組；又因?yàn)橐粋€(gè)員工只能屬于一個(gè)部門，一個(gè)部門可以有多名員工，員工和部門之間的所屬聯(lián)系類型為m：1，所以需要將1端的碼并入多端，即將“部門號(hào)”加入員工關(guān)系模式中。 空(5)應(yīng)增加一個(gè)主鍵“客房號(hào)”，用來唯一標(biāo)識(shí)客房關(guān)系中的每一個(gè)元組。 空(6)應(yīng)增加一個(gè)主鍵“身份證號(hào)”，用來唯一標(biāo)識(shí)客戶關(guān)系中的每一個(gè)元組。 空(7)應(yīng)填崗位，因?yàn)椴煌膷徫痪哂胁煌臋?quán)限，所以需要增加崗位屬性。 空(8)應(yīng)增加“客房號(hào)”和“身份證號(hào)”。因?yàn)閷τ陬A(yù)定情況是客戶與客房之間多對多的聯(lián)系，所以應(yīng)該將兩端的碼作為聯(lián)系的主鍵。 若去掉權(quán)限表，那么需

29、要將權(quán)限表中的操作權(quán)限屬性放在員工表中，則相同崗位的操作權(quán)限在員工表中重復(fù)存儲(chǔ)，存在數(shù)據(jù)冗余。試題三8、A1：User A2：Author A3：Reviewer A4：PCChair 9、U1：list accepted/rejected papers U2：browse submitted papers U3：assign paper to reviewer 注：U2和U3的答案可互換 10、(1)：extend(2)：include 11、Action1：enter title and abstract Action2：select subject group Action3：selec

30、t paper location Action4：upload paper試題三分析 本題涉及面向?qū)ο笙到y(tǒng)開發(fā)時(shí)的UML用例圖、活動(dòng)圖以及用例之間的關(guān)聯(lián)關(guān)系。 構(gòu)建用例圖時(shí)，常用的方式是先識(shí)別參與者，然后確定用例。創(chuàng)建參與者之間的繼承關(guān)系是為了簡化繪圖。繼承關(guān)系可以通過子類型“是一種”父類型進(jìn)行判定。在本題中，作者和審稿人分別是一種用戶，委員會(huì)主席是一種特殊審稿人。因此，A1：User、 A2：Author、A3：Reviewer、A4：PCChair。 考查用例時(shí)，通過判斷用例是哪一個(gè)特定參與者發(fā)起或者觸發(fā)，來建立和參與者之間的關(guān)聯(lián)。審稿人可以設(shè)定興趣領(lǐng)域、審閱稿件給出意見和羅列錄用或/和拒

31、絕的稿件，因此U1：list accepted/rejiected papers，會(huì)議委員會(huì)主席可以瀏覽提交的稿件、給審稿人分配稿件、羅列錄用和(或)拒絕的稿件以及關(guān)閉審稿過程，U2和U3分別為browse submitted papers和assign paper to reviewer(可互換)。 考查用例之間的關(guān)系時(shí)，extend(擴(kuò)展)關(guān)系可以通過判斷是否可以從一個(gè)用例的執(zhí)行中，在需要時(shí)轉(zhuǎn)向執(zhí)行另一個(gè)用例，執(zhí)行完返回繼續(xù)，即存在extend關(guān)系。include(包含)定義了用例之間的包含關(guān)系，用于一個(gè)用例包含另一個(gè)用例的行為的建模，通過這種方式，可以把抽象(公共)行為從多個(gè)行為中分離出

32、來。本題中，只有作者能提交稿件，“提交稿件”時(shí)判斷是否登錄，如果沒有登錄，先“登錄”，然后返回繼續(xù)提交稿件，所以(1)處應(yīng)填extend。審稿人可以羅列錄用和(或)拒絕的稿件，會(huì)議委員會(huì)主席在關(guān)閉審稿過程時(shí)須包括羅列錄用和(或)拒絕的稿件，即用例“l(fā)ist accepted/rejected papers”和用例“close reviewing process”存在包含關(guān)系，所以(2)處應(yīng)填include。 可以通過為每個(gè)用例構(gòu)造一個(gè)活動(dòng)圖對用例進(jìn)一步細(xì)化。構(gòu)造活動(dòng)圖時(shí)可以通過如下步驟進(jìn)行：從一個(gè)作為起點(diǎn)的初始節(jié)點(diǎn)開始；為用例的每個(gè)主要步驟添加一個(gè)動(dòng)作：從一個(gè)活動(dòng)到另一個(gè)活動(dòng)、決策點(diǎn)或終點(diǎn)添加

33、一條流；在流分解成不同路線的地方添加決策，并用一個(gè)合并將各個(gè)流重新合并；在有并行執(zhí)行活動(dòng)的地方添加分支和聯(lián)合；用一個(gè)單一的活動(dòng)終止符號(hào)結(jié)束。本題中，根據(jù)說明中條目2中描述的提交稿件的過程構(gòu)建活動(dòng)圖，所以Actionl處填enter title and abstract、Action2處填select subject group、 Action3處填select paper location、Action4處填upload paper。試題四12、(1)nvi-1jnvi-1j-pi+vi (2)nvijnvi-1j (3)jj-pi 13、(4)m2，m3，m4 (注：答案中食物編碼無前后順序

34、關(guān)系) (5) 605 14、(6)O(nM)，或O(nM)，或O(n*M)試題四分析 本題實(shí)質(zhì)上是一個(gè)0-1背包問題，該最優(yōu)化問題的目標(biāo)函數(shù)是 maxViXi(Xi0，1) i1 約束函數(shù)是 PiXiM (xi0,1) 0-1背包問題可用動(dòng)態(tài)規(guī)劃策略求得最優(yōu)解，求解的遞歸式為 其中，nvij表示由前i項(xiàng)食物組合且價(jià)格不超過j的套餐的最大營養(yǎng)價(jià)值。問題最終要求的套餐的最大營養(yǎng)價(jià)值為nvnM。根據(jù)上述遞歸式，可以很容易以自底向上的方式編寫偽代碼。問題1中偽代碼的第1行到第12行計(jì)算數(shù)組nv的元素值，第1行到第4行計(jì)算i為0或者j為0時(shí)nvij的值，對應(yīng)遞歸式的第一種情況；第7行和第8行計(jì)算當(dāng)jp

35、i時(shí)即不能選擇mi時(shí)nvij的值，對應(yīng)遞歸式的第二種情況：第9到第12行對應(yīng)遞歸式的第三種情況，故根據(jù)遞歸式，空(1)的答案為nvi-1jnvi-1j-pi +vi。偽代碼的第13行到第19行求解哪些食物放入到套餐中，食物項(xiàng)從后向前考慮，若nvijnvi-1j，表示食物mi沒有放入套餐中，即xi0，故空(2)的答案為nvijnvi-1j。相反，若食物mi放入套餐中，則xi1，同時(shí)套餐還能選擇不超過j-pi的價(jià)格的食物，故空(3)的答案為jj-pi。 問題2的實(shí)例要求總價(jià)格不超過100，根據(jù)上述遞歸式，計(jì)算出要選擇的食物項(xiàng)為 m2、m3和m4，對應(yīng)的總價(jià)值為605，總價(jià)格為100。 根據(jù)問題1的

36、偽代碼，第1行到第2行、第3行到第4行以及第14行到19行的時(shí)間復(fù)雜度為O(n)，第5行到第12行的時(shí)間復(fù)雜度為O(nM)。故算法總的時(shí)間復(fù)雜度為 O(nM)。試題五15、(1)pa*LA (2)pb & pb-elem!pa-elem，或其等價(jià)表示 (3)pb或pb!=NULL (4)pa-next，或(*pa).next，或其等價(jià)表示 (5)pre-next，或(*pre)next (6)prepa解析 本題考查鏈表結(jié)構(gòu)上的基本運(yùn)算。 集合A與B的差是指在集合A中而不在集合B中的元素。本題用鏈表表示集合并將運(yùn)算結(jié)果用表示集合A的鏈表存儲(chǔ)，因此涉及到鏈表上的查找、刪除基本運(yùn)算。 基本思路為：

37、對于集合A中的每個(gè)元素，在集合B中進(jìn)行查找，若找到，則應(yīng)將該元素從集合A中去掉；否則保留，用兩層循環(huán)實(shí)現(xiàn)，外層循環(huán)用于遍歷集合A，內(nèi)層循環(huán)遍歷集合B。 代碼中的指針pa用于指向集合A的元素；pb指向集合B的元素；臨時(shí)指針q指向需要被刪除的元素；pre用于實(shí)現(xiàn)刪除時(shí)結(jié)點(diǎn)的鏈接，與pa保持所指結(jié)點(diǎn)的前后繼關(guān)系。 顯然，pa需要一個(gè)初始值，即指向集合A的第一個(gè)元素結(jié)點(diǎn)。由于參數(shù)LA是指向集合A第一個(gè)結(jié)點(diǎn)的指針的指針，因此空(1)處應(yīng)填入pa*LA。 在內(nèi)層循環(huán)中遍歷集合B時(shí)，初始時(shí)令pb指向B的第一個(gè)元素(pbLB)，此后應(yīng)在鏈表中查找與A中當(dāng)前元素相同者，因此空(2)處應(yīng)填入pb & pb-elem ! pa-elem。 此后，應(yīng)判斷在B中是否找到指定元素。顯然，若找到(即pb-elempa-elem)，則指針pb不為空，否則，pb為空。因此，空(3)處填入pb或pb!=NULL，空(6)處則填入prepa。 由于鏈表不帶頭結(jié)點(diǎn)，因此，當(dāng)需要?jiǎng)h除集合A的第一個(gè)元素時(shí)，表示該集合的鏈表頭指針會(huì)被修改。pre初始值為NULL，可標(biāo)志刪除的是否為A的第一個(gè)元素。因此查找成功時(shí)，pre為空(!pre成立)表示需要?jiǎng)h除A的第一個(gè)元素(pa指針?biāo)?，使得 A的頭指針