試題三
閱讀下列說明和圖，回答問題1至問題3。
【說明】
某圖書管理系統的主要功能如下：
1．圖書管理系統的資源目錄中記錄著所有可供讀者借閱的資源，每項資源都有一個唯一的索引號。系統需登記每項資源的名稱、出版時間和資源狀態(tài)(可借閱或已借出)。
2．資源可以分為兩類：圖書和唱片。對于圖書，系統還需登記作者和頁數；對于唱片，還需登記演唱者和介質類型(CD或者磁帶)。
3．讀者信息保存在圖書管理系統的讀者信息數據庫中，記錄的信息包括：讀者的識別碼和讀者姓名。系統為每個讀者創(chuàng)建了一個借書記錄文件，用來保存讀者所借資源的相關信息。
現采用面向對象方法開發(fā)該圖書管理系統。識別類是面向對象分析的第一步。比較常用的識別類的方法是尋找問題描述中的名詞，再根據相關規(guī)則從這些名詞中刪除不可能成為類的名詞，最終得到構成該系統的類。表10-4給出了[說明]中出現的所有名詞。

通過對表10-4中的名詞進行分析，最終得到了圖10-4所示的UML類圖(類的說明如表10-5所示)。

【問題1】
表10-5所給出的類并不完整，根據[說明]和表10-4，將圖10-4中的(a)～(c)處補充完整。



【問題2】
根據【說明】中的描述，給出圖10-4中的類CatalogItem以及(b)、(c)處所對應的類的關鍵屬性(使用表10-4中給出的詞匯)，其中，CamlogItem有4個關鍵屬性；(b)、 (c)處對應的類各有兩個關鍵屬性。
【問題3】
識別關聯的多重度是面向對象建模過程中的一個重要步驟。根據[說明]中給出的描述，完成圖10-4中的(1)～(6)。

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

實現貪心算法的流程如圖10-6所示，請?zhí)畛淦渲锌瞻撞⒂嬎阍撍惴ǖ臅r間復雜度，其中：
1．d[i](1≤i≤N)表示第i個房子到公路A端的距離，N表示房子的總數，房子的編號按照房子到公路A端的距離從小到大進行編號。
2．s[k]表示第k(k≥1)個基站到公路A端的距離，算法結束后k的值為基站的總數。


該算法的時間復雜度為  (5)  。

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

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

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

試題七
閱讀下列說明和Java代碼，應填入  (n)  處。
【說明】
某游戲公司現欲開發(fā)一款面向兒童的模擬游戲，該游戲主要模擬現實世界中各種鴨子的發(fā)聲特征、飛行特征和外觀特征。游戲需要模擬的鴨子種類及其特征如表10-7所示：

為支持將來能夠模擬更多種類鴨子的特征，采用策略設計模式(Strategy)設計的類圖如圖10-12所示：



其中，Duck為抽象類，描述了抽象的鴨子，而類RubberDuck、MallardDuck、 CottonDuck 和 RedHeadDuck分別描述具體的鴨子種類，方法fly()、quack()和display()分別表示不同種類的鴨子都具有飛行特征、發(fā)聲特征和外觀特征；接口FlyBehavior與 QuackBehavior分別用于表示抽象的飛行行為與發(fā)聲行為；類FlyNoWay與FlyWithWings分別描述不能飛行的行為和用翅膀飛行的行為；類Quack、Squeak與QuackNoWay分別描述發(fā)出“嘎嘎”聲的行為、發(fā)出橡皮與空氣摩擦聲的行為與不發(fā)聲的行為。請?zhí)钛a以下代碼中的空缺。
【Java代碼】
(1)   FlyBehavior{
public void fly()；
}；
(2)  QuackBehavior{
public void quack()；
}；
class FlyWithWings implements FlyBehavior{
public void fly(){System.out.println(“使用翅膀飛行!”)；}
}；
class FlyNoWay implements FlyBehavior{
public void fly(){System.out.println(“不能飛行!”)；}
}；
class Quack implements QuackBehavior{
public void quack(){System.out.println(“發(fā)出\‘嘎嘎\’聲!”)； }
}；
class Squeak implements QuackBehavior{
public void quack(){System.out.println(“發(fā)出空氣與橡皮摩擦聲 !”)；
}
}；
class QuackNoWay implements QuackBehavior{
public void quack(){System.out.println(“不能發(fā)聲!”)；}
}；
abstract class Duck{
protected  FlyBehavior  (3)  ；
protected  QuackBehavior  (4)  ；
public void fly(){  (5)  ；  }
public void quack()  {  (6)  ；}；
public   (7)  void display()；
}；
class RubberDuck extends Duck{
public RubberDuck(){
flyBehavior＝new  (8)  ；
quackBehavior＝new  (9)  ；
}
public void display(){/*此處省略顯示橡皮鴨的代碼*/  }
}；
//其他代碼省略