中級軟件設(shè)計(jì)師上半年下午試題

1、.中級軟件設(shè)計(jì)師 2007上半年下午試題試題一閱讀以下說明和圖，回答問題1至問題 3?！菊f明】某房屋租賃公司欲建立一個(gè)房屋租賃服務(wù)系統(tǒng)， 統(tǒng)一管理房主和租賃者的信息， 從而快速地提供租賃服務(wù)。該系統(tǒng)具有以下功能：1登記房主信息。對于每名房主，系統(tǒng)需登記其姓名、住址和聯(lián)系電話，并將這些信息寫入房主信息文件。2登記房屋信息。所有在系統(tǒng)中登記的房屋都有一個(gè)唯一的識(shí)別號(對于新增加的房屋，系統(tǒng)會(huì)自動(dòng)為其分配一個(gè)識(shí)別號)。除此之外，還需登記該房屋的地址、房型(如平房、帶陽臺(tái)的樓房、獨(dú)立式住宅等)、最多能夠容納的房客數(shù)、租金及房屋狀態(tài)(待租賃、已出租)。這些信息都保存在房屋信息文件中。一名房主可以在系統(tǒng)中

2、登記多個(gè)待租賃的房屋。3登記租賃者信息。所有想通過該系統(tǒng)租賃房屋的租賃者，必須首先在系統(tǒng)中登記個(gè)人信息，包括：姓名、住址、電話號碼、 出生年月和性別。這些信息都保存在租賃者信息文件中。4租賃房屋。已經(jīng)登記在系統(tǒng)中的租賃者，可以得到一份系統(tǒng)提供的待租賃房屋列表。一旦租賃者從中找到合適的房屋， 就可以提出看房請求。 系統(tǒng)會(huì)安排租賃者與房主見面。 對于每次看房，系統(tǒng)會(huì)生成一條看房記錄并將其寫入看房記錄文件中。5收取手續(xù)費(fèi)。房主登記完房屋后，系統(tǒng)會(huì)生成一份費(fèi)用單，房主根據(jù)費(fèi)用單交納相應(yīng)的費(fèi)用。6變更房屋狀態(tài)。當(dāng)租賃者與房主達(dá)成租房或退房協(xié)議后，房主向系統(tǒng)提交變更房屋狀態(tài)的請求。系統(tǒng)將根據(jù)房主的請求，修

3、改房屋信息文件。數(shù)據(jù)流圖 10-1和圖 10-2分別給出了該系統(tǒng)的頂層數(shù)據(jù)流圖和0層數(shù)據(jù)流圖。.1. 【問題 1】使用 說明 中給出的詞匯，將數(shù)據(jù)流圖10-1中 (1) (4)處的數(shù)據(jù)流補(bǔ)充完整。這道題您沒有回答答案 :(1)費(fèi)用單 (2) 待租賃房屋列表(3) 看房請求 (4)變更房屋狀態(tài)請求2. 【問題 2】使用 說明 中給出的詞匯，將數(shù)據(jù)流圖10-2中的 (5) (8) 補(bǔ)充完整。這道題您沒有回答答案 :(5)房主信息文件(6) 租賃者信息文件(7)房屋信息文件(8)看房記錄文件3. 【問題 3】數(shù)據(jù)流程圖 10-2中缺失了三條數(shù)據(jù)流，請指出這三條數(shù)據(jù)流的起點(diǎn)、終點(diǎn)和數(shù)據(jù)流名稱。這道題您

4、沒有回答答案 :(1)起點(diǎn)：房主終點(diǎn)：變更房屋狀態(tài)數(shù)據(jù)流名稱：變更房屋狀態(tài)請求(2) 起點(diǎn)：租賃者終點(diǎn)：登記租賃者信息數(shù)據(jù)流名稱：租賃者信息(3) 起點(diǎn)：租賃者終點(diǎn)：安排租賃者看房數(shù)據(jù)流名稱：看房請求 分析 本題考查的是DFD 的應(yīng)用，屬于比較傳統(tǒng)的題目，考查點(diǎn)也與往年類似。 問題 1 考查的是頂層DFD 。頂層 DFD 通常用來確定系統(tǒng)邊界，其中只包含一個(gè)唯一的加工( 即待開發(fā)的系統(tǒng))、外部實(shí)體以及外部實(shí)體與系統(tǒng)之間的輸入輸出數(shù)據(jù)流。題目要求填充的正是數(shù)據(jù)流。細(xì)心的考生可能會(huì)發(fā)現(xiàn)，在0層 DFD 中，與 “房主 ”相關(guān)的數(shù)據(jù)流有5條。其中的 “費(fèi)用單 ”是頂層 DFD 中沒有出現(xiàn)過的，而且是

5、系統(tǒng)輸出給“房主 ”的。這條數(shù)據(jù)流恰好可以與第(1)空對應(yīng)，因此 (1)處缺失的數(shù)據(jù)流就是 “費(fèi)用單 ”。如果確定了 (4)處的數(shù)據(jù)流，實(shí)際上 問題 3 要求的一條數(shù)據(jù)流也就找到了。由于 (4) 處缺失的數(shù)據(jù)流是一條輸入數(shù)據(jù)流，從 說明 中可以看出，只有功能6“當(dāng)租賃者與房主達(dá)成租房或退房協(xié)議后，房主向系統(tǒng)提交變更房屋狀態(tài)的請求”所描述的數(shù)據(jù)流沒有在“房主”與系統(tǒng)之間體現(xiàn)出來。因此可以確定，(4) 處缺失的數(shù)據(jù)流就是“變更房屋狀態(tài)請求”。相應(yīng)地，可以確定，在0層圖中缺失的其中一條數(shù)據(jù)流也是它，其起點(diǎn)是“房主 ”，終點(diǎn)是 “變更.房屋狀態(tài) ”這個(gè)加工。類似地，通過比較兩張 DFD 中與外部實(shí)體

6、“租賃者 ”相關(guān)的數(shù)據(jù)流， 可以發(fā)現(xiàn)：出現(xiàn)在 0層圖上的數(shù)據(jù)流 “帶租賃房屋列表 ”是頂層圖上沒有的，且與 (2)處的數(shù)據(jù)流的方向一致。由此可以斷定， (2)處的數(shù)據(jù)流就是“帶租賃房屋列表”。而頂層圖中的數(shù)據(jù)流“租賃者信息 ”卻是 0層圖上沒有的。 這樣就找到了 0層圖上缺失的第2條數(shù)據(jù)流： 租賃者信息， 它的起點(diǎn)是 “租賃者 ”，終點(diǎn)是加工 “登記租賃者信息”。再回到 說明 l，其中與 “租賃者 ”相關(guān)的功能 “一旦租賃者從中找到合適的房屋，就可以提出看房請求 ”并沒有在圖中體現(xiàn)出來。這樣就能確定(3)處的數(shù)據(jù)流應(yīng)該是“看房請求 ”。而0層圖中也沒有出現(xiàn)這條數(shù)據(jù)流。所以，0層圖中缺失的第3條

7、數(shù)據(jù)流就是 “看房請求 ”，它的起點(diǎn)是“租賃者 ”，終點(diǎn)是加工 “安排租賃者看房”。到此為止所有缺失的數(shù)據(jù)流都補(bǔ)齊了，0層圖中的 (5) (8) 需要填的是數(shù)據(jù)存儲(chǔ)。由 說明 可以確定，這個(gè)系統(tǒng)中的數(shù)據(jù)存儲(chǔ)有房主信息文件(功能 1)、房屋信息文件(功能 2)、租賃者信息文件 (功能 3)、看房記錄文件(功能 4)。下面就可以根據(jù)相應(yīng)的加工對號入座了。顯然，(5)處的是房主信息文件： (6)處的是租賃者信息文件； (7)處的是房屋信息文件； (8)處的是看房記錄文件。試題二閱讀下列說明，回答問題1至問題 3。【說明】某醫(yī)院的門診管理系統(tǒng)實(shí)現(xiàn)了為患者提供掛號、 處方藥品收費(fèi)的功能。 具體的需求及設(shè)

8、計(jì)如下：1醫(yī)院醫(yī)師具有編號，姓名，科室，職稱，出診類型和出診費(fèi)用，其中出診類型分為專家門診和普通門診， 與醫(yī)師職稱無關(guān)； 各個(gè)醫(yī)師可以具有不同的出診費(fèi)用， 與職稱和出診類型無關(guān)。2患者首先在門診掛號處掛號，選擇科室和醫(yī)師， 根據(jù)選擇的醫(yī)師繳納掛號費(fèi)(醫(yī)師出診費(fèi) )。收銀員為患者生成掛號單，如表10-1所示，其中，就診類型為醫(yī)師的出診類型。表 10-1××醫(yī)院門診掛號單收銀員： 13011時(shí)間：2007年 2月 1日 08:58就診號姓名科室醫(yī)師就診類型掛號費(fèi)20070205015葉萌內(nèi)科楊玉明專家門診5元3患者在醫(yī)師處就診后，憑借掛號單和醫(yī)師手寫處方到門診藥房交費(fèi)買藥。收銀

9、員根據(jù)就診號和醫(yī)師處方中開列的藥品信息，查詢藥品庫 (如表 10-2所示 )并生成門診處方單(如表10-3所示 )。表 10-2藥品庫藥品編藥品名類型庫存貨架編單位規(guī)格單價(jià)碼稱號12007牛蒡子中藥51590B1401G炒0.034011090百部中藥36950B1523G片0.0313表 10-3××醫(yī)院門診處方單時(shí)間：2007年 2月 1日 10:31就診號20070205015病人姓名葉萌醫(yī)師姓名楊玉明金額總計(jì)0.65項(xiàng)目總計(jì)2收銀員21081藥品編碼藥品名稱數(shù)量單位單價(jià)金額 (元).12007牛蒡子10G0.03400.3411090百部10G0.03130.314

10、由于藥品價(jià)格會(huì)發(fā)生變化，因此，門診管理系統(tǒng)必須記錄處方單上藥品的單價(jià)。根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖和關(guān)系模式(不完整 )如下所示：1實(shí)體聯(lián)系圖2關(guān)系模式掛號單 (就診號，病患姓名，醫(yī)師編號，時(shí)間，(5)收銀員 (編號，姓名，級別)醫(yī)師 (編號，姓名，科室，職稱，出診類型，出診費(fèi)用)門診處方 ( (6) ，收銀員，時(shí)間)處方明細(xì) (就診號，(7)藥品庫 (藥品編碼，藥品名稱，(8)4. 【問題 1】根據(jù)問題描述，填寫圖10-3實(shí)體聯(lián)系圖中(1) (4) 處聯(lián)系的類型。這道題您沒有回答答案 :(1)1(2)*，或 n，或 m(3)*，或 n，或 m(4)*，或 n，或 m5. 【問題

11、2】圖10-3 中還缺少幾個(gè)聯(lián)系 ?請指出每個(gè)聯(lián)系兩端的實(shí)體名，格式如下。實(shí)體 1：實(shí)體 2例如，收銀員與門診處方之間存在聯(lián)系，表示為：收銀員：門診處方或 門診處方：收銀員這道題您沒有回答答案 :缺少的聯(lián)系數(shù)：3掛號單：收銀員掛號單：醫(yī)師掛號單：門診處方6. 【問題 3】根據(jù)實(shí)體聯(lián)系圖10-3，填寫掛號單、門診處方、處方明細(xì)和藥品庫關(guān)系模式中的空(5) (8)處，并指出掛號單、門診處方和處方明細(xì)關(guān)系模式的主鍵。.這道題您沒有回答答案 :(5)收銀員，或收銀員編號(6) 就診號(7) 藥品編碼，數(shù)量，單價(jià)(8) 類型，庫存，貨架編號，單位，規(guī)格，單價(jià)掛號單主鍵：就診號 門診處方主鍵：就診號處方明

12、細(xì)主鍵：就診號、藥品編碼分析 問題 1分析本題主要是考數(shù)據(jù)庫的概念結(jié)構(gòu)設(shè)計(jì)。根據(jù)題目的需求描述和表10-3中的數(shù)據(jù)可知， 一名醫(yī)生可以開多張門診處方，一張門診處方由一名醫(yī)生開出。所以對于醫(yī)生實(shí)體與門診處方實(shí)體之間的聯(lián)系“開處方 ”，其聯(lián)系的類型為一對多 (1： n)。 (1)空的答案為 1，(2) 空的答案為n。根據(jù)題目的需求描述和表 10-3中的數(shù)據(jù)可知， 一張門診處方包含多種庫存中的藥品， 一種庫存中的藥品也可以在多張門診處方中。所以對于門診處方實(shí)體與藥品庫存實(shí)體之間的聯(lián)系“明細(xì) ”，其聯(lián)系的類型為多對多 (m： n)。 (3)空的答案為 m， (4)空的答案為 n。問題 2分析根據(jù)題目的

13、需求描述和表 10-1中的數(shù)據(jù)可知， 掛號單由收銀員進(jìn)行收費(fèi)， 因此掛號單實(shí)體與收銀員實(shí)體之間存在聯(lián)系。掛號單：收銀員病人掛某個(gè)醫(yī)師的號， 將掛號信息記錄在掛號單實(shí)體中， 因此掛號單實(shí)體與醫(yī)師實(shí)體之間存在聯(lián)系。掛號單：醫(yī)師根據(jù)題目的需求描述和表 10-3中的數(shù)據(jù)可知， 收銀員根據(jù)掛號單和醫(yī)師的手寫處方生成門診處方，所以掛號單實(shí)體與門診處方實(shí)體之間存在聯(lián)系。掛號單：門診處方因此，缺少的聯(lián)系數(shù)：3問題 3分析本題主要考查數(shù)據(jù)庫的邏輯結(jié)構(gòu)設(shè)計(jì)。根據(jù)實(shí)體聯(lián)系圖和表 10-1的數(shù)據(jù)，對于 “掛號單 ”關(guān)系模式，由于掛號單與收銀員實(shí)體有聯(lián)系，需記錄對應(yīng)的收銀員，因此，“掛號單 ”關(guān)系模式需補(bǔ)充屬性 (5)

14、：收銀員。根據(jù)實(shí)體聯(lián)系圖和表10-3的數(shù)據(jù)，由于門診處方實(shí)體與掛號單實(shí)體有聯(lián)系，因此，“門診處方”關(guān)系模式需記錄(6)：就診號。并且，根據(jù)題意在門診處方和掛號單之間存在的是1對 1的聯(lián)系，因此掛號單的主鍵可以作為門診處方的主鍵。根據(jù)實(shí)體聯(lián)系圖和表10-2、表 10-3的數(shù)據(jù)，由于廣張門診處方中包含多項(xiàng)藥品信息，而一種藥品也可以屬于多張門診處方，所以通過 “處方明細(xì) ”關(guān)系模式來表示這種多對多的聯(lián)系。并且由于每種藥品的具體信息已經(jīng)在“藥品庫存 ”關(guān)系模式中記錄，所以，“處方明細(xì) ”關(guān)系模式主要記錄的是門診處方與藥品的對應(yīng)關(guān)系和處方所需藥品的具體數(shù)量。并且，根據(jù)題目描述，由于藥品價(jià)格會(huì)發(fā)生變化，門

15、診管理系統(tǒng)必須記錄處方單上藥品的當(dāng)前單價(jià)。因此，“藥品庫存 ”關(guān)系模式補(bǔ)充屬性(7) ：塹顯纏昱， 數(shù)量，單價(jià)。 其中就診號和藥品編號一起作為主鍵。“藥品庫存 ”關(guān)系模式主要記錄藥品的詳細(xì)信息和庫存信息，根據(jù)實(shí)體聯(lián)系圖和表10-2的數(shù)據(jù)， “藥品庫存 ”關(guān)系模式需補(bǔ)充屬性(8)：類型，庫存，貨架編號，單位，規(guī)格，單價(jià)。掛號單主鍵：就診號門診處方主鍵：就診號處方明細(xì)主鍵：就診號、藥品編碼試題三閱讀下列說明和圖，回答問題1至問題 3。.【說明】某圖書管理系統(tǒng)的主要功能如下：1圖書管理系統(tǒng)的資源目錄中記錄著所有可供讀者借閱的資源，每項(xiàng)資源都有一個(gè)唯一的索引號。系統(tǒng)需登記每項(xiàng)資源的名稱、出版時(shí)間和資源

16、狀態(tài)( 可借閱或已借出)。2資源可以分為兩類：圖書和唱片。對于圖書，系統(tǒng)還需登記作者和頁數(shù)；對于唱片，還需登記演唱者和介質(zhì)類型 (CD 或者磁帶 )。3讀者信息保存在圖書管理系統(tǒng)的讀者信息數(shù)據(jù)庫中，記錄的信息包括：讀者的識(shí)別碼和讀者姓名。系統(tǒng)為每個(gè)讀者創(chuàng)建了一個(gè)借書記錄文件，用來保存讀者所借資源的相關(guān)信息?，F(xiàn)采用面向?qū)ο蠓椒ㄩ_發(fā)該圖書管理系統(tǒng)。 識(shí)別類是面向?qū)ο蠓治龅牡谝徊健?比較常用的識(shí)別類的方法是尋找問題描述中的名詞， 再根據(jù)相關(guān)規(guī)則從這些名詞中刪除不可能成為類的名詞，最終得到構(gòu)成該系統(tǒng)的類。表10-4給出了 說明 中出現(xiàn)的所有名詞。表 10-4圖書管理系統(tǒng)資源目錄讀者資源索引號系統(tǒng)名稱出

17、版時(shí)間資源狀態(tài)圖書唱片作者頁數(shù)演唱者介質(zhì)類型CD磁帶讀者信息讀者信息數(shù)據(jù)庫識(shí)別碼姓名借書記錄文件信息通過對表 10-4中的名詞進(jìn)行分析，最終得到了圖10-4所示的UML類圖 (類的說明如表10-5所示 )。表 10-5類名說明LibrarySystem圖書管理系統(tǒng)BorrowerDB保存讀者信息的數(shù)據(jù)庫CatalogItem資源目錄中保存的每項(xiàng)資源Borrower讀者BorrowerItems為每個(gè)讀者創(chuàng)建的借書記錄文件7. 【問題 1】表10-5 所給出的類并不完整，根據(jù) 說明 和表 10-4，將圖 10-4中的 (a) (c)處補(bǔ)充完整。.這道題您沒有回答答案 :(a)資源目錄(b) 圖書

18、(c)唱片注： (b) 和(c)的答案可以互換8. 【問題 2】根據(jù)【說明】中的描述，給出圖10-4中的類 CatalogItem 以及 (b) 、 (c)處所對應(yīng)的類的關(guān)鍵屬性( 使用表 10-4中給出的詞匯 )，其中， CamlogItem 有 4個(gè)關(guān)鍵屬性； (b) 、 (c)處對應(yīng)的類各有兩個(gè)關(guān)鍵屬性。這道題您沒有回答答案 :CatalogItem 的屬性：索引號、名稱、出版時(shí)間、資源狀態(tài)圖書的屬性：作者、頁數(shù)唱片的屬性：演唱者、介質(zhì)類型9. 【問題 3】識(shí)別關(guān)聯(lián)的多重度是面向?qū)ο蠼＿^程中的一個(gè)重要步驟。根據(jù) 說明 中給出的描述，完成圖10-4 中的 (1) (6) 。這道題您沒有回

19、答答案 :(1)1 (2)0.* (3)1 (4)0.* (5)1 (6)1或者 0.1分析 本題主要考查面向?qū)ο蠓治鲋蓄悎D的設(shè)計(jì)，涉及到類的識(shí)別、 屬性的識(shí)別以及多重度的計(jì)算。 問題 1 要求的是將所有的類找出來。 由于 說明 中給出了識(shí)別類的規(guī)則， 并給出了所有的候選類和一張不完整的類圖， 從而為我們提供了大量的提示信息。 從類圖可以看出， 這里有一個(gè)繼承結(jié)構(gòu)，確實(shí)這兩個(gè)類恰好是這個(gè)繼承結(jié)構(gòu)的子類。根據(jù) 說明 中提供信息，我們發(fā)現(xiàn)只有 “資源 ”、“圖書 ”和 “唱片 ”這三者之間存在著繼承結(jié)構(gòu)所描述的“一般 特殊 ”關(guān)系。因?yàn)椤皥D書 ”和 “唱片 ”都是圖書管理系統(tǒng)中的資源，因此具有共性

20、 (索引號、名稱、出版時(shí)間、資源狀態(tài) )；而這兩者又是兩種完全不同的事物，所以有著各自特有的性質(zhì)。同時(shí)，這三者又都在候選類集合中。所以可以斷定 (b) 、(c)處要填的類就是“唱片 ”和 “圖書 ”。這里連這三個(gè)類.的屬性也可以完全確定了。類CatalogItem 描述的是共性，所以它的屬性是索引號、名稱、出版時(shí)間、資源狀態(tài)。由 說明 中第 2條可以確定， “圖書 ”的屬性是作者和頁數(shù)； “唱片 ”的屬性是演唱者和介質(zhì)類型。下面需要確定 (a)處的類到底是什么?從 說明 中的第 1條和表 10-5可以看出，CatalogItem 表示的是 “資源目錄保存的每項(xiàng)資源”，這是集合 (資源目錄 )與

21、其中的元素的概念。所以(a)處的類應(yīng)該是 “資源目錄 ”一既然明確這里是集合的概念，(1) 和 (2) 處的多重度也可以確定了。CatalogItem 表示的是部分，所以(1)處應(yīng)填 1，(2) 處應(yīng)填 1.*(0.* 也可以 )。類似的， BorrowerDB 與 Borrower 之間也具有相似的關(guān)系。因?yàn)閿?shù)據(jù)庫中可以保存多個(gè)讀者的信息。因此 (3) 處填 1， (4)處填 1.*(0.* 也可以 )。系統(tǒng)為每個(gè)讀者都創(chuàng)建了借書記錄文件，所以 (5) 處填 1， (6)填 1(0.1也可以 )。試題四閱讀以下說明和圖，填補(bǔ)流程圖中的空缺。10. 【說明】在一條農(nóng)村公路的一邊稀疏地分布著房子

22、，其分布如圖 10-5所示。某電信公司需要在某些位置放置蜂窩電話基站，由于基站的覆蓋范圍是6公里，因此必須使得每棟房子到某個(gè)基站的直線距離不超過6公里。為簡化問題， 假設(shè)所有房子在同一直線上，并且基站沿該直線放置?，F(xiàn)采用貪心策略實(shí)現(xiàn)用盡可能少的基站覆蓋所有的房子。實(shí)現(xiàn)貪心算法的流程如圖10-6所示，請?zhí)畛淦渲锌瞻撞⒂?jì)算該算法的時(shí)間復(fù)雜度，其中：1 di(1 i 表示N)第 i 個(gè)房子到公路 A 端的距離， N 表示房子的總數(shù)，房子的編號按照房子到公路 A 端的距離從小到大進(jìn)行編號。2 sk 表示第 k(k 1)個(gè)基站到公路A 端的距離，算法結(jié)束后k 的值為基站的總數(shù)。.該算法的時(shí)間復(fù)雜度為(5

23、) 。這道題您沒有回答答案 :(1)k=0(2)j N，或其等價(jià)形式(3)k=k+1 ，或其等價(jià)形式(4)di+6 ，或其等價(jià)形式(5)O(N) ，或 O(n)分析 該問題可以建模為如圖10-7所示，其中直線表示房子所在的直線，實(shí)心正方形表示房子。問題是要求如何在該直線上布局機(jī)站， 使其能覆蓋所有的房子， 并且所用機(jī)站的數(shù)量要盡可能的少。這是一個(gè)通過進(jìn)行一系列選擇求最優(yōu)解的問題。分析該問題， 發(fā)現(xiàn)其具有最優(yōu)子結(jié)構(gòu)，并且具有貪心選擇性質(zhì)，故該問題可以用貪心算法來求解。算法思想：問題的規(guī)模為N。從第一個(gè)房子(最左端 )開始布局機(jī)站，把第一個(gè)機(jī)站放置在該房子右方的 6公里處，這時(shí)該機(jī)站會(huì)覆蓋從第一個(gè)

24、房子到其右方 12公里的直線的長度上的所有房子，假設(shè)覆蓋了 N 1個(gè)房子。此時(shí)問題規(guī)模變成了 N-N 1。把第一個(gè)機(jī)站覆蓋的房子去掉， 再從 N-N 1 中選擇第一個(gè) (最左端 )房子開始布局機(jī)站， 將第二個(gè)機(jī)站放置在該房子右方的 6公里處。依此布局，直到覆蓋所有的房子。圖10-8 是問題解的模型，其中直線表示房子所在的直線，實(shí)心正方形表示房子，實(shí)心圓形表示機(jī)站，虛線圓以對應(yīng)機(jī)站為圓心，直徑為機(jī)站的覆蓋范圍，即對應(yīng)機(jī)站的覆蓋范圍。.算法中包含兩個(gè)循環(huán)，但實(shí)際上只是遍歷所有房子一次，故算法復(fù)雜度是O(N) 。試題五(以下試題五至試題七中任選一題解答)閱讀以下說明和C 語言函數(shù)，應(yīng)填入(n) 處。

25、11. 【說明】在一個(gè)分布網(wǎng)絡(luò)中， 資源 (石油、天然氣、 電力等 ) 可從生產(chǎn)地送往其他地方。 在傳輸過程中，資源會(huì)有損耗。 例如，天然氣的氣壓會(huì)減少， 電壓會(huì)降低。我們將需要輸送的資源信息稱為信號。在信號從信源地送往消耗地的過程中，僅能容忍一定范圍的信號衰減，稱為容忍值。分布網(wǎng)絡(luò)可表示為一個(gè)樹型結(jié)構(gòu)，如圖10-9所示。信號源是樹根，樹中的每個(gè)節(jié)點(diǎn)( 除了根 )表示一個(gè)可以放置放大器的子節(jié)點(diǎn)， 其中某些節(jié)點(diǎn)同時(shí)也是信號消耗點(diǎn)， 信號從一個(gè)節(jié)點(diǎn)流向其子節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)有一個(gè)d 值，表示從其父節(jié)點(diǎn)到該節(jié)點(diǎn)的信號衰減量。例如，在圖 10-9中，節(jié)點(diǎn) w、p、 q 的 d 值分別為 2、 1、 3，樹

26、根節(jié)點(diǎn)表示信號源，其d 值為 0。每個(gè)節(jié)點(diǎn)有一個(gè)M 值，表示從該節(jié)點(diǎn)出發(fā)到其所有葉子的信號衰減量的最大值。顯然，葉子節(jié)點(diǎn)的M 值為 0。對于非葉子節(jié)點(diǎn)j， M(j)=maxM(k)+d(k)|k是 j 的孩子節(jié)點(diǎn) 。在此公式中，要計(jì)算節(jié)點(diǎn)的M 值，必須先算出其所有子節(jié)點(diǎn)的M 值。在計(jì)算 M 值的過程中，對于某個(gè)節(jié)點(diǎn)i ，其有一個(gè)子節(jié)點(diǎn)k 滿足 d(k)+M(k) 大于容忍值，則應(yīng)在 k 處放置放大器，否則，從節(jié)點(diǎn)i 到某葉子節(jié)點(diǎn)的信號衰減量會(huì)超過容忍值，使得到達(dá)該葉子節(jié)點(diǎn)時(shí)信號不可用，而在節(jié)點(diǎn)i 處放置放大器并不能解決到達(dá)葉子節(jié)點(diǎn)的信號衰減問題。例如，在圖 10-9中，從節(jié)點(diǎn)p 到其所有葉子節(jié)

27、點(diǎn)的最大衰減值為4。若容忍值為 3，則必須在s 處放置信號放大器，這樣可使得節(jié)點(diǎn)p 的 M 值為 2。同樣，需要在節(jié)點(diǎn)小v 處放置信號放大器， 如圖 10 10陰影節(jié)點(diǎn)所示。 若在某節(jié)點(diǎn)放置了信號放大器， 則從該節(jié)點(diǎn)輸出的信號與信號源輸出的信號等價(jià)。.函數(shù) placeBoosters(TreeNode*root) 的功能是：對于給定樹型分布網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)，計(jì)算其信號衰減量的最大值，并確定應(yīng)在樹中的哪些節(jié)點(diǎn)放置信號放大器。全局變量 Tolerance 保存信號衰減容忍值。樹的節(jié)點(diǎn)類型定義如下：typedef struct TreeNodeint id ； /* 當(dāng)前節(jié)點(diǎn)的識(shí)別號*/int Chi

28、ldNum ； /* 當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目*/int d; /* 父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的信號衰減值*/struct TreeNode *childptr ； /* 向量，存放當(dāng)前節(jié)點(diǎn)到其所有子節(jié)點(diǎn)的指針*/int M ； /* 當(dāng)前節(jié)點(diǎn)到其所有子節(jié)點(diǎn)的信號衰減值中的最大值*/bool boost ； /* 是否在當(dāng)前節(jié)點(diǎn)放置信號放大器的標(biāo)志*/TreeNode ；【C 語言函數(shù)】void placeBoosters(TreeNode *root) /*計(jì)算 root 所指節(jié)點(diǎn)處的衰減量，如果衰減量超出了容忍值，則放置放大器*/TreeNode *p ；int i ， degradation ；if

29、( (1)degradation = 0 ；root- M = 0 ；i = 0 ；if (i =root- ChildNum)return；p= (2) ；for(;i root- ChildNum && p； i+ ，p = (3)p- M = 0 ；(4) ；if (p- d+p- M Tolerance) /* 在 p 所指節(jié)點(diǎn)中放置信號放大器 */ p- boost=true ；p- M = 0 ；if (p- d + p- M degradation)degradation = p- d + p- M ；root- M = (5) ；.這道題您沒有回答答案 :(1)

30、root(2)root- childptr0 ，或其等價(jià)形式(3)root- childptri ， p+，或其等價(jià)形式(4)placeBoosters(p)(5)degradation分析 本題考查樹結(jié)構(gòu)的應(yīng)用。根據(jù)題目中的說明，節(jié)點(diǎn)的M 值表示從該節(jié)點(diǎn)出發(fā)到其所有葉子的信號衰減量的最大值。顯然，葉子節(jié)點(diǎn)的 M 值為 0。對于非葉子節(jié)點(diǎn)j ， M(j)=maxM(k)+d(k)| k是 j 的孩子節(jié)點(diǎn) 。在此公式中，要計(jì)算節(jié)點(diǎn)的M 值，必須先算出其所有子節(jié)點(diǎn)的M 值。因此，需要對樹進(jìn)行后序遍歷。對樹中節(jié)點(diǎn)的運(yùn)算應(yīng)針對非空節(jié)點(diǎn)，因此空(1)處應(yīng)填入 root 。變量 degradation 用

31、于計(jì)算節(jié)點(diǎn)的信號衰減量。節(jié)點(diǎn)中的ChildNum 表示當(dāng)前節(jié)點(diǎn)的孩子數(shù)目，因此若“i root- ChildNum ”，則 root 指向的節(jié)點(diǎn)是葉子。以下代碼是對樹進(jìn)行后序遍歷并計(jì)算節(jié)點(diǎn)的信號衰減量。p= (2) ；for(;i root- ChildNum && p； i+ ， p = (3)p- M = 0 ；(4) ；if (p- d+p- M Tolerance) /* 在 p 所指節(jié)點(diǎn)中放置信號放大器 */ p- boost = true ；p- M = 0 ；if (p- d + p- M degradation)degradation = p- d + p- M

32、 ；root- M= (5) ；分析以上代碼可知，指針p 用于指向子節(jié)點(diǎn)，其初始值應(yīng)為第一個(gè)子節(jié)點(diǎn)“childptr0 的指”針，因此空 (2)處應(yīng)填入 “root- childptr0，”此后 p 依次指向下一個(gè)子節(jié)點(diǎn)，因此空(3) 處填入“root- childpbtri或”“p+”。由于樹結(jié)構(gòu)是遞歸的，因此，可用遞歸方法計(jì)算所有子節(jié)點(diǎn)的信號衰減量。在設(shè)計(jì)思路上，應(yīng)考慮節(jié)點(diǎn)為葉子時(shí)的情況(遞歸終止 )以及從子節(jié)點(diǎn)返回父節(jié)點(diǎn)后需要處理的情況。對于當(dāng)前的子節(jié)點(diǎn) (childptri) ，顯然需要通過遞歸調(diào)用去處理， 因此空 (4)處應(yīng)填入 “placeBoosters(p) ” 在計(jì)算 M 值

33、的過程中，對于某個(gè)節(jié)點(diǎn) i ，其有一個(gè)子節(jié)點(diǎn) k 滿足 d(k)+M(k) 大于容忍值 (p- d+p- M Tolerance)，則應(yīng)在 k 處放置放大器 (p- boost true)，否則，從節(jié)點(diǎn) i 到某葉子節(jié)點(diǎn)的信號衰減量會(huì)超過容忍值，使得到達(dá)該葉子節(jié)點(diǎn)時(shí)信號不可用，而在節(jié)點(diǎn)i 處放置放大器并不能解決到達(dá)葉子節(jié)點(diǎn)的信號衰減問題。當(dāng) root 所指節(jié)點(diǎn)的所有子節(jié)點(diǎn)的信號衰減量最大值求出來并按要求放置信號放大器后，就可以記錄該節(jié)點(diǎn)的信號衰減量最大值了，因此空(5) 處應(yīng)填入 “degradation?！痹囶}六閱讀下列說明和C+ 代碼，應(yīng)填入(n)處。.12. 【說明】某游戲公司現(xiàn)欲開發(fā)一

34、款面向兒童的模擬游戲，該游戲主要模擬現(xiàn)實(shí)世界中各種鴨子的發(fā)聲特征、飛行特征和外觀特征。游戲需要模擬的鴨子種類及其特征如表10-6所示：表 10-6為支持將來能夠模擬更多種類鴨子的特征，采用策略設(shè)計(jì)模式(Strategy) 設(shè)計(jì)的類圖如圖10-11所示：其中， Duck 為抽象類，描述了抽象的鴨子，而類RubberDuck 、MallardDuck 、 CottonDuck和 RedHeadDuck 分別描述具體的鴨子種類，方法fly() 、 quack() 和 display() 分別表示不同種類的鴨子都具有飛行特征、發(fā)聲特征和外觀特征；類FlyBehavior 與 QuackBehavior

35、 為抽象類，分別用于表示抽象的飛行行為與發(fā)聲行為：類FlyNoWay 與 FlyWithWings 分別描述不能飛行的行為和用翅膀飛行的行為； 類 Quack、Squeak 與 QuackNoWay 分別描述發(fā)出 “嘎嘎 ” 聲的行為、發(fā)出橡皮與空氣摩擦聲的行為與不發(fā)聲的行為。請?zhí)钛a(bǔ)以下代碼中的空缺?！?C+ 代碼】#include iostreamusing namespace (1)； class FlyBehaviorpublic ： (2) fly()=0 ； ；class QuackBehaviorpublic ： (3) quack() = 0 ； ；.class FlyWithW

36、ings ： public FlyBehaviorpublic ： void fly() cout “使用翅膀飛行!” endl； ；class FlyNoWay ： public FlyBehaviorpublic ： void fly() cout “不能飛行 ! ” endl； ；class Quack： public QuackBehaviorpublic ： void quack() cout “發(fā)出 嘎嘎 聲 ! ” endl； ；class Squeak：public QuackBehaviorpublic ： void quack()cout “發(fā)出空氣與橡皮摩擦聲! ” en

37、dl； ；class QuackNoWay： public QuackBehaviorpublic ： void quack () cout “不能發(fā)聲! ” endl； ；class Duckprotected：FlyBehavior* (4) ；QuackBehavior* (5) ；public ：void fly() (6)； void quack() (7) ；) ；virtual void display()=0 ； ；class RubberDuck ：public Duckpublic ：RubberDuck()flyBehavior=new (8) ；quackBehavio

38、r new (9) ； RubberDuck()if(!flyBehavior)delete flyBehavior；if(!quackBehavior) delete quackBehavior ；void display()/*此處省略顯示橡皮鴨的代碼*/ ；/其他代碼省略這道題您沒有回答答案 :(1) std(2) virtual void(3) virtual void(4) fiyBehavior(5) quackBehavior(6) flyBehavior- fly().(7) quackBehavior- quack()(8) FlyNoWay()(9) Squeak()分析

39、C+ 標(biāo)準(zhǔn)的輸出輸入的命名空間為std，在本題的代碼中使用了cout ，因此必須使用標(biāo)準(zhǔn)的命名空間，空 (1) 處應(yīng)該填寫std；FlyWithWings和 FlyNoWay 類繼承了FlyBehavior ，根據(jù)它們的成員函數(shù)fly 的定義可知， fly 函數(shù)的返回值為void ，又因?yàn)镕lyBehavior 中函數(shù)為純虛擬函數(shù)，因此，空(2)處應(yīng)該填寫virtual void ，空 (3) 處的原理和空(2)相同； Duck 是各種鴨子種類的基類， 而每一種鴨子都具有飛行特征和發(fā)聲特征，這兩種特征分別通過FlyBehavior和 QuackBehavior 來實(shí)現(xiàn)， 因此空 (4) 和 (

40、5) 處應(yīng)該為這兩個(gè)類的對象或者指針 (這兩個(gè)類為純虛類，因此只能采用指針形式 )。每一種具體的鴨子種類的飛行特征和發(fā)聲特征是不同的，因此，在每一種具體鴨子類的構(gòu)造函數(shù)中需要指定其具有的飛行特征和發(fā)聲特征，表10-6已經(jīng)指出了RubberDuck 的這兩種特征分別為FlyNoWay和 Squeak，所以，通過構(gòu)造相應(yīng)類的對象來實(shí)現(xiàn)該特征。試題七閱讀下列說明和Java 代碼，應(yīng)填入(n) 處。13. 【說明】某游戲公司現(xiàn)欲開發(fā)一款面向兒童的模擬游戲，該游戲主要模擬現(xiàn)實(shí)世界中各種鴨子的發(fā)聲特征、飛行特征和外觀特征。游戲需要模擬的鴨子種類及其特征如表10-7所示：表 10-7為支持將來能夠模擬更多種

41、類鴨子的特征，采用策略設(shè)計(jì)模式(Strategy) 設(shè)計(jì)的類圖如圖10-12所示：其中，Duck 為抽象類， 描述了抽象的鴨子， 而類 RubberDuck 、MallardDuck 、 CottonDuck 和 RedHeadDuck 分別描述具體的鴨子種類， 方法 fly() 、quack() 和 display() 分別表示不同種類的鴨子都具有飛行特征、發(fā)聲特征和外觀特征；接口FlyBehavior 與 QuackBehavior 分別用于表示抽象的飛行行為與發(fā)聲行為；類FlyNoWay 與 FlyWithWings 分別描述不能飛行的行為和用翅膀飛行的行為；類 Quack、 Squeak 與 QuackNoWay 分別描述發(fā)出 “嘎嘎 ”聲的行為、發(fā)出橡皮與空氣摩擦聲的行為與不發(fā)聲的行為。請?zhí)钛a(bǔ)以下代碼中的空缺。【 Java 代碼】(1)FlyBehaviorpublic