IT 考试网 http://www.pc30.com


		关于站长
		收藏本站
		设为首页

※ 最新动态 ∣ 考试简介 ∣　历年试题 ∣ 编程工具 ∣ 在线考试 ∣ 考试论坛 ∣ 给我留言 ∣ 答疑信箱 ※

您的位置：首页——历年试题

一九九九年度高级程序员级　下午试卷

从下列的3道试题（试题一至试题三）中任先2道解答。如果解答的试题数超过2道，则题号小的2道解答有效。

试题一

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

【说明】

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

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

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

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

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

月报表格式：

物品编号日期入库数出库数

xxxx xx xx xx

xx xx xx

当月小计 xxx xxx

xxxx xx xx xx

xx xx xx

【问题１】

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

【问题2】

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

【问题３】

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

【流程图】

试题二

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

【说明】

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

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

０１２  －＋－＋＋＋ －

３４５－＋－＋－＋＋－＋ ―――

６７８  一＋一＋＋＋ 一

图（ａ）图（b）图（Ｃ）图（ｄ）图（ｅ）

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

方格位置相关位置集

００１３４

１０１２

２１２４５

３０３６

４１３４５７

５２５８

６３４６７

７６７８

８４５７８

【问题1】

填充图中的①－④。

【问题2】

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

【问题3】

如果每次由游戏者选择方格改由程序自动枚举选择，那么，为从初态出发求出所有可

能的获胜重画操作序列，在哪些情况下需要进行回溯处理。

【流程图】

试题三

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

【说明】

本流程图采用状态矩阵方法将已知字符序列翻译成实数（其句法本题的状态矩阵分成两部分，语义动作矩阵FM和状志转换矩阵S放每个状态遇到某字符时应执行的语义动作以及执行动作后应转移到的新状态。

本题的状态矩阵分成两部分，语义动作矩阵FM和状志转换矩阵S放每个状态遇到某字符时应执行的语义动作以及执行动作后应转移到的新状态。本流程图从０状态出发逐个读入字符，在执行了FM中相应的语义动作SM中指出的相应新状态，重复这一过程，直至到达９状态或１０状确地把该字符序列翻译成实数（注意，此时已多读进实数后的下一个字符）；出错。

图3.1 某语言的实数句法图

状态转换矩阵 SM

＼＼字符类＼新状态＼状态＼＼	＋或－（类别0）	数字（类别1）	小数点（类别2）	字符E （类别3）	其它字符（类别4）
0	1	2	3	10	10
1	10	①	②	10	10
2	9	2	4	6	9
3	10	5	10	10	10
4	9	③	9	④	9
5	9	5	9	6	9
6	7	8	10	10	10
7	10	⑤	10	10	10
8	9	8	9	9	9

语义动作矩阵 FM

＼＼字符类＼新状态＼状态＼＼	＋或－（类别0）	数字（类别1）	小数点（类别2）	字符E （类别3）	其它字符（类别4）
0	f1	f2	f0	f7	f7
1	f7	⑥	f0	f7	f7
2	f6	⑦	f0	f0	f6
3	f7	⑧	f7	f7	f7
4	f6	f3	f6	f0	f6
5	f6	f3	f6	⑨	f6
6	⑩	f5	f7	f7	f7
7	f7	f5	f7	f7	f7
8	f6	f5	f6	f6	f6

现有以下语义动作函数：

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

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

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

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

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

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

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

f7：输出错误信息。

【流程图】

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

【问题1】

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

【问题２】

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

试题四

在ＣＯＭＳＴ型计算机上可以使用试卷上所附的ＣＡＳＬ汇编语言，阅读程序说明和

CASL程序，把应填入＿（n）＿处的字句，写在答卷的对应栏内。

【程序4.1说明】

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

进入此子程序时，１５位二进位串在ＧＲ1的第１位至第１５位，假定ＧＲ1的第０位是０，求得的奇校验位装配在ＧＲ1的第０位上。

【程序4.1】

START

BEG PUSH 0，GR2

PUSH 0，GR2

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 是将存贮字Ａ起的ｎ（n ＞０）个字求和, 并将结果存于存贮字Ｂ中。

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

（GR1）＋0 A

＋1 B

＋2 C

【程序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

＿＿＿＿＿（5）＿＿＿＿＿

ST GR0，0，GR3

RET

END

试题五

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

【程序５说明】

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

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

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

f(x)=f_nxⁿ+ ... +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= (0≤i≤k)

【程序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;

}

试题六

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

【程序６说明】

本程序从n种不同重量、不同价值的物品中选取一部分物品。要求在不超过限定重量

limw的前提下，使被选取的那些物品的总价值较大。这里约定limw不超过n种物品的重量总和,也没有一种物品的重量超过limw，并且各物品的价值都大于0。

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

【程序６】

#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;

}