试题二
阅读下列说明，回答问题1至问题3。
【说明】
某医院的门诊管理系统实现了为患者提供挂号、处方药品收费的功能。具体的需求及设计如下：
1．医院医师具有编号，姓名，科室，职称，出诊类型和出诊费用，其中出诊类型分为专家门诊和普通门诊，与医师职称无关；各个医师可以具有不同的出诊费用，与职称和出诊类型无关。
2．患者首先在门诊挂号处挂号，选择科室和医师，根据选择的医师缴纳挂号费(医师出诊费)。收银员为患者生成挂号单，如表10-1所示，其中，就诊类型为医师的出诊类型。
3．患者在医师处就诊后，凭借挂号单和医师手写处方到门诊药房交费买药。收银员根据就诊号和医师处方中开列的药品信息，查询药品库(如表10-2所示)并生成门诊处方单(如表10-3所示)。

4．由于药品价格会发生变化，因此，门诊管理系统必须记录处方单上药品的单价。
根据需求阶段收集的信息，设计的实体联系图和关系模式(不完整)如下所示：



2．关系模式
挂号单(就诊号，病患姓名，医师编号，时间，  4  )
收银员(编号，姓名，级别)
医师(编号，姓名，科室，职称，出诊类型，出诊费用)
门诊处方(  5  ，收银员，时间)
处方明细(就诊号，  6  )
药品库(药品编码，药品名称，  7  )
【问题1】
根据问题描述，填写图10-3实体联系图中(1)～(4)处联系的类型。
【问题2】
图10-3中还缺少几个联系?请指出每个联系两端的实体名，格式如下。
实体1：实体2
例如，收银员与门诊处方之间存在联系，表示为：
收银员：门诊处方    或    门诊处方：收银员
【问题3】
根据实体联系图10-3，填写挂号单、门诊处方、处方明细和药品库关系模式中的空 (5)～(8)处，并指出挂号单、门诊处方和处方明细关系模式的主键。

试题三
阅读下列说明和图，回答问题1至问题3。
【说明】
某图书管理系统的主要功能如下：
1．图书管理系统的资源目录中记录着所有可供读者借阅的资源，每项资源都有一个唯一的索引号。系统需登记每项资源的名称、出版时间和资源状态(可借阅或已借出)。
2．资源可以分为两类：图书和唱片。对于图书，系统还需登记作者和页数；对于唱片，还需登记演唱者和介质类型(CD或者磁带)。
3．读者信息保存在图书管理系统的读者信息数据库中，记录的信息包括：读者的识别码和读者姓名。系统为每个读者创建了一个借书记录文件，用来保存读者所借资源的相关信息。
现采用面向对象方法开发该图书管理系统。识别类是面向对象分析的第一步。比较常用的识别类的方法是寻找问题描述中的名词，再根据相关规则从这些名词中删除不可能成为类的名词，最终得到构成该系统的类。表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公里。为简化问题，假设所有房子在同一直线上，并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。

实现贪心算法的流程如图10-6所示，请填充其中空白并计算该算法的时间复杂度，其中：
1．d[i](1≤i≤N)表示第i个房子到公路A端的距离，N表示房子的总数，房子的编号按照房子到公路A端的距离从小到大进行编号。
2．s[k]表示第k(k≥1)个基站到公路A端的距离，算法结束后k的值为基站的总数。


该算法的时间复杂度为  (5)  。