试题二
阅读下列说明和图，回答问题1至问题4，将解答填入对应栏内。
【说明】
某宾馆拟开发一个宾馆客房预订子系统，主要是针对客房的预订和入住等情况进行管理。
【需求分析结果】
1．员工信息主要包括：员工号、姓名、出生年月、性别、部门、岗位、住址、联系电话和密码等信息。岗位有管理和服务两种。岗位为“管理”的员工可以更改(添加、删除和修改)员工表中本部门员工的岗位和密码，要求将每一次更改前的信息保留；岗位为“服务”的员工只能修改员工表中本人的密码，且负责多个客房的清理等工作。
2．部门信息主要包括：部门号、部门名称、部门负责人、电话等信息。一个员工只能属于一个部门，一个部门只有一位负责人。
3．客房信息包括：客房号、类型、价格、状态等信息。其中类型是指单人间、三人间、普通标准间、豪华标准间等；状态是指空闲、入住和维修。
4．客户信息包括：身份证号、姓名、性别、单位和联系电话。
5．客房预定情况包括：客房号、预定日期、预定入住日期、预定入住天数、身份证号等信息。一条预定信息必须且仅对应一位客户，但一位客户可以有多条预定信息。
【概念模型设计】
根据需求阶段收集的信息，设计的实体联系图(不完整)如下图所示。

【逻辑结构设计】
逻辑结构设计阶段设计的部分关系模式(不完整)如下：
员工(  4  ，姓名，出生年月，性别，岗位，住址，联系电话，密码)
权限(岗位，操作权限)
部门(部门号，部门名称，部门负责人，电话)
客房(  5  ，类型，价格，状态，入住日期，入住时间，员工号)
客户(  6  ，姓名，性别，单位，联系电话)
更改权限(员工号，  7  ，密码，更改日期，更改时间，管理员号)
预定情况(  8  ，预定日期，预定入住日期，预定入住天数)
【问题1】
根据问题描述，填写上图中(1)～(3)处联系的类型。联系类型分为一对一、一对多和多对多三种，分别使用1:1，1:n或1:*，m:n或*:*表示。
【问题2】
补充上图中的联系并指明其联系类型。
【问题3】
根据需求分析结果和上图，将逻辑结构设计阶段生成的关系模式中的空(4)～(8)补充完整。(注：一个空可能需要填多个属性)
【问题4】
若去掉权限表，并将权限表中的操作权限属性放在员工表中(仍保持管理和服务岗位的操作权限规定)，则与原有设计相比有什么优缺点(请从数据库设计的角度进行说明)。

试题三
阅读下列说明和图，回答问题1至问题4，将解答填入对应栏内。
【说明】
在线会议审稿系统(Online Reviewing System，ORS)主要处理会议前期的投稿和审稿事务，其功能描述如下：
1．用户在初始使用系统时，必须在系统中注册(register)成为作者或审稿人。
2．作者登录(login)后提交稿件和浏览稿件审阅结果。提交稿件必须在规定提交时间范围内，其过程为先输入标题和摘要、选择稿件所属主题类型、选择稿件所在位置 (存储位置)。上述几步若未完成，则重复；若完成，则上传稿件至数据库中，系统发送通知。
3．审稿人登录后可设置兴趣领域、审阅稿件给出意见以及罗列录用和(或)拒绝的稿件。
4．会议委员会主席是一个特殊审稿人，可以浏览提交的稿件、给审稿人分配稿件、罗列录用和(或)拒绝的稿件以及关闭审稿过程。其中，关闭审稿过程须包括罗列录用和(或)拒绝的稿件。
系统采用面向对象方法开发，使用UMi进行建模。在建模用例图时，常用的方式是先识别参与者，然后确定参与者如何使用系统来确定用例，每个用例可以构造一个活动图。参与者名称、用例和活动名称分别参见以下各表。参与者列表


【问题1】
根据[说明]中的描述，使用参与者列表的英文名称，给出ORS用例图中A1～A4所对应的参与者。
【问题2】
根据[说明]中的描述，使用用例名称列表中的英文名称，给出ORS用例图中U1一 U3所对应的用例。
【问题3】
根据[说明]中的描述，给出ORS用例图中  (1)  和  (2)  所对应的关系。
【问题4】
根据[说明]中的描述，使用用例名称列表和活动名称列表中的英文名称，给出提交稿件过程的活动图中Actionl～Action4对应的活动。

试题四
阅读下列说明，回答问题1至问题3，将解答填入对应栏内。
【说明】
某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1，m2，…，mn，每项食物mi的营养价值为vi，价格为pi其中i＝1，2，…，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。
【问题1】
下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。
伪代码中的主要变量说明如下。
n：总的食物项数；
v：营养价值数组，下标从1到n，对应第1到第n项食物的营养价值；
p：价格数组，下标从1到n，对应第1到第n项食物的价格；
M：总价格标准，即套餐的价格不超过M；
x：解向量(数组)，下标从1到n，其元素值为0或1，其中元素值为0表示对应的食物不出现在套餐中，元素值为1表示对应的食物出现在套餐中；
nv：n+1行M+1列的二维数组，其中行和列的下标均从0开始，nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。
伪代码如下：
MaxNutrientValue(n，v，p，M，x)
1  for i＝0  to n
2  nv[i][0] ＝ 0
3  for j＝1 to M
4  nv[0][j]＝0
5  for i＝1 to n
6  for j＝1 to M
7  if j＜p[i]  //若食物mi不能加入到套餐中
8  nv[i][j] ＝  nv[i-1][j]
9  else if   (1)
10  nv[i][j]＝  nv[i-1][j]
11  else
12  nv[i][j]＝  nv[i-1][j-p[i]]  +  v[i]
13  j ＝ M
14  for i＝n downto 1
15  if   (2)
16  x[i] ＝ 0
17  else
18  x[i] ＝ 1
19    (3)
20  return x and nv[n][M]
【问题2】
现有5项食物，每项食物的营养价值和价格如下表所示。

食物营养价值及价格表
若要求总价格不超过100的营养价值最大的套餐，则套餐应包含的食物有  (4)  (用食物项的编码表示)，对应的最大营养价值为  (5)  。
【问题3】
问题1中伪代码的时间复杂度为  (6)  (用O符号表示)。