2003年度软件设计师下午试题

试题二
阅读下列说明，回答问题1至问题4，将解答填入答题纸的对应栏内。
[说明]
甲公司的经营销售业务目前是手工处理的，随着业务量的增长，准备采用关系数据库对销售信息进行管理。经销业务的手工处理主要涉及三种表：订单、客户表和产品表。
   
为了用计算机管理销售信息，甲公司提出应达到以下要求：产品的单价发生变化时，应及时修改产品表中的单价数据。客户购货计价采用订货时的单价。订货后，即使单价发生变化，计算用的单价也不变。
在设计数据库时，经销部的王先生建立了以下数据模型：
    
其中，方框表示实体，单向箭头表示1对多的联系，双向箭头表示多对多的联系。
由于上述模型对建立关系数据库是不合适的，因此王先生又修改了数据模型，并设计了如下几个关系(带下划线的数据项是关键项，最后一个关系中没有指出关键项)：
Customer(CustomerNo(关键项)，CustomerName，Address，Phone)
Product(ProductNo(关键项)，ProductName，UnitPrice)
Order(OrderNo(关键项)，CustomerNo，Date)
OrderDetail(OrderNo，ProductNo，Quantity)

[问题1]
请按[说明]中的要求画出修改后的数据模型。

[问题2]
（1）[说明]中的几个关系仍无法实现甲公司的要求，为什么?
（2）需要在哪个关系中增加什么数据项才能实现这个要求?

[问题3]
写出OrderDetail中的关键项。

[问题4]
以下SQL语句用于查询没有订购产品代码为“1K10”的产品的所有客户名。请填补其中的空缺。
SELECT CustomerName FROM Customer ___(1)____
      WHERE ___(2)___
         (SELECT * FROM OrderDetail B，Order C
           WHERE B．ProductNo = C.ProductNo
             AND B．ProductNo = '1KIO'
             AND C．CustomerNo = A.CustomerNo)

试题三
阅读下列说明和有关的图，回答问题1至问题4，将解答填入答题纸的对应栏内。
[说明]
某制造企业的物料出入库管理的工作流程分别叙述如下：

1．出库工作流程
①领料人提交领料单(每一种物料有一张领料单)；
②仓库保管员根据领料计划单检验该领料单是否有效；
⑨若经检验没有相应的领料计划，则通知领料人该领料单无效；
④若领料单有效，仓库保管员根据领料单上的物料代码核对是否有足够的库存；
⑤若没有足够的库存，仓库保管员向领料人发缺货单；
⑥若有足够的库存，仓库保管员在领料单上签字，并登记出库单，修改物料主文件中的现有库存数；相应的物料出库，物料清单交领料人。

2．入库工作流程
①采购员提交入库申请单(每一种物料有一张入库申请单)；
②仓库保管员根据采购计划单验收入库申请单；
⑧若验收发现没有相应的采购计划，则仓库保管员向采购员发无效申请单：
④若验收合格，则仓库保管员向检验员申请物料检验；检验员根据检验结果填写物料检验单。
⑤如果物料或供货方不合格，则向采购员发出退货单；
⑥如果检验合格，则仓库保管员登记入库单，修改物料主文件中的现有库存数，相应的物料入库。
为便于及时了解库存情况、核查出入库情况，该企业决定将上述人工流程由计算机来实现。在设计该系统时，采用了两种方法：结构化方法和面向对象方法。

图3.1给出了物料出入库系统的数据流图，图中的数据流并没有画全，需要考生填补。图3.2给出了采用面向对象方法所认定出的类。
    
[问题1]
图3.1中缺少了那些数据流?请指明每条数据流的名称、起点和终点。

[问题2]
给出“领料单”和“入库申请单”这两个类至少应具有的属性。

[问题3]
为建立功能完善的库存管理系统，除了查询、统计、报表输出功能外，还应具有哪些对提高企业效益至关重要的功能?

[问题4]
用面向对象方法设计的类中，有一些类的对象是需要持久存储的，这样的类一般需要映射到关系数据库模式中。请指出图3.2中哪些类需要做这样的映射。

试题四
在COMET型计算机上可以使用试卷上所附的CASL汇编语言，阅读程序说明和CASL程序，把应填入___(n)___ 处的字句写在答卷的对应栏内。
[程序4说明]
本程序统计出考试成绩在80分以上(含80分)、60分到79分、低于60分的学生人数，并将统计结果存放在以CHJG为首地址的连续三个内存单元中。学生的成绩数据连续存放在以XSCH为首地址的内存空间中，以数据-1作为结束标志。
[程序4]
START　 BEGIN
XSCH　　 DC 90
；……
；此处的数据未完全列出
；……
         DC -1
CHJB　 　DC 80
         DC 60
CHJG 　　DC 0
         DC 0
         DC 0
ONE 　 　DC 1
BEGIN　　___(1)___
         LEA　　　GR1，0 ;　　　　　　给GR1赋初值0
NEXT 　　LD　　　 GR2，XSCH，GR1 ;　　把一个学生成绩读入GR2
         LEA　　　GR0，0，GR2 ;　 　　把GR2的内容读入GR0
         JMI　　　EXIT　　 　　 　　　如果GR2中的数小于0，
         LEA　　　GR2，0 ;　　　　　　给GR2赋初值0
         CPA　　　GR0，CHJB ;　　 　　比较GR0与CHJB的大小,由于CHJB=80，所以此处所做的工作是看成绩是否大于等于80分
         JPZ　　　GOON ;　　　　　　　如果成绩大于等于80分则跳到 GOON 继续执行
         ____(2)____
         LEA 　　 GR2,1,GR2 ;　　 　　GR2+1->GR2，
         ____(3)____
         CPA 　　 GR0,CHJB,GR2 ;　　　当成绩小于80分时，再看成绩是不是大于等于60分
         JPZ　　　GOON ;　　　　　　　如果成绩大于等于60分则跳到 GOON 继续执行
         LEA　　　GR2，1，GR2 ;　　　 GR2+1->GR2
GOON 　　___(4)____
         LD　　　 GR0,CHJG,GR2 ;　　　把当前成绩对应的统计结果取出。(CHJG+0)存的是80分以上的人数，(CHJG+1)存的是60分以上的人数，(CHJG+,2)存的是60分以下的人数。
         ___(5)____
         ADD　　　 GR0,ONE ;　　　　　 把取出的统计人数加1，即把当前成绩统计进去。
         ST 　　 　GR0，CHJG，GR2 ;　　把新统计结果存入。
         LEA GR1，1，GR1; 　　　　　　 GR1+1->GR1 ;指针下移一条记录，即使得(LD GR2，XSCH，GR1)取下一个成绩。
         JMP NEXT ;　　　　　　　　　　无条件转移至NEXT
EXIT　　EXIT
        END

试题五
阅读以下预备知识、函数说明和C代码，将应填入__(n)__处的字句写在答题纸的对应栏内。
[预备知识]

①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合<a，b，c，d}及其权值2、7、4、5，可构造如下所示的最优二叉树和相应的结构数组Ht(数组元素Ht[0]不用)。
    
结构数组Ht的类型定义如下：
  #define MAXLEAFNUM 20
  struct node{
      char ch； /*扫当前结点表示的字符，对于非叶子结点，此域不用*/
      int weight； /*当前结点的权值*/
      int parent； /*当前结点的父结点的下标，为0时表示无父结点*/
      int lchild，rchild； /*当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点*/
       ｝Ht[2*MAXLEAFNUM]；

②用'0'或'1'标识最优二叉树中分支的规则是：从一个结点进入其左(右)孩子结点，就用'0'('1')标识该分支(示例见上图)。

③若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由‘0’、‘1’组成的一个序列，称此序列为该叶子结点的前缀编码。例如上图所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。

[函数5.1说明]
函数void LeafCode(int root，int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参n为叶子结点个数。
在构造过程中，将Ht[p].weight域用作被遍历结点的遍历状态标志。
[函数5.1]

  char **HC；
  void LeafCode(int root，int n)
    {/*为最优二叉树中的n个叶子结点构造前缀编码，root是树的根结点下标*/
       int i，p=root，cdlen=0; char code[20];
       Hc = (char **)malloc((n+1)*sizeof(char *))；/*申请字符指针数组*/
       for(i = 1；i<= p；++i)
          Ht[i].weight = 0；/*遍历最优二叉树时用作被遍历结点的状态标志*/
       while(p){ /*以非递归方法遍历最优二叉树，求树中每个叶子结点的编码*/
          if(Ht[p].weight == 0){ ／*向左*／
          Ht[p].weight = 1;
          if(Ht[p].lchild != 0) {p = Ht[p].lchild；code[cdlen++] = '0';}
          else if(Ht[p].rchild == 0){/*若是叶子结点，则保存其前缀编码*/
             Hc[p] = (char *)malloc((cdlen+1)*sizeof(char));
             ___(1)___;
             strcpy(Hc[p]，code)；
              }
              }
          else if(Ht[p].weight == 1){ ／*向右*／
             Ht[p].weight = 2;
             if(Ht[p].rchild != 0) {p = Ht[p].rchild；code[cdlen++] = '1';}
              }
          else { /*Ht[p].weight == 2，回退*/
             Ht[p].weight = 0；
             p = __(2)__;
             ___(3)___;／*退回父结点*／
             }
             }／*while结束*／
   }
[函数5.2说明]
函数void Decode(char *buff，int root)的功能是：将前缀编码序列翻译成叶子结点的字符序列，并输出。其中形参root为最优二叉树的根结点下标；形参buff指向前缀编码序列。
[函数5.2]
   void Decode(char *buff，int root)
     { int pre = root，p;
       while(*buff != '\0'){
       p = root;
         while(p != 0){/* 存在下标为p的结点*/
         pre = p；
         if(__(4)___) p = Ht[p].lchild； /*进入左子树*/
         else p = Ht[p].rchild： ／*进入右子树*／
         buff++; ／*指向前缀编码序列的下一个字符*／
          }
        ___(5)___;
        printf("％c"，Ht[pre].ch);
          }
      }

试题六
阅读以下说明和C++代码，将应填入__(n)__处的字句写在答题纸的对应栏内。
[说明]
本题将有向网(带权有向图)定义为类AdjacencyWDigraph。类中的数据成员n表示有向网中的顶点数；a为带权邻接矩阵，用于存储有向网中每一对顶点间弧上的权值；c为二维数组，存储有向网中每一对顶点间的最短路径长度；kay为二维数组，存储最短路径，kay[i][j] = k表示顶点i到达顶点j的最短路径必须经过顶点k.类中的主要成员函数有：

Input():输入有向网的顶点数、各条弧及权值，建立带权邻接矩阵a。若顶点i到顶点j有弧，则a[i][j]取弧上的权值，否则a[i][j]的值取NoEdge。
AllPairs()：用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。
OutShortestPath(int i，int j)：计算顶点i到顶点j的最短路径。
outputPath(int i，int j)：输出顶点i到顶点j的最短路径上的顶点。
   
Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1,C2...,Cn，其中C0是已知的带权邻接矩阵a，Ck(i，j)(0≤ij<n)表示从顶点i到顶点j的中间顶点序号不大于k的最短路径长度。如果i到j的路径没有中间顶点, 则对于0≤k<n, 有Ck (i，j) = C0(i，j) = a[i][j]。递推地产生C1,C2，…,Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。

[C++代码]
  #include <iostream.h>
  #define NoEdge 10000／／当两个顶点之间没有边相连时，在邻接矩阵中用NoEdge表示
  void Make2DArray(int **&x，int rows，int cols);
  class AdjacencyWDigraph{
        private：
                int n； ／／有向网中的顶点数目
                int **a； ／／存储顶点间弧上的权值
                int **c； ／／存储计算出的最短路径长度
                int **kay； ／／存储求出的最短路径
        public：
                int Vertices()const {return n；}
                void AllPairs()；
                void Input()；／／输入有向网的顶点数、各条弧及权值，建立邻接矩阵a
                void OutShortestPath(int i,intj)；／／计算顶点i到j的最短路径(试卷中未列出)
                ~AdjacencyWDigraph()； ／／析构函数(试卷中未列出)
        private：
                void outputPath(int i，int j);
     };
void AdjacencyWDigraph::AllPairs()
     { int i，j，k，t1，t2，t3；
         for(i = 1；i <=n; i++)
            for(j = 1; j <=n; ++j)
               { c[i][j] = ___(1)___;
                 kay[i][j] = 0; }
         for(k =1; k <=n; k++)
               for(i = 1; i <= n; i++) {
                  if(i == k)continue;
                  t1 = c[i][k];
               for(j = 1; j <= n; j++){
                  if(j == k || j == i) continue;
                    t2 == c[k][j]; t3 == c[i][j];
                  if( t1 != NoEdge && t2 != NoEdge && (t3 == NoEdge || t1+t2 < t3))
                    { c[i][j] = ___(2)___;
                    kay[i][j] = ___(3)___; }
                  } //for
                  }//for
 }
 void AdjacencyWDigraph::outputPath(int i，int j)
    { //输出顶点i到j的最短路径上的顶点
      if(i == j)return;
      if(kay[i][j] == 0 ) cout << j <<’ ’;
      else { outputPath(i,___(4)___);
        outputPath(____(5)____);
          }
      }
 void AdjacencyWDigraph::Input()
    { int i，j，u，v，w，E;
     cout << "输入网中顶点个数:"; cin>>n;
     cout<< "输入网中弧的个数:"; cin>>E;
     Make2DArray(a，n+1，n+1);
        for(i = 1;i <= n; i++)
           for(j = 1; j <= n; j++) a[i][j] = NoEdge;
        for(i =1；i <= n; i++) a[i][i]= 0;
     Make2DArray(c，n+1，n+1);
     Make2DArray(kay，n+1，n+1);
        for(i = 1；i <= E；i++) {
           cout<< "输入弧的信息(起点 终点 权值):"; cin>>u>>v>>w; a[u][v] = w;
             }
     }
  void Make2DArray(int **&x，int rows，int cols)
     { int i，j；
      x = new int* [rows+1]；
      for(i = 0; i < rows+1; i++) x[i] =new int [cols+1];
      for(i = 1; i <= rows; i++)
         for(j = 1;j <= cols; j++) x[i][j] = 0;
      }