现要求实现一个能够自动生成求职简历的程序，简历的基本内容包括求职者的姓名、性别、年龄及工作经历。希望每份简历中的工作经历有所不同，并尽量减少程序中的重复代码。
现采用原型模式（Prototype）来实现上述要求，得到如图6-1所示的类图。

  
图6-1  类图

【Java代码】
public  class  WorkExperience   (1)   Cloneable{   //工作经历
private  String  workDate;
private  String  company;
public  Object  clone(){
      (2)  ;
      Obj.workDate= this.workDate;
      Obj.company = this.company;
       return Obj;
}
  //其余代码省略
}

public  class  Resume    (3)    Cloneable{      //简历
private  String  name;
private  String  sex;
private  String  age;
private  WorkExperience  work;

public  Resume(string name){
        this.name = name;
        work = new WorkExperience();
}
private  Resume(WorkExperience  work){
      this.work =   (4)   ;
}
public  void  SetPersonInfo(string sex,string age){/*实现省略*/}
public  void  SetWorkExperience(string workDate,string company){/*实现省略*/}
public  Object  clone(){
     Resume Obj =    (5)   ;
     return Obj;
}
}

Class WorkResume{
public  static  void  main(){
      Resume   a  = new Resume(“张三”);
      a.SetPersonInfo(“男”,“29”)；
      a.SetWorkExperience(“1998-2000”,“XXX公司”);
      Resume  b =    (6)   ;
      b. SetWorkExperience(“2001-2006”,“YYY公司”);
}
}

现要求实现一个能够自动生成求职简历的程序，简历的基本内容包括求职者的姓名、性别、年龄及工作经历。希望每份简历中的工作经历有所不同，并尽量减少程序中的重复代码。
现采用原型模式（Prototype）来实现上述要求，得到如图5-1所示的类图。

图5-1  类图

【C++代码】
#include
using namespace std;
class  Cloneable{
public:
       (1)  ;
};
class  workExperience:public  Cloneable{   //工作经历
private:
      string  workData;
      string  company;
public:
     Cloneable * clone(){
      (2)  ;
     Obj->workDate= this->workDate;
     Obj->company = this->company;
     return Obj;
}
 //其余代码省略
};

class  Resume:public  Cloneable{      //简历
private:
        string name;
        string sex;
        string age;
        WorkExperience * work;
        Resume(WorkExperience * work){
        this->work =    (3)  ;
        }
public:
        Resume(string name){/*实现省略*/}
        void SetPersonInfo(string sex,string age){/*实现省略*/}
        void SetWorkExperience(string workDate,string company){/*实现省略*/}
        Cloneable * Clone(){
         (4)   ;
        Obj->name = this->name;
       Obj->sex = this->sex;
       Obj->age = this->age;
       return Obj;
}
};

int  main(){
        Resume * a  = new Resume(“张三”);
        a->SetPersonInfo(“男”,“29”)；
        a-> SetWorkExperience(“1998-2000”,“XXX公司”);
        Resume * b =    (5)   ;
        b-> SetWorkExperience(“2001-2006”,“YYY公司”);
        return 0;
}

设有m台完全相同的机器运行n个独立的任务，运行任务i所需的时间为ti，要求确定一个调度方案，使得完成所有任务所需要的时间最短。
假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略，按顺序先把每个任务分配到一台机器上，然后将剩余的任务依次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
1.常量和变量说明
m：机器数
n：任务数
t[]：输入数组，长度为n，下标从0开始，其中每个元素表示任务的运行时间，下标从0开始。
s[][]：二维数组，长度为m*n，下标从0开始，其中元素s[i][j]表示机器i运行的任务j的编号。
d[]：数组，长度为m其中元素d[i]表示机器i的运行时间，下标从0开始。
count[]：数组，长度为m，下标从0开始，其中元素count[i]表示机器i运行的任务数。
i：循环变量。
j：循环变量。
k：临时变量。
max：完成所有任务的时间。
min：临时变量。

2.函数schedule
void  schedule(){
int i,j,k,max=0;
 for( i=0;i       d[i]=0;
      for(j=0;j          s[i][j]=0;
      }
  }
  for(i=0;i      s[i][0]=i;
      (1)     ;
      count[i]=1;
   }
   for(  (2)  ;i      int min = d[0];
     k=0;
     for(j=1;j         if(min>d[j]){
          min = d[j];
           k=j;                    //机器k空闲
      }
    }
   (3)   ;
   count[k] = count[k]+1;
   d[k] = d[k]+t[i];
}

   for(i =0;i       if(  (4)  ){
         max=d[i];
      }
   }
}

【问题1】（8分）
根据说明和C代码，填充C代码中的空（1）~（4）。
【问题2】（2分）
根据说明和C代码，该问题采用了 （5）   算法设计策略，时间复杂度   （6）  （用O符号表示）
【问题3】（5分）
考虑实例m=3（编号0~2），n=7（编号0~6），各任务的运行时间为{16，14，6，5，4，3，2}。则在机器0、1和2上运行的任务分别为（7）、（8）和（9）（给出任务编号）。从任务开始运行到完成所需的时间为（10）。

    表3-1 类列表

 

    

    

【问题1】（5分）
    根据说明中的描述，给出图3-1中A1和A2处所对应的参与者，UC1和UC2所对应的用例以及（1）处的关系。
【问题2】（7分）
    根据说明中的描述，给出图3-2中C1~C5所对应的类名（表3-1中给出的类名）和（2）~（5）处所对应的多重度。
【问题3】（3分）
    认定类是面向对象分析中非常关键的一个步骤。一般首先从问题域中得到候选类集合，在根据相应的原则从该集合中删除不作为类的，剩余的就是从问题域中认定出来的类。简要说明选择候选类的原则，以及对候选类集合进行删除的原则。

【逻辑结构设计】
    根据概念模式设计阶段完成的实体联系图，得出如下关系模型（不完整）：
    演播厅（房间号，房间面积）
    栏目（栏目名称，播出时间，时长）
    广告（广告编号，销售价格，  （1）  ）
    员工（工号，姓名，性别，出生日期，电话，住址）
    主持人（主持人工号，  （2）  ）
    插播单（  （3）  ，播出时间）
    调度单（  （4）  ）

【问题1】（7分）
    补充图2-1中的联系和联系类型。
【问题2】（5分）
    根据图2-1，将逻辑结构设计阶段生产的关系模型的空(1)~(4)补充完整，并用下划线指出（1）~（4）所在关系模型的主键。
【问题3】（3分）
    现需要记录广告商信息，增加广告商实体。一个广告商可以提供多条广告，一条广告只由一个广告商提供。请根据该要求，对图2-1进行修改，画出修改后的实体间联系和联系的类型。

【问题1】（4分）
    使用说明中的词语，给出图1-1中的实体E1~E4的名称。
【问题2】（7分）
    在建模DFD时，需要对有些复杂加工（处理）进行进一步精化，图1-2为图1-1中处理3的进一步细化的1层数据流图，图1-3为图1-2中3.1进一步细化的2层数据流图。补全1-2中加工P1、P2和P3的名称和图1-2与图1-3中缺少的数据流。
【问题3】（4分）
    使用说明中的词语，给出图1-3中的数据存储D1~D4的名称。

阅读下列说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 
【说明】 
　　已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如图 7-1 所示。该遥控器共有 4 个按钮，编号分别是 0 至 3，按钮 0和 2 能够遥控打开电器 1 和电器 2，按钮 1 和 3 则能遥控关闭电器 1 和电器 2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。 现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如7-2所示。   

　　图7-2中， 类RomoteController的方法onPressButton(int button)表示当遥控器按键按下时调用的方法，参数为按键的编号；Command 接口中 on 和 off 方法分别用于控制电器的开与关；Light中turnLight(int degree)方法用于调整电灯灯光的强弱，参数degree值为0时表示关灯， 值为100时表示开灯并且将灯光亮度调整到最大； TV 中setChannel(int channel)方法表示设置电视播放的频道，参数 channel 值为 0 时表示关闭电视，为 1 时表示开机并将频道切换为第1频道。 

【Java 代码】  

阅读下列说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 
【说明】 
　　已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如图 6-1 所示。该遥控器共有 4 个按钮，编号分别是 0 至 3，按钮 0和 2 能够遥控打开电器 1 和电器 2，按钮 1 和 3 则能遥控关闭电器 1 和电器 2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。 现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如6-2所示。   

　　图6-2中， 类RomoteController的方法onPressButton(int button)表示当遥控器按键按下时调用的方法，参数为按键的编号；Command 接口中 on 和 off 方法分别用于控制电器的开与关；Light中turnLight(int degree)方法用于调整电灯灯光的强弱，参数degree值为0时表示关灯， 值为100时表示开灯并且将灯光亮度调整到最大；TV 中setChannel(int channel)方法表示设置电视播放的频道，参数 channel 值为 0 时表示关闭电视，为 1 时表示开机并将频道切换为第1频道。 

【C++代码】 

　　本题中，应用命令模式能够有效让类 （5） 和类 （6） 、类 （7） 之间的耦合性降至最小。

阅读下列说明和C代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 
【说明】 
　　栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(Stack Top)，而另一端称为栈底(Stack Bottom)。栈的基本操作包：
　　创建栈(NewStack)、  判断栈是否为空(IsEmpty)、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。 
　　当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储（如图5-1）。  

以下C 代码采用链式存储结构实现一个整数栈操作。 

【C代码】 
　　 
　　以上程序运行时的输出结果为： （5）   

阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。 
【说明】
　　快速排序是一种典型的分治算法。 采用快速排序对数组A[p..r]排序的三个步骤如下： 
　　分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组（可能为空） A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。 
　　递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。 
　　合并：快速排序在原地排序，故不需合并操作。 

【问题1】（6 分）  
　　下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下：   
　　A：待排序数组 
　　p， r：数组元素下标，从p到r 
　　q：划分的位置 
　　x：枢轴元素 
　　i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值 
　　j：循环控制变量，表示数组元素下标 

 
【问题2】（5分）  
　　（1）假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O记号。最佳情况为 （4） ，平均情况为 （5） ，最坏情况为 （6） 。 
　　（2）假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况？ （7） 。(最佳、平均、最坏) 
 【问题3】（4分）  
　　（1）待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码—利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i，j)表示随机取i到j之间的一个数，包括i和j。

　　（2） 随机化快速排序是否能够消除最坏情况的发生？ （10） 。（是或否）