《2010年下半年（下午）《軟件設(shè)計師》真題》由會員分享，可在線閱讀，更多相關(guān)《2010年下半年（下午）《軟件設(shè)計師》真題（8頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、2010年下半年（下午）《軟件設(shè)計師》真題 注意：圖片可根據(jù)實際需要調(diào)整大小 卷面總分：6分 答題時間：240分鐘 試卷題量：6題 練習(xí)次數(shù)：0次 問答題 （共6題，共6分） 1.某網(wǎng)上藥店允許顧客憑借醫(yī)生開具的處方，通過網(wǎng)絡(luò)在該藥店購買處方上的藥品。該網(wǎng)上藥店的基本功能描述如下： （1）注冊。顧客在買藥之前，必須先在網(wǎng)上藥店注冊。注冊過程中需填寫顧客資料以及付款方式（信用卡或者支付寶賬戶）。此外顧客必須與藥店簽訂一份授權(quán)協(xié)議書，授權(quán)藥店可以向其醫(yī)生確認處方的真?zhèn)巍? （2）登錄。已經(jīng)注冊的顧客可以登錄

2、到網(wǎng)上藥房購買藥品。如果是沒有注冊的顧客，系統(tǒng)將拒絕其登錄。 （3）錄入及提交處方。登錄成功后，顧客按照“處方錄入界面”顯示的信息，填寫開具處方的醫(yī)生的信息以及處方上的藥品信息。填寫完成后，提交該處方。 （4）驗證處方。對于已經(jīng)提交的處方（系統(tǒng)將其狀態(tài)設(shè)置為“處方已提交”），其驗證過程為： ①核實醫(yī)生信息。如果醫(yī)生信息不正確，該處方的狀態(tài)被設(shè)置為“醫(yī)生信息無效”，并取消這個處方的購買請求；如果醫(yī)生信息是正確的，系統(tǒng)給該醫(yī)生發(fā)送處方確認請求，并將處方狀態(tài)修改為“審核中”。 ②如果醫(yī)生回復(fù)處方無效，系統(tǒng)取消處方，并將處方狀態(tài)設(shè)置為“無效處方”。如果醫(yī)生沒有在7天內(nèi)給出確認答復(fù)，系統(tǒng)也會取消

3、處方，并將處方狀態(tài)設(shè)置為“無法審核”。 ③如果醫(yī)生在7天內(nèi)給出了確認答復(fù)，該處方的狀態(tài)被修改為“準許付款”。 系統(tǒng)取消所有未通過驗證的處方，并自動發(fā)送一封電子郵件給顧客，通知顧客處方被取消以及取消的原因。 （5）對于通過驗證的處方，系統(tǒng)自動計算藥品的價格并郵寄藥品給己經(jīng)付款的顧客。 該網(wǎng)上藥店采用面向?qū)ο蠓椒ㄩ_發(fā)，使用UML進行建模。系統(tǒng)的類圖如圖3-1所示。 【問題1】（8分） 根據(jù)說明中的描述，給出圖3-1中缺少的C1~C5所對應(yīng)的類名以及（1）~（6）處所對應(yīng)的多重度。 【問題2】（4分） 圖3-2給出了“處方”的部分狀態(tài)圖。根據(jù)說明中的描述，給出圖3-2中缺少的S

4、1~S4所對應(yīng)的狀態(tài)名以及（7）~（10）處所對應(yīng)的遷移（transition）名。 【問題3】（3分） 圖3-1中的符號在UML中分別表示類和對象之間的哪兩種關(guān)系？兩者之間的區(qū)別是什么？ 正確答案： 本題解析： 【問題1】（8分） C1：付款方式（1分） C2：處方（1分） C3：信用卡（1分） C4：支付寶賬戶（1分） C5：處方上的藥品（或藥品）（1分） 【其中C3、C4位置可互換】 （1）1（2）0..*（3）1 （4）1..*（5）0..*（6）1 （1）～（6）各0

5、.5分 【問題2】（4分，各0.5分） S1：審核中S2：無法審核S3：醫(yī)生信息無效S4：無效處方 （7）醫(yī)生信息不正確（8）醫(yī)生信息正確 （9）醫(yī)生回復(fù)處方無效（10）醫(yī)生沒有在7天內(nèi)給出確認答復(fù) 【其中S2/(9)和S4/(10)可成對互換，S1/(7)和S3/(8)可成對互換，】 【問題3】（3分） 表示組合（composition），表示聚合（aggregation）。（1分） 在組合關(guān)系中，整體對象與部分對象具有同一的生存周期。當(dāng)整體對象不存在時，部分對象也不存在。（1分） 而聚合關(guān)系中，對整體對象與部分對象沒有這樣的要求。（1分） 本題考查面向?qū)ο箝_發(fā)相關(guān)知識，

6、涉及UML類圖以及類圖設(shè)計時的設(shè)計模式。UML目前在面向?qū)ο筌浖_發(fā)中廣泛使用，是面向?qū)ο筌浖_發(fā)考查的重要內(nèi)容。 【問題1】 本問題考查類圖。要完成這個題目我們需要根據(jù)題目的描述來進行，根據(jù)題目前面的描述，我們不難找出該系統(tǒng)中應(yīng)包含的類有顧客、處方、信用卡、支付寶賬戶、核實醫(yī)生、付款方式和藥品等。在類圖中已經(jīng)給出了顧客和核實醫(yī)生兩個類。根據(jù)題目描述：顧客在買藥之前，必須先在網(wǎng)上藥店注冊。注冊過程中需填寫顧客資料以及付款方式（信用卡或者支付寶賬戶）。此外顧客必須與藥店簽訂一份授權(quán)協(xié)議書，授權(quán)藥店可以向其醫(yī)生確認處方的真?zhèn)巍Ｔ俳Y(jié)合類圖，我們不難看出C2應(yīng)該是處方，因為它與顧客和醫(yī)生都有關(guān)系，

7、那么根據(jù)類圖也就知道C5是藥品。另外也可以知道C1是支付方式，而C3和C4是從C1繼承而來，那么很顯然是題目中描述的兩種付款方式，分別是信用卡和支付寶賬戶。 知道了C1到C5的類以后，要求他們之間的重復(fù)度，就變得容易了，由于一個顧客可以與0至多個處方聯(lián)系，而一個處方可以包含一至多種藥品（如果沒有藥品，那么處方就沒有存在的必要了），另外一個醫(yī)生可以驗證多張?zhí)幏?，也可以不驗證處方。因此，顧客與處方是1：0...*關(guān)系，處方與藥品是1：1...*的關(guān)系，而醫(yī)生與處方為1：0...*的關(guān)系。 【問題2】 本問題考查狀態(tài)圖。狀態(tài)圖用來描述一個特定對象的所有可能狀態(tài)及其引起狀態(tài)轉(zhuǎn)移的事件。根據(jù)題目意

8、思，在提交處方后，就應(yīng)該驗證處方，驗證處方的步驟，首先是驗證醫(yī)生信息，如果醫(yī)生信息不正確，該處方的狀態(tài)被設(shè)置為“醫(yī)生信息無效”，并取消這個處方的購買請求，那么結(jié)合狀態(tài)圖，我們可以知道，S3應(yīng)該為“醫(yī)生信息無效”，而7是醫(yī)生信息不正確；那么8就是另外一個分支，是醫(yī)生信息正確，如果醫(yī)生信息正確，系統(tǒng)給該醫(yī)生發(fā)送處方確認請求，并將處方狀態(tài)修改為“審核中”，因此S1狀態(tài)是“審核中”那么8就是醫(yī)生信息正確。接著進入描述中的第二步，如果醫(yī)生回復(fù)處方無效，系統(tǒng)取消處方，并將處方狀態(tài)設(shè)置為“無效處方”。如果醫(yī)生沒有在7天內(nèi)給出確認答復(fù)，系統(tǒng)也會取消處方，并將處方狀態(tài)設(shè)置為“無法審核”。 結(jié)合狀態(tài)圖，我們可以

9、知道S2應(yīng)該是“無法審核”狀態(tài)，而S4就是“無效處方”狀態(tài)。相應(yīng)的9就是醫(yī)生回復(fù)處方無效，10就是醫(yī)生沒有在7天內(nèi)給出確認答復(fù)。 【問題３】 本問題考查聚合與組合這兩種關(guān)系的聯(lián)系與區(qū)別。 表示組合（composition），表示聚合（aggregation）。 在組合關(guān)系中，整體對象與部分對象具有同一的生存周期。當(dāng)整體對象不存在時，部分對象也不存在。 而聚合關(guān)系中，對整體對象與部分對象沒有這樣的要求。 2.某時裝郵購提供商擬開發(fā)訂單處理系統(tǒng)，用于處理客戶通過電話、傳真、郵件或Web站點所下訂單。其主要功能如下： （1）增加客戶記錄。將新客戶信息添加到

10、客戶文件，并分配一個客戶號以備后續(xù)使用。 （2）查詢商品信息。接收客戶提交商品信息請求，從商品文件中查詢商品的價格和可訂購數(shù)量等商品信息，返回給客戶。 （3）增加訂單記錄。根據(jù)客戶的訂購請求及該客戶記錄的相關(guān)信息，產(chǎn)生訂單并添加到訂單文件中。 （4）產(chǎn)生配貨單。根據(jù)訂單記錄產(chǎn)生配貨單，并將配貨單發(fā)送給倉庫進行備貨；備好貨后，發(fā)送備貨就緒通知。如果現(xiàn)貨不足，則需向供應(yīng)商訂貨。 （5）準備發(fā)貨單。從訂單文件中獲取訂單記錄，從客戶文件中獲取客戶記錄，并產(chǎn)生發(fā)貨單。 （6）發(fā)貨。當(dāng)收到倉庫發(fā)送的備貨就緒通知后，根據(jù)發(fā)貨單給客戶發(fā)貨；產(chǎn)生裝運單并發(fā)送給客戶。 （7）創(chuàng)建客戶賬單。根據(jù)訂單文件

11、中的訂單記錄和客戶文件中的客戶記錄，產(chǎn)生并發(fā)送客戶賬單，同時更新商品文件中的商品數(shù)量和訂單文件中的訂單狀態(tài)。 （8）產(chǎn)生應(yīng)收賬戶。根據(jù)客戶記錄和訂單文件中的訂單信息，產(chǎn)生并發(fā)送給財務(wù)部門應(yīng)收賬戶報表。 現(xiàn)采用結(jié)構(gòu)化方法對訂單處理系統(tǒng)進行分析與設(shè)計，獲得如圖1-1所示的頂層數(shù)據(jù)流圖和圖1-2所示0層數(shù)據(jù)流圖。 圖1-2 0層數(shù)據(jù)流圖 【問題1】（3分） 使用說明中的詞語，給出圖1-1中的實體E1~E3的名稱。 【問題2】（3分） 使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲D1~D3的名稱。 【問題3】（9分） （1）給出圖1-2中處理（加工）P1和P2的名稱及其相應(yīng)的輸

12、入、輸出流。 （2）除加工P1和P2的輸入輸出流外，圖1-2還缺失了1條數(shù)據(jù)流，請給出其起點和終點。 注：名稱使用說明中的詞匯，起點和終點均使用圖1-2中的符號或詞匯。 正確答案： 本題解析： 【問題1】 E1：客戶E2：財務(wù)部門E3：倉庫 【問題2】 D1：客戶文件D2：商品文件D3：訂單文件 【問題3】 （1）加工名稱數(shù)據(jù)流 P1：產(chǎn)生配貨單P2：準備發(fā)貨單 數(shù)據(jù)流名稱：訂單記錄起點：D3或訂單文件終點：P1或產(chǎn)生配貨單 數(shù)據(jù)流名稱：配貨單起點：P1或產(chǎn)生配貨單終點：E3或倉

13、庫 數(shù)據(jù)流名稱：訂單記錄起點：D3或訂單文件終點：P2或準備發(fā)貨單 數(shù)據(jù)流名稱：客戶記錄起點：D1或客戶文件終點：P2或準備發(fā)貨單 數(shù)據(jù)流名稱：發(fā)貨單起點：P2或準備發(fā)貨單終點：發(fā)貨 注：各行次序無關(guān)，P1和P2可互換，但必須整體互換 （2）缺少的數(shù)據(jù)流 起點：D1或客戶文件終點：創(chuàng)建客戶賬單 本題考查數(shù)據(jù)流圖(DFD）的應(yīng)用，是比較傳統(tǒng)的題目，要求考生細心分析題目中所描述的內(nèi)容。DFD是一種便于用戶理解、分析系統(tǒng)數(shù)據(jù)流程的圖形工具。是系統(tǒng)邏輯模型的重要組成部分。 【問題1】 本問題要求我們給出圖1-1中的實體E1~E3的名稱。這個需要我們從題目中的描述和該圖來獲得。題目中有

14、信息描述：當(dāng)收到倉庫發(fā)送的備貨就緒通知后，根據(jù)發(fā)貨單給客戶發(fā)貨；產(chǎn)生裝運單并發(fā)送給客戶，從這條語句中我們就可以看出，應(yīng)該有實體客戶和倉庫；另外有描述：根據(jù)客戶記錄和訂單文件中的訂單信息，產(chǎn)生并發(fā)送給財務(wù)部門應(yīng)收賬戶報表。從這里我們可以找到應(yīng)該還有實體財務(wù)部門。再結(jié)合圖1-1中數(shù)據(jù)流和實體的對應(yīng)關(guān)系可知，E1為客戶，E2為財務(wù)部門，E3為倉庫。 【問題2】 本問題考查數(shù)據(jù)存儲的確定。說明中描述：將新客戶信息添加到客戶文件；從商品文件中查詢商品的價格和可訂購數(shù)量等商品信息，返回給客戶；從訂單文件中獲取訂單記錄。我們可知系統(tǒng)中應(yīng)存在客戶文件、商品文件和訂單文件。再結(jié)合圖1-2，由于D1的輸入輸出

15、數(shù)據(jù)流都是客戶記錄，可知D1應(yīng)該為客戶文件；D2的輸入數(shù)據(jù)流是商品數(shù)量，而輸出數(shù)據(jù)流有商品數(shù)量和價格，可知D2應(yīng)該為商品文件；同樣的道理可以知道D3應(yīng)該為訂單文件。 【問題3】 本問題的第一小問，要我們給出圖1-2中處理P1和P2的名稱及相應(yīng)的數(shù)據(jù)流。在題目的描述中給出了8個處理，但在圖中只有6個已經(jīng)給出，那么處理P1和P2就應(yīng)該是剩下的兩個處理，即應(yīng)該為產(chǎn)生配貨單和準備發(fā)貨單。由于在圖中沒有給出任何關(guān)于這兩個處理的數(shù)據(jù)流，那么P1和P2是可以互換的。這里我們假設(shè)P1為產(chǎn)生配貨單，那么根據(jù)產(chǎn)生配貨單處理的描述（根據(jù)訂單記錄產(chǎn)生配貨單，并將配貨單發(fā)送給倉庫進行備貨）我們可以知道，它的輸入數(shù)據(jù)

16、流是從訂單文件流入的訂單記錄，輸出數(shù)據(jù)流是配貨單，流向倉庫。 而根據(jù)準備發(fā)貨單處理的描述（從訂單文件中獲取訂單記錄，從客戶文件中獲取客戶記錄，并產(chǎn)生發(fā)貨單），我們可以知道，它的輸入流有兩條，分別為從訂單文件流入的訂單記錄和客戶文件流入客戶記錄，輸出數(shù)據(jù)流為發(fā)貨單，流向發(fā)貨。 第二個小問題是要我們查找缺失的數(shù)據(jù)流，做這類題應(yīng)該結(jié)合上層圖及題目的描述來完成，在這個題目中，主要是要根據(jù)題目的描述來完成，題目中給出了8個處理的詳細描述，我們可以根據(jù)這些描述來判斷，還有哪些數(shù)據(jù)流沒有給出。經(jīng)過仔細分析，我們可以發(fā)現(xiàn)創(chuàng)建客戶賬單的處理缺失一條輸入數(shù)據(jù)流，它的描述說：根據(jù)訂單文件中的訂單記錄和客戶文件中

17、的客戶記錄，產(chǎn)生并發(fā)送客戶賬單。很明顯說明它有兩條輸入數(shù)據(jù)流，但在圖中只給出了訂單記錄輸入數(shù)據(jù)流，而缺失了客戶記錄輸入數(shù)據(jù)流。 3.某公司擬開發(fā)一套小區(qū)物業(yè)收費管理系統(tǒng)。初步的需求分析結(jié)果如下： （1）業(yè)主信息主要包括：業(yè)主編號，姓名，房號，房屋面積，工作單位，聯(lián)系電話等。房號可唯一標識一條業(yè)主信息，且一個房號僅對應(yīng)一套房屋；一個業(yè)主可以有一套或多套的房屋。 （2）部門信息主要包括：部門號，部門名稱，部門負責(zé)人，部門電話等；一個員工只能屬于一個部門，一個部門只有一位負責(zé)人。 （3）員工信息主要包括：員工號，姓名，出生年月，性別，住址，聯(lián)系電話，所在部門號，

18、職務(wù)和密碼等。根據(jù)職務(wù)不同員工可以有不同的權(quán)限，職務(wù)為“經(jīng)理”的員工具有更改（添加、刪除和修改）員工表中本部門員工信息的操作權(quán)限；職務(wù)為“收費”的員工只具有收費的操作權(quán)限。 （4）收費信息包括：房號，業(yè)主編號，收費日期，收費類型，數(shù)量，收費金額，員工號等。收費類型包括物業(yè)費、衛(wèi)生費、水費和電費，并按月收取，收費標準如表2-1所示。其中：物業(yè)費=房屋面積（平方米）×每平米單價，衛(wèi)生費=套房數(shù)量（套）×每套房單價，水費=用水?dāng)?shù)量（噸）×每噸水單價，電費=用電數(shù)量（度）×每度電單價。 （5）收費完畢應(yīng)為業(yè)主生成收費單，收費單示例如表2-2所示。 表2-1收費標準 表2-2收費單示例

19、 【概念模型設(shè)計】 根據(jù)需求階段收集的信息，設(shè)計的實體聯(lián)系圖（不完整）如圖2-1所示。圖2-1中收費員和經(jīng)理是員工的子實體。 圖2-1實體聯(lián)系圖 【邏輯結(jié)構(gòu)設(shè)計】 根據(jù)概念模型設(shè)計階段完成的實體聯(lián)系圖，得出如下關(guān)系模式（不完整）： 業(yè)主((1)，姓名，房屋面積，工作單位，聯(lián)系電話) 員工((2)，姓名，出生年月，性別，住址，聯(lián)系電話，職務(wù)，密碼) 部門((3)，部門名稱，部門電話) 權(quán)限(職務(wù)，操作權(quán)限) 收費標準((4)) 收費信息((5)，收費類型，收費金額，員工號) 【問題1】（8分） 根據(jù)圖2-1，將邏輯結(jié)構(gòu)設(shè)計階段生成的關(guān)系模式中的空（1）~（5）補充完整

20、，然后給出各關(guān)系模式的主鍵和外鍵。 【問題2】（5分） 填寫圖2-1中（a）～（f）處聯(lián)系的類型（注：一方用1表示，多方用m或n或*表示），并補充完整圖2-1中的實體、聯(lián)系和聯(lián)系的類型。 【問題3】（2分） 業(yè)主關(guān)系屬于第幾范式？請說明存在的問題。 正確答案： 本題解析： 【問題1】（8分） （1）業(yè)主編號，房號（0.5分） 主鍵：房號外鍵：無（0.5分） （2）員工號，所在部門號（1分） 主鍵：員工號外鍵：所在部門號，職務(wù)（1分） （3）部門號，部門負責(zé)人（1分） 主鍵：部門號外鍵

21、：部門負責(zé)人（1分） （4）收費類型，單位，單價（0.5分） 主鍵：收費類型外鍵：無（0.5分） （5）房號，業(yè)主編號，收費日期，數(shù)量（1分） 主鍵：房號，業(yè)主編號，收費日期，收費類型 外鍵：房號，員工號，收費類型（1分） 【問題2】（5分） （a）n，或m，或*（0.5分） （b）n，或m，或*（0.5分） （c）1（0.5分） （d）n，或m，或*（0.5分） （e）1（0.5分） （f）n，或m，或*（0.5分） 圖2-1補充完整的實體聯(lián)系圖 （共2分，實體“收費標準”1分，三元聯(lián)系“收費”及其聯(lián)系類型1分） 【問題3】（2分） 業(yè)主關(guān)系屬于第2范式（

22、1分）； 存在的問題：當(dāng)某業(yè)主有多套住房時，屬性“業(yè)主編號，姓名，工作單位，聯(lián)系電話”等信息在業(yè)主關(guān)系表中重復(fù)存儲，存在數(shù)據(jù)冗余（1分）。 本題考查數(shù)據(jù)庫概念結(jié)構(gòu)設(shè)計、概念至邏輯結(jié)構(gòu)轉(zhuǎn)換及范式的判定等內(nèi)容。 此類題目要求考生認真閱讀題目，根據(jù)題目的需求描述，給出實體間的聯(lián)系。 【問題1】 該問題要我們補充完整各關(guān)系模式中缺失的屬性并給出各關(guān)系模式的主鍵和外鍵。要補充各關(guān)系模式缺失的屬性應(yīng)該根據(jù)題目的描述來完成。第1空是要我們補充業(yè)主缺失的屬性，根據(jù)題目的描述，我們可以知道業(yè)主的信息有：業(yè)主編號，姓名，房號，房屋面積，工作單位，聯(lián)系電話，因此第1空應(yīng)該填（業(yè)主編號，房號）；第2空是要我

23、們補充員工缺失的屬性，根據(jù)題目的描述，我們可以知道員工的信息有：員工號，姓名，出生年月，性別，住址，聯(lián)系電話，所在部門號，職務(wù)和密碼，因此第2空應(yīng)該填（員工號，所在部門號）；同樣的道理我們可以知道第3空應(yīng)該填（部門號，部門負責(zé)人），第5空應(yīng)填（房號，業(yè)主編號，收費日期，數(shù)量）。第4空前面有所不同，它主要是通過給出的表來找出其屬性的，從題目給出的收費標準表中我們可以看出收費標準應(yīng)該有收費類型、單位、單價三個屬性。如果題目再考難一點，可能會存在一些隱蔽點的屬性，考試時也應(yīng)該注意。 主鍵是能唯一標識一條記錄的屬性組，而外鍵是其他關(guān)系模式的主鍵。那么結(jié)合題目的描述我們可以知道，業(yè)主關(guān)系的主鍵為房號；

24、員工關(guān)系的主鍵為員工號，因為它能唯一標識一個員工；部門關(guān)系的主鍵為部門號；收費標準關(guān)系的主鍵為收費類型；收費信息關(guān)系的主鍵為（房號，業(yè)主編號，收費日期，收費類型）。 外鍵是其他關(guān)系模式的主鍵。業(yè)主關(guān)系沒有外鍵；員工關(guān)系的外鍵是所在部門號、職務(wù)，其中所在部門號是部門關(guān)系的主鍵，職務(wù)是權(quán)限關(guān)系的主鍵；部門關(guān)系的外鍵是部門負責(zé)人，部門負責(zé)人列出的是負責(zé)人的員工號，而員工號是員工關(guān)系的主鍵；收費標準沒有外鍵；收費信息的外鍵有房號、員工號、收費類型，其中房號是業(yè)主關(guān)系的主鍵，員工號是員工關(guān)系的主鍵，收費類型是收費標準的主鍵。 【問題2】 根據(jù)題意可知，業(yè)主和收費員之間的聯(lián)系類型為多對多；部門與員工

25、之間的聯(lián)系類型為1對多，因為一個部門可以有多個員工，而一個員工只能屬于一個部門；員工與權(quán)限之間的聯(lián)系類型為多對1，因為可以是多個員工擁有同一種權(quán)限，而一個員工只能擁有一種權(quán)限。 另外，本題中還要求我們補充完整圖中實體、聯(lián)系和聯(lián)系的類型。從題目的描述我們可以知道，還有一個實體收費標準在圖中沒有給出，那么它肯定是與收費有關(guān)系的，因為收費要按照收費標準來進行，從題目的意思來看，不同的收費類型應(yīng)采用不同的收費標準，因此收費標準的聯(lián)系類型應(yīng)該也是多端。 【問題3】 本題主要考查我們對范式定義的理解。由于在前面已經(jīng)講到，業(yè)主關(guān)系的主鍵是房號，是一個單屬性的主鍵，那么就不存在部分依賴，因此是滿足第2范

26、式的，但在該關(guān)系中，房號-->業(yè)主編號，業(yè)主編號-->姓名，存在傳遞函數(shù)依賴，因此不滿足第3范式。 當(dāng)某業(yè)主有多套住房時，屬性“業(yè)主編號，姓名，工作單位，聯(lián)系電話”等信息在業(yè)主關(guān)系表中重復(fù)存儲，存在數(shù)據(jù)冗余。 4.堆數(shù)據(jù)結(jié)構(gòu)定義如下： 對于n個元素的關(guān)鍵字序列{a1，a2，...,an}，當(dāng)且僅當(dāng)滿足下列關(guān)系時稱其為堆。 在一個堆中，若堆頂元素為最大元素，則稱為大頂堆；若頂堆元素為最小元素，則稱為小頂堆。堆常用完全二叉樹表示，圖4-1是一個大頂堆的例子。 圖4-1大頂堆示例 堆數(shù)據(jù)結(jié)構(gòu)常用于優(yōu)先隊列中，以維護由一組元素構(gòu)成的集合。對應(yīng)于兩類堆結(jié)

27、構(gòu)，優(yōu)先隊列也有最大優(yōu)先隊列和最小優(yōu)先隊列，其中最大優(yōu)先隊列采用大頂堆，最小優(yōu)先隊列采用小頂堆。以下考慮最大優(yōu)先隊列。 假設(shè)現(xiàn)已建好大頂堆A，且已經(jīng)實現(xiàn)了調(diào)整堆的函數(shù)heapify（A,n,index）。 下面將C代碼中需要完善的三個函數(shù)說明如下： （1）heapMaximum(A)：返回大頂堆A中的最大元素。 （2）heapExtractMax(A)：去掉并返回大頂堆A的最大元素，將最后一個元素“提前”到堆頂位置，并將剩余元素調(diào)整成大頂堆。 （3）maxHeapInsert(A,key)：把元素key插入到大頂堆A的最后位置，再將A調(diào)整成大頂堆。 優(yōu)先隊列采用順序存儲方式，其存儲

28、結(jié)構(gòu)定義如下： #define PARENT(i)i/2 typedef struct array{ int*int_array;//優(yōu)先隊列的存儲空間首地址 int array_size;//優(yōu)先隊列的長度 int capacity;//優(yōu)先隊列存儲空間的容量 }ARRAY; 【C代碼】 （1）函數(shù)heapMaximum int heapMaximum(ARRAY*A){return(1);} （2）函數(shù)heapExtractMax int heapExtractMax(ARRAY*A){ int max; max=A->int_array[0]; （2）; A

29、->array_size--; heapify(A,A->array_size,0);//將剩余元素調(diào)整成大頂堆 return max; } （3）函數(shù)maxHeapInsert int maxHeapInsert(ARRAY*A,int key){ int i,*p; if(A->array_size==A->capacity){//存儲空間的容量不夠時擴充空間 p=(int*)realloc(A->int_array,A->capacity*2*sizeof(int)); if(!p)return-1; A->int_array=p; A->capacity=2*A-

30、>capacity; } A->array_size++; i=（3）; while(i>0&&（4）){ A->int_array[i]=A->int_array[PARENT(i)]; i=PARENT(i); } （5）; return 0; } 【問題1】（10分） 根據(jù)以上說明和C代碼，填充C代碼的空（1）~（5）。 【問題2】（3分） 根據(jù)以上C代碼，函數(shù)heapMaximum、heapExtractMax和maxHeapInsert的時間復(fù)雜度的緊致上界分別為（6）、（7）、（8）（用O符號表示）。 【問題3】（2分） 若將元素10插入到堆A={1

31、5，13，9，5，12，8，7，4，0，6，2，1}中，調(diào)用maxHeapInsert函數(shù)進行操作，則新插入的元素在堆A中的第（9）個位置（從1開始）。 正確答案： 本題解析： 【問題1】 （1）A->int_array[0] （2）A->int_array[0]=A->int_array[A->array_size-1] （3）A->array_size-1 （4）A->int_array[PARENT(i)]＜key （5）A->int_array[i]=key 【問題2】 （6）O(

32、1)（7）O(lgn)（8）O(lgn) 【問題3】 （9）3 【問題1】 本題考查堆數(shù)據(jù)結(jié)構(gòu)的相關(guān)內(nèi)容。題目告訴我們函數(shù)heapMaximum（A）的功能返回大頂堆A中的最大元素；函數(shù)heapExtractMax（A）的功能是去掉并返回大頂堆A的最大元素，將最后一個元素“提前”到堆頂位置，并將剩余元素調(diào)整成大頂堆；而函數(shù)maxHeaplnsert（A，key）的功能是把元素key插入到大頂堆A的最后位置，再將A調(diào)整成大頂堆。 第（1）空在函數(shù)heapMaximum（A）中，而且從程序中可以看出，是返回的結(jié)果，那么應(yīng)該是大頂堆中最大元素，就應(yīng)該是A->int_array[0]。 第

33、（2）空在函數(shù)heapExtractMax（A）中，根據(jù)該函數(shù)的功能描述，并結(jié)合程序可以看出，第（2）空是在將最大元素移出后，那么接下了來應(yīng)該處理將最后一個元素“提前”到堆頂位置，那么就應(yīng)該是A->int_array[0]=A->int_array[A->array_size-1]。 第（3）（4）（5）空都在函數(shù)maxHeaplnsert（A，key）中。從程序和函數(shù)的功能我們可以知道，從程序第（3）空最后，其作用是找到元素key的插入位置并插入該元素。第（3）空是給變量i賦值，從后面的程序中我們可以看出i是做為數(shù)組下標的；而查找元素插入的位置應(yīng)該從后往前的順序，因此i的初值應(yīng)該為A->a

34、rray_size–1，從循環(huán)中也可以看出i的值在逐漸變小。 第（4）空是循環(huán)的一個條件，而循環(huán)的作用是找到合適的插入位置，由于大頂堆的特點是根節(jié)點的值大于左右子樹節(jié)點上的值，那么找到比待插入元素大的父節(jié)點時，應(yīng)該就找到了它插入的合適位置，而每次操作后i的值被賦值為PARENT（i），很顯然這是找到其父節(jié)點的存儲位置，因此循環(huán)結(jié)束的一個條件就是找到一個比key值大的父節(jié)點，那么循環(huán)繼續(xù)的條件就是父節(jié)點的值小于key的值，所以本空的答案為A->int_array[PARENT(i)]＜key。＜key。 第（5）空就是插入元素，所以應(yīng)該填A(yù)->int_array[i]=key。 【問題2】

35、 根據(jù)題目描述，heapMaximum用來返回大頂堆A中的最大元素，而且大頂堆已經(jīng)建成，只需要通過一步操作就能取到。因此時間復(fù)雜度是O（1）， 而對于heapExtractMax是用來去掉大頂堆A的根，然后重新建堆，當(dāng)輸出堆頂結(jié)點并將堆中最后一個結(jié)點設(shè)置為根結(jié)點之后，根結(jié)點將有可能不再滿足堆的性質(zhì)，所幸的是整個序列也只有根結(jié)點一處的堆結(jié)構(gòu)可能被破壞，其余結(jié)點仍然滿足堆性質(zhì)，故可利用性質(zhì)進行堆調(diào)整，算法的基本思想為：將新堆頂沿著其關(guān)鍵字較大的孩子結(jié)點向下移動，直到葉子結(jié)點或者滿足堆性質(zhì)為止。因此相對于有N個元素的堆，只需要log2n次比較即可完成，因此時間復(fù)雜度是O（log2n），這與書本說

36、堆排序的算法時間復(fù)雜度是：O(nlog2n)不沖突，因為書本上是對堆中所有元素進行操作，而這里其實相當(dāng)于只將一個元素入堆，因此少了一個n。同樣的道理可以得到maxHeaplnsert的時間復(fù)雜度O（log2n）。 【問題3】 這個我們可以結(jié)合題目給出的那個大頂堆的圖來看，首先將key插入在最后，應(yīng)該是8這個節(jié)點的右子樹，由于10比8大，所以應(yīng)該互換，再與節(jié)點9比較，由于10仍然大于9，所以也應(yīng)該互換，這個時候再與其父節(jié)點15比較，由于小于15，所以不需要再調(diào)整，那么調(diào)整后的結(jié)果就是10這個元素應(yīng)該作為根節(jié)點15的右子樹。那么很顯然10應(yīng)該是在堆A中第3個位置。

37、 5.某公司的組織結(jié)構(gòu)圖如圖5-1所示，現(xiàn)采用組合（Composition）設(shè)計模式來構(gòu)造該公司的組織結(jié)構(gòu)，得到如圖5-2所示的類圖。 圖5-1組織結(jié)構(gòu)圖 圖5-2類圖 其中Company為抽象類，定義了在組織結(jié)構(gòu)圖上添加（Add）和刪除（Delete）分公司/辦事處或者部門的方法接口。類ConcreteCompany表示具體的分公司或者辦事處，分公司或辦事處下可以設(shè)置不同的部門。類HRDepartment和FinanceDepartment分別表示人力資源部和財務(wù)部。 【C++代碼】 #include＜iostream> #include＜list> #include

38、＜string> using namespace std; class Company{//抽象類 protected: strìng name; public: Company(string name){（1）=name;} （2）;//增加子公司、辦事處或部門 （3）;//刪除子公司、辦事處或部門 }; class ConcreteCompany:public Company{ private: list＜（4）>children;//存儲子公司、辦事處或部門 public: ConcreteCompany(string name):Company(name){

39、} void Add(Company*c){（5）.push_back(c);} void Delete(Company*c){（6）.remove(c);} }; class HRDepartment:public Company{ public: HRDepartment(string name):Company(name){}//其他代碼省略 }; class FinanceDepartment:public Company{ public: FinanceDepartment(string name):Company(name){}//其他代碼省烙 }; voi

40、d main（　　）{ ConcreteCompany*root=new ConcreteCompany("北京總公司"); root->Add(new HRDepartment("總公司人力資源部")); root->Add(new FinanceDepartment("總公司財務(wù)部")); ConcreteCompany*comp=new ConcreteCompany("上海分公司"); comp->Add(new HRDepartment("上海分公司人力資源部")); comp->Add(new FinanceDepartment("上海分公司財務(wù)部")); （7）;

41、 ConcreteCompany*comp1=new ConcreteCompany("南京辦事處"); comp1->Add(new HRDepartment("南京辦事處人力資源部")); comp1->Add(new FinanceDepartment("南京辦事處財務(wù)部")); （8）;//其他代碼省略 } 正確答案： 本題解析： （1）this->name（1分） （2）virtual void Add(Company*c)=0（2分） （3）virtual void Delete

42、(Company*c)=0（2分） （4）Company*（2分） （5）children（2分） （6）children（2分） （7）root->Add(comp)（2分） （8）comp->Add(comp1)（2分） 本題考查基本面向?qū)ο笤O(shè)計模式的運用能力。 組合設(shè)計模式主要是表達整體和部分的關(guān)系，并且對整體和部分對象的使用無差別。由類圖知Company是ConcreteCompany類、HRDepartment類和FinanceDepartment類的父類，它抽象了三個類的共有屬性和行為。 第（1）空是在構(gòu)造函數(shù)中，被賦值為name，而name是構(gòu)成函數(shù)所帶的參數(shù)，那

43、么這里是給類的一個屬性name賦值，因此這空答案為：this->name。 第（2）空與第（3）空我們可以根據(jù)注釋來完成，根據(jù)題目的描述，這里只提供接口，是虛方法，因此第（2）空與第（3）空分別應(yīng)該為virtual void Add(Company*c)=0和virtual void Delete(Company*c)=0，這兩個方法的參數(shù)可以從后面類的相應(yīng)方法中獲得。 第（4）空根據(jù)注釋可以推導(dǎo)出應(yīng)該填Company*。第（5）空與第（6）空的答案應(yīng)該一致，都應(yīng)該為children。 第（7）空和第（8）空在main函數(shù)中，用來創(chuàng)建組件結(jié)構(gòu)圖，根據(jù)題目提供的圖，我們可以知道，創(chuàng)建了上海

44、分公司接的后，應(yīng)該將其添加至root下，因此第7空答案為root->Add(comp)，同樣的道理，第（8）空的答案為comp->Add(comp1)。 6.某公司的組織結(jié)構(gòu)圖如圖6-1所示，現(xiàn)采用組合(Composition)設(shè)計模式來設(shè)計，得到如圖6-2所示的類圖。 其中Company為抽象類，定義了在組織結(jié)構(gòu)圖上添加(Add)和刪除(Delete)分公司/辦事處或者部門的方法接口。類ConcreteCompany表示具體的分公司或者辦事處，分公司或辦事處下可以設(shè)置不同的部門。類HRDepartment和FinanceDepartment分別表示人力資源部

45、和財務(wù)部。 圖6-1組織結(jié)構(gòu)圖 圖6-2類圖 【Java代碼】 import java.util.*; （1）Company{ protectedString name; public Company(String name){（2）=name;} public abstract void Add(Company c);//增加子公司、辦尊處或部門 public abstract void Delete(Company c);//刪除子公司、辦事處或部門 } class ConcreteCompany extends Company{ private List＜

46、（3）>children=new ArrayList＜（4）>（　?。? //存儲子公司、辦事處或部門 public ConcreteCompany(String name){super(name);} public void Add(Company c){（5）.add(c);} public void Delete(Company c){（6）.remove(c);} } class HRDepartment extends Company{ public HRDepartment(String name){super(name);} //其他代碼省略 } class

47、FinanceDepartment extends Company{ public FinanceDepartment(String name){super(name);} //其他代碼省略 } public class Test{ public static void main(String[]args){ ConcreteCompany root=new ConcreteCompany("北京總公司"); root.Add(new HRDepartment("總公司人力資源部")); root.Add(new FinanceDepartment("總公司財務(wù)部")); C

48、oncreteCompany comp=new ConcreteCompany("上海分公司"); comp.Add(new HRDepartment("上海分公司人力資源部")); comp.Add(new FinanceDepartment("上海分公司財務(wù)部")); （7）; ConcreteCompany comp1=new ConcreteCompany("南京辦事處"); comp1.Add(new HRDepartment("南京辦事處人力資源部")); comp1.Add(new Fina.nceDepartment("南京辦事處財務(wù)部")); （8）;//其他代

49、碼省略 } } 正確答案： 本題解析： （1）abstract class（2分） （2）this.name（1分） （3）Company（2分） （4）Company（2分） （5）children（2分） （6）children（2分） （7）root.Add(comp)（2分） （8）comp.Add(comp1)（2分） 本題考查了Java語言的應(yīng)用能力和組合設(shè)計模式的應(yīng)用。 第（1）空在類名Company前，很明顯應(yīng)該要加關(guān)鍵字abstract class，因為題目描述的

50、Company類是一個抽象類。第（2）空在構(gòu)造函數(shù)中的賦值語句中，應(yīng)該為this.name，就是給該類的一個屬性name賦值，這里應(yīng)該用this.name來引用這個屬性。第（3）空與第（4）空的答案應(yīng)該都為Company，這樣要注意在java中與C++中的區(qū)別。第（5）和第（6）空的答案應(yīng)該一樣，一個用來增加節(jié)點，一個用來刪除節(jié)點，都是使用的children對象。根據(jù)題目提供的組織結(jié)構(gòu)圖，我們可以知道，創(chuàng)建了上海分公司接的后，應(yīng)該將其添加至root（北京總公司）下，因此第7空答案為root.Add(comp)，同樣的道理，第（8）空的答案為comp.Add(comp1)。