軟件水平考試（中級(jí)）軟件設(shè)計(jì)師下午

（應(yīng)用技術(shù)）試題模擬試卷37

一、必答題（本題共14題，每題1.0分，共14分。）

閱讀以下某圖書管理系統(tǒng)的技術(shù)說明和數(shù)據(jù)流圖，根據(jù)要求回答問題I?問題4。

［說明］某圖書管理系統(tǒng)的主要功能是圖書管理和信息查詢。對于初次借書的讀者，

系統(tǒng)自動(dòng)生成讀者號(hào)，并與讀者基本信息（姓名、單位和地址等）一起寫入讀者文

件。該系統(tǒng)的圖書管理功能主要分為購入新書、讀者借書、讀者還書及圖書注銷4

個(gè)方面。（1）購入新書時(shí)需要為該書編制入庫單。入庫單內(nèi)容包括圖書分類目錄

號(hào)、書名、作者、價(jià)格、數(shù)量和購書日期，將這些信息寫入圖書目錄文件并修改文

件中的庫存總量（表示到目前為止，購入此種圖巾的數(shù)量）。（2）讀者借書時(shí)需填寫

借書單。借書單內(nèi)容包存讀者號(hào)和所借圖書分類目錄號(hào)。系統(tǒng)首先檢查該讀者號(hào)是

否有效，若無效，則拒絕借書；若有效，則進(jìn)一步檢查該讀者已借圖書是否超過最

大限制數(shù)（假設(shè)每位讀者能同時(shí)借閱的書不超過10本），若已達(dá)到最大限制數(shù)，則

拒絕借書；否則允許借書，同時(shí)將圖書分類目錄號(hào)、讀者號(hào)和借閱日期等信息寫入

借書文件中。（3）讀者還書時(shí)需填寫還書單。系統(tǒng)根據(jù)讀者號(hào)和圖書分類目錄號(hào)，

從借書文件中讀出與該圖書相關(guān)的借閱記錄，標(biāo)明還書日期，再寫回到借書文件

中，若圖書逾期，則處以相應(yīng)的罰款。（4）注銷圖書時(shí)，需填寫注銷單并修改圖書

目錄文件中的庫存總量。系統(tǒng)的信息查詢功能主要包括讀者信息查詢和圖書信息

查詢。其中，讀者信息查詢可得到讀者的基本信息及讀者借閱圖書的情況；圖書信

息杳詢可得到圖書基本信息和圖書的借出情況。該圖書管理系統(tǒng)的頂層數(shù)據(jù)流

圖，如圖2-21所示;該圖書管理系統(tǒng)的第0層DFD圖,如圖2-22所示；其中加工

圖

書含由睛求侑口皿閆不痂牛伸］

tt

用

坊圖書情況或區(qū)牌耳途者一］

杭法表體息

圖2-21某圖書管理系統(tǒng)的頂層數(shù)據(jù)流圖

圖2?22某圖書管埋系統(tǒng)第。層DFD圖

宜義土■虜求伯口加法曾尚謾占謂求仁月、

〉1---------

［讀者文件|借書文件

|圖書R錄文件

(^4：；金)HH5情況

臺(tái)詢陽杵靖求信白

非法力西崖引謫4廣息'

2的細(xì)化圖，如圖2-23所示。圖2-23加工2的細(xì)化圖

1、請用100字以內(nèi)的文字簡要說明邏輯數(shù)據(jù)流圖(LogicalDataFlowDiagram)和物

理數(shù)據(jù)流圖(PhysicalDataFlowDiagram)之間的主要差別。

標(biāo)準(zhǔn)答案：這是一道要求讀者掌握邏輯數(shù)據(jù)流圖和物理數(shù)據(jù)流圖區(qū)別點(diǎn)的簡答題。

本題所涉及的知識(shí)點(diǎn)如下。①數(shù)據(jù)流圖是系統(tǒng)分析階段用于描述系統(tǒng)邏輯模型的

圖形描述工具，解決信息系統(tǒng)"做什么''的問題。它可分為邏輯數(shù)據(jù)流圖和物理數(shù)據(jù)

流圖。②邏輯數(shù)據(jù)流圖強(qiáng)調(diào)參與者所做的事情，可以幫助設(shè)計(jì)者決定需要哪些系

統(tǒng)資源、為了運(yùn)行系統(tǒng)用戶必須執(zhí)行的活動(dòng)、在系統(tǒng)安裝之后如何保護(hù)和控制這些

系統(tǒng)等內(nèi)容。邏輯數(shù)據(jù)流圖說明應(yīng)該具有哪些加工和數(shù)據(jù)存儲(chǔ)，而不關(guān)心這些加工

和數(shù)據(jù)存儲(chǔ)是如何實(shí)現(xiàn)的。③物理數(shù)據(jù)流圖關(guān)注的是系統(tǒng)中的物理實(shí)體，以及一

些具體的文檔、報(bào)告和其他輸入/輸出數(shù)據(jù)。它通常用做系統(tǒng)構(gòu)造和實(shí)現(xiàn)的技術(shù)性

藍(lán)圖。在物理數(shù)據(jù)流圖中需要說明加工和數(shù)據(jù)存儲(chǔ)是如何實(shí)現(xiàn)的。

知識(shí)點(diǎn)解析：暫無解析

2、該圖書管理系統(tǒng)的第0層DFD圖（見圖2?22）有兩條數(shù)據(jù)流是錯(cuò)誤的，請指出改

正后這兩條數(shù)據(jù)流的起點(diǎn)、終點(diǎn)和數(shù)據(jù)流名稱。

標(biāo)準(zhǔn)答案：這是一道要求讀者掌握DFD父圖與子圖的平衡原則和輸入/輸出平衡原

則的綜合分析題。本題的解答思路如下。①根據(jù)DFD父圖與子圖的平衡原則和輸

入/輸出平衡原則，通過比對圖2-21和圖2-22中所有輸入數(shù)據(jù)流和輸出數(shù)據(jù)流可

知，如圖2-22所示中與加工“1處理管理請求”相關(guān)的兩條輸入數(shù)據(jù)流和兩條輸出數(shù)

據(jù)流都是正確的。其中，如圖2-21所示中數(shù)據(jù)流“非法請求信息”在如圖2-22所示

中包含了“非法管理工作請求單”和“非法查詢請求信息”兩條子數(shù)據(jù)流。②由題干

給出的關(guān)鍵信息“對于初次借書的讀者，系統(tǒng)自動(dòng)生成讀者號(hào)，并與讀者基本信息

（姓名、單位和地址等）一起寫入讀者文件”可知，加工“3登記讀者信息”將有一條

“讀者情況”數(shù)據(jù)流輸出到數(shù)據(jù)存儲(chǔ)“讀者文件”，即加工3是用來登記讀者信息，應(yīng)

該將登記的讀者信息寫入讀者文件，因此，在如圖2-22所示中這一“寫入”的箭頭

方向畫反了。這條改正后數(shù)據(jù)流的起點(diǎn)是“3登記讀者信息”，終點(diǎn)是“讀者文件”，

數(shù)據(jù)流名稱是“讀者情況”。其中，該數(shù)據(jù)流名稱應(yīng)綜合考慮題干中關(guān)鍵信息“系統(tǒng)

自動(dòng)生成讀者號(hào)，并與讀者基本信息一起寫入讀者文件”，并從如圖2?22所示中數(shù)

據(jù)流“讀者信息”、“讀者情況”中得到啟發(fā)。③由題干給出的關(guān)鍵信息'”系統(tǒng)首先檢

查該讀者號(hào)是否有效，若無效，則拒絕借書；若有效……''和“系統(tǒng)的信息查詢功能

主要包括讀者信息查詢和圖書信息查詢。其中讀者信息查詢可得到讀者的基本信息

及讀者借閱圖書的情況……”，并結(jié)合加工2的細(xì)化圖（見圖2-23）中加工“2.1讀者

信息查詢”與數(shù)據(jù)存儲(chǔ)“讀者文件''之間數(shù)據(jù)流的箭頭方向可知，加工“2處理查詢請

求”應(yīng)該從數(shù)據(jù)存儲(chǔ)“讀者文件”中讀出讀者的信息，因此在如圖2-22所示中這一

“查詢”的箭頭畫反了。這條改正后的數(shù)據(jù)流的起點(diǎn)是“讀者文件”，終點(diǎn)是“2處理查

詢請求”，數(shù)據(jù)流名稱是“讀者情況）其中，該數(shù)據(jù)流名稱可從圖2-22所示中加工

“2處理查詢請求”的輸出數(shù)據(jù)流“讀者情況”中得到啟發(fā)。

知識(shí)點(diǎn)解析：暫無解析

3、加工2的細(xì)化圖（見圖2-23）中缺少3條數(shù)據(jù)流，請指出這3條數(shù)據(jù)流的起點(diǎn)、

終點(diǎn)和數(shù)據(jù)流名稱。

標(biāo)準(zhǔn)答案：這也是一道耍求讀者從題干說明信息中識(shí)別數(shù)據(jù)流，以及掌握局部數(shù)據(jù)

存儲(chǔ)的隱蔽性原則的綜合分析題。本題的解答思路如下。①根據(jù)DFD父圖與子圖

的平衡原則和輸入/輸出平衡原則，通過比對圖2-22和圖2-23中所有輸入/輸出數(shù)

據(jù)流可知，如圖2-22所示中數(shù)據(jù)流“查詢請求信息"在如圖2-23所示中包含了“查詢

讀者請求信息”和“查詢圖書請求信息”兩條子數(shù)據(jù)流；如圖2-22所示中數(shù)據(jù)流“非

法查詢請求信息''在如圖2-23所示中包含了“非法查詢讀者請求信息”和“非法查詢

圖書請求信息”兩條子數(shù)據(jù)流。②由題干給出的說明信息可知，讀者基本信息存儲(chǔ)

在讀者文件中，而讀者借閱圖書的信息存儲(chǔ)在借書文件中。再由題干給出的關(guān)鍵信

息”讀者信息查詢可以得到讀者的基木信息及讀者借閱圖書的情況”，并結(jié)合［問題

2］的分析過程可知，在如圖2-23所示中加工“2.1讀者信息查詢”應(yīng)從數(shù)據(jù)存儲(chǔ)“借書

文件''中獲取該讀者借閱圖書的情況。因此在如圖2-23所示中補(bǔ)充的一條數(shù)據(jù)流起

點(diǎn)是“借書文件”，終點(diǎn)是“2.1讀者信息查詢”，數(shù)據(jù)流名稱是“讀者借閱圖書情

況”。③同理，由題干給出的說明信息可知，讀者借閱圖書的信息存儲(chǔ)在借書文件

中，而圖書的基本信息存儲(chǔ)在圖書目錄文件中。再由題干給出的關(guān)鍵信息“圖書信

息查詢可以得到圖書基本信息和圖書的借出情況”可知，在如圖2-23所示中加工

“2.2圖書信息查詢”應(yīng)從數(shù)據(jù)存儲(chǔ)”圖書目錄文件”中獲取所查詢圖書的基本信息，

從數(shù)據(jù)存儲(chǔ)“借書文件”中獲取所查詢圖書的借出情況。因此在如圖2-23所示中補(bǔ)

充的一條數(shù)據(jù)流起點(diǎn)是“圖書目錄文件”，終點(diǎn)是“2.2圖書信息查詢”，數(shù)據(jù)流名稱

是“圖書基本信息”；另一條數(shù)據(jù)流起點(diǎn)是“借書文件”，終點(diǎn)是“2.2圖書信息查

詢”，數(shù)據(jù)流名稱是“圖書借出情況”。

知識(shí)點(diǎn)解析：暫無解析

4、請根據(jù)系統(tǒng)功能描述數(shù)據(jù)流圖，并使用［說明J中的詞匯，將以下數(shù)據(jù)字典條目

中(I)?(5)空缺處的內(nèi)容填寫完整。查詢請求信息，查詢讀者請求信息|查詢圖書請

求信息］讀者情況=讀者號(hào)+姓名+所在單位+｛借書情況)管理工作請求單=(1)入庫

單=(2)借書單：(3)還書單=(4)非法請求信息=(5)

標(biāo)準(zhǔn)答案：這是一道要求讀者根據(jù)具體應(yīng)用環(huán)境編寫數(shù)據(jù)字典條目的綜合分析題。

本題的解答思路如下。①由題干給出的關(guān)鍵信息”入庫單內(nèi)容包括圖書分類目錄

號(hào)、書名、作者、價(jià)格、數(shù)量和購書日期“，并結(jié)合試題中給出的數(shù)據(jù)字典條目示

例”讀者情況=讀者號(hào)+姓名+所在單位+｛借書情況｝”的編寫風(fēng)格，可得到“入庫單''的

數(shù)據(jù)字典條目如下。入庫單二分類目錄號(hào)+書名+作者+價(jià)格+數(shù)量+購書口期②同

理，由題干給出的關(guān)鍵信息“借書單內(nèi)容包括讀者號(hào)和所借圖書分類目錄號(hào)''和"假

設(shè)每位讀者能同時(shí)借閱的書不超過10本”可知，每位讀者一次可借閱多本圖書(即

1：n的關(guān)系)，每次借閱時(shí)需向系統(tǒng)提交“讀者號(hào)”和“所借圖書分類目錄號(hào)”，因此

可得到“借書單”的數(shù)據(jù)字典條目如下。借書單二讀者號(hào)+｛所借圖書分類目錄號(hào)｝③

同理，由題干給出的關(guān)鍵信息“讀者還書時(shí)需填寫還書單。系統(tǒng)根據(jù)讀者號(hào)和圖書

分類目錄號(hào)，從借書文件中讀出與該圖書相關(guān)的借閱記錄……”，并結(jié)合常識(shí)，每位

讀者一次可歸還多本圖書(即1：n的關(guān)系)”等信息，可得到“借書單”的數(shù)據(jù)字典條

目如下。還書單二讀者號(hào)+｛所還圖書分類目錄號(hào)｝④由題干給出的關(guān)鍵信息“該系

統(tǒng)的圖書管理功能主要分為購入新書、讀者借書、讀者還書及圖書注銷4個(gè)方

面“，以及題干中關(guān)于“入庫單”、“借書單”、”還書單”和“注銷單”的描述信息可知，

每一項(xiàng)管理工作都需要填寫相應(yīng)的單據(jù)。結(jié)合試題中給出的示例“查詢請求信息

=［查詢讀者請求信息I查詢圖書請求信息］,可得到“管理工作請求單”的數(shù)據(jù)字典條

目如下。管理工作請求單=［入庫單|借書單|還書單|注銷單］⑤由［問題2］、［問題3］

的分析過程可知，如圖2-21所示中數(shù)據(jù)流“非法請求信息”在如圖2-22所示中包含

了“非法管理工作請求單”和“非法查詢請求信息”兩條子數(shù)據(jù)流，而數(shù)據(jù)流“非法查

詢請求信息”在如圖2-23所示中又包含了“非法查詢讀者請求信息”和“非法查詢圖

書請求信息”兩條子數(shù)據(jù)流，因此“非法請求信息”的數(shù)據(jù)字典條目如下。非法請求

信息二［非法管理工作請求單I非法查詢請求信息］或豐法請求信息=［非法管理工作請

求單I非法查詢讀者請求信息I非法查詢圖書請求信息］

知識(shí)點(diǎn)解析：暫無解析

閱讀以下某人才信息交流網(wǎng)數(shù)據(jù)庫設(shè)計(jì)的技術(shù)說明和圖，根據(jù)要求回答問題1?問

題5。|說明|某市人才交流中心為促進(jìn)當(dāng)?shù)厝肆Y源的合理配置，加強(qiáng)當(dāng)?shù)仄髽I(yè)與

人才的溝通，擬建立人才信息交流網(wǎng)。［需求分析結(jié)果］1.每個(gè)前來登記的個(gè)人需

填寫《人才入庫登記表》，如表2-17所示，并出示相關(guān)證件，經(jīng)工作人員審核后

錄入個(gè)人信息。

表2-17人才入庫登記表

個(gè)人編號(hào)：登記日期：一年一月一日

姓名性別出生日期

籍貫身份證號(hào)

畢業(yè)院校專業(yè)學(xué)歷

照片

1.

證書名稱編號(hào)

2.

移動(dòng)電話家庭電話電子郵件

職位名稱最低薪水備注

求職意向及薪水1.

2.

個(gè)人簡歷及特長

2.每個(gè)前來登記的企業(yè)需填寫《企業(yè)信息登記表》，如表2-18所示，并出示相關(guān)

證明及復(fù)印件，經(jīng)工作人員核實(shí)后錄入企業(yè)信息。3.個(gè)人和企業(yè)的基本信息

只需在第一次登記時(shí)填寫，個(gè)人編號(hào)和企業(yè)編號(hào)由系統(tǒng)自動(dòng)生成。個(gè)人和企業(yè)的基

本信息由計(jì)算機(jī)長期存儲(chǔ)，以后個(gè)人只需提供個(gè)人編號(hào)和求職意向信息，企業(yè)只需

提供企業(yè)編號(hào)和崗位需求信息。4.個(gè)人的求職意向信息和企業(yè)的崗位需求信

息在兩個(gè)工作日內(nèi)由工作人員錄入數(shù)據(jù)庫并發(fā)布。［概念模型設(shè)計(jì)］根據(jù)

需求階段收集的信息，設(shè)計(jì)人才、崗位和企業(yè)的實(shí)體聯(lián)系圖如圖2?24所示（不完

整）。

表2-18企業(yè)信息登記表

企業(yè)編號(hào)：登記日期：_年_月_日

企業(yè)名稱地址企業(yè)陽址

我系人聯(lián)系電話電子郵件

職位專業(yè)學(xué)歷薪水備注

崗位需求

企業(yè)簡介

人才<1)

圖124人才、崗位10企業(yè)的塞體聯(lián)系圖

［邏輯結(jié)構(gòu)設(shè)計(jì)］1.將概念模型設(shè)計(jì)的實(shí)體聯(lián)系圖轉(zhuǎn)換為以下關(guān)系模式人才（個(gè)人編

號(hào)，姓名，性別，出生三期，身份證號(hào)，畢業(yè)院校，專業(yè)，學(xué)歷，證書名稱，證書

編號(hào)，聯(lián)系電話，電子郵件，個(gè)人簡歷及特長）企業(yè)（企業(yè)編號(hào)，企業(yè)名稱，聯(lián)系

人,聯(lián)系電話，地址，企業(yè)網(wǎng)址，電子郵件，企業(yè)簡介）求職意向（（2））崗位需求

（（3））2.由于一個(gè)人可能持有多個(gè)證書，因此對“人才”關(guān)系模式進(jìn)行優(yōu)化，得到如

下兩個(gè)新的關(guān)系模式人才（（4））證書（（5））根據(jù)上述的設(shè)計(jì)過程，回答以下問題。

5、在（1）空缺處填入所需的實(shí)體、聯(lián)系及其屬性，完成概念模型設(shè)計(jì)。

標(biāo)準(zhǔn)答案：這是一道要求讀者掌握數(shù)據(jù)庫概念模型設(shè)計(jì)的綜合分析題。本題的解答

思路如下。根據(jù)題干中給出的關(guān)鍵信息“根據(jù)需求階段收集的信息，設(shè)計(jì)人才、崗

位和企業(yè)的實(shí)體聯(lián)系圖”可知，應(yīng)建立人才、崗位和企業(yè)3個(gè)實(shí)體之間的聯(lián)系。可

見，（1）空缺處還缺少了一個(gè)“崗位''實(shí)體。題干在“邏輯結(jié)構(gòu)設(shè)計(jì)”中已給出了“人才

（個(gè)人編號(hào)，姓名，性別，出生日期，身份證號(hào)，畢業(yè)院校，專業(yè)，學(xué)歷，證書名

稱，證書編號(hào)，聯(lián)系電話，電子郵件，個(gè)人簡歷及特長）”、“企業(yè)（企業(yè)編號(hào)，企業(yè)

名稱，聯(lián)系人，聯(lián)系電話，地址，企業(yè)網(wǎng)址，電子郵件，企業(yè)簡介戶、“求職意向

（（2））”和“崗位需求（（3））”4個(gè)關(guān)系模式，結(jié)合常識(shí)可知，人才與崗位之間是“求職

意向”聯(lián)系，企業(yè)與崗位之間是“崗位需求”聯(lián)系。同理，結(jié)合常識(shí)可知，“人才”、

“崗位”實(shí)體之間是多對多（m：n）的聯(lián)系。從試題中給出的人才入庫登記表（表2-17）

中，扣除“邏輯結(jié)構(gòu)設(shè)計(jì)”關(guān)系模式“人才”的相關(guān)屬性后，可得到剩余的屬性有“登

記日期”、“職位名稱”和“最低薪水，因此與聯(lián)系“求職意向”相關(guān)的屬性有“登記日

期”和“最低薪水”。由常識(shí)可知，“企業(yè)”與“崗位”實(shí)體之間也是多對多（m：n）的聯(lián)

系。從試題中給出的企業(yè)信息登記表（表2-18）中，扣除“邏輯結(jié)構(gòu)設(shè)計(jì)”關(guān)系模式

“企業(yè)”的相關(guān)屬性后,可得到剩余的屬性有“登記日期”、“職位（名稱）”、“專業(yè)”、

“學(xué)歷”、“薪水”和“備注”。因此，與聯(lián)系“崗位需求”相關(guān)的屬性有“登記日期”、“專

業(yè),,、“學(xué)歷,,、“薪水,，和“備注結(jié)合以上分析結(jié)果，整理可得完整的人才、崗位

和企業(yè)的實(shí)體聯(lián)系圖如圖2-28所示。

圖2-28完整的人才、崗位和企業(yè)的實(shí)體聯(lián)系圖

另外說明一點(diǎn)，“需求”是人才、崗位和企業(yè)3個(gè)實(shí)體之間的聯(lián)系，而事實(shí)上只有人

才被聘用之后三者之間才產(chǎn)生聯(lián)系。根據(jù)題干所給出的信息，主要解決的是人才的

求職和企業(yè)的崗位需求之間的問題，而人才與企業(yè)之間沒有直接的聯(lián)系。

知識(shí)點(diǎn)解析：暫無解析

6、在（2）?（5）空缺處填入對應(yīng)關(guān)系的屬性，完成邏輯結(jié)構(gòu)設(shè)計(jì)。（參見本題［附］）

標(biāo)準(zhǔn)答案：這是一道要求讀者掌握數(shù)據(jù)庫邏輯結(jié)構(gòu)設(shè)計(jì)的綜合分析題。本題的解答

思路如下。邏輯?結(jié)構(gòu)設(shè)計(jì)是建立在概念結(jié)構(gòu)設(shè)計(jì)的基礎(chǔ)上的，按照E-R圖向關(guān)系

模式的轉(zhuǎn)換方法，將實(shí)體和聯(lián)系分別轉(zhuǎn)換為關(guān)系模式。本題中已給出了實(shí)體對應(yīng)的

關(guān)系模式，其中“崗位”實(shí)體沒有屬性，應(yīng)歸并到聯(lián)系中。結(jié)合［問題1］的分析結(jié)果

可知，求職意向的關(guān)系模式如下。求職意向（個(gè)人編號(hào)，崗位名稱，最低薪水，登

記日期）同理，結(jié)合［問題1］的分析結(jié)果可知，崗位需求的關(guān)系模式如下。崗位需

求（企業(yè)編號(hào)，崗位名稱，專業(yè)，學(xué)歷，薪水，備注，登記日期）本試題還要求對

“人才”關(guān)系模式進(jìn)行模式分解，以達(dá)到實(shí)體分離的優(yōu)化目的（即規(guī)范化）。分解后“人

才“新關(guān)系模式可以減少“證書編號(hào)''這一屬性，而“證書''新增關(guān)系模式的屬性有“證

書名稱”和“證書編號(hào)。這兩個(gè)新的關(guān)系模式如下。人才（個(gè)人編號(hào)，姓名，性別，

出生日期，身份證號(hào)，畢業(yè)院校，專業(yè)，學(xué)歷，證書名稱，聯(lián)系電話，電子郵件，

個(gè)人簡歷及特長）證書（證書名稱，證書編號(hào)）

知識(shí)點(diǎn)解析：暫無解析

7、對于［問題2］所完成的各實(shí)體關(guān)系模式，以下畫線指出其主鍵和外鍵。

標(biāo)準(zhǔn)答案：這是一道要求讀者根據(jù)題目給定的關(guān)系模式，以及屬性間的函數(shù)依賴關(guān)

系和關(guān)系模式的語義，并結(jié)合E-R圖向關(guān)系模式的轉(zhuǎn)換方法來確定各關(guān)系模式主

鍵和外鍵的綜合分析題。本試題的解答思路如下。（1）由題干中給出的關(guān)鍵信息“一

個(gè)人可能持有多個(gè)證書”可知，在證書關(guān)系模式中，證書名稱可以決定證書關(guān)系模

式中的全屬性，因此證書關(guān)系模式的主鍵如下。證書（證書名稱，證書編號(hào)）（2）由

題干中給出的關(guān)鍵信息“個(gè)人和企業(yè)的基本信息只需在第一次登記時(shí)填寫，個(gè)人編

號(hào)和企業(yè)編號(hào)由系統(tǒng)自動(dòng)生成……以后個(gè)人只需提供個(gè)人編號(hào)和求職意向信息，企

業(yè)只需提供企業(yè)編號(hào)和崗位需求信息”可知，個(gè)人編號(hào)可以決定人才關(guān)系模式中的

全屬性。同時(shí)考慮至產(chǎn)證書名稱''是證書關(guān)系模式的主鍵，因此“證書名稱”應(yīng)為人才

關(guān)系模式的外鍵。最后可得人才關(guān)系模式的主鍵、外鍵如下。人才（個(gè)人編號(hào)，姓

名，性別，出生日期，身份證號(hào)，畢業(yè)院校，專業(yè)，學(xué)歷，證書名稱，聯(lián)系電話，

電子郵件，個(gè)人簡歷及特長）（3）同理，由于企業(yè)編號(hào)可以決定企業(yè)關(guān)系模式中的全

屬性，因此企業(yè)關(guān)系模式的主鍵如下。企業(yè)（企業(yè)編號(hào)，企業(yè)名稱，聯(lián)系人，聯(lián)系

電話，地址，企業(yè)網(wǎng)址，電子郵件，企業(yè)簡介）（4）由|問題1］的分析結(jié)果可知，“人

才''與"崗位''實(shí)體之間是多對多（m：n）的聯(lián)系，個(gè)人編號(hào)多值決定崗位，如果僅用

“個(gè)人編號(hào)”作為求職意向關(guān)系模式的主鍵，則無法唯一區(qū)分求職意向關(guān)系中的每一

個(gè)元組（記錄）。如果用“個(gè)人編號(hào)”、“崗位名稱”作為主鍵，則可以唯一區(qū)分求職意

向關(guān)系中的每一個(gè)元組。同時(shí)考慮到“個(gè)人編號(hào)''是人才關(guān)系模式的主鍵，因此“個(gè)

人編號(hào)''也是求職意向美系模式的外鍵。最后可得，求職意向關(guān)系模式的主鍵、外

鍵如下。求職意向（隹途町1位繼,最低薪水，登記日期）（5）同理，“企業(yè)”與

“崗位”實(shí)體之間是多對多（m：n）的聯(lián)系，企業(yè)編號(hào)多值決定崗位，需要用“企業(yè)編

號(hào)”、“崗位名稱”作為主鍵，才可唯一區(qū)分崗位需求關(guān)系中的每一個(gè)元組。同時(shí)考

慮到“企、也編號(hào)”是企業(yè)關(guān)系模式的主鍵，則“企業(yè)編號(hào)”也是崗位需求關(guān)系模式的外

鍵。最后可得，崗位需求關(guān)系模式的主鍵、外鍵如下。崗位需求

企業(yè)編號(hào),崗位名稱上*工,夕小小、口口甘目、

（J-,專業(yè)，學(xué)歷，薪水，備汪，登記日期）

知識(shí)點(diǎn)解析：暫無解析

8、如果允許企業(yè)通過互聯(lián)網(wǎng)修改本企業(yè)的基本信息，應(yīng)對數(shù)據(jù)庫的設(shè)計(jì)做哪些修

改?請用200字以內(nèi)的文字?jǐn)⑹鰧?shí)現(xiàn)方案。［附］關(guān)系模式的標(biāo)記規(guī)則如下：關(guān)系名

（屬性名1,屬性名2,…，屬性名n）其中：①若該屬性僅為主鍵屬性時(shí)，則該屬

性名下畫實(shí)下畫線；②若該屬性僅為外鍵屬性時(shí)，則該屬性名下畫虛下畫線；@

若該屬性既是主鍵屬性，又是外鍵屬性時(shí)，則在該屬性名下畫實(shí)下畫線和虛下畫

線；④若該屬性既不是主鍵屬性，乂不是外鍵屬性時(shí)、則在該屬性名下不做標(biāo)

記。

標(biāo)準(zhǔn)答案：這是一道要求讀者針對新應(yīng)用進(jìn)行數(shù)據(jù)表擴(kuò)充的綜合分析題。本題的解

答思路如下。如果允許企業(yè)通過互聯(lián)網(wǎng)修改本企業(yè)的基本信息，則應(yīng)建立企業(yè)的

登錄信息表。該表中包含用戶名和密碼，用來記錄企業(yè)的用戶名和密碼。接著將對

本企業(yè)的基本信息的修改權(quán)限賦予相關(guān)的用戶名。企業(yè)工作人員可以通過輸入用戶

名和密碼，經(jīng)過服務(wù)器將其與登錄信息表中記錄的該企業(yè)的用戶名和密碼進(jìn)行驗(yàn)證

后，合法用戶才有權(quán)限修改企業(yè)的信息。

知識(shí)點(diǎn)解析：暫無解析

閱讀以下某門禁控制系統(tǒng)的技術(shù)說明，根據(jù)要求回答問題1?問題3。［說明］門禁

系統(tǒng)是樓宇安防系統(tǒng)的重要組成部分，也是大廈智能化管理的體現(xiàn)。其工作過程

是，如果在入口處的讀卡器上刷卡，鎖控器（LockController）接收讀卡器

（FingerReader）的讀卡信息并進(jìn)一步識(shí)別，如果為有效卡，則觸發(fā)控制電控鎖（Lock）

的繼電器，讓持卡人通過。鎖控器還會(huì)將這些讀卡及進(jìn)出事件存儲(chǔ)起來，并將相關(guān)

事件記錄傳送給上位機(jī)。每個(gè)鎖控器管理1?4個(gè)門，每5?8個(gè)鎖控器接入1條

RS-485總線，并轉(zhuǎn)換成RS-232方式與管理主機(jī)的串行口。對鎖控器進(jìn)行相關(guān)設(shè)置

后，允許它脫機(jī)獨(dú)立對門禁點(diǎn)進(jìn)行控制，管理主機(jī)或通信線路故障都不會(huì)影響它的

正常運(yùn)行。在普通場合通常會(huì)設(shè)置1個(gè)出門按鈕，允許已進(jìn)入的人員按動(dòng)此按鈕以

打開電控鎖；而對于一些重要場合通常會(huì)在門的內(nèi)外安裝兩個(gè)讀卡器，進(jìn)出門時(shí)都

需按預(yù)設(shè)方式進(jìn)行刷卡。門禁系統(tǒng)中的每個(gè)電控鉞都有一個(gè)唯一的編號(hào)。鎖的狀

態(tài)有兩種：“已鎖住”和“未鎖住”。在管理主機(jī)上可以設(shè)置每把鎖的安全級(jí)別及用戶

的開鎖權(quán)限。只有當(dāng)用戶的開鎖權(quán)限大于或等于鎖的安全級(jí)別并且鎖處于“已鎖住''

狀態(tài)時(shí)，才能將鎖打開。用戶的感應(yīng)卡信息、開鎖權(quán)限及鎖的安全級(jí)別都保存在管

理主機(jī)的數(shù)據(jù)庫中。表2-19給出了門禁系統(tǒng)主要組成部件的作用。

表2-19感應(yīng)門禁系統(tǒng)主要組成部件及其作用表

部件名稱主要作用(功能)

讀卡感應(yīng)器(FingerReader)通過射頻感應(yīng)原理，識(shí)別感應(yīng)卡內(nèi)置加密卡號(hào)

存儲(chǔ)感應(yīng)卡權(quán)限和刷卡記錄，向管理軟件上傳讀卡器送來的信號(hào)，

鎖控器(LockController)

并負(fù)責(zé)和上位機(jī)通訊和其他數(shù)據(jù)存儲(chǔ)器協(xié)調(diào)

電控鎖(Lock)電動(dòng)執(zhí)行機(jī)構(gòu)

主機(jī)管理軟件(Win-Pak通過計(jì)算機(jī)對所有單元進(jìn)行中央管理和監(jiān)控，進(jìn)行相應(yīng)的時(shí)鐘'授

Software)權(quán)、統(tǒng)計(jì)管理工作

RS-485/232信號(hào)轉(zhuǎn)換器對所有數(shù)據(jù)存儲(chǔ)器進(jìn)行聯(lián)刖和遠(yuǎn)距離通信

門禁電源提供系統(tǒng)工作時(shí)所需的電源能堂

感應(yīng)卡存儲(chǔ)用戶的不可復(fù)制和解密的ID號(hào)

開門按鈕出門時(shí)可以設(shè)置為按此按鈕出門(可選部件)

軟件開發(fā)公司A承擔(dān)了該門禁控制系統(tǒng)的開發(fā)任務(wù)，其開發(fā)小組采用根據(jù)問題領(lǐng)

域的模型建立系統(tǒng)結(jié)構(gòu)的面向?qū)ο蠓椒ㄍ瓿稍撓到y(tǒng)的設(shè)計(jì)，系統(tǒng)中的類及類之間的

關(guān)系用UML類圖表示。

9、如圖2.25所示是門禁控制系統(tǒng)的一個(gè)不完整類圖，根據(jù)題干說明中給出的術(shù)

語，請給出類Lock的主要屬性。圖2?25門禁控制系統(tǒng)類圖

標(biāo)準(zhǔn)答案：這是一道要求讀者掌握如何從問題域中抽象出類的屬性的綜合分析題。

本題的解答思路如下。①首先要仔細(xì)理解題目中的信息，從這些信息牛獲知該感

應(yīng)門禁系統(tǒng)主要部件有鎖控器(LockController)、讀卡感應(yīng)器(FingerReader)、電控

鎖(Lock)和主機(jī)管理軟件(Win-PakSoftware)o將關(guān)鍵信息轉(zhuǎn)化成如圖2-29所示的

系統(tǒng)體系結(jié)構(gòu)。

D<^5]

代理主機(jī)數(shù)據(jù)庫

RS-4R5總線

債控腮I

圖2-29感應(yīng)門禁系統(tǒng)體系結(jié)構(gòu)圖②在面向?qū)ο?/p>

系統(tǒng)建模過程中，通常用概念模型來詳細(xì)描述系統(tǒng)的問題域。類圖用于描述系統(tǒng)的

結(jié)構(gòu)化設(shè)計(jì)，即用來表示概念模型，表達(dá)了類、接口及它們之間的靜態(tài)結(jié)構(gòu)和關(guān)

系。它最基本的元素是類或接I」。通常，在類圖上包含泛化(Generalization)、實(shí)例

(Realization)關(guān)聯(lián)(Association)、聚集(Aggregation)、組裝(Composition)、依賴

(Dependency)等關(guān)系。③對系統(tǒng)的靜態(tài)設(shè)計(jì)視圖建模時(shí)，通常以對系統(tǒng)的詞匯建

模、對簡單協(xié)作建模、對邏輯數(shù)據(jù)庫模式建模這3種方式之一使用類圖。其中，對

系統(tǒng)的詞匯建模需劃分哪些抽象是考慮中的系統(tǒng)的一部分，哪此抽象是處于系統(tǒng)的

邊界之外，即用類圖詳細(xì)描述這些抽象和它們的職責(zé)。而對簡單協(xié)作建模中，協(xié)作

是一些共同工作的類，接口和其他元素的群體，該群體提供的一此合作行為強(qiáng)于所

有這些元素的行為之和。在很多領(lǐng)域中要在關(guān)系數(shù)據(jù)庫或面向?qū)ο髷?shù)據(jù)庫中存儲(chǔ)永

久信息，可以用類圖對這些數(shù)據(jù)庫的模式進(jìn)行建模。④在圖2-25類圖中，已經(jīng)完

成了面向?qū)ο蠓治鲋械恼J(rèn)定類，讀者所要完成的工作是定義類的內(nèi)部信息。類

Lock是本系統(tǒng)中的一個(gè)關(guān)鍵類，題目與它的屬性相關(guān)的描述有“門禁系統(tǒng)中的每個(gè)

電控鎖都有一個(gè)唯一的編號(hào)”、“鎖的狀態(tài)有兩種”、“在管理主機(jī)上可以設(shè)置每把鎖

的安全級(jí)別''、"鎖處于，已鎖住，狀態(tài)時(shí)，才能將鎖打開”等。從這些信息中提煉出說

明類Lock關(guān)鍵屬性及特性的答案，即“鎖的編號(hào)”、“鎖的狀態(tài)”和“鎖的安全級(jí)

別”。

知識(shí)點(diǎn)解析：暫無解析

10、序列圖是場景的圖形化表示，描述了以時(shí)間順序組織的對象之間的交互活動(dòng),

即顯示了一組對象和由這組對象發(fā)送和接收的消息。如圖2-26所示是用戶成功開

鎖的序列圖。依據(jù)上述說明中給出的詞語，將圖2-26中的(1)?(5)空缺處補(bǔ)充完

I辱I

(4)：

⑹:u

開俄：

開幡：

整。圖2-26用戶成功開鎖的序列圖

標(biāo)準(zhǔn)答案：這是一道要求讀者掌握UML建模中序列圖知識(shí)點(diǎn)的分析題。本題的解

答思路如下。①系統(tǒng)的動(dòng)態(tài)行為常采用UML序列圖表示，它展現(xiàn)了一組對象和

由這組對象收發(fā)的消息，用于按時(shí)間順序?qū)刂屏鹘！Ｒ⒁馑鼜?qiáng)調(diào)的是時(shí)間和

順序。②圖2-26所表達(dá)的序列圖有兩個(gè)特征：一是它有對象生命線；二是它有控

制焦點(diǎn)。對象生命線是一條垂直的虛線，表示一個(gè)對象的生命跨度。控制焦點(diǎn)是一

個(gè)瘦高的矩形，表示一個(gè)對象執(zhí)行一個(gè)動(dòng)作所經(jīng)歷的時(shí)間段。矩形的頂部表示動(dòng)作

的開始，底部表示動(dòng)作的結(jié)束。在序列圖頂部水平方向畫出的是參與交換的對象。

③看懂序列圖之后，接著根據(jù)問題要點(diǎn)，查找題目中與用戶開鎖相關(guān)的信息。對

這些關(guān)鍵信息進(jìn)行歸納整理的結(jié)果如下：用戶開鎖時(shí)，只需將感應(yīng)卡靠近讀卡器。

讀卡器獲取信息后將發(fā)送一個(gè)中斷事件給鎖控器，鎖控器從讀卡器讀取用戶卡的

ID號(hào)并將該ID號(hào)信息發(fā)送到管理主機(jī)，管理主機(jī)根據(jù)數(shù)據(jù)庫中存儲(chǔ)的信息來判斷

用戶是否具有開鎖權(quán)限，若有且鎖當(dāng)前處于“已鎖住”狀態(tài)，則將鎖打開；否則系統(tǒng)

報(bào)警。④通過以上分析，可以得出用戶開鎖的激發(fā)事件是：用戶感應(yīng)卡靠近讀卡

器。⑤由于序列圖是按照時(shí)間順序組織對象之間交互活動(dòng)，因此需要將這些活動(dòng)

按照時(shí)間順序進(jìn)行排序，并記錄下參與每個(gè)活動(dòng)的對象。根據(jù)以上分析結(jié)果結(jié)合圖

2-26已給山的信息，可以得出用戶開鎖涉及的活動(dòng)事件如表2-20所示。

表2-20用戶開鎖活動(dòng)過程表

順序活動(dòng)事件活動(dòng)對象順序活動(dòng)事件活動(dòng)對象

①發(fā)送“中斷事件”讀卡器一鎖控器讀取鎖的安全級(jí)別管理主機(jī)f鎖

判斷用戶是否能夠開

②讀取用戶卡的ID號(hào)鎖控器一讀卡器⑦管理主機(jī)一管理主機(jī)

鎖

鎖控器-管理主

③諳求開鎖⑧通知能夠開鎖管理主機(jī)f鎖控器

機(jī)

④讀取鎖的當(dāng)前狀態(tài)管理主機(jī)一鎖⑨將鎖打開鎖控器f鎖

⑤讀取用戶的開鎖權(quán)限管理主機(jī)f用戶

知識(shí)點(diǎn)解析：暫無解析

11、在系統(tǒng)的需求分析階段，可以使用用例對系統(tǒng)需求建模。用例可以使用UML

的用例圖來表示。請分別用100字以內(nèi)的文字解釋UML用例圖中擴(kuò)展用例和抽象

用例的內(nèi)涵。

標(biāo)準(zhǔn)答案：這是一道要求讀者掌握UML用例圖中擴(kuò)展用例和抽象用例的內(nèi)涵的簡

答題。本試題所涉及的知識(shí)點(diǎn)如下。①由某個(gè)更復(fù)雜的用例提取出來的事件序列

所構(gòu)成的用例稱為擴(kuò)展用例，它可以簡化原有用例并擴(kuò)展其功能。②若從幾個(gè)執(zhí)

行相同功能步驟的用例中，將公共步驟提取成獨(dú)立的用例，那么這個(gè)提取出來的用

例就稱為抽象用例。它制表某種形式的“復(fù)用”，可以降低用例之間的冗余。

知識(shí)點(diǎn)解析：暫無解析

閱讀以下算法說明，根據(jù)要求回答問題1?問題3。[說明]快速排序是一種典型的

分治算法。采用快速排序?qū)?shù)組A[p..r]排序的3個(gè)步驟如下。1.分解：選擇一個(gè)

樞軸(pivot)元素劃分?jǐn)?shù)組。將數(shù)組A[p..r]劃分為兩個(gè)子數(shù)組(可能為空)A[p..q」和

A[q+l..r],使得A[q]大于等于A[p..q-1]中的每個(gè)元素，小于A[q+I..r]中的每個(gè)元

素。q的值在劃分過程中計(jì)算。2.遞歸求解：通過遞歸的調(diào)用快速排序，對子數(shù)

組A[p..q?l]和A[q+L.r]分別排序。3.合并：快速排序在原地排序，故無需合并操

作。

12、下面是快速排序的偽代碼，請將空缺處⑴?⑶的內(nèi)容填寫完整。偽代碼中的

主要變星說明如下。A：待排序數(shù)組p,r：數(shù)組元素下標(biāo)，從p到rq：劃分的位置

x：樞軸元素i：整型變量，用于描述數(shù)組下標(biāo)。下標(biāo)小于或等于i的元素的值，小

于或等于樞軸元素的值j：循環(huán)控制變量，表示數(shù)組元素下標(biāo)

QUICKSORT(A,p,r)(

if(P<r)(

q=PARTITICN(A,p,r)j

QUICKSORT(A,p,q-1);

QUICKSORT(A,q+1,r);

)

)

PARTITION(A.p,r){

X?A(r)；i=P-1;

for(j■p;jr-1；”?)(

if(A[jl4x)(

i?i?1；

交換Ali]和A⑶

)

)

交換⑴和(2)〃注，空(1)和空(2)答案可互換,但兩空全部答對方可得分

return(3)

標(biāo)準(zhǔn)答案：這是一道考萱快速排序算法偽代碼的分析題。快速排序是對冒泡排序的

一種改進(jìn)，其基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其

中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部

分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有

序序列。快速排序最核心的處理是進(jìn)行劃分，即PARTITION操作：根據(jù)樞軸元素

的值，把一個(gè)較大的數(shù)組分成兩個(gè)較小的子數(shù)組，一個(gè)子數(shù)組的所有元素的值小于

等于樞軸元素的值，一個(gè)子數(shù)組的所有元素的值大于樞軸元素的值，而子數(shù)組內(nèi)的

元素不排序。劃分時(shí)，以最后一個(gè)元素為樞軸元素，從左到右依次訪問數(shù)組的每一

個(gè)元素，判斷其與樞軸元素的大小關(guān)系，并進(jìn)行元素的交換，如圖2-30所示。

piJr

I?II?IIII；III|IF

--------------------------------------_____________________________________A__________________________________/

A［pgxJ-//>XA(j..r//未臉定

圖2-30PARTITION操作在

|問題1］所給出的偽代碼中，當(dāng)for循環(huán)結(jié)束后，A|p..i］中的值應(yīng)小于等于樞軸元素

值x,而A［i+l.rl］中的值應(yīng)大于樞軸元素值X。此時(shí)A［i+1］是第一個(gè)比A［r］大的

元素，因此A［r］與A［i+1］進(jìn)行交換，得到劃分后的兩個(gè)子數(shù)組。PARTITION操作

返回樞軸元素的位置，因此返回值為i+l。

知識(shí)點(diǎn)解析：暫無解析

13、(1)假設(shè)要排序包含n個(gè)元素的數(shù)組，請給出在各種不同的劃分情況下，快速

排序的時(shí)間復(fù)雜度(用0記號(hào))。最佳情況為(4),平均情況為(5),最壞情況為(6)。

(2)假設(shè)要排序的n個(gè)元素都具有相同值時(shí)，快速排序的運(yùn)行時(shí)間復(fù)雜度屬于哪種

情況？(7)。(最佳、平均、最壞)

標(biāo)準(zhǔn)答案：這是一道考查快速排序算法時(shí)間復(fù)雜度的分析題。當(dāng)每次能作均勻劃分

時(shí)，算法為最佳情況，此時(shí)時(shí)間復(fù)雜度可以通過計(jì)算遞歸式T(n)=2T(n/2)+O(n),

得到時(shí)間復(fù)雜度為O(nlogn)。當(dāng)每次為極端不均勻劃分時(shí)，即長度為n的數(shù)組劃分

后一個(gè)子數(shù)組為n-1,一個(gè)為0,算法為最壞情況，此時(shí)時(shí)間復(fù)雜度可以通過計(jì)算

遞歸式T(n尸T(n-1)+O(n),得到時(shí)間復(fù)雜度為0(n2)0對于平均情況的分析較為復(fù)

雜，假設(shè)數(shù)組每次劃分為9/10：1/10,此時(shí)時(shí)間復(fù)雜度可以通過計(jì)算遞歸式

T(n)=T(9/10)+T(l/10)+0(n),得到時(shí)間復(fù)雜度為O(nlogn),因此在平均情況下快速

排序仍然有較好的性能，時(shí)間復(fù)雜度為O(nlogn)。當(dāng)所有的n個(gè)元素具有相同的

值時(shí)，可以認(rèn)為數(shù)組已經(jīng)有序，此時(shí)每次都劃分為長度為n-1和。的兩個(gè)子數(shù)組，

屬于最壞情況。

知識(shí)點(diǎn)解析：暫無解析

14、(1)待排序數(shù)組是否能被較均勻地劃分對快速排序的性能有重要影響，因此樞

軸元素的選取非常重要。有人提出從待排序的數(shù)組元素中隨機(jī)地取出一個(gè)元素作為

樞軸元素。下面是隨機(jī)叱快速排序劃分的偽代碼——利用原有的快速排序的劃分操

作，請?zhí)畛淦渲械目杖碧帯Ｆ渲校琑ANDOM。,j)表示隨機(jī)取i到j(luò)之間的一個(gè)數(shù)，

包括i和八

RANDOMIZED-PABTITION(A4p,r){

i=RANDOM(p.r);

交換(8)和(9);〃注、空(8)和空(9)答案可互換.但兩空全部答對方可得分

returnPARTITIONA,p,r)；

)⑵

隨機(jī)化快速排序是否能夠消除最壞情況的發(fā)生？(10)o(是或否)

標(biāo)準(zhǔn)答案：由于隨機(jī)化的快速排序的劃分調(diào)用了傳統(tǒng)的快速排序算法的

PARTITION操作，而傳統(tǒng)的劃分每次以數(shù)組的最后一個(gè)元素作為樞軸元素，因此

隨機(jī)化的劃分操作中每次先隨機(jī)獲得一個(gè)元素，將其與最后一個(gè)元素交換。隨機(jī)化

的快速排序消除了輸入數(shù)據(jù)的不同排列對算法性能的影響，降低了極端不均勻劃分

的概率，但不能保證不會(huì)導(dǎo)致最壞情況的發(fā)生。

知識(shí)點(diǎn)解析：暫無解析

二、選答題(本題共3題，每題分，共3分。)

15、請認(rèn)真閱讀以下函數(shù)說明、圖及C程序，將程序段中(1)?⑺空缺處的語句填

寫完整。I說明］一般的樹結(jié)構(gòu)常采用孩子一兄弟表示法表示，即用二叉鏈表做樹

的存儲(chǔ)結(jié)構(gòu)，鏈表中節(jié)點(diǎn)的兩個(gè)鏈域分別指向該節(jié)點(diǎn)的第一個(gè)孩子節(jié)點(diǎn)和下一個(gè)兄

弟節(jié)點(diǎn)。例如，如圖l-15(a)所示樹的孩子一兄弟表示如圖l-15(b)所示。

圖1-15樹及其孩子一兄弟表不小意圖函數(shù)LcvelTravcrse()的功能是

對給定樹進(jìn)行層序遍歷。例如，對如圖1?15所示的樹進(jìn)行層序遍歷時(shí)，節(jié)點(diǎn)的訪

問次序?yàn)镈BAEFPG對樹進(jìn)行層序遍歷時(shí)使用了隊(duì)列結(jié)構(gòu)，實(shí)現(xiàn)隊(duì)列基本操

作的函數(shù)原型如表1-11所示。BookStatus類型定義如下：

typedefenum(FALSE*。，TRUE?1)Bool;

typedefenum(OVERELOW=-2,UND￡RFSW=?1,ERR砥=0,OKN1)Status；樹的二叉鏈表節(jié)點(diǎn)定義

如下：

typedefstructNode(

chardata;

structNode*firstchild,*nextbrother；

)Node,*TreeNode；

表Lil實(shí)現(xiàn)隊(duì)列基本操作的函數(shù)原型表

函敷原型說明

voidInitQueue(Queue+Q)初始化隊(duì)列

判斷隊(duì)列是否為空，若是則返回true,否則

BoolIsEmpty(QueueQ)

返回false

voidEnQueue(Queue構(gòu)

元素入隊(duì)列

TreeNodep)

voidDeQueue(Queue構(gòu)

元素出隊(duì)列

TreeNode*p)

StatusLcvelTraverse(TreeNoderoot)(

/?層序遍歷樹,樹采用孩子兄弟表小法,root是樹根節(jié)點(diǎn)的指管■?/

QueueteanpQ；

TreeNodeptr.brotherptr；

if(!root)

returnERROR;

iniCQueueC&te^Q)；

(1);

brotherptr=root'>nextbrother;

while(brotherptr){EnQueue(&teirpQ,brothcrptr)；

(2);

}/*end-while*/

vrtiile((3))(

(4);

printsptr->data);

if((5))continue;

(6);

brotherptr=ptr->firstchiId->nextbrother；

while(brotherptr){

EnQueue(itenpQ.brotherptr)；

(7);

}/*end-while*/

}7*end-whilew/

returnOK；

［C函數(shù)程序］)/*LevelTravemc*/

標(biāo)準(zhǔn)答案：這是一道要求讀者掌握樹結(jié)構(gòu)的存儲(chǔ)及遍歷運(yùn)算的程序分析題。本試題

的解答思路如下。隊(duì)列可以保證訪問節(jié)點(diǎn)時(shí)按照層次和自左至右的順序。借的隊(duì)

列結(jié)構(gòu)對樹進(jìn)行層序遍歷時(shí)，每個(gè)節(jié)點(diǎn)都進(jìn)出隊(duì)列一次，節(jié)點(diǎn)出隊(duì)列時(shí)進(jìn)行訪問。

其過程是，首先令樹根節(jié)點(diǎn)入隊(duì)，若是森林(樹根之間互為兄弟)，接著則令其余樹

的根節(jié)點(diǎn)入隊(duì)，然后在隊(duì)列非空的情況下，隊(duì)頭節(jié)點(diǎn)出隊(duì)，訪問該節(jié)點(diǎn)同時(shí)令其孩

子節(jié)點(diǎn)入隊(duì)。以此類推，直到隊(duì)列為空。在試題所給出的［C函數(shù)程序］中，代碼

4iInitQueue(&tempQ)；(1)；”完成初始化隊(duì)列并令根節(jié)點(diǎn)入隊(duì)列的功能，因此(1)

空缺處所填寫的內(nèi)容是“EnQueue(&tempQ、root)”。采用二叉樹存儲(chǔ)樹結(jié)構(gòu)時(shí)，其

右分支表示兄弟關(guān)系，因此隊(duì)頭節(jié)點(diǎn)出隊(duì)時(shí)，應(yīng)沿右分支將隊(duì)頭節(jié)點(diǎn)的所有孩子依

次加入隊(duì)列。(2)空缺處所在的while循環(huán)完成處理第一棵樹的兄弟節(jié)點(diǎn)的功能，因

此，(2)空缺處所填寫的內(nèi)容是“brotherptr=brotherptr->nextbrother”。至此，就完成

了第一層節(jié)點(diǎn)的處理。(3)空缺處用于判斷隊(duì)列是否為空，即應(yīng)填入

FsEmpty(tempQ)”或其他等價(jià)形式。使用隊(duì)列或棧結(jié)構(gòu)存儲(chǔ)元素以實(shí)現(xiàn)某種運(yùn)算

的基本特點(diǎn)是，當(dāng)隊(duì)列非空時(shí)，應(yīng)令隊(duì)頭元素出隊(duì)列。因此(4)空缺處所填寫的內(nèi)

容是“DcQucuc(&tcmpQ,&ptr)”。若一個(gè)節(jié)點(diǎn)不存在孩子，則其firstchild指針域

為空，也無須令其孩子節(jié)點(diǎn)入隊(duì)列。因此，(5)空缺處所填寫的內(nèi)容是"!ptr?>

firstchild”或其他等價(jià)形式。反之，若一個(gè)節(jié)點(diǎn)有孩子，則應(yīng)首先令其第一個(gè)孩子

節(jié)點(diǎn)入隊(duì)列，然后通過右分支鏈?zhǔn)蛊渌⒆庸?jié)點(diǎn)入隊(duì)列。因此，(6)空缺處所填寫

的內(nèi)容是“EnQueue(&tempQ,ptr->firstchild)”,⑺空缺處所填寫的內(nèi)容是

ubrotherptr=brotherptr->nextbrother'*。

知識(shí)點(diǎn)解析：暫無解析

16、請閱讀以下技術(shù)說明、類圖及C++代碼，根據(jù)要求將(1)?(7)空缺處的內(nèi)容填

寫完整。［說明］已知某企.業(yè)欲開發(fā)一家用電器遙控系統(tǒng)，即用戶使用一個(gè)遙控器

即可控制某些家用電器的開與關(guān)。遙控器面板如圖1?16所示。該遙控器共有4個(gè)

按鈕，編號(hào)分別是。至3,按鈕。和2能夠遙控打開電器1和電器2,按鈕1和3

則能遙控關(guān)閉電器1和電器2。由于遙控系統(tǒng)需要支持形式多樣的電器，因此,該

系統(tǒng)的設(shè)計(jì)要求具有較高的擴(kuò)展性。現(xiàn)假設(shè)需要控制客廳電視和臥室電燈，對該遙

控系統(tǒng)進(jìn)行設(shè)計(jì)所得類圖如圖1-17所示。

圖1/6某東川電器遙控器面板

圖】“7某遙控器系統(tǒng)類圖在圖1-17中，類

RomoleController的方法onPressButton(intbutlon)表示當(dāng)遙控器按鍵按卜時(shí)調(diào)層的

方法，參數(shù)為按鍵的編號(hào)；Command接口中on和off方法分別用于控制電器的開

與關(guān)；Light中turnLight(intdegree)方法用于調(diào)整電燈燈光的強(qiáng)弱，參數(shù)degree值

為0時(shí)表示關(guān)燈，值為100時(shí)表示開燈并且將燈光亮度調(diào)整到最大；TV中

setChannel(intchannel)方法表示設(shè)置電視播放的頻道，參數(shù)channel值為0時(shí)表示

關(guān)閉電視，為1時(shí)表示開機(jī)并將頻道切換為第1頻道。［C++代碼］

classLight(〃電燈類

public：

voiderunLight(inedegree)(oa^JWr.100*示科J

);

classTV(〃電視機(jī)次

public:

voidsetchannel(intchannel)(〃調(diào)整電機(jī)鼻道,。表示關(guān)機(jī)，1我示開機(jī)井切怏到1頻)

);

classCommand(〃抽It命令美

public：

vlrtuftlvoidon：)>0j

vircualvoidott()>0/

)；

classRerooteControllerf〃遙控類

protected：

Cortnand*ccstnands[4]t〃遙控?有4個(gè)按鈕，按照分別對應(yīng)4個(gè)Coon*nd對總

public：

voidonPressButtondntbutton)(，/校鑰被技下時(shí)執(zhí)行命令對總中的金令

(button%2■?0)cocnnand*(button]>>oci();

cotaaands(button];

voidsetCcxntnand(intbutton,CcmMnd?comnand)(

⑴?ccranand;〃設(shè)置每個(gè)按鈕對應(yīng)的命令財(cái)拿

)?

)；

classLightCocnmand:publicCconand(〃蛇J?令?yuàn)W

protected:L