試題一
閱讀以下說(shuō)明和圖，回答問(wèn)題1至問(wèn)題3。
【說(shuō)明】
某房屋租賃公司欲建立一個(gè)房屋租賃服務(wù)系統(tǒng)，統(tǒng)一管理房主和租賃者的信息，從而快速地提供租賃服務(wù)。該系統(tǒng)具有以下功能：
1．登記房主信息。對(duì)于每名房主，系統(tǒng)需登記其姓名、住址和聯(lián)系電話，并將這些信息寫(xiě)入房主信息文件。
2．登記房屋信息。所有在系統(tǒng)中登記的房屋都有一個(gè)唯一的識(shí)別號(hào)(對(duì)于新增加的房屋，系統(tǒng)會(huì)自動(dòng)為其分配一個(gè)識(shí)別號(hào))。除此之外，還需登記該房屋的地址、房型(如平房、帶陽(yáng)臺(tái)的樓房、獨(dú)立式住宅等)、最多能夠容納的房客數(shù)、租金及房屋狀態(tài)(待租賃、已出租)。這些信息都保存在房屋信息文件中。一名房主可以在系統(tǒng)中登記多個(gè)待租賃的房屋。
3．登記租賃者信息。所有想通過(guò)該系統(tǒng)租賃房屋的租賃者，必須首先在系統(tǒng)中登記個(gè)人信息，包括：姓名、住址、電話號(hào)碼、出生年月和性別。這些信息都保存在租賃者信息文件中。
4．租賃房屋。已經(jīng)登記在系統(tǒng)中的租賃者，可以得到一份系統(tǒng)提供的待租賃房屋列表。一旦租賃者從中找到合適的房屋，就可以提出看房請(qǐng)求。系統(tǒng)會(huì)安排租賃者與房主見(jiàn)面。對(duì)于每次看房，系統(tǒng)會(huì)生成一條看房記錄并將其寫(xiě)入看房記錄文件中。
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)的請(qǐng)求。系統(tǒng)將根據(jù)房主的請(qǐng)求，修改房屋信息文件。
數(shù)據(jù)流圖10-1和圖10-2分別給出了該系統(tǒng)的頂層數(shù)據(jù)流圖和0層數(shù)據(jù)流圖。

【問(wèn)題1】

使用[說(shuō)明]中給出的詞匯，將數(shù)據(jù)流圖10-1中(1)～(4)處的數(shù)據(jù)流補(bǔ)充完整。

【問(wèn)題2】

使用[說(shuō)明]中給出的詞匯，將數(shù)據(jù)流圖10-2中的(5)～(8)補(bǔ)充完整。

【問(wèn)題3】

數(shù)據(jù)流程圖10-2中缺失了三條數(shù)據(jù)流，請(qǐng)指出這三條數(shù)據(jù)流的起點(diǎn)、終點(diǎn)和數(shù)據(jù)流名稱(chēng)。

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

通過(guò)對(duì)表10-4中的名詞進(jìn)行分析，最終得到了圖10-4所示的UML類(lèi)圖(類(lèi)的說(shuō)明如表10-5所示)。

【問(wèn)題1】
表10-5所給出的類(lèi)并不完整，根據(jù)[說(shuō)明]和表10-4，將圖10-4中的(a)～(c)處補(bǔ)充完整。



【問(wèn)題2】
根據(jù)【說(shuō)明】中的描述，給出圖10-4中的類(lèi)CatalogItem以及(b)、(c)處所對(duì)應(yīng)的類(lèi)的關(guān)鍵屬性(使用表10-4中給出的詞匯)，其中，CamlogItem有4個(gè)關(guān)鍵屬性；(b)、 (c)處對(duì)應(yīng)的類(lèi)各有兩個(gè)關(guān)鍵屬性。
【問(wèn)題3】
識(shí)別關(guān)聯(lián)的多重度是面向?qū)ο蠼＿^(guò)程中的一個(gè)重要步驟。根據(jù)[說(shuō)明]中給出的描述，完成圖10-4中的(1)～(6)。

試題四
閱讀以下說(shuō)明和圖，填補(bǔ)流程圖中的空缺。
【說(shuō)明】
在一條農(nóng)村公路的一邊稀疏地分布著房子，其分布如圖10-5所示。某電信公司需要在某些位置放置蜂窩電話基站，由于基站的覆蓋范圍是6公里，因此必須使得每棟房子到某個(gè)基站的直線距離不超過(guò)6公里。為簡(jiǎn)化問(wèn)題，假設(shè)所有房子在同一直線上，并且基站沿該直線放置?，F(xiàn)采用貪心策略實(shí)現(xiàn)用盡可能少的基站覆蓋所有的房子。

實(shí)現(xiàn)貪心算法的流程如圖10-6所示，請(qǐng)?zhí)畛淦渲锌瞻撞⒂?jì)算該算法的時(shí)間復(fù)雜度，其中：
1．d[i](1≤i≤N)表示第i個(gè)房子到公路A端的距離，N表示房子的總數(shù)，房子的編號(hào)按照房子到公路A端的距離從小到大進(jìn)行編號(hào)。
2．s[k]表示第k(k≥1)個(gè)基站到公路A端的距離，算法結(jié)束后k的值為基站的總數(shù)。


該算法的時(shí)間復(fù)雜度為  (5)  。

試題五
(以下試題五至試題七中任選一題解答)
閱讀以下說(shuō)明和C語(yǔ)言函數(shù)，應(yīng)填入  (n)  處。
【說(shuō)明】
在一個(gè)分布網(wǎng)絡(luò)中，資源(石油、天然氣、電力等)可從生產(chǎn)地送往其他地方。在傳輸過(guò)程中，資源會(huì)有損耗。例如，天然氣的氣壓會(huì)減少，電壓會(huì)降低。我們將需要輸送的資源信息稱(chēng)為信號(hào)。在信號(hào)從信源地送往消耗地的過(guò)程中，僅能容忍一定范圍的信號(hào)衰減，稱(chēng)為容忍值。分布網(wǎng)絡(luò)可表示為一個(gè)樹(shù)型結(jié)構(gòu)，如圖10-9所示。信號(hào)源是樹(shù)根，樹(shù)中的每個(gè)節(jié)點(diǎn)(除了根)表示一個(gè)可以放置放大器的子節(jié)點(diǎn)，其中某些節(jié)點(diǎn)同時(shí)也是信號(hào)消耗點(diǎn)，信號(hào)從一個(gè)節(jié)點(diǎn)流向其子節(jié)點(diǎn)。
每個(gè)節(jié)點(diǎn)有一個(gè)d值，表示從其父節(jié)點(diǎn)到該節(jié)點(diǎn)的信號(hào)衰減量。例如，在圖10-9中，節(jié)點(diǎn)w、p、q的d值分別為2、1、3，樹(shù)根節(jié)點(diǎn)表示信號(hào)源，其d值為0。
每個(gè)節(jié)點(diǎn)有一個(gè)M值，表示從該節(jié)點(diǎn)出發(fā)到其所有葉子的信號(hào)衰減量的最大值。顯然，葉子節(jié)點(diǎn)的M值為0。對(duì)于非葉子節(jié)點(diǎn)j，M(j)=max{M(k)+d(k)|k是j的孩子節(jié)點(diǎn)}。在此公式中，要計(jì)算節(jié)點(diǎn)的M值，必須先算出其所有子節(jié)點(diǎn)的M值。

在計(jì)算M值的過(guò)程中，對(duì)于某個(gè)節(jié)點(diǎn)i，其有一個(gè)子節(jié)點(diǎn)k滿(mǎn)足d(k)+M(k)大于容忍值，則應(yīng)在k處放置放大器，否則，從節(jié)點(diǎn)i到某葉子節(jié)點(diǎn)的信號(hào)衰減量會(huì)超過(guò)容忍值，使得到達(dá)該葉子節(jié)點(diǎn)時(shí)信號(hào)不可用，而在節(jié)點(diǎn)i處放置放大器并不能解決到達(dá)葉子節(jié)點(diǎn)的信號(hào)衰減問(wèn)題。
例如，在圖10-9中，從節(jié)點(diǎn)p到其所有葉子節(jié)點(diǎn)的最大衰減值為4。若容忍值為3，則必須在s處放置信號(hào)放大器，這樣可使得節(jié)點(diǎn)p的M值為2。同樣，需要在節(jié)點(diǎn)小v處放置信號(hào)放大器，如圖10—10陰影節(jié)點(diǎn)所示。若在某節(jié)點(diǎn)放置了信號(hào)放大器，則從該節(jié)點(diǎn)輸出的信號(hào)與信號(hào)源輸出的信號(hào)等價(jià)。

函數(shù)placeBoosters(TreeNode*root)的功能是：對(duì)于給定樹(shù)型分布網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)，計(jì)算其信號(hào)衰減量的最大值，并確定應(yīng)在樹(shù)中的哪些節(jié)點(diǎn)放置信號(hào)放大器。
全局變量Tolerance保存信號(hào)衰減容忍值。
樹(shù)的節(jié)點(diǎn)類(lèi)型定義如下：
typedef struct TreeNode{
int id；                      /*當(dāng)前節(jié)點(diǎn)的識(shí)別號(hào)*/
int ChildNum；                /*當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目*/
int d;                       /*父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的信號(hào)衰減值*/
struct TreeNode **childptr；  /*向量，存放當(dāng)前節(jié)點(diǎn)到其所有子節(jié)點(diǎn)的指針*/
int M；                       /*當(dāng)前節(jié)點(diǎn)到其所有子節(jié)點(diǎn)的信號(hào)衰減值中的最大值*/
bool boost；                  /*是否在當(dāng)前節(jié)點(diǎn)放置信號(hào)放大器的標(biāo)志*/
}TreeNode；
【C語(yǔ)言函數(shù)】
void placeBoosters(TreeNode *root)
{                               /*  計(jì)算root所指節(jié)點(diǎn)處的衰減量，如果衰減量超出了容忍值，則放置放大器*/
TreeNode *p；
int i，degradation；
if(  (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)中放置信號(hào)放大器*/
p-＞boost=true；
p-＞M = 0；
}
if  (p-＞d + p-＞M ＞ degradation)
degradation = p-＞d + p-＞M；
}
root-＞M =   (5)  ；
}
}