中級軟件設(shè)計師下午試題-115

1、中級軟件設(shè)計師下午試題-115（總分：90.00，做題時間：90分鐘）一、試題1（總題數(shù)：1,分?jǐn)?shù)：15.00）閱讀以下說明和數(shù)據(jù)流圖，根據(jù)要求回答下列問題。說明現(xiàn)準(zhǔn)備為某銀行開發(fā)一個信用卡管理系統(tǒng)CCMS該系統(tǒng)的基本功能如下。1 信用卡申請。非信用卡客戶填寫信用卡申請表，說明所要申請的信用卡類型及申請者的基本信息，提交CCMS如果信用卡申請被銀行接受， CCM將記錄該客戶的基本信息，并發(fā)送確認(rèn)函給該客戶，告知客戶信 用卡的有效期及信貸限額；否則該客戶將會收到一封拒絕函。非信用卡客戶收到確認(rèn)函后成為信用卡客戶。2 信用卡激活。信用卡客戶向 CCMSg交激活請求，用信用卡號和密碼激活該信用卡。激

2、活操作結(jié)束后，CCMS各激活通知發(fā)送給客戶，告知客戶其信用卡是否被成功激活。3信用卡客戶信息管理。信用卡客戶的個人信息可以在CCM中進行在線管理。每位信用卡客戶可以在線查詢和修改個人信息。4交易信息查詢。信用卡客戶使用信用卡進行的每一筆交易都會記錄在CCM神。信用卡客戶可以通過 CCMS查詢并核實其交易信息（包括信用卡交易記錄及交易額）。圖8-15和圖8-16分別給出了該系統(tǒng)的頂層數(shù)據(jù)流圖和0層數(shù)據(jù)流圖的初稿。（分?jǐn)?shù)：15.00 ）（1）.問題 1根據(jù)說明，將圖8-15中的E1E3填充完整。（分?jǐn)?shù)：3.75 ） 正確答案：（E1 :非信用卡客戶E2 :信用卡客戶E3:銀行）解析：由題干關(guān)鍵信息

3、“ 1信用卡申請。非信用卡客戶填寫信用卡申請表 CCMS將記錄該客戶的基本 信息，并發(fā)送確認(rèn)函給該客戶否則該客戶將會收到一封拒絕函”，以及圖8-15中數(shù)據(jù)流“確認(rèn)函”、“拒絕函”等信息可知，外部實體E1的名稱是“非信用卡客戶”。由題干關(guān)鍵信息“ 2.信用卡客戶向CCMSg交激活請求CCMS將激活通知發(fā)送給客戶”和圖8-15中數(shù)據(jù)流“激活通知”，題干信息“ 3.每位信用卡客戶可以在線查詢和修改個人信息”和圖8-15中數(shù)據(jù)流“查詢/修改個人信息”、“個人信息”，題干信息“ 4.信用卡客戶可以通過 CCM查詢并核實其交易信息”和圖8-15中數(shù)據(jù)流“交易記錄查詢請求”可知，外部實體E2的名稱是“信用卡

4、客戶”。由題干說明中“ 1.信用卡申請。如果信用卡申請被銀行接受”、圖8-15中數(shù)據(jù)流“信用卡申請信息”、“信用卡申請驗證結(jié)果”和常識等關(guān)鍵信息可知，外部實體E3的名稱是“銀行”。.問題2圖8-15中缺少3條數(shù)據(jù)流，根據(jù)說明，分別指岀這3條數(shù)據(jù)流的起點和終點。（注：數(shù)據(jù)流的起點和終點均采用圖中的符號和描述。）（分?jǐn)?shù)：3.75 ）8-15中缺少了 1條名稱為“信用卡申請表”的數(shù)據(jù)流，其起點是E1,終點為P0。同理，由題干關(guān)鍵信息“ 2.信用卡激活。信用卡客戶向CCM提交激活請求”和圖 8-15中數(shù)據(jù)流“激 活通知”及其流向等綜合信息可知，外部實體E2 “信用卡客戶”有一條輸出數(shù)據(jù)流“激活請求”，

5、流向加工P0“信用卡管理系統(tǒng) CCMS。換而言之，圖 8-15中缺少了一條名稱為“激活請求”的數(shù)據(jù)流，其起點 是E2,終點為P0o由題干關(guān)鍵信息“ 4.交易信息查詢信用卡客戶可以通過CCMS詢并核實其交易信息”、圖8-15中數(shù)據(jù)流“交易記錄查詢請求”及其流向和生活常識等綜合信息可知，加工P0“信用卡管理系統(tǒng) CCM”有一條輸出數(shù)據(jù)流“信用卡交易信息”，流向外部實體E2“信用卡客戶”。換而言之，圖8-15中缺少了一條名稱為“信用卡交易信息”的數(shù)據(jù)流，其起點是P0,終點為E2o（3）. 問題 3圖8-16中有兩條數(shù)據(jù)流是錯誤的，請指出這兩條數(shù)據(jù)流的名稱，并改正。（注：數(shù)據(jù)流的起點和終點均采用圖中的

6、符號和描述。）（分?jǐn)?shù)：3.75 ） 正確答案： （錯誤的數(shù)據(jù)流名稱：激活請求和信用卡申請表 改正后的數(shù)據(jù)流：數(shù)據(jù)流名稱 改正后數(shù)據(jù)流起點 改正后數(shù)據(jù)流終點激活請求 E2 P3信用卡申請表 E1 P4）解析：將問題1利問題2的分析結(jié)果填寫到圖8-15中。題干說明中“信用卡申請”、“信用卡激活”、“信用卡客戶信息管理”和“交易信息查詢”是典型的加工名稱。根據(jù)數(shù)據(jù)流圖父圖與子圖數(shù)據(jù)平衡原則，對照圖 8-16 和信息填充后的圖 8-15 可以直觀地發(fā)現(xiàn)，圖 8-16 中存在的一條錯誤數(shù)據(jù)流是“信用卡申請 表”。數(shù)據(jù)流“信用卡申請表”在圖8-15中是從外部實體 E1流向CCM系統(tǒng)，而在圖8-16中是從加

7、工P4流向外部實體E1，應(yīng)以予更正。根據(jù)題干說明中“ 1.信用卡申請”描述信息， 結(jié)合圖8-16中與加工P4相關(guān)的“信用卡申請表”、“信用卡申請信息”、“信用卡申請驗證結(jié)果”等關(guān)鍵數(shù)據(jù)流信息可得，加工P4的名稱是“信用卡申請”。圖8-16中數(shù)據(jù)流“信用卡申請表”的起點應(yīng)改正為E1，終點應(yīng)修改為P4o同理，在圖8-15中數(shù)據(jù)流“激活請求”從外部實體E2流向CCM系統(tǒng)，而在圖8-16中是從加工P4流向加工P3,應(yīng)以予更正。根據(jù)題干說明中“ 2.信用卡激活”描述信息，結(jié)合圖 8-16中加工P3的輸出數(shù)據(jù)流“激活通知”等信息可得，加工P3的名稱是“信用卡激活”。圖 8-16中數(shù)據(jù)流“激活請求”的起點應(yīng)

8、改正為E2,終點應(yīng)修改為 P3o（4）. 問題 4根據(jù)說明，將圖8-16中P1P4的處理名稱填充完整。（分?jǐn)?shù)：3.75 ） 正確答案： （P1 ：交易信息查詢 P2： （信用卡）客戶信息管理P3:信用卡激活P4 :信用卡申請）解析：根據(jù)題干說明中“ 3.信用卡客戶信息管理”描述信息，結(jié)合圖8-16中與加工P2相關(guān)的“查詢/修改個人信息”、“個人信息”等關(guān)鍵數(shù)據(jù)流信息可得，加工P2的名稱是“信用卡客戶信息管理”。根據(jù)題干說明中“ 4.交易信息查詢”描述信息，結(jié)合圖8-16中與加工P1相關(guān)的“交易記錄查詢請求”、“交易信息”等關(guān)鍵數(shù)據(jù)流信息可得，加工P1的名稱是“交易信息查詢”。根據(jù)問題3的分析結(jié)

9、果可知，加工 P3的名稱是“信用卡激活”，加工 P4的名稱是“信用卡申請”。二、試題 2 （總題數(shù)： 1，分?jǐn)?shù)： 15.00）閱讀下列說明，根據(jù)要求回答下列問題。 說明 某地區(qū)舉行籃球比賽，需要開發(fā)一個比賽信息管理系統(tǒng)來記錄比賽的相關(guān)信息。 需求分析結(jié)果 1 登記參賽球隊的信息。 記錄球隊的名稱、代表地區(qū)、成立時間等信息。系統(tǒng)記錄球隊的每個隊員的姓名、 年齡、身高、體重等信息。每個球隊有一個教練負(fù)責(zé)管理球隊，一個教練僅負(fù)責(zé)一個球隊。系統(tǒng)記錄教練 的姓名、年齡等信息。2安排球隊的訓(xùn)練信息。比賽組織者為球隊提供了若干個場地，供球隊進行適應(yīng)性訓(xùn)練。系統(tǒng)記錄現(xiàn)有的場地信息，包括場地名稱、場地規(guī)模、位置

10、等信息。系統(tǒng)可為每個球隊安排不同的訓(xùn)練場地，如表8-6所示。系統(tǒng)記錄訓(xùn)練場地安排的信息。表8-6訓(xùn)練安排表球隊名稱場地名稱訓(xùn)練時間解放軍一號球場 2008-06-09 14:0018:00解放軍一號球場 2008-06-12 09:0012:00解放軍二號球場 2008-06-11 14:0018:00山西一號球場 2008-06-10 09:00»12:003安排比賽。該賽事聘請了專職裁判，每場比賽只安排一個裁判。系統(tǒng)記錄裁判的姓名、年齡、級別等信息。系統(tǒng)按照一定的規(guī)則，首先分組，然后根據(jù)球隊、場地和裁判情況，安排比賽（每場比賽的對陣雙方分別稱為甲隊和乙隊）。記錄參賽球隊、比賽時間

11、、比分、場地名稱等信息，如表8-7所示。表8-7 比賽安排表A組：甲隊-乙隊場地名稱比賽時間裁判比分解放軍一北京一號球場 2008-06-17 15:00李大明天津一山西一號球場 2008-06-17 19:00胡學(xué)梅B組：甲隊-乙隊場地名稱比賽時間裁判比分上海-安徽二號球場 2008-06-17 15:00丁鴻平山東一遼寧二號球場 2008-06-17 19:00郭愛琪4所有球員、教練和裁判可能岀現(xiàn)重名情況。概念模型設(shè)計根據(jù)需求階段收集的信息，設(shè)計的實體聯(lián)系圖和關(guān)系模式（不完整）如下1 實體聯(lián)系圖（如圖8-17所示）2關(guān)系模式教練（教練編號，姓名，年齡）隊員（隊員編號，姓名，年齡，身高，體重

12、，（a）球隊（球隊名稱，代表地區(qū)，成立時間，（b）場地（場地名稱，場地規(guī)模，位置）訓(xùn)練記錄（c）裁判（裁判編號，姓名，年齡，級別）比賽記錄（d）（分?jǐn)?shù)：15.00 ）（1）.問題 1根據(jù)問題描述，補充4個聯(lián)系，完善圖8-17的實體聯(lián)系圖。（分?jǐn)?shù)：5.00 ） 正確答案：（參見圖8-25解析：本題考查讀者對數(shù)據(jù)庫概念結(jié)構(gòu)設(shè)計及向邏輯結(jié)構(gòu)轉(zhuǎn)換的掌握情況。此類題目要求認(rèn)真閱讀題目對現(xiàn)實問題的描述，經(jīng)過分類、聚集、概括等方法，從中確定實體及其聯(lián)系。題目已經(jīng)給岀了4個實體，需要根據(jù)需求描述，給岀實體間的聯(lián)系。由“每個球隊有一個教練負(fù)責(zé)管理球隊，一個教練僅負(fù)責(zé)一個球隊。”知球隊與教練間為1:1聯(lián)系；球隊與

13、隊員之間應(yīng)為1:N聯(lián)系；多個球隊使用多個訓(xùn)練場地，球隊與場地之間為M:M聯(lián)系；比賽是球隊、場地與裁判之間的聯(lián)系，一個球隊會與同組的其他多個隊之間比賽，有多個場地和裁判，一位裁判會對多場比 賽判罰，一個場地會有多場比賽，涉及多個球隊和裁判，因此球隊、場地與裁判之間的比賽關(guān)系為M:N:P聯(lián)系。補充完整的實體聯(lián)系圖如圖8-25所示。.問題2根據(jù)你的實體聯(lián)系圖，完成關(guān)系模式，并給岀訓(xùn)練記錄和比賽記錄關(guān)系模式的主鍵和外鍵。（分?jǐn)?shù)：5.00） 正確答案：（填空：（a）球隊名稱（b）教練編號（c）球隊名稱，場地名稱，開始時間，結(jié)束時間（d）甲隊，乙隊，比賽時間，場地名稱，比分，裁判，分組 主鍵：訓(xùn)練記錄（球

14、隊，開始時間）或訓(xùn)練記錄（場地名稱，開始時間） 或訓(xùn)練記錄（球隊，結(jié)束時間）或訓(xùn)練記錄（場地名稱，結(jié)束時間） 比賽記錄（場地名稱，比賽時間）或比賽記錄（裁判，比賽時間） 或比賽記錄（甲隊，比賽時間）或比賽記錄（乙隊，比賽時間） 外鍵： 訓(xùn)練記錄的外鍵：球隊名稱，場地名稱 比賽記錄的外鍵：甲隊，乙隊，場地名稱，裁判）解析：根據(jù)補充后的 E-R圖，球隊與球員之間的1:N聯(lián)系應(yīng)通過將1端實體（球員）的主碼（球隊名稱）加入 到N端實體（球員）對應(yīng)的關(guān)系中來表達(dá)。 這類聯(lián)系也可通過一個獨立的關(guān)系來表達(dá)，如球隊一球員（球隊名稱，隊員編號），這樣會對查詢增加多余的連接操作，因此一般不采用這種方法。同樣，球隊

15、與教練之間的 1:1聯(lián)系也應(yīng)通過將一方的主碼增加到另一方實體對應(yīng)的關(guān)系中，來表達(dá)聯(lián)系。 訓(xùn)練和比賽為多對多聯(lián)系，只能獨立成一個關(guān)系模式，由該聯(lián)系相關(guān)連的各實體的碼及聯(lián)系自有的屬性構(gòu) 成。如比分和分組應(yīng)該是比賽的屬性，再加上球隊、裁判、場地的碼，即構(gòu)成“比賽記錄”的關(guān)系模式。比賽記錄關(guān)系模式的主鍵可以是“場地名稱，比賽時間”，也可以是“裁判，比賽時間”，或者是“甲隊，比賽時間”，再或者是“乙隊，比賽時間”。其外鍵是“甲隊，乙隊，場地名稱，裁判”。同理，訓(xùn)練是球隊和場地的多對多聯(lián)系，訓(xùn)練開始時間和結(jié)束時間為訓(xùn)練的屬性，加上球隊的碼和場地的 碼，構(gòu)成“訓(xùn)練記錄”關(guān)系模式。訓(xùn)練記錄關(guān)系模式的主鍵可以是

16、“球隊，開始時間”，也可以是“場地 名稱，開始時間”，或者是“球隊，結(jié)束時間”，再或者是“場地名稱，結(jié)束時間”。其外鍵是“球隊名 稱，場地名稱”。.問題3如果考慮記錄一些特別資深的熱心球迷的情況，每個熱心球迷可能支持多個球隊。熱心球迷的基本信息包括姓名、住址和喜歡的俱樂部等。根據(jù)這一要求修改圖8-17的實體聯(lián)系圖，給岀修改后的關(guān)系模式。（分?jǐn)?shù): 5.00 ） 正確答案：（修改后的E-R圖見圖8-26，新增的關(guān)系模式如下：熱心球迷（球迷編號，姓名，住址，俱樂部 ）支持球隊（球迷編號，球隊）解析：球迷與球隊之間為多對多聯(lián)系，需新增球迷實體和球迷與球隊之間的支持聯(lián)系，如圖8-26所示。新增的關(guān)系模式

17、如下。熱心球迷（球迷編號，姓名，住址，俱樂部 ）支持球隊（球迷編號，球隊）三、試題3（總題數(shù)：1,分?jǐn)?shù)：15.00）閱讀以下技術(shù)說明，根據(jù)要求回答下列問題。說明某汽車停車場欲建立一個信息系統(tǒng)，已經(jīng)調(diào)查到的需求如下。1.在停車場的入口和岀口分別安裝一個自動欄桿、一臺停車卡打印機、一臺讀卡器和一個車輛通過傳感器等，其示意圖見圖8-18。2當(dāng)汽車到達(dá)入口時，駕駛員按下停車卡打印機的按鈕獲取停車卡。當(dāng)駕駛員拿走停車卡后，系統(tǒng)命令欄 桿自動抬起；汽車通過入口后，入口處的傳感器通知系統(tǒng)發(fā)岀命令，欄桿自動放下。3在停車場內(nèi)分布著若干個付款機器。駕駛員將在入口處獲取的停車卡插入付款機器，并繳納停車費。付 清停

18、車費之后，將獲得一張岀場卡，用于離開停車場。4當(dāng)汽車到達(dá)岀口時，駕駛員將岀場卡插入岀口處的讀卡器。如果這張卡是有效的，系統(tǒng)命令欄桿自動抬 起；汽車通過岀口后，岀口傳感器通知系統(tǒng)發(fā)岀命令，欄桿自動放下。若這張卡是無效的，系統(tǒng)不發(fā)岀欄 桿抬起命令而發(fā)岀告警信號。5.系統(tǒng)自動記錄停車場內(nèi)空閑的停車位的數(shù)量。若停車場當(dāng)前沒有車位，系統(tǒng)將在入口處顯示“車位已滿”信息。這時，停車卡打印機將不再岀卡，只允許場內(nèi)汽車岀場。根據(jù)上述描述，采用面向?qū)ο蠓椒▽ζ溥M行分析與設(shè)計，得到如表8-8所示的類/用例/狀態(tài)列表，如圖8-19所示的用例圖，如圖8-20所示的初始類圖以及如圖 8-21所示的描述入口自動欄桿行為的U

19、ML狀態(tài)圖。表8-8類/用例/狀態(tài)列表用戶名說明類名說明狀態(tài)名說明空閑狀態(tài)，Car entry汽車進入停Cen tralComputer停車場信息Idle汽車可車場汽車離開停車場系統(tǒng)以進入停車 場Car exitPayme ntMachi ne 付款機器Disable沒有車位CarPark停車場，保存 車位信AwaitEn try等待汽車進Report記錄停車場自入的相關(guān)丿息Statistics信息Barrier自動護欄AwaitTicketTake等待打印停車卡Car entry沒有車位時，汽車請En tryBarrier入口的護欄Await等待停車場內(nèi)有空whe n full求進入停車出口

20、的護欄En able場ExitBarrier閑車位（分?jǐn)?shù)：15.00 ）（1）.問題 1根據(jù)說明中的描述，使用表8-8給出的用例名稱，給出圖8-19中U1、U2和U3所對應(yīng)的用例。（分?jǐn)?shù)：3.75 ） 正確答案：(U1 ： Car entry U2 : Car exitU3： Car entry when full)解析：表 8-8 中給出了 Car entry、Car exit 、Report Statistics 、Car entry when full 4 個用例。在 這4個用例中，兩個用例表示汽車進入停車場，一個用例表示汽車退岀停車場，另一個用例表示記錄停車 場相關(guān)信息。經(jīng)分析得出，前

21、3個用例的參與者都是駕駛員，因此U1、U2和U3對應(yīng)進入和退出停車場。U1和U3之間存在擴展關(guān)系，而用例之間的延伸關(guān)系用于對被用戶看作是可選系統(tǒng)行為的用例的一部分建 模。通過這種方式，可以把可選行為從必需的行為中分離出來。Car entrv when full 和car entry 之間就可以使用extend關(guān)系進行建模。.問題2根據(jù)說明中的描述，使用表 8-8給出的類的名稱，給出圖 8-20中的AD所對應(yīng)的類。(分?jǐn)?shù)：3.75 ) 正確答案：(A : CarPark B : BarrierC： EntryBarrier D : ExitBarrier)，關(guān)聯(lián)(Association)繼承表示

22、類與類之間UML圖形表示為解析：在UML類圖中，類與類之間的 5種關(guān)系從弱到強依次為：依賴 (Dependency) 聚合(Aggregation)，組合(Composition) 和繼承(Inheritance) 。因此依賴關(guān)系最弱, 關(guān)系最強。依賴(Dependency)關(guān)系是類與類之間的連接，并且依賴總是單向的，其標(biāo)準(zhǔn) 表示其相聯(lián)的兩個類之間存在關(guān)聯(lián)關(guān)系，用于描述兩個概念上位于相同級別的類的實例之間存在的某種語義上的聯(lián)系。聚合關(guān)系是關(guān)聯(lián)關(guān)系的一種特例，代表兩個類之間的整體/局部關(guān)系,其標(biāo)準(zhǔn)UML圖形表示為“行為與含義，子類還可以增加或者覆蓋父類的行為。子類可以岀現(xiàn)在父類岀現(xiàn)的任何位置。表

23、示其相聯(lián)的兩個類之間存在繼承關(guān)系。子類繼承父類的依題意可以判斷 Barlrier 、EntryBarrier 和ExitBarrer 之間存在繼承關(guān)系，而在圖8-20類圖中“所表示的繼承關(guān)系的部分只有一處，因此這3個類分別對應(yīng)于圖8-20中的類B、類C和類D,而剩下的類A只有選擇類 CarPark 了。.問題3根據(jù)說明中的描述，使用表 8-8給出的狀態(tài)名稱，給出圖 8-21中S1S4所對應(yīng)的狀態(tài)。(分?jǐn)?shù)：3.75 ) 正確答案：(S1 : Idle S2 : Await Ticket TakeS3： Await Enable S4 : Await Entry)解析：在圖8-21中，Idle表示

24、有空閑車位，Disable表示沒有空閑車位，因此在其之間存在雙向的狀態(tài)遷移，即狀態(tài)圖上的狀態(tài) S1為Idle狀態(tài)。當(dāng)停車場存在空閑車位時，汽車請求進入停車場，根據(jù)說明描述“當(dāng)汽車到達(dá)入口時，駕駛員按下停車卡打印機的按鈕獲取停車卡”，可知該動作正對應(yīng)于狀態(tài)圖上的S1和狀態(tài)S2之間的遷移，因此，狀態(tài) S2表示的含義應(yīng)該是按下按鈕后的狀態(tài)，此時，駕駛員等待打印停車 卡，所以狀態(tài) S2為Await Ticket Take 。同理可分析出狀態(tài) S3和狀態(tài)S4。.問題4簡要解釋圖8-19中用例U1和U3之間的extend關(guān)系的內(nèi)涵。(分?jǐn)?shù)：3.75 )正確答案：(用例之間的延伸關(guān)系用于對被用戶看作是可選系

25、統(tǒng)行為的用例的一部分建模。通過這種方式， 可以把可選行為從必需的行為中分離岀來)解析：在用例的執(zhí)行過程中，可能會在不同的流程分支中選擇執(zhí)行，也可能會出現(xiàn)異常行為。此時，可以 將異常行為或可選分支抽象成一個單獨的擴展用例，它與主用例之間形成“擴展 (extend) ”關(guān)系。四、試題4(總題數(shù)：1,分?jǐn)?shù)：15.00)閱讀下列算法說明和流程圖，根據(jù)回答下列問題。說明某機器上需要處理n個作業(yè)job 1，job 2，job n，其中：(1) 每個作業(yè)job i(1<i <n)的編號為i ， job i有一個收益值pi和最后期限值di;(2) 機器在一個時刻只能處理一個作業(yè)，而且每個作業(yè)需要一

26、個單位時間進行處理，一旦作業(yè)開始就不可中斷，每個作業(yè)的最后期限值為單位時間的正整數(shù)倍；job 1jobn的收益值呈非遞增順序排列，即p1 >p2 >. >pn;如果作業(yè)job i在其期限之內(nèi)完成，則獲得收益pi;如果在其期限之后完成，則沒有收益。為獲得較高的收益，采用貪心策略求解在期限之內(nèi)完成的作業(yè)序列。圖8-22是基于貪心策略求解該問題的流程圖。(1)整型數(shù)組J有n個存儲單元，變量k表示在期限之內(nèi)完成的作業(yè)數(shù)，J1.k存儲所有能夠在期限內(nèi)完成的作業(yè)編號，數(shù)組 J1.k里的作業(yè)按其最后期限非遞減排序，即dJ1 <. wdJk。為了便于在數(shù)組J中加入作業(yè)，增加一個虛擬作業(yè)

27、job 0，并令d0=0，J0=0。(3) 算法大致思想是：先將作業(yè) job i的編號1放入J1，然后，依次對每個作業(yè) job i (2<i <n)進行判定, 看其能否插入到數(shù)組J中。若能，則將其編號插入到數(shù)組 J的適當(dāng)位置，并保證 J中作業(yè)按其最后期限非 遞減排列；否則不插入。job i能插入數(shù)組J的充要條件是：job i和數(shù)組J中已有作業(yè)均能在其期限之內(nèi)完成。(4) 流程圖中的主要變量說明如下。i :循環(huán)控制變量，表示作業(yè)的編號。k：表示在期限內(nèi)完成的作業(yè)數(shù)。r :若job i能插入數(shù)組J，則其在數(shù)組J中的位置為 葉1。q：循環(huán)控制變量，用于移動數(shù)組J中的元素。(分?jǐn)?shù)：15.0

28、0 )(1).問題 1請將圖8-22中的空缺處的內(nèi)容填寫完整。(分?jǐn)?shù)：5.00 ) 正確答案：(i v =ndJr> diJr+1=i，或 Jq+1=i)解析：.問題2假設(shè)有6個作業(yè)job 1，job 2，job 6；完成作業(yè)的收益數(shù)組p=(p1,p2,p3,p4,p5,p6)=(90,80,50,30,20,10);每個作業(yè)的處理期限數(shù)組d=(d1,d2,d3,d4,d5,d6)=(1,2,1,3,4,3)。請應(yīng)用試題中描述的貪心策略算法，給岀在期限之內(nèi)處理的作業(yè)編號序列 (按作業(yè)處理的順序給岀)，得到的總收益為。(分?jǐn)?shù)：5.00 )正確答案：(1,2,4,5 或job 1、job 2

29、、job 4、job 5及其等價描述形式220)解析：這是一道考查貪心算法實例應(yīng)用的分析題。6個作業(yè)、job1、job2、.、job6的收益已經(jīng)按降序排列，根據(jù)圖8-22的算法流程，將作業(yè)1、2、4和5放入數(shù)組J中，并得到總收益為220,具體分析過程見表8-9。表8-9貪心算法實例執(zhí)行過程J數(shù)組收益考慮的作業(yè)期限操作0job 11放入J中190job 22放入J中1,2170job 31不放入J中1,2170job 43放入J中1,2,4200job 54放入J中1,2,4,5220job 63不放入J中1,2,4,5220問題3對于本試題的作業(yè)處理問題，用圖8-22的貪心算法能否求得最高收益

30、 ?（能或不能）。用貪心算法求解任意給定問題時，是否一定能得到最優(yōu)解?（能或不能）。（分?jǐn)?shù)：5.00）正確答案：（能，或可以、行及其他含義相同的詞語不能，或不可以、不行及其他含義相同的詞語）解析：這是一道判斷貪心算法是否能求得最優(yōu)解的應(yīng)用分析題。對于本試題的作業(yè)處理問題，用圖8-22的貪心算法策略，能求得最優(yōu)解（即能求得最高收益）。但不是所有的問題都能通過貪心策略來求得最優(yōu)解， 一個典型的例子是0-1背包問題。例如，有3件物品，背包可容納 50磅重的東西，每件物品的詳細(xì)信息如 表8-10所示，問如何裝包使得其價值最大 ？表8-10 貪心算法實例執(zhí)行過程物品編號重量（磅）價值（美元）單位價值R1

31、0606S201005T301204如果按貪心策略求解該問題，優(yōu)先選擇單位價值最大的物品，則先選擇物品R,然后選擇物品S。由于此時背包容量還剩下50-10-20=20，不足以容納物品T，故總價值為60+100=160美元。但若選擇物品 S和物品 T，容量總和為20+30,小于等于總?cè)萘?0,得到總價值為100+120=220美元，會得到更優(yōu)解。此時用貪心 策略不能得到最優(yōu)解。五、試題5（總題數(shù)：1,分?jǐn)?shù)：15.00）1.請閱讀以下技術(shù)說明、類圖及C+代碼，回答下列問題。說明已知某企業(yè)的采購審批是分級進行的，即根據(jù)采購金額的不同由不同層次的主管人員來審批。主任可以審批5萬元以下（不包括5萬元）的

32、采購單，副董事長可以審批5萬元至10萬元（不包括10萬元）的采購單，董事長可以審批10萬元至50萬元（不包括50萬元）的采購單，50萬元及以上的采購單就需要開會討論決采用責(zé)任鏈設(shè)計模式（Chain of Responsibility）對上述過程進行設(shè)計后得到的類圖如圖8-23所示。C+代碼#include < String >#include < iostream >using namespace std;class PurchaseRequestpublic:double Amount; / 采購的金額int Number; / 采購的單號string Purpose

33、; /采購的目的class Approver /審批者類public:Approver。successor=NULL;virtual void ProcessRequest (PurchaseRequest aRequest)if successor !=NULL) successor- > ;void SetSuccessor (Approver *aSuccesssor) successor=aSuccesssor; private:successor;class Congress:public Approverpublic:void ProcessRequest (Purohase

34、Request aRequest)if (aRequest.Amount > :500000)/* 決定是否審批的代碼省略 */ else ProcessRequest(aRequest);class Director:public Approver public:void ProcessRequest(PurchaseRequest aRequest) /* 此處代碼省略 */ class President:public Approverpublic:void ProcessRequest(PurchaseRequest aRequest) /* 此處代碼省略 */ class Vi

35、cePresident:public Approver此處代碼省略 */public:void ProcessRequest(PurchaseRequest aRequest /* void main()Congress Meeting; VicePresident Sam; Director Larry; President Tammy; / 構(gòu)造責(zé)任鏈Meeting.SetSuccessor(NULL); Sam.SetSuccessor();Tammy.SetSuccessor();Larry.SetSuccessor();PurchaseRequest aRequest; /構(gòu)造一采購

36、審批請求cin >> aRequest.Amount; /輸入采購請求的金額.ProcessRequest(aRequest); / 開始審批 return;分?jǐn)?shù)： 15.00 ） 正確答案： （ProcessRequest（aRequest）Approver*Approver:&Tammy&Meeting&SamLarry） 解析：六、試題 6 （總題數(shù)： 1，分?jǐn)?shù)： 15.00）2. 請閱讀以下技術(shù)說明、類圖及 Java 代碼，回答下列問題。 說明 已知某企業(yè)的采購審批是分級進行的，即根據(jù)采購金額的不同由不同層次的主管人員來審批，主任可以審 批5 萬元以

37、下 （不包括 5 萬元）的采購單，副董事長可以審批5萬元至 10萬元（不包括 10萬元）的采購單，董事長可以審批10萬元至50萬元(不包括50萬元)的采購單，50萬元及以上的采購單就需要開會討論決 采用責(zé)任鏈設(shè)計模式(Chain of Responsibility)對上述過程進行設(shè)計后得到的類圖如圖8-24所示。Java代碼class PurchaseRequestpublic double Amount; /采購金額public int Number; /采購單編號public String Purpose; / 采購目的>class Approver /審批者類public Approver。s