1991年度高级程序员级下午试题

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

[说明]

流程图实现下列递归函数的计算。递归函数定义如下：

其中 n，x，y 均为非负整数。

递归函数的计算使用了三个栈，它们分别用数组 N(1：5000)，X(1：5000)，Y(1：5000) 来存放，top 为栈顶指针，中间计算结果和最终计算销果均存放在变量 F 中。
[问题1]

填充流程图中的①～⑤，使之成为完整的沉程图。
[问题2]

指出应在流程图的哪些位置(用⑤～⑨表示 y 上增加检测错误的流程图，并分别指出这些位置能报告哪些错误信息。

试题 2

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

[说明]

流程图用来计算矩阵 K，Y 的乘积 Z，其中 X，Y，Z 均为 m 行 m 列的下三角方阵，即行号小于列号的元素均为零的 m 阶方阵。为节省存贮空间，它们均以压缩形式( 不存放矩阵上三角中的零元素 )分别按列存放在一维数组 A，B，C 中。

例：若

则： A=(5，7，8，3，4，1)

流程图中省略了 A，B 的输入和 C 的输出，p 表示第 j 列元素在一维数组中的起始位置。

[问题1]

填充流程图中的 ①～④，使之成为完整的流程图。

[问题2]

程序执行完时，t的值是多少。
[流程图]  

试题 3

阅读下列说明和流程图，回答问题 1～4 ，把解答写在答卷的对应栏内。

[说明]

流程图是采用结构化分析方法画出的某考务处理系统的数据流图 (DFD)。图中圆圈表示加工；→表示数据流，表示数据源终点；〓〓表示文件。该系统有如下功能：

(1)对考生送来的报名单进行检查。

(2)对合格的报名单编好准考证号后将准考证送给考生，并将汇总后的考生名单送给阅卷站。

(3)对阅卷站送来的成绩清单进行检查，并根据考试中心制订的合格标准审定合格者。

(4)制作考生通知单送给考生。

(5)进行成绩分类统计(按地区、年龄、文化程度、职业、考试级别等分类)和试题难度分析，产生统计分析表。

部分数据流的组成如下所示：

报名单＝地区+序号+姓名+性别+年龄+文化程度+职业+考试级别+通信地址

正式报名单＝报名单牛准考证号

准考证＝地区+序号+姓名+准考证号牛考试级别

考生名单＝{准考证号+考试级别} ( 其中{w}表示 w 重复多次 )

统计分析表＝分类统计表+难度分析表

考生通知单＝考试级别十准考证号+姓名+合格标志+通信地址
[问题1]

指出一层之一(　图(c)　)的数据流图中　①，②，③　的数据流名。
[问题2]

指出0层(图(b))数据流图中有什么成分可删去。
[问题3] 

指出一层之二( 图(d) )的数据流图中在哪些位置遗漏哪些数据流；也就是说，要求给出漏掉了哪个加工的输入或输出数据流的名字。例如，加工2.5的输出数据流“难度分析表”。
[问题4]

指出考生名册文件的记录至少应包括哪些内容。

试题4

阅读下列说明和流程图，回答问题 1～3，把解答填入答卷的对应栏内。

[说明]

流程图描述了某厂五金仓库物品的出库单处理流程。该厂有 50 个车间和科室，五金仓库内有近万种物品。仓库管理人员凭入库单收进物品，凭出库单发出物品。系统要求每天根据出库单更新物品库存文件；当某物品更新后的库存量低于该物品的最低库存量时，输出订购清单；每月还要以车间和科室为单位输出该部门一个月内领取各类物品的总数( 称为月报表 )。

规定每张出库单由两位操作员分别输入，以检查操作员的输入错误。

物品库存文件按物品编号排序，其格式如下：

其中“最高库存量”是指该物品允许存放在库中的最大值。

领料单位文件按领料单位编号排序，其格式如下：

出库单格式如下：

[问题1]

指出处理2排序时的第一关键项和第二关键项。
[问题2]

指出图中A，B所指的文件名称及其在处理1中的作用。
[问题3]

若把流程图改成入库单处理流程，并且入库单的格式如下：

那么，除了将图中的“出库”改成“入库”外，还应作何修改。
  

试题5

阅读下列说明和流程图。回答问题 1 和 2，把解答填入答卷的对应栏内。

流程图描述了某高校图书订购与编目系统的处理流程。全校的图书典藏在校图书馆和各系的资料室中。学校每年分若干批向出版单位订购图书，同一批订购的图书将陆续邮寄到学校。出版单位在寄出图书的同时附上到书清单和发票，发票上仅给出一份到书清单中书的总册数和总金额。学校收到图书和发票后，

参照订购单进行验收，然后进行编目，并把有关信息存放在：书种文件、书名文件、作者文件、复本文件中，以供读者检索用。

书种文件记录了每种书的有关信息。所谓一种书是指同一作者、同一书名、同一出版单位、同一出版年份出版的书。例如，1990 年王某在高等教育出版社出版了《高等数学》( 印数8000册 )和《 高等代数 》( 印数 5000 册 )，则王某在 1990 年出版了两种书。在全校的藏书中，如果一种书只有一册，则该书的信息存放在书种文件中；如果一种书有多册，则其中一册书的信息存放在书种文件中，其余的书作为复本将信息存放在复本文件中。复本文件的结构与书种文件的结构相同。每种书都有一个书号，书号唯一地标识了一种书。在书库中，每册书有一个登录号，登录号唯一地标识了一册书。此外，为了图书检索的方便，将图书按学科分类，分类号用来标识不同的学科领域。

各类单据和文件的结构如下：

订购单：订购批号，书名，作者名，出版单位，出版年份，单价，订购册数，订购部门代码，订购日期

到书清单：订购批号，书名，作者名，出版单位，出版年份，单价，册数

发 票：订购批号，发票号，总册数，总金额

书种文件：分类号，登录号，书名代码，作者代码，出版单位，出版年份，单价，复本标志，典藏部门代码，借出标志

其中：复本标志用来指示该种书在书库中有没有复本；对于书名相同的若干种书，书名代码是相同的。

书名文件：书名代码，书名

作者文件：作者代码，作者名
[问题1]

指出验收文件至少应由哪些数据项组成。
[问题2]

由于处理 5 和处理 6 的分类，可能导致分类后的文件中一张发票无法找到与它对应的那些书，从而当一组发票的金额之和与一组到书清单中的书价之和不等时，无法知道是哪一张发票和哪一份清单不一致。如果仍使用原流程图，那么到书清单文件的结构作何改动后，能找出不一致的发票和相应的书目。
[问题3]

若在书种文件中增加数据项“书号”，则如何重新设计复本文件的结构，使数据冗余最小。

试题6

在 COMET 型计算机上可以使用试卷上所附的 CASL 汇编语言。阅读下列程序说明和 CASL 程序，把应填入其中__n__处的字句，写在答卷的对应栏内。

[程序说明]

本子程序将存贮字 A 中的第 a 位起的 n 位二进位，搬至存贮字 B 的第 b 位起的 n 位中。

(1)主程序在 GR1 中给出子程序所需参数的起始地址。

(2)子程序所需参数个数和含义如下图所示。

(3)0≤a≤15； 0≤b≤15； 1≤n≤16； a+n≤16； b+n≤16。

(4)存贮字B中，除b开始的n位外的其它二进位应保持原值。
[问题]

在程序中的①～⑧处各填入一条正确的指令，以完成此程序。除非必要，标号栏不要填写。
[程序]

试题7

阅读下列程序说明和 C 程序，把应填入其中__n__ 处的字句，写在答卷的对应栏内。

[程序说明]

本程序用来对英文文献中出现的单词按下列计算公式统计其使用频度：

程序中用一个根结点为，treeroot 的分类二叉树存放文献中的每个英文单词及其在文献中的使用次数。对于二叉树中的每个结点中的单词，按字典序比较大小，小的存放在它的左子树中，大的存放在其右子树中。当统计完毕后，程序将按中序遍历该分类二叉树，得到一个按英文单词字典序分类的单词表( LIST * result )，并且按单词的使用次数为关键字降序输出统计结果。

程序调用了如下一些函数：

(1)函数 binary_tree 将某单词按二分查找法插入分类二叉树，中并统计该单词在文献中的使用次数。

(2)函数 travel_tree 按中序遍历分类二叉树，并形成相应的单词表。所谓中序遍历，即先访问其左子树，然后访问根结点，最后访问其右子树。

(3)函数 getword 从存放英文文献的数据文件“TEXT.H”中取出一个单词，放入字符数组 keyword 中。如果遇到文件结束标志，则返回 0；否则，返回 1。为简单起见，假定每个英文单词长度不超过 20 个字母。

(4)函数 sort_list 将单词表以单词的使用次数为关键字，按降序排序。

(5)函数 display_list 输出单词表中各单词和它的使用频度。

(6)函数 strcopy(s1，s2) 将字符串 sl 拷贝至字符串s2。

(7)函数 strcmp(s1，s2) 按字典序对两字符串 s1 和 s2 进行比较。若 s1 大于 s2，则返回一个正整数；若 s1 等于s2，则返回 0；若 s1 小于 s2，则返回一个负整数。

程序清单中省去了上述编号为(3)，(4)，(5)，(7)的函数的内容。
[程序]

#include <stdio.h>

#include <alloc.h>

#define EMPLY 0

#define MAXLEN 21

typedef struct tree

{ charword[MAXLENl

int count；

struct tree *leftson；

struct tree *rightson；

} BINARY；

typedef struct

{ char word [MAXLEN]；

int count；

} LIST；

BINARY * treeroot＝EMPTY；

main()

{ LIST xresults

FILE *fp，*fopen()；

char keyword[MAXLEN]；

int total_word＝0；

fp＝{ open("TEXT.H"，"＼")；

while ( getword(keyword，fp) )

{ binary_tree(keyword)；

total word++；

}

fclose(fp)；

result＝( LIST * )malloc(total_wotd * sizeof(LIST))；

travel_tree( treeroot，result )；

sort_list(resuli，total_word)；

display_1ist(result，total_word)；

}

hnary_tree(keyword)

char *keyword；

{

BINARY *ptr，*temp；

int strcmp_resul；

temp=EMPTY；

prt＝treeroot；

while ( ptr=EMPTY )

{ strcmp_result＝strcmp(keyword，ptr--*word)；

if (strcmp_result；；0)

{ ptr-~count++

returnI

}

else

{ temp＝ptr；

if ( strcmp_result>0 )

ptr＝ __①__ ；

else

ptr＝ __②__ ；

}

}

ptr＝(BINARY *)malloc(sizeof(BINARY))；

ptr→rightson=ptr→leftson=MPTY；

ptr→count＝1；

strcopy(keyword，ptr→word)；

if ( temp＝＝EMPTY )

treeroot=ptr；

else

if (strcmp_result~0)

temp__③__ptr；

else temp→ __④__ ＝ptr；

}

travel_tree(root，result)

BINARY *root；

LIST result[]； ·

{ static x＝0；

if ( root==EMPTY ) __⑤__ ；

else

{ travel_ tree( __⑥__ ，result)；

strcopy(root’word，result[x).word)；

result[x++].count＝root→count；

travel tree( __⑦__ ，result)；

}

}

strcopy(sl，s2)   /* - Copy string S1 to S2 - */

char *S1，*S2；

{ while( __⑧__ != '＼0')；}

试题8～10 略（COBOL、FORTRAN、PASCAL）

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