阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
    用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为a_i和b_i。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间（所有作业被处理的时间之和）最少。
算法步骤：
    （1）确定候选解上界为最短的单台处理机处理所有作业的完成时间m，

   

  int n， m;
  int a[60]， b[60]， p[100][100][60];
  void read(){ /*输入n、a、b，求出m，代码略*/}
  void schedule(){ /*求解过程*/
      int x，y，k;
  for（x=0；x<=m；x++）{
    for(y=0；y       （1）
        for（k=1；k           p[x][y][k]=0；
    }
  }
  for（k=1；k<=n；k++）{
    for（x=0；x<=m；x++）{
      for（y=0；y<=m；y++）{
         if（x - a[k-1]>=0）    （2）    ；
         if（ （3） ）p[x][y][k]=(p[x][y][k] ||p[x][y-b[k-1]][k-1]);
        }
      }
    }
  }
  void write(){    /*确定最优解并输出*/
  int x，y，temp，max=m;
      for（x=0；x<=m；x++）{
       for（y=0;y<=m;y++）{
        if(  （4）  ）{
          temp=（5） ；
          if（temp< max）max = temp;
        }
      }
    }
    printf(“\n%d\n”，max），
  }
  void main(){   read();    schedule();    write();   }

【问题1】 （9分）
根据以上说明和C代码，填充C代码中的空（1）～（5）。
【问题2】（2分）
根据以上C代码，算法的时间复杂度为（6）（用O符号表示）。
【问题3】（4分）
考虑6个作业的实例，各个作业在两台处理机上的处理时间如表4-1所示。该实例的最优解为（7），最优解的值（即最短处理时间）为（8）。最优解用（x1，x2，x3，x4，x5，x6）表示，其中若第i个作业在A上处理，则xi=1，否则xi=2。如（1，1，1，1，2，2）表示作业1，2，3和4在A上处理，作业5和6在B上处理。

表4-1

阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】   
某网上购物平台的主要功能如下：   
（1）创建订单。顾客（ Customer）在线创建订单（Order），主要操作是向订单中添加项目、从订单中删除项目。订单中应列出所订购的商品（Product）及其数量（quantities）。
（2）提交订单。订单通过网络来提交。在提交订单时，顾客需要提供其姓名（name）、收货地址（address）、以及付款方式（form of payment）（预付卡、信用卡或者现金）。为了制定送货计划以及安排送货车辆，系统必须确定订单量（volume）。除此之外，还必须记录每种商品的名称（Name）、造价（cost price）、售价（sale price）以及单件商品的包装体积（cubic volume）。
（3）处理订单。订单处理人员接收来自系统的订单；根据订单内容，安排配货，制定送货计划。在送货计划中不仅要指明发货日期（delivery date），还要记录每个订单的限时发送要求（Delivery Time Window）。
（4）派单。订单处理人员将己配好货的订单转交给派送人员。
（5）送货／收货。派送人员将货物送到顾客指定的收货地址。当顾客收货时，需要在运货单（delivery slip）上签收。签收后的运货单最终需交还给订单处理人员。
（6）收货确认。当订单处理人员收到签收过的运货单后，会和顾客进行一次再确认。
现采用面向对象方法开发上述系统，得到如图3-1所示的用例图和图3-2所示的类图。

图3-1 用例图

                                                               图3-2 类图
 

【问题1】（5分）
根据说明中的描述，给出图3-1中A1～A3所对应的参与者名称和U1～U2处所对应的用例名称。
【问题2】（7分）
根据说明中的描述，给出图3-2中C1～C3所对应的类名以及（1）～（4）处所对应的多重度（类名使用说明中给出的英文词汇）。
【问题3】（3分）
根据说明中的描述，将类C2和C3的属性补充完整（属性名使用说明中给出的英文词汇）。
 

阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】
某医院拟开发一套住院病人信息管理系统，以方便对住院病人、医生、护士和手术等信息进行管理。
【需求分析】   
（1）系统登记每个病人的住院信息，包括：病案号、病人的姓名、性别、地址、身份证号、电话号码、入院时问及病床等信息，每个病床有唯一所属的病区及病房，如表2-1所示。其中病案号唯一标识病人本次住院的信息。

表2-1 住院登记表

（2）在一个病人的一次住院期间，由一名医生对该病人的病情进行诊断，并填写一份诊断书，如表2-2所示。对于需要进行一次或多次手术的病人，系统记录手术名称、手术室、手术日期、手术时间、主刀医生及多名协助医生，每名医生在手术中的责任不同，如表2-3所示，其中手术室包含手术室号、楼层、地点和类型等信息。

表2-2 诊断书

（3）护士分为两类：病床护士和手术室护士。每个病床护士负责护理一个病区内的所有病人，每个病区由多名护士负责护理。手术室护士负责手术室的护理工作。每个手术室护士负责多个手术室，每个手术室由多名护士负责，每个护士在手术室中有不同的责任，并由系统记录其责任。   

表2-3 手术安排表

【概念模型设计】
 根据需求阶段收集的信息，设计的实体联系图（不完整）如图2-1所示。

图2-1   实体联系图

【逻辑结构设计】
根据概念模型设计阶段完成的实体联系图，得出如下关系模式（不完整）：
    病床（病床号，病房，病房类型，所属病区）
    护士（护士编号，姓名，类型，性别，级别）
    病床护士（    （1）    ）
    手术室（手术室号，楼层，地点，类型）
    手术室护士（    （2）    ）
    病人（   （3），姓名，性别，地址，身份证号，电话号码，入院时间）
    医生（医生编号，姓名，性别，职称，所属科室）
    诊断书（  （4），诊断，诊断时间）
    手术安排（病案号，手术室号，手术时间，手术名称）
    手术医生安排（  （5） ，医生责任）

【问题1】（6分）
补充图2-1中的联系和联系的类型。
【问题2】（5分）
根据图2-1，将逻辑结构设计阶段生成的关系模式中的空（1）～（5）补充完整，并用下划线指出主键。
【问题3】（4分）
如果系统还需要记录医生给病人的用药情况，即记录医生给病人所开处方中药品的名称、用量、价格、药品的生产厂家等信息。请根据该要求，对图2-1进行修改，画出补充后的实体、实体间联系和联系的类型。

阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。
【说明】   
某学校开发图书管理系统，以记录图书馆藏图书及其借出和归还情况，提供给借阅者借阅图书功能，提供给图书馆管理员管理和定期更新图书表功能。主要功能的具体描述如下：
（1）处理借阅。借阅者要借阅图书时，系统必须对其身份（借阅者ID）进行检查。通过与教务处维护的学生数据库、人事处维护的职工数据库中的数据进行比对，以验证借阅者ID是否合法，若合法，则检查借阅者在逾期未还图书表中是否有逾期未还图书，以及罚金表中的罚金是否超过限额。如果没有逾期未还图书并且罚金未超过限额，则允许借阅图书，更新图书表，并将借阅的图书存入借出图书表，借阅者归还所借图书时，先由图书馆管理员检查图书是否缺失或损坏，若是，则对借阅者处以相应罚金并存入罚金表；然后，检查所还图书是否逾期，若是，执行“处理逾期”操作；最后，更新图书表，删除借出图书表中的相应记录。 
（2）维护图书。图书馆管理员查询图书信息；在新进图书时录入图书信息，存入图书表；在图书丢失或损坏严重时，从图书表中删除该图书记录。
（3）处理逾期。系统在每周一统计逾期未还图书，逾期未还的图书按规则计算罚金，
并记入罚金表，并给有逾期未还图书的借阅者发送提醒消息。借阅者在借阅和归还图书时，
若罚金超过限额，管理员收取罚金，并更新罚金表中的罚金额度。
现采用结构化方法对该图书管理系统进行分析与设计，获得如图1-1所示的顶层数据
流图和图1-2所示的0层数据流图。

图1-2  0层数据流图

【问题1】
使用说明中的词语，给出图1-1中的实体E1-E4的名称。
【问题2】
使用说明中的词语，给出图1-2中的数据存储D1～D4的名称。
【问题3】 
在DFD建模时，需要对有些复杂加工（处理）进行进一步精化，绘制下层数据流图。针对图1-2中的加工“处理借阅”，在1层数据流图中应分解为哪些加工？（使用说明中的术语）
【问题4】
说明【问题3】中绘制1层数据流图时要注意的问题。
 

阅读下列说明和Java代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
现欲开发一个软件系统，要求能够同时支持多种不同的数据库，为此采用抽象工厂模式设计该系统。以SQL Server和Access两种数据库以及系统中的数据库表Department为例，其类图如图6-1所示。

图6-1 类图

【Java代码】
import javA．util.*;
class Department{/*代码省略*/}
 
interface IDepartment{
    (1)    ；
    (2)    ；
}
 
class SqlserverDepartment (3) {
    public void  Insert(Department department){
       System.out.println(”Insert a record into Department in SQL Server!");
       ∥其余代码省略
    }
    public Department GetDepartment(int id){
  /*代码省略*/
    }
}
 
classAccessDepartment(4) {
    public void Insert(Department department){
   System.out.println("Insert a record into Department in ACCESS!”);
   ∥其余代码省略
    }
    public Department GetDepartment(int id){
       /*代码省略*/
    }
}
(5)  {
    (6)   ；
}
 
class SqlServerFactory implements IFactory{
    public IDepartment CreateDepartment(){
  retum new SqlserverDepartment();
    }
    ∥其余代码省略
}
class AccessFactory implements IFactory{
    public IDepartment CreateDepartment(){
  return new AccessDepartment();
    }
    ∥其余代码省略
}

阅读下列说明和C++代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
现欲开发一个软件系统，要求能够同时支持多种不同的数据库，为此采用抽象工厂模式设计该系统。以SQL Server和Access两种数据库以及系统中的数据库表Department为例，其类图如图5-1所示。

图5-1 类图

【C++代码】
#include
using namespace std;
 
class Department{/*代码省略*/}；
class IDepartment{
public:
    (1)    =0；
    (2)    =0；
}；
 
class SqlserverDepartment:(3){
public:
  void Insert(Department* department){
   cout <<"Insert a record into Department in SQL Server!\n";
∥其余代码省略
    }
    Department GetDepartment(int id){
   /*代码省略*/
    }
}；
 
class AccessDepartment: (4) {
public:
    void Insert(Department* department){
   cout <<"Insert a record into Department in ACCESS!\n"；
       ∥其余代码省略
    }
    Department GetDepartment(int id){
   /*代码省略*/
    }
}；
   
(5){
public:
    (6)=0；
}；
class SqlServerFactory:public IFactory{
public:
    IDepartment*CreateDepartment(){  return new SqlserverDepartment();  }
    ∥其余代码省略
}；
 
class AccessFactory:public IFactory{
public:
    IDepartment* CreateDepartment(){  return new AccessDepartment();}
    ∥其余代码省略
}；

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
设有n个货物要装入若干个容量为C的集装箱以便运输，这n个货物的体积分别为{S1，S2，．．．，Sn}，且有si≤C(1≤i≤ n)。为节省运输成本，用尽可能少的集装箱来装运这n个货物。
下面分别采用最先适宜策略和最优适宜策略来求解该问题。
最先适宜策略( firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。
最优适宜策略( bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容量最小的集装箱，使得该箱子装入货物后闲置空间最小。
【C代码】
下面是这两个算法的C语言核心代码。
(1)变量说明
    n：货物数
    C：集装箱容量
    s：数组，长度为n，其中每个元素表示货物的体积，下标从0开始
    b：数组，长度为n，b[i]表示第i+1个集装箱当前已经装入货物的体积，下标从0开始
    i，j：循环变量
    k：所需的集装箱数
    min:当前所用的各集装箱装入了第i个货物后的最小剩余容量
    m:当前所需要的集装箱数
    temp：临时变量
(2)函数firstfit
int firstfit(){
    inti，j；
    k=0：
    for(i=0；i   b[i]=0；
    }
    for（i=0；i       (1)；
      while(C-b[j]     j++;
      }
      (2)；
k=k>(j+1)?k：(j+1)；
  }
  return k；
}
(3)函数bestfit
int bestfit() {
  int i，j，min，m，temp;
  k=0；
  for（i=0；i     b[i]=0；
  }
  for (i=0；i     min=C；
    m=k+1；
    for(j=0;j< k+1；j++){
  temp=C- b[j] - s[i];
  if(temp>0&&temp< min){
    (3)    ；
    m=j ;
  }
    }
    (4)；
    k=k>(m+1)?k:(m+1)；
  }
  return k；
}

【问题1】（8分）
根据【说明】和【C代码】，填充C代码中的空(1)～(4)。
【问题2】（4分）
 根据【说明】和【C代码】，该问题在最先适宜和最优适宜策略下分别采用了(5) 和(6)算法设计策略，时间复杂度分别为 (7) 和 (8)（用O符号表示）。
【问题3】（3分）
考虑实例n= 10，C= 10，各个货物的体积为{4，2，7，3，5，4，2，3，6，2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为(9)和(10)。考虑一般的情况，这两种求解策略能否确保得到最优解？(11)  （能或否）

阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】
某城市的各国家公园周边建造了许多供游客租用的小木屋和营地，为此，该城市设置了一个中心售票处和若干个区域售票处。游客若想租用小木屋或营地，必须前往中心售票处进行预定并用现金支付全额费用。所有的预定操作全部由售票处的工作人员手工完成。现欲开发一信息系统，实现小木屋和营地的预定及管理功能，以取代手工操作。该系统的
主要功能描述如下：
1．管理预定申请。游客可以前往任何一个售票处提出预定申请。系统对来自各个售票处的预定申请进行统一管理。
2．预定。预定操作包含登记游客预定信息、计算租赁费用、付费等步骤。
3．支付管理。游客付费时可以选择现金和信用卡付款两种方式。使用信用卡支付可以享受3%的折扣，现金支付没有折扣。
4．游客取消预定。预定成功之后，游客可以在任何时间取消预定，但需支付赔偿金，剩余部分则退还给游客。赔偿金的计算规则是，在预定入住时间之前的48小时内取消，支付租赁费用10%的赔偿金；在预定入住时间之后取消，则支付租赁费用50%的赔偿金。
5．自动取消预定。如果遇到恶劣天气（如暴雨、山洪等），系统会自动取消所有的预定，发布取消预定消息，全额退款。
6．信息查询。售票处工作人员查询小木屋和营地的预定情况和使用情况，以判断是否能够批准游客的预定申请。
现采用面向对象方法开发上述系统，得到如表3-1所示的用例列表和表3-2所示的类列表。对应的用例图和类图分别如图3-1和3-2所示。

 表3-1

 

表3-2 类列表

图3-1  用例图

【问题1】（6分）
    根据说明中的描述与表3-1，给出图3-1中UC1～UC6处所对应的用例名称。
【问题2】 (7分)
    根据说明中的描述与表3-2，给出图3-2中C1～C7处所对应的类名。
【问题3】（2分）
对于某些需求量非常大的小木屋或营地，说明中功能4的赔偿金计算规则，不足以弥补取消预定所带来的损失。如果要根据预定的时段以及所预定场地的需求量，设计不同层次的赔偿金计算规则，需要对图3-2进行怎样的修改？（请用文字说明）

阅读下列说明和图，回答问题1至问题3。
【说明】
某会议策划公司为了方便客户，便于开展和管理各项业务活动，需要构建一个基于网络的会议预定系统。
【需求分析】
1．会议策划公司设有受理部、策划部和其他部门。部门信息包括部门号、部门名称、部门主管、电话和邮箱号。每个部门有多名员工处理部门的日常事务，每名员工只能在一个部门工作。每个部门有一名主管负责管理本部门的事务和人员。
2．员工信息包括员工号、姓名、部门号、职位、联系方式和工资；其中，职位包括主管、业务员、策划员等。业务员负责受理会议申请。若申请符合公司规定，则置受理标志并填写业务员的员工号。策划部主管为已受理的会议申请制定策划任务，包括策划内容、参与人数、要求完成时间等。一个已受理的会议申请对应一个策划任务，一个策划任务只对应一个已受理的会议申请，但—个策划任务可由多名策划员参与执行，且一名策划员可以参与多项策划任务。
3．客户信息包括客户号、单位名称、通信地址、所属省份、联系人、联系电话、银行账号。其中，一个客户号唯一标识一个客户。一个客户可以提交多个会议申请，但一个会议申请对应唯一的一个客户号。
4．会议申请信息包括申请号、开会日期、会议地点、持续天数、会议人数、预算费用、会议类型、酒店要求、会议室要求、客房类型、客房数、联系人、联系方式、受理标志和业务员的员工号等。客房类型有豪华套房、普通套房、标准间、三人间等，且申请号和客房类型决定客房数。
【概念模型设计】
根据需求阶段收集的信息，设计的实体联系图和关系模式（不完整）如下：

【关系模式设计】
 部门（部门号，部门名称，主管，电话，邮箱号）
 员工（员工号，姓名， （a） ，联系方式，工资）
 客户（客户号，单位名称，通信地址，所属省份，联系人，联系电话，银行账号）
 会议申请（ （b） ，开会日期，会议地点，持续天数，会议人数，预算费用，会议类型，酒店要求，会议室要求，客房数，联系人，联系方式，受理标志，员工号）
 策划任务（ （c） ，策划内容，参与人数，要求完成时间）
 执行策划（ （d） ，实际完成时间）
 

 【问题1】（5分）
   根据问题描述，补充五个联系、联系的类型，完善图2-1的实体联系图。
 【问题2】（7分）
   根据实体联系图，将关系模式中的空（a）～（d）补充完整（1个空缺处可能有多个数据项）。对会议申请、策划任务和执行策划关系模式，用下划线和#分别指出各关系模式的主键和外键。
 【问题3】（3分）
  请说明关系模式“会议申请”存在的问题及解决方案。

 

阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。
【说明】
某电子商务系统采用以数据库为中心的集成方式改进购物车的功能，详细需求如下：
（1）加入购物车。顾客浏览商品，点击加入购物车，根据商品标识从商品表中读取商品信息，并更新购物车表。
（2）浏览购物车。顾客提交浏览购物车请求后，显示出购物车表中的商品信息。
（3）提交订单。顾客点击提交订单请求，后台计算购物车表中商品的总价（包括运费）加入订单表，将购物车表中的商品状态改为待付款，显示订单详情。若商家改变价格，则刷新后可看到更改后的价格。
（4）改变价格。商家查看订购自家商品的订单信息，根据特殊优惠条件修改价格，更新订单表中的商品价格。
（5）付款。顾客点击付款后，系统先根据顾客表中关联的支付账户，将转账请求（验证码、价格等）提交给支付系统（如信用卡系统）进行转账；然后根据转账结果返回支付状态并更改购物车表中商品的状态。
（6）物流跟踪。商家发货后，需按订单标识添加物流标识（物流公司、运单号）；然后可根据顾客或商家的标识以及订单标识，查询订单表中的物流标识，并从相应物流系统查询物流信息。
（7）生成报表。根据管理员和商家设置的报表选项，从订单表、商品表以及商品分类表中读取数据，调用第三方服务Crystal Reports生成相关报表。
（8）维护信息。管理员维护（增、删、改、查）顾客表、商品分类表和商品表中的信息。
现采用结构化方法实现上述需求，在系统分析阶段得到如图1-1所示的顶层数据流图和图1-2所示的0层数据流图。
 
   图1-1 顶层数据流图

【问题1】 (4分)
 使用说明中的词语，给出图1-1中的实体E1～E4的名称。
【问题2】 (4分)
使用说明中的词语，给出图1-2中的数据存储D1～D4的名称。
【问题】 (4分)
 图1-2中缺失了数据流，请用说明或图1-2中的词语，给出其起点和终点。
【问题4】（3分）
根据说明，给出数据流“转账请求”、“顾客订单物流查询请求”和“商家订单物流查询请求”的各组成数据项。