1999年中国计算机软件资格水平考试高级程序员下午试题

试题一

阅读以下说明和流程图，回答问题1至问题3，将解答写在答卷的对应栏内。

【说明】

本流程图描述了某仓库物品入出库管理的处理流程。每张入库单或出库单都由两位操作员分别录入，经处理 1 或处理 3 输入系统后作合法性检查，并将合法的入库单或出库单记入入库单文件或出库单文件。然后通过处理 2 或处理 4 实时更新库存文件。处理5每周执行一次，它依次检查库中的每一种物品，当某物品的库存量小于该物品的最低库存量时，制订采购计划，输出订购单。处理 6 和处理 7 每月执行一次，处理 6将入库单文件和出库单文件合并成月入出库文件，并根据统计的要求对其进行排序。处理 7 进行统计，产生月报表，并把该月合并后的月入出库文件添加到月入出库后备文件中，以备日后查找，最后清除入库单文件、出库单文件和月入出库文件。

系统中某些文件和报表的格式如下：

库存文件记录：物品编号 + 名称 + 规格 + 库存量 + 最低库存量 + 最高库存量（其中“最高库存量”指该物品允许存放在库中的最大值）

入库单文件记录：日期 ＋ 物品编号 ＋ 数量

出库单文件记录：日期 + 物品编号 + 数量

月报表格式：

【问题 1 】

指出处理 3 能检查出库单中的哪些错误。

【问题 2 】

指出月入出库文件的记录格式．

【问题 3 】

指出处理 6 排序的第一和第二关键字。

试题二

阅读以下说明和流程图，回答问题 1 至问题 3，将解答写在答卷的对应栏内。

【说明】

有一种游戏，其规则如下：有一个 3×3 的方格，每个方格中只可画‘＋’符号或‘－’符号，表示该方格的值。图 (a) 定义了各方格的位置，表 1 为每个方格位置定义了与其相关联的位置集，各方格的初值如图 (b) 所示。游戏开始后，每次可选一个值为‘＋’的方格位置，然后根据表 1 将该位置所对应的每个相关联的位置上的符号重画成与其不同的符号，即将‘＋’重画成‘－’，将‘－’重画成‘＋’。重画操作可用所选的位置编号来描述。例如在图 (b) 所示的情况下，选择位置 4 时，重画结果如图 (c) 所示。经过连续的若干次这样的操作后，当 3×3 方格呈现出图 (d) 所示的图形时，表示获胜；当呈现出图 (e) 所示的图形时，表示失败。

下列流程图旨在输出从初始状态出发直至获胜的重画操作（即所选的位置编号）序列。图中假定数组 A[0..8] 存放 3×3 方格的值，数组 c[0..8][1..5] 存放表 1 所示的各方格位置的相关联的位置集、数组 d[0..8] 存放各方格位置的相关联的位置个数，数组元素 S[1]～S[k] 存放各次重画操作所对应的位置编号，变量 N 存放 3×3 方格中当前的‘＋’符号的个数。

表1 方格位置及其相关位置集的对照表

【问题 1 】

填充图中的①－④。

【问题 2 】

图中的⑤应与 A、B、C 中的哪一点连接。

【问题 3 】

如果每次由游戏者选择方格改由程序自动枚举选择，那么，为从初态出发求出所有可能的获胜重画操作序列，在哪些情况下需要进行回溯处理。

【流程图】　

试题三

阅读以下说明和流程图，回答问题 1 和问题 2， 将解答写在答卷的对应栏内。

【说明】

本流程图采用状态矩阵方法将已知字符序列翻译成实数（其句法图如图3.1所示）。

本题的状态矩阵分成两部分，语义动作矩阵 FM 和状志转换矩阵 SM ，它们分别存放每个状态遇到某字符时应执行的语义动作以及执行动作后应转移到的新状态。

本流程图从 0 状态出发逐个读入字符，在执行了 FM 中相应的语义动作后，SM 中指出的相应新状态，重复这一过程，直至到达 9 状态或 10 状态。9 状态表示已正确地把该字符序列翻译成实数（注意：此时已多读进实数后的下一个字符）；10 状态表示出错。

图3.1 某语言的实数句法图

状态转换矩阵 SM

语义动作矩阵 FM

现有以下语义动作函数：

f0: 空函数，不做任何操作。

f1：按当前字符确定实数符号 sign 为 1 或 -1。

f2：翻译实数的整数部分值（求 m ）。

f3：翻译实数的小数部分值（求 d）。

f4：按当前字符（幂的正负号）确定求幂所用的因子 PS（10.0或0.1）。

f5：翻译实数的幂（求 p ）。

f6：求实数的值 R=sign*(m+d)*p

f7：输出错误信息。

【流程图】

注：设已知实数字符串存于字符数组 str 中。

【问题 1 】

将状态转换矩阵 SM 中①－⑤处的正确内容填入答卷的对应栏内。

【问题 2 】

将语义动作矩阵 FM 中⑥－⑩处的正确内容填入答卷的对应栏内。

试题四

在 COMST 型计算机上可以使用试卷上所附的 CASL 汇编语言，阅读程序说明和CASL程序，把应填入＿(n)＿ 处的字句，写在答卷的对应栏内。

【程序 4.1 说明】

本子程序是对 15 位二进位串，求它的奇校验位，生成 16 位二进位串，使 16 位二进位串中有奇效个 1。

进入此子程序时，15 位二进位串在 GR1 的第 1 位至第 15 位，假定 GR1 的第 0 位是 0，求得的奇校验位装配在 GR1 的第 0 位上。

【程序 4.1 】

START

BEG     PUSH       0，GR2

PUSH       0，GR3

LEA         GR3，1

__ (1) __

L1       SLL           GR2，1

__ (2) __

LEA          GR3，1，GR3

L2       JZE           L3

JMP          L1

L3       __ (3) __

ST             GR3，WORK

ADD         GR1，WORK

POP          GR3

POP          GR2

RET

WORK  DS      1

END

【程序 4.2 说明】

子程序 SUM 是将存贮字 A 起的 n(n > 0)个字求和, 并将结果存于存贮字 B 中。

调用该子程序时，主程序在 GR1 中给出存放子程序所需参数的起始地址。参数的存放次序如下图：

【程序 4.2 】

  START

SUM     LD         GR2，0，GR1

  LD         GR3，1，GR1

  LEA       GR0，0

L5         ADD       GR0，0，GR2

  LEA       GR2，1，GR2

  __ (4) __

 JNZ         L5

L3         __(5)__ 

 ST           GR0，0，GR3

 RET

 END

试题五

阅读下列程序说明和 C 代码，将应填入＿(n)＿ 处的字句写在答卷的对应栏内

【程序 5 说明】

本程序实现两个多项式相乘。多项式用链表表示，链表上的各表元按多项式的幂指数降序链接。例如：

f(x)=5.7x¹⁵ + 4.8x⁶ + 9.65

设两个多项式f(x)和g(x)分别为

f(x)=fnxn+ ... +f₁x+f₀ g(x)=g_mx^m+ ... +g₁x+g₀

其积多项式为 s(x)=f(x)g(x)=s_kx^k+ ... +s₁x+s₀

其中 k = n + m , s_i = Σ∫_u * g_v (0≤i≤k)

                     ^u+v=i

【程序 5 】

#include <stdio.h>

#include <malloc.h>

typedef struct elem { int index; double coef; struct elem *next;

                    } POLYNODE;

void write (POLYNODE *g)

{ POLYNODE *p = g;

  while (p) { printf(“%8.4f”, p->coef);

        if (p->index) printf("*x %d", p->index);

        if (p->next && p-next->coef > 0 ) printf("+");

        p = p->next;

  }

  printf(“\n\n”);

}

main()

{ POLYNODE *f, *g, *s, *inpoly(), *polymul();

  f = inpoly(); g = inpoly(); s = polymul(f, g); write(s);

}

POLYNODE *reverse(POLYNODE *g)

{ POLYNODE *u = NULL, *v = g, *w;

  while(v) { w = v->next; v->next = u; u = v; v = w;}

  return u;

}

POLYNODE *polymul(POLYNODE *f, POLYNODE *g)

{ POLYNODE *fp, *gp, *tail, *p = NULL, *q;

  int i, maxindex; double temp;

  maxindex = f->index + g->index; g = reverse(g);

  for(i = maxindex; i >= 0; i--) {

      fp = f; gp = g;

      while (fp != NULL && fp->index > i) fp = fp->next;

      while (gp != NULL && gp->index < i- fp->index) gp = gp->next;

      temp = 0.0;

      while(fp && gp)

        if (fp->index + gp->index == i) {

          temp += fp->coef * gp->coef; fp = fp->next; gp = gp->next;

        }

        else if ( ___(1)___ ) fp = fp->next;

           else gp = gp->next;

        if (temp != 0.0) {

           q = (POLYNODE *)malloc(sizeof(POLYNODE));

           q->index = i; q->coef = temp; q->next = NULL;

           if ( ___(2)___ ) p = q; else ___(3)___;

           tail = q;

        }

  }

  g = reverse(g); return p;

}

POLYNODE * inpoly()

{ POLYNODE *u, *v, *h = NULL, *p; int index; double coef;

  printf("Input index(<0 for finish) "); scanf("%d", &index);

  while (index >= 0 ) {

    printf(“Input coef “); scanf ("%1f", &coef);

    p = (POLYNODE *)malloc(sizeof(POLYNODE));

    p->index = index; p->coef = coef;

    v = h ;

    while (v != NULL && index < v->index) { u = v; v = v->next;}

    if (v == NULL || index > v->index)

    { p->next = v; if (v == h ) ___(4)___; else ___(5)___;}

      else v->coef += coef;

      printf("Input index(<0 for finish) "); scanf("%d", &index);

  }

  return h;

}

试题六

阅读下列程序说明和 C 代码，将应填入＿（n）＿处的字句写在答卷的对应栏内。

【程序 6 说明】

本程序从 n 种不同重量、不同价值的物品中选取一部分物品。要求在不超过限定重量 limw 的前提下，使被选取的那些物品的总价值较大。这里约定 limw 不超过 n 种物品的重量总和,也没有一种物品的重量超过 limw ，并且各物品的价值都大于 0 。

程序中，n 种物品被顺序编号为 0、1、2、......、n-1。

【程序 6 】

#include <stdio.h>

#define N 100

double limw;

int opts[N]; /* 存储临时最佳的选择方案，当opts[i]为 1，物品 i 在解中 */

struct elem { double weight;

              double value;

             } a[N]; /* 物品的重量和价值信息 */

int k, n ;

struct { int flg; /* 物品的考虑状态：0：不选，1：将被考虑，2：曾被选中 */

         double tw; /* 已达到的总重量 */

         double tv; /* 期望的总价值 */

       ｝twv[N]; /* 当前候选解中各物品的考虑状态，以及候选解的状态 */

main()

{ double maxv, find();

  printf("Enter number of matter. "); scanf("%d", &n);

  printf("Enter limit of weight. "); scanf("%1f", &limw);

  printf("Enter weight and values of matters. ");

  for (k = 0; k < n; k++) scanf("%1f%1f", &a[k].weight, &a[k].value);

  maxv = find(a,n);

  for(k = 0; k < n; k++) if(opts[k]) printf("%4d", k);

  printf("\nTotal value = %1f\n", maxv);

}

next(int i , double tw, double tv) /* 将考虑 i 号物品 */

{ twv[i].flg = 1; twv[i].tw = tw; twv[i].tv = tv; }

look(int i, int *f, double *tw, double *tv) /* 取i号物品在解中的状态信息 */

{ *f = twv[i].flg; *tw = twv[i].tw; *tv = twv[i].tv; }

double find (struct elem *a, int n )

{ int i, k, f;

  double maxv, tw, tv, totv = 0.0;

  maxv = 0;

  for(k = 0; k < n; k++) ____(1)____;

  next(0, 0.0, totv);

  i = 0;

  while(i >= 0) {

     look(i, &f, &tw, &tv);

     switch (f) {

        case 1: twv[i].flg++; /* 先考虑被选中 */

            if(____(2)____ <= limw) /* 选中可行吗？ */

            if(i < n-1) { /* 后面还有物品吗？ */

                next(____(3)____); /* 置i+1物品的状态 */

                i++;

            }

            else if (tv > maxv) { /* 是一个更好的候选解吗？ */

                maxv = tv;

                for(k = 0; k < n; k++)

                    opts[k] = twv[k].flg != 0;

            }

            break;

        case 0: i--; break; /* 回退 */

        default: /* f == 2 */

            twv[i].flg = 0;

            if (____(4)____) /* 不选i号物品可行吗？ */

                if(i < n-1) { /* 后面还有物品吗？ */

                    next(____(5)____);

                    i++;

                }

                else {

                    maxv = tv – a[i].value;

                    for(k = 0; k < n; k++)

                    opts[k] = twv[k].flg != 0;

                    i--;

                }

                break;

      }

  }

  return maxv;

}

 回目录      老顽童校对整理 2002年5月