阅读下列说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
　　现欲构造一文件／目录树，采用组合（Composite）设计模式来设计，得到的类图如5-1所示：

                                                           图5-1类图

【C++代码】
#include
#include
#include
using namespace std;
 
class AbstractFile{
protected:
   string name;   //文件或目录名称
public：
   void printName(){cout<    virtual void addChild(AbstractFile*file)=0  ；  //给一个目录增加子目录或文件
   virtual void removeChild(AbstractFile*file)=0  ；  //删除一个目录的子目录或文件
   virtual list< AbstractFile *> *getChildren()=0  ； //获得一个目录的子目录或文件
}；
class File:public AbstracFile{
public:
  File(string name){   (1)   =name;}
  void addChild(AbstractFile*file) { return; }
  void removeChild(AbstractFile*file) { return; }
   (2)   getChildren(){ return   (3)    ;}
};
classFolder :public AbstractFile{
private:
  list< AbstractFile *>childList;   //存储子目录或文件
public：
  Folder(string name){   (4)   name;}
  void addChild(AbstractFile*file) {childList.push_back(file); }
  void removeChild(AbstractFile*file) { childList.remove(file); }
  list< AbstractFile *>*getChildren(){return   (5)   ; }
};
void main(){
 //构造一个树形的文件/目录结构
 AbstractFile*rootFolder=new Folder(“c:\\”);
 AbstractFile*compositeFolder=new Folder(“composite”);
 AbstractFile*windowsFolder=new Folder(“windows”);
AbstractFile*file= new File(“TestComposite.java”);
rootFolder->addChild(compositeFolder);
rootFolder->addChild(windowsFolder);
compositeFolder->addChild(file);
}

 
                                                        图5-1类图

【C++代码】
#include
#include
#include
using namespace std;
 
class AbstractFile{
protected:
   string name;   //文件或目录名称
public：
   void printName(){cout<    virtual void addChild(AbstractFile*file)=0 ;   //给一个目录增加子目录或文件
   virtual void removeChild(AbstractFile*file)=0   ; //删除一个目录的子目录或文件
   virtual list< AbstractFile > *getChildren()=0  ; //获得一个目录的子目录或文件
}；
class File:public AbstractFile{
public:
  File(string name){   (1)   =name;}
  void addChild(AbstractFile*file) { return; }
  void removeChild(AbstractFile*file) { return; }
   (2)   getChildren(){ return   (3)    ;}
};
classFolder :public AbstractFile{
private:
  list< AbstractFile *>childList;   //存储子目录或文件
public：
  Folder(string name){   (4)   name;}
  void addChild(AbstractFile*file) {childList.push_back(file); }
  void removeChild(AbstractFile*file) { childList.remove(file); }
  list< AbstractFile *>*getChildren(){return   (5)   ; }
};
void main(){
 //构造一个树形的文件/目录结构
 AbstractFile*rootFolder=new Folder(“c:\\”);
 AbstractFile*compositeFolder=new Folder(“composite”);
 AbstractFile*windowsFolder=new Folder(“windows”);
AbstractFile*file= new file(“TestComposite.java”);
rootFolder->addChild(compositeFolder);
rootFolder->addChild(windowsFolder);
compositeFolder->addChild(file);
}

阅读下列说明，回答问题1至问题2，将解答填入答题纸的对应栏内。
【说明】 
　　0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为v_i ，重量为w_i（v_i，和w_i为非负数），背包容量为W（W为非负数），选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即，其中，x_i∈{0，1}，x_i=0表示第i个物品不放入背包，x_i=1表示第i个物品放入背包。

【问题1】（8分）
　　用回溯法求解此0-1背包问题，请填充下面伪代码中（1）~（4）处空缺。
       回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点己经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND（v，w，k，W）函数，其中v， w， k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。
　　下面给出0-1背包问题的回溯算法伪代码。
　　函数参数说明如下：
　　W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。
　　变量说明如下：
　　cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。
       BKNAP(W,n,w,v,fw,fp,X)
     1 cw ← cp ← 0
     2   (1)   
     3  fp← -1
     4  while true
     5         while k≤n and cw+w[k]≤W do
     6                 (2) 
     7                cp ← cp+ v[k]
     8                Y[k] ← 1
     9                k ← k+1
     10    if k>n then
     11         if fp      12            fp ← cp
     13            fw ← cw
     14            k ← n
     15            x ←Y
     16     else Y(k) ← 0
     17     while BOUND(cp,cw,k,W)≤fp do
     18         while k≠0 and Y(k) ≠1 do
     19               (3) 
     20         if k=0   then return
     21          Y(k) ← 0
     22          cw ← cw - w[k]
     23          cp ←cp - v[k]
     24            (4)  
【问题2】（7分）
　　考虑表4-1的实例，假设有3个物品，背包容量为22。图4-1中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字1/0分别表示选择／不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品 （5） ，获得的价值为 （6） 。

        

　　对于表4-1的实例，若采用穷举法搜索整个解空间，则搜索树的结点数为 （7） ，而用了上述回溯法，搜索树的结点数为 （8） 。

阅读下列说明和UML图，回答问题1至问题4，将解答填入答题纸的对应栏内。
【说明】
　　某企业为了方便员工用餐，餐厅开发了一个订餐系统（COS：Cafeteria Ordering System），企业员工可通过企业内联网使用该系统。
　　企业的任何员工都可以查看菜单和今日特价。
　　系统的顾客是注册到系统的员工，可以订餐（如果未登录，需先登录）、注册工资支付、预约规律的订餐，在特殊情况下可以覆盖预订。
　　餐厅员工是特殊顾客，可以进行备餐、生成付费请求和请求送餐，其中对于注册工资支付的顾客生成付费请求并发送给工资系统。
　　菜单管理员是餐厅特定员工，可以管理菜单。
　　送餐员可以打印送餐说明，记录送餐信息（如送餐时间）以及记录收费（对于没有注册工资支付的顾客，由送餐员收取现金后记录）。
　　顾客订餐过程如下：
　　1．顾客请求查看菜单；
　　2．系统显示菜单和今日特价；
　　3．顾客选菜；
　　4．系统显示订单和价格；
　　5．顾客确认订单；
　　6．系统显示可送餐时间；
　　7．顾客指定送餐时间、地点和支付方式；
　　8．系统确认接受订单，然后发送Email给顾客以确认订餐，同时发送相关订餐信息通  知给餐厅员工。
　　系统采用面向对象方法开发，使用UML进行建模。系统的顶层用例图和一次订餐的活动图初稿分别如图3-1和图3-2所示。

图3-1    COS系统顶层用例图

图3-2     一次订餐的活动图

【问题1】（2分）
　　根据【说明】中的描述，给出图3-1中A1和A2所对应的参与者。
【问题2】（8分）
　　根据【说明】中的描述，给出图3-1中缺少的四个用例及其所对应的参与者。
【问题3】（4分）
　　根据【说明】中的描述，给出图3-2中（1）~（4）处对应的活动名称或图形符号。
【问题4】（1分）
　　指出图3-1中员工和顾客之间是什么关系，并解释该关系的内涵。

图3-1    COS系统顶层用例图

图3-2     一次订餐的活动图

阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】
某公司拟开发一多用户电子邮件客户端系统，部分功能的初步需求分析结果如下：
（1）邮件客户端系统支持多个用户，用户信息主要包括用户名和用户密码，且系统中的用户名不可重复。
（2）邮件帐号信息包括邮件地址及其相应的密码，一个用户可以拥有多个邮件地址  （如userl＠123.com）。
（3）一个用户可拥有一个地址薄，地址簿信息包括联系人编号、姓名、电话、单位、地址、邮件地址1、邮件地址2、邮件地址3等信息。地址薄中一个联系人只能属于一个用户，且联系人编号唯一标识一个联系人。
（4）一个邮件帐号可以含有多封邮件，一封邮件可以含有多个附件。邮件主要包括邮件号、发件人地址、收件人地址、邮件状态、邮件主题、邮件内容、发送时间、接收时间。其中，邮件号在整个系统内唯一标识一封邮件，邮件状态有己接收、待发送、已发送和已删除4种，分别表示邮件是属于收件箱、发件箱、己发送箱和废件箱。一封邮件可以发送给多个用户。附件信息主要包括附件号、附件文件名、附件大小。一个附件只属于一封邮件，附件号仅在一封邮件内唯一。

【问题1】（5分）
根据以上说明设计的E-R图如图2-1所示，请指出地址簿与用户、电子邮件帐号与邮件、邮件与附件之间的联系类型。

【问题2】（4分）
该邮件客户端系统的主要关系模式如下，请填补(a) ~ (c)的空缺部分。
用户（用户名，用户密码）
地址簿（  （a）  ，联系人编号，姓名，电话，单位地址，邮件地址1，邮件地址2，邮件地址3）
邮件帐号（邮件地址，邮件密码，用户名）
邮件（  （b）  ，收件人地址，邮件状态，邮件主题，邮件内容，发送时间，接收时间）
附件（  （c）  ，附件号，附件文件名，附件大小）
【问题3】（6分）
（1）请指出【问题2】中给出的地址簿、邮件和附件关系模式的主键，如果关系模式存在外键请指出。
（2）附件属于弱实体吗？请用50字以内的文字说明原因。

阅读以下说明和数据流图，回答问题1至问题4，将解答填入答题纸的对应栏内。
【说明】
　　现准备为某银行开发一个信用卡管理系统CCMS，该系统的基本功能为：
　　1．信用卡申请。非信用卡客户填写信用卡申请表，说明所要申请的信用卡类型及申请者的基本信息，提交CCMS。如果信用卡申请被银行接受，CCMS将记录该客户的基本信息，并发送确认函给该客户，告知客户信用卡的有效期及信贷限额；否则该客户将会收到一封拒绝函。非信用卡客户收到确认函后成为信用卡客户。
　　2．信用卡激活。信用卡客户向CCMS提交激活请求，用信用卡号和密码激活该信用卡。激活操作结束后，CCMS将激活通知发送给客户，告知客户其信用卡是否被成功激活。
　　3．信用卡客户信息管理。信用卡客户的个人信息可以在CCMS中进行在线管理。每位信用卡客户可以在线查询和修改个人信息。
　　4．交易信息查询。信用卡客户使用信用卡进行的每一笔交易都会记录在CCMS中。信用卡客户可以通过CCMS查询并核实其交易信息（包括信用卡交易记录及交易额）。
　　图1-1和图1-2分别给出了该系统的顶层数据流图和0层数据流图的初稿。

      图1-1 顶层数据流图

【问题1】（3分）
　　根据【说明】，将图1-1中的E1~E3填充完整。
【问题2】（3分）
　　图1-1中缺少三条数据流，根据【说明】，分别指出这三条数据流的起点和终点。（注：数据流的起点和终点均采用图中的符号和描述）
【问题 3】（5分）
　　图1-2中有两条数据流是错误的，请指出这两条数据流的名称，并改正。（注：数据流的起点和终点均采用图中的符号和描述）
【问题4】（4分）
　　根据【说明】，将图1-2中P1~P4的处理名称填充完整。

（）（共15分） 
　　阅读下列说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 
【说明】 
　　现欲实现一个图像浏览系统，要求该系统能够显示BMP、JPEG 和GIF三种格式的文件，并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG 和GIF三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计所得类图如图7-1所示

　　采用该设计模式的原因在于：系统解析BMP、GIF与JPEG文件的代码仅与文件格式相关，而在屏幕上显示像素矩阵的代码则仅与操作系统相关。 

【Java 代码】 
class Matrix{  //各种格式的文件最终都被转化为像素矩阵
//此处代码省略
};
 
abstract class ImageImp{
    public  abstract void doPaint(Matrix m);   //显示像素矩阵m
};
 
class WinImp extends ImageImp{
   public void doPaint(Matrix m){ /*调用Windows系统的绘制函数绘制像素矩阵*/}
}；

class LinuxImp extends ImageImp{
   public void doPaint(Matrix m)(  /*调用Linux系统的绘制函数绘制像素矩阵*/)
}；
 
abstract class Image{
      public void setImp(ImageImp imp){
        (1)   =imp;}
      public abstract void parseFile(String fileName)；
      protected   （2）  imp；
}；

class  BMP extends Image{
      public void parseFile(String fileName){
         //此处解析BMP文件并获得一个像素矩阵对象m
          (3)  ;//显示像素矩阵m
    }
};

class  GIF extends Image{
  //此处代码省略
};

class  JPEG extends Image{
  //此处代码省略
};

public class javaMain{
    public static void main(string[] args){
   // 在windows操作系统上查看demo.bmp图像文件
        Image image1=     （4）；
        ImageImp  imageImp1=     （5）；
               （6）；
       Image1.parseFile（“demo.bmp”）;
  }
}

阅读下列说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 
【说明】 
　　现欲实现一个图像浏览系统，要求该系统能够显示BMP、JPEG 和GIF三种格式的文件，并且能够在Windows和Linux两种操作系统上运行。系统首先将BMP、JPEG 和GIF三种格式的文件解析为像素矩阵，然后将像素矩阵显示在屏幕上。系统需具有较好的扩展性以支持新的文件格式和操作系统。为满足上述需求并减少所需生成的子类数目，采用桥接（Bridge）设计模式进行设计，所得类图如图6-1所示。 


采用该设计模式的原因在于：系统解析BMP、GIF与JPEG文件的代码仅与文件格式相关，而在屏幕上显示像素矩阵的代码则仅与操作系统相关。 

【C++代码】 
class Matrix{     //各种格式的文件最终都被转化为像素矩阵
      //此处代码省略
};

class ImageImp{
public:
  virtual void doPaint(Matrix m)=0;    //显示像素矩阵m
};
 
class WinImp:public ImageImp{
public:
        void doPaint(Matrix m){  /*调用Windows系统的绘制函数绘制像素矩阵*/}
};

class LinuxImp:public ImageImp{
public:
          void doPaint(Matrix m){  /*调用Linux系统的绘制函数绘制像素矩阵*/}
};

class Image{
public:
     void setImp(ImageImp*Imp){   (1)  =imp;}
     virtual void parseFile(string fileName)=0;
protected:
      (2)     *imp;
};

class  BMP : public Image{
public:
          void parseFile(string fileName){
         //此处解析BMP文件并获得一个像素矩阵对象m
         (3)      ;   //显示像素矩阵m
     }
};

class  GIF : public Image{
        //此处代码省略
}；
 
class  JPEG : public Image{
       //此处代码省略
}；

void main(){
  //在windows操作系统上查看 demo.bmp图像文件
  Image*image1  =  （4） ;
  ImageImp*imageImp1  =  （5） ;
     (6)     ;
   Image1->parseFile(“demo.bmp”);
}

现假设该系统需要支持10种格式的图像文件和5种操作系统，不考虑类Matrix，若采用桥接设计模式则至少需要设计（7）个类。 

阅读下列说明和C 函数代码，将应填入（n）处的字句写在答题纸的对应栏内。 
【说明】   
　　对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。 
　　设二叉树采用二叉链表存储，结点类型定义如下：
　　typedef struct BtNode{ 
            ElemType  data;/*结点的数据域，ElemType的具体定义省略*/ 
　　     struct BtNode *lchild，*rchild;/*结点的左、右孩子指针域*/ 
　　}BtNode， *BTree; 
 
　　在函数InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点的单向链表（简称链栈），其结点类型定义如下： 
　　typedef struct StNode{  /*链栈的结点类型*/ 
　         BTree elem;  /*栈中的元素是指向二叉链表结点的指针*/ 
　         struct StNode *link; 
　　}StNode; 
　　假设从栈顶到栈底的元素为 en、en-1、…、e1，则不含头结点的链栈示意图如图 5-1所示。 

【C函数】
    int  InOrder(BTree root)               /*实现二叉树的非递归中序遍历 */

阅读下列说明，回答问题1和问题2，将解答填入答题纸的对应栏内。 
【说明】 
　　现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其它各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其它各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。

【问题1】（12分）  
　　本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。 已知图G 的顶点集合为V= {1，2，...，n } ，W= ｛Wij｝n*n 为权重矩阵。设 d^(k)_ij为从顶点i到顶点 j的一条最短路径的权重。当k = 0时，不存在中间顶点，因此d⁽⁰⁾_ij=w_ij；当k >0 时，该最短路径上所有的中间顶点均属于集合 {1，2， ...， k｝若中间顶点包括顶点 k ，则d^(k)_ij=d^(k-1)_ik+d^(k-1)_kj；若中间顶点不包括顶点k，则d^(k)_ij=d^(k-1)_ij。于是得到如下递归式

　

　　因为对于任意路径，所有的中间顶点都在集合{1，2， ...， n｝ 内，因此矩阵D⁽ⁿ⁾=｛d⁽ⁿ⁾_ij｝_n*n 给出了任意两个顶点之间的最短路径，即对所有i， j ∈V，d⁽ⁿ⁾_ij表示顶点i到顶点 j的最短路径。 
　　下面是求解该问题的伪代码，请填充其中空缺的 (1)至(6)处。 伪代码中的主要变量说明如下： 
　　W：权重矩阵 
　　n： 图的顶点个数 
　　SP：最短路径权重之和数组，SP[i]表示顶点i到其它各顶点的最短路径权重之和，i从1到n 
　　min_SP：最小的最短路径权重之和 
　　min_v：具有最小的最短路径权重之和的顶点 
　　i：循环控制变量  
　　j：循环控制变量 
　　k：循环控制变量 

【问题2】（3分）
　　【问题1】中伪代码的时间复杂度为（7）（用Ο 符号表示）。

阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。 
【说明】 
　　某银行计划开发一个自动存提款机模拟系统（ATM  System）。系统通过读卡器（CardReader）读取 ATM 卡；系统与客户（Customer）的交互由客户控制台（CustomerConsole）实现；银行操作员（Operator）可控制系统的启动（System Startup）和停止（System Shutdown）；系统通过网络和银行系统（Bank）实现通信。
       当读卡器判断用户已将ATM卡插入后，创建会话（Session）。会话开始后，读卡器进行读卡，并要求客户输入个人验证码（PIN）。系统将卡号和个人验证码信息送到银行系统进行验证。验证通过后，客户可从菜单选择如下事务（Transaction）： 
　　1. 从ATM卡账户取款（Withdraw）； 
　　2. 向ATM卡账户存款（Deposit）； 
　　3. 进行转账（Transfer）； 
　　4. 查询（Inquire）ATM卡账户信息。 
　　一次会话可以包含多个事务，每个事务处理也会将卡号和个人验证码信息送到银行系统进行验证。若个人验证码错误，则转个人验证码错误处理（Invalid PIN Process）。每个事务完成后，客户可选择继续上述事务或退卡。选择退卡时，系统弹出 ATM 卡，会话结束。
       系统采用面向对象方法开发，使用 UML 进行建模。系统的顶层用例图如图 3-1 所示，一次会话的序列图（不考虑验证）如图3-2所示。消息名称参见表3-1。 

【问题1】（7分）   

　　根据【说明 】中的描述，给出图 3-1 中 A1 和 A2 所对应的参与者，U1 至 U3 所对应的用例，以及该图中空 （1） 所对应的关系。（U1至U3的可选用例包括：Session、Transaction、Insert Card．Invalid PIN Process和Transfer） 
【问题2】（6分）   
　　根据【说明 】中的描述，使用表3-1中的英文名称，给出图3-2中6～9对应的消息。  
【问题3】（2分）
　　 解释图3-1中用例U3和用例Withdraw、Deposit等四个用例之间的关系及其内涵。