算机软件资格水平考试高级程序员下午试题

1、1999年中国计算机软件资格水平考试高级程序员下午试题从下列的3道试题（试题一至试题三）中任先 2道解答 如果解答的试题数超过2道，则题号小的2道解答有效试题一阅读以下说明和流程图，回答问题1至问题3,将解答写在答卷的对应栏内。 【说明】本流程图描述了某仓库物品入出库管理的处理流程。每张入库单或出库单 都由两位操作员分别录入，经处理1或处理3输入系统后作合法性检查，并将 合法的入库单或出库单记入入库单文件或出库单文件。然后通过处理2或处理4实时更新库存文件。处理5每周执行一次，它依次检查库中的每一种物品，当 某物品的库存量小于该物品的最低库存量时， 制订采购计划，输出订购单。处理 6和处理7每

2、月执行一次，处理6将入库单文件和出库单文件合并成月入出库 文件，并根据统计的要求对其进行排序。处理 7进行统计，产生月报表，并把 该月合并后的月入出库文件添加到月入出库后备文件中，以备日后查找，最后清除入库单文件、出库单文件和月入出库文件。系统中某些文件和报表的格式如下：库存文件记录：物品编号+名称+规格+库存量+最低库存量+最咼 库存量（其中“最高库存量”指该物品允许存放在库中的最大值）入库单文件记录：日期 +物品编号+数量出库单文件记录：日期+物品编号+数量月报表格式：物品编号日期入库数出库数x x x xx xx xx xx xx xx xx xx xx x当月小计x x xx x xx

3、 x x xx xx xx xx xx xx x【问题1】指出处理3能检查出库单中的哪些错误【问题2】指出月入出库文件的记录格式.【问题3】指出处理6排序的第一和第二关键字。流程图试题二阅读以下说明和流程图，回答问题 1至问题3，将解答写在答卷的对应栏 内。【说明】有一种游戏，其规则如下：有一个3X 3的方格，每个方格中只可画 + ' 符号或符号，表示该方格的值。图（a）定义了各方格的位置，表1为每 个方格位置定义了与其相关联的位置集，各方格的初值如图（b）所示。游戏开始后，每次可选一个值为 + '的方格位置，然后根据表1将该位置所对应的每个相关联的位置上的符号重画成与其不同的

4、符号，即将 + '重画成一， 将-重画成 + '。重画操作可用所选的位置编号来描述。例如在图（b）所 示的情况下，选择位置4时，重画结果如图（c）所示。经过连续的若干次这样 的操作后，当3X3方格呈现出图（d）所示的图形时，表示获胜；当呈现出图（e） 所示的图形时，表示失败。下列流程图旨在输出从初始状态出发直至获胜的重画操作（即所选的位置 编号）序列。图中假定数组A0.8 存放3X 3方格的值，数组c0.81.5 存放表1所示的各方格位置的相关联的位置集、数组d0.8 存放各方格位置 的相关联的位置个数，数组元素S1Sk存放各次重画操作所对应的位置编 号，变量N存放3X 3方格

5、中当前的 + '符号的个数。0 1 2 -+ -+ + + -3 4 5- + -+ - + - + -6 7 8-+ -+ + + -图(a)图(b)图(c)图(d)图(e)表1方格位置及其相关位置集的对照表00 1 3 410 1 221 2 4 530 3 641 3 4 5 752 5 863 4 6 776 7 884 5 7 8【问题1】填充图中的一。【问题2】图中的应与A、B C中的哪一点连接。【问题3】如果每次由游戏者选择方格改由程序自动枚举选择，那么，为从初态出发 求出所有可能的获胜重画操作序列，在哪些情况下需要进行回溯处理。【流程图】CW 数組A置初值k=D（重画）

6、N=1T游戏韜选择/m=dij|k=k+l重iSi重iSi/输出:失败” /输出讯1卜址/AciIj= - *A呗=卞4j=j+i试题二阅读以下说明和流程图，回答问题 1和问题2 ,将解答写在答卷的对应 栏内。【说明】本流程图采用状态矩阵方法将已知字符序列翻译成实数（其句法图如图3.1 所示）。本题的状态矩阵分成两部分，语义动作矩阵 FM和状志转换矩阵SM，它 们分别存放每个状态遇到某字符时应执行的语义动作以及执行动作后应转移到 的新状态。本流程图从0状态出发逐个读入字符，在执行了 FM中相应的语义动作 后，SM中指出的相应新状态，重复这一过程，直至到达9状态或10状态。9状 态表示已正确地把

7、该字符序列翻译成实数（注意：此时已多读进实数后的下一个 字符）；10状态表示出错。图3.1某语言的实数句法图状态转换矩阵SM新 状态字符类+或一（类别0）数字（类别1）小数点（类别2）字符E（类别3）其它字符 （类别4）状态01231010110101029246931051010104999595969678101010710101010898999语义动作矩阵FM语义函数字符类+或（类别0）数字（类别1）小数点（类别2）字符E（类别3）其它字符 （类别4）状态0f1f2f0f7f71f7f0f7f72f6f0f0f63f7f7f7f74f6f3f6f0f65f6f3f6f66f5f7f7f

8、77f7f5f7f7f78f6f5f6f6f6现有以下语义动作函数： fO:空函数，不做任何操作。fl ：按当前字符确定实数符号sign为1或-1。f2 :翻译实数的整数部分值（求 m ）。f3 :翻译实数的小数部分值（求d ）。f4 :按当前字符（幕的正负号）确定求幕所用的因子PS（ 10.0或0.1）f5 :翻译实数的幕（求p ）。f6 :求实数的值 R=sign*（m+d）*pf7 :输出错误信息。【流程图】C 3°g o P J 1A ps- 10A d- 0.0弘0，2 0, sign- 1, m j 0,0k type （str i） 注：钞餐（）返回字符的Q类别号（0-

9、4）5*- SM s, k閑用f语义动作函数注：设已知实数字符串存于字符数组 str中。【问题1】将状态转换矩阵SM中一处的正确内容填入答卷的对应栏内将语义动作矩阵FM中一处的正确内容填入答卷的对应栏内试题四在COMST型计算机上可以使用试卷上所附的 CASL汇编语言，阅读程序说 明和CASL程序，把应填入(n)处的字句，写在答卷的对应栏内。【程序4.1说明】本子程序是对15位二进位串，求它的奇校验位，生成 16位二进位串， 使16位二进位串中有奇效个1。进入此子程序时，15位二进位串在GR1的第1位至第15位，假定GR1 的第0位是0，求得的奇校验位装配在 GR1的第0位上。【程序4.1】S

10、TARTBEG PUSH 0，GR2PUSH 0，GR3LEAGR3 1(1)L1(2)SLLGR2 1LEAGR31，GR3L2JZEL3JMPL1L3(3)STGR3WORKADDGR1WORKPOPGR3POPGR2RETWORKDS1END【程序4.2说明】调用该子程序时，主程序在 GR1中给出存放子程序所需参数的起始地址参数的存放次序如下图：(GR1)+ 01r+ 1n+ 21B【程序4.2】STARTSUM LDGR2LD GR30，GR11，GR1子程序SUM是将存贮字A起的n(n > 0)个字求和,并将结果存于存贮字 B中。LEA GR0 0L5 ADD GR0 0, G

11、R2LEA GR2 1, GR2_JNZ L5L3 _(5)_ST GR0 0, GR3RETEND试题五阅读下列程序说明和C代码，将应填入(n)处的字句写在答卷的对应 栏内【程序5说明】本程序实现两个多项式相乘。多项式用链表表示，链表上的各表元按多项式的幕指数降序链接。例如：f(x)=5.7x 15 + 4.8x 6 + 9.65156r05.74.8久65设两个多项式f(x)和g(x)分别为f(x)=fnxn+ . +f1X+fo g(x)=g mA . +g 1X+3其积多项式为 s(x)=f(x)g(x)=skxk+ . +s1X+S0其中 k = n + m , s i = E /

12、u * gv (0 < i < k)u+v=i【程序5】#i nclude <stdio.h>#i nclude <malloc.h>typedef struct elem int in dex; double coef; struct elem *n ext; POLYNODE; void write (POLYNODE *g) POLYNODE *p = g;while (p) printf(“8.4f” , p ->coef);if (p->index) printf("*x %d", p->index);if (

13、p->next && p-next->coef > 0 ) printf("+"); p = p->n ext; printf( “ n”)；mai n() POLYNODE *f, *g, *s, * in poly(), *polymul();POLYNODE *reverse(POLYNODE *g) POLYNODE *u = NULL, *v = g, *w;while(v) w = v->n ext; v->n ext = u; u = v; v = w; return u;POLYNODE *polymul(

14、POLYNODE *f, POLYNODE *g) POLYNODE *fp, *gp, *tail, *p = NULL, *q;int i, maxin dex; double temp;maxin dex = f->in dex + g->in dex; g = reverse(g);for(i = maxi ndex; i >= 0; i-) fp = f; gp = g;while (fp != NULL && fp->index > i) fp = fp->next; while (gp != NULL && gp

15、->in dex < i- fp->in dex) gp = gp->n ext;temp = 0.0;while(fp && gp)if (fp->i ndex + gp->i ndex = i) temp += fp->coef * gp->coef; fp = fp->n ext; gp=gp->n ext;else if (1) fp = fp->n ext;else gp = gp->n ext;if (temp != 0.0) q = (POLYNODE *)malloc(sizeof(POLY

16、NODE); q->in dex = i; q->coef = temp; q->n ext = NULL;if (2) p = q; else _(3)_;tail = q;g = reverse(g); return p;POLYNODE * in poly() POLYNODE *u, *v, *h = NULL, *p; in t in dex; double coef; printf("Input index(<0 for finish) "); scanf("%d", &index); while (in de

17、x >= 0 ) printf( “ In put coef “)； scanf ("%1f", & coef);p = (POLYNODE *)malloc(sizeof(POLYNODE);p->in dex = in dex; p->coef = coef;v = h ;while (v != NULL && in dex < v->in dex) u = v; v = v->n ext; if (v = NULL | index > v->index) p->n ext = v; if (

18、v = h )(4); else(5);else v->coef += coef;printf("Input index(<0 for finish) "); scanf("%d".&in dex); return h; 试题六阅读下列程序说明和C代码，将应填入_( n)_处的字句写在答卷的对 应栏内。【程序6说明】本程序从n种不同重量、不同价值的物品中选取一部分物品。要求在不超 过限定重量limw的前提下，使被选取的那些物品的总价值较大。这里约定limw 不超过n种物品的重量总和，也没有一种物品的重量超过limw ，并且各物品的 价

19、值都大于0。程序中，n种物品被顺序编号为0、1、2、n-1。【程序6】#i nclude <stdio.h>#define N 100double limw;in t optsN; /*存储临时最佳的选择方案，当optsi为1，物品i在解中*/struct elem double weight;double value; aN; /*物品的重量和价值信息*/int k, n ;struct int flg; /*物品的考虑状态：0:不选，1:将被考虑，2：曾被选中*/double tw; /*已达到的总重量*/double tv; /*期望的总价值*/ twvN; /*当前候选解中

20、各物品的考虑状态，以及候选解的状态*/mai n() double maxv, fin d();printf("Enter number of matter. "); scanf("%d", &n);prin tf("E nter limit of weight. "); scan f("%1f", & imw); prin tf("E nter weight and values of matters.");for (k = 0; k < n; k+) scanf(&qu

21、ot;%1f%1f", &ak.weight,& ak.value);maxv = fin d(a ,n);for(k = 0; k < n; k+) if(optsk) pri ntf("%4d", k);prin tf("nTotal value = %1fn", maxv);next(int i , double tw, double tv)/*将考虑 i 号物品 */ twvi.flg = 1; twvi.tw = tw; twvi.tv = tv; 取i号物品在解中的look(i nt i, i nt *f, double *tw, double *tv) /* 状态信息*/ *f = twvi.flg; *tw = twvi.tw; *tv = twvi.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);n ext(0, 0.0, totv);i = 0;while(i >= 0) look(i, &f, & tw, &tv);s