試題二
閱讀下列說明，回答問題1至問題3。
【說明】
某醫(yī)院的門診管理系統(tǒng)實現(xiàn)了為患者提供掛號、處方藥品收費的功能。具體的需求及設計如下：
1．醫(yī)院醫(yī)師具有編號，姓名，科室，職稱，出診類型和出診費用，其中出診類型分為專家門診和普通門診，與醫(yī)師職稱無關(guān)；各個醫(yī)師可以具有不同的出診費用，與職稱和出診類型無關(guān)。
2．患者首先在門診掛號處掛號，選擇科室和醫(yī)師，根據(jù)選擇的醫(yī)師繳納掛號費(醫(yī)師出診費)。收銀員為患者生成掛號單，如表10-1所示，其中，就診類型為醫(yī)師的出診類型。
3．患者在醫(yī)師處就診后，憑借掛號單和醫(yī)師手寫處方到門診藥房交費買藥。收銀員根據(jù)就診號和醫(yī)師處方中開列的藥品信息，查詢藥品庫(如表10-2所示)并生成門診處方單(如表10-3所示)。

4．由于藥品價格會發(fā)生變化，因此，門診管理系統(tǒng)必須記錄處方單上藥品的單價。
根據(jù)需求階段收集的信息，設計的實體聯(lián)系圖和關(guān)系模式(不完整)如下所示：



2．關(guān)系模式
掛號單(就診號，病患姓名，醫(yī)師編號，時間，  4  )
收銀員(編號，姓名，級別)
醫(yī)師(編號，姓名，科室，職稱，出診類型，出診費用)
門診處方(  5  ，收銀員，時間)
處方明細(就診號，  6  )
藥品庫(藥品編碼，藥品名稱，  7  )
【問題1】
根據(jù)問題描述，填寫圖10-3實體聯(lián)系圖中(1)～(4)處聯(lián)系的類型。
【問題2】
圖10-3中還缺少幾個聯(lián)系?請指出每個聯(lián)系兩端的實體名，格式如下。
實體1：實體2
例如，收銀員與門診處方之間存在聯(lián)系，表示為：
收銀員：門診處方    或    門診處方：收銀員
【問題3】
根據(jù)實體聯(lián)系圖10-3，填寫掛號單、門診處方、處方明細和藥品庫關(guān)系模式中的空 (5)～(8)處，并指出掛號單、門診處方和處方明細關(guān)系模式的主鍵。

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

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

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



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

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

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


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