2010年下半年（下午）《軟件設計師》真題

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

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

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

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

4、1~S4所對應的狀態(tài)名以及（7）~（10）處所對應的遷移（transition）名。 【問題3】（3分） 圖3-1中的符號在UML中分別表示類和對象之間的哪兩種關系？兩者之間的區(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ī)生回復處方無效（10）醫(yī)生沒有在7天內給出確認答復 【其中S2/(9)和S4/(10)可成對互換，S1/(7)和S3/(8)可成對互換，】 【問題3】（3分） 表示組合（composition），表示聚合（aggregation）。（1分） 在組合關系中，整體對象與部分對象具有同一的生存周期。當整體對象不存在時，部分對象也不存在。（1分） 而聚合關系中，對整體對象與部分對象沒有這樣的要求。（1分） 本題考查面向對象開發(fā)相關知識，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、：部門負責人（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è)主關系屬于第2范式（

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

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

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

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

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

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

28、結構定義如下： #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);//將剩余元素調整成大頂堆 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分） 根據以上說明和C代碼，填充C代碼的空（1）~（5）。 【問題2】（3分） 根據以上C代碼，函數(shù)heapMaximum、heapExtractMax和maxHeapInsert的時間復雜度的緊致上界分別為（6）、（7）、（8）（用O符號表示）。 【問題3】（2分） 若將元素10插入到堆A={1

31、5，13，9，5，12，8，7，4，0，6，2，1}中，調用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ù)據結構的相關內容。題目告訴我們函數(shù)heapMaximum（A）的功能返回大頂堆A中的最大元素；函數(shù)heapExtractMax（A）的功能是去掉并返回大頂堆A的最大元素，將最后一個元素“提前”到堆頂位置，并將剩余元素調整成大頂堆；而函數(shù)maxHeaplnsert（A，key）的功能是把元素key插入到大頂堆A的最后位置，再將A調整成大頂堆。 第（1）空在函數(shù)heapMaximum（A）中，而且從程序中可以看出，是返回的結果，那么應該是大頂堆中最大元素，就應該是A->int_array[0]。 第

33、（2）空在函數(shù)heapExtractMax（A）中，根據該函數(shù)的功能描述，并結合程序可以看出，第（2）空是在將最大元素移出后，那么接下了來應該處理將最后一個元素“提前”到堆頂位置，那么就應該是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ù)組下標的；而查找元素插入的位置應該從后往前的順序，因此i的初值應該為A->a

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

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

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

37、 5.某公司的組織結構圖如圖5-1所示，現(xiàn)采用組合（Composition）設計模式來構造該公司的組織結構，得到如圖5-2所示的類圖。 圖5-1組織結構圖 圖5-2類圖 其中Company為抽象類，定義了在組織結構圖上添加（Add）和刪除（Delete）分公司/辦事處或者部門的方法接口。類ConcreteCompany表示具體的分公司或者辦事處，分公司或辦事處下可以設置不同的部門。類HRDepartment和FinanceDepartment分別表示人力資源部和財務部。 【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("總公司財務部")); ConcreteCompany*comp=new ConcreteCompany("上海分公司"); comp->Add(new HRDepartment("上海分公司人力資源部")); comp->Add(new FinanceDepartment("上海分公司財務部")); （7）;

41、 ConcreteCompany*comp1=new ConcreteCompany("南京辦事處"); comp1->Add(new HRDepartment("南京辦事處人力資源部")); comp1->Add(new FinanceDepartment("南京辦事處財務部")); （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分） 本題考查基本面向對象設計模式的運用能力。 組合設計模式主要是表達整體和部分的關系，并且對整體和部分對象的使用無差別。由類圖知Company是ConcreteCompany類、HRDepartment類和FinanceDepartment類的父類，它抽象了三個類的共有屬性和行為。 第（1）空是在構造函數(shù)中，被賦值為name，而name是構成函數(shù)所帶的參數(shù)，那

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

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

45、和財務部。 圖6-1組織結構圖 圖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("總公司財務部")); C

48、oncreteCompany comp=new ConcreteCompany("上海分公司"); comp.Add(new HRDepartment("上海分公司人力資源部")); comp.Add(new FinanceDepartment("上海分公司財務部")); （7）; ConcreteCompany comp1=new ConcreteCompany("南京辦事處"); comp1.Add(new HRDepartment("南京辦事處人力資源部")); comp1.Add(new Fina.nceDepartment("南京辦事處財務部")); （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語言的應用能力和組合設計模式的應用。 第（1）空在類名Company前，很明顯應該要加關鍵字abstract class，因為題目描述的

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