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

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

[说明]

流程图描述了某织布厂—生产管理系统的部分处理流程。用户订单经处理1输入，在订货文件和客户文件中添加新的记录。然后由系统逐项显示订货需求，通过人机交互在处理2中进行排产，产生排产单和排产文件，并更新订货文件中的相关字段内容。系统产生的排产单交给值机人员生产，一份订单中同类的布可能安排在几台织机上生产。产品合格后填写成品卡。系统每天通过处理3输入成品卡，参照排产文件检查其合法性后产生日成品文件。日成品文件经处理4、处理5分类汇总后输出机台日产量报表。同时处理6根据日成品文件和订货文件，对产量进行汇总，并更新订货文件中的相关字段内容·，最后再通过处理7输出订单完成情况表。

输入单据、输出表格与文件的组织情况说明如下：

订单：订单号，客户名称，客户地址，订货日期，布类名称，订货数量，应交货日期

成品卡：排产单号，订单号，生产日期，织机号，班次，布类代码，产量，值机员代码

排产数据：排产单号，投产日期，织机号，班次，计划生产量，用料说明

排产单：排产单号，订单号，织机号，班次，投产日期，布类代码，布类名称，计划生产量，用料说明

布类代码对照表：市类代码，布类名称

客户文件：订单号，客户名称，客户地址

排产文件：排产单号，订单号，织机号，班次，布类代码，计划生产量

     订单完成情况表

其中完成情况有三种：①已完成，②已排产但尚未完成，③尚未排产

[问题 1]

分别指出订货文件和日成品文件至少应包括哪些数据项。

[问题 2]

指出处理 4 分类的第一、二关键项。

[问题 3]

为提高处理 6 的效率，流程图中需作何补充?( 用文字简述 )

[流程图1]

试题 2

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

[说明]

将自然数依次排列成如下所示的数码排列：

1 2 3 4 5 6· 7 8 9 l0 l1 l2 l3 14 l5 l6 ...

流程图5a和流程图 b 都能输出从头数起的第 1 个数码。

流程图中 K 存放输出数码，N 存放自然数，M 存放自然数的位数。图中↑表示乘幂运算，「W」表示不超过 W 的最大整数。

流程图 a 采用逐个增添自然数的方法。

流程图 b 采用一次增添位数相同的自然数序列段的方法。
[问题 1]

填充这两个流程图中的①～⑧，使他们成为完整的流程图。

[问题 2]

比较流程图a 和流程图b 的优缺点。

[流程图]  

试题 3

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

[说明]

流程图的功能是对预处理后的正文进行排版输出。

假定：预处理后的正文存放在字符串 S 中，S 由连续的单词组成，单词由连续的英文字母组成。在预处理过程中已产生以下信息：

变量 NW 存放正文中单词的个数，数组元素 SL(1)存放正文中第 1 个单词在S中的字符位置，SN(1) 存放正文中第 1 个单词的长度。规定 S 中的字符位置从 1 开始计数，每个字符占一个位置。字符串S中的某个单词可用如下的子串形式来存取：

S( 单词起始位置：单词终止位置 )

并规定在对字符串( 或子串 )赋值时，赋值号两端的字符串( 或子串 )长度必须相等。

排版输出的要求如下：

(1)每行输出 80 个字符；

(2)一个单词不能输出在两行中；

(3)除最后一行外，所有输出行既要左对齐又要右对齐。即每行的第一个字符必须是某个单词的第一个字母，最后一个字符必须是某个单词的最后一个字母；

(4)单词之间必须有 1 个或 1 个以上的空格；

(5)最后一行只须左对齐，且单词之间均只有一个空格；

(6)使字格尽可能地均匀分布在单词之间，即同一行中相邻的单词间的空格数最多相差 1。

假定正文中至少有两个以上单词，每个单词的长度均小于 40。此外，流程图中省略了数据的输入部分。图中「W」表示不超过W的最大整数。

[问题1]

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

[问题2]

图中的“输出末行”框未经细化。如果将图中的虚线部分复制到“输出末行”框上，那么复制部分应作怎样的修改?可用图中所标的 a，b，…，j来回答，例如 a 改成 1→I ：删除 b。

[问题3]

如将图中开始部分的 SN(1)→LN 改成 0→LN；2→I 改成 1→I，则修改后的流程图是否正确。

[流程图]

试题4

阅读下列说明和 E—R 图，回答问题 1～3，把解答写在答卷的对应栏内。

试用 SQL 语言定义教师( TEACHER )模式。回答时字段的数据类型以及题中未指明的名字由考生自己定义。

[说明]

设有下列关于教务管理系统的 E—R 图。图中矩形表示实体，圆表示属性，双圆表示关键字属性，菱形表示实体间的联系。为了答题的方便，图中的实体和属性同时给出了中英文两种名字，回答问题时只须写出英文名即可。

[问题1]

写出与上述 E—R 图对应的关系模式，并用下划线标明相应的关键字。

[问题2]

问题 1 中的关系模式属于第几范式? 如果属于第三范式，则说明理由；如果不属于第三范式，则将它化为第三范式( 回答时只须写出修改的部分 )。

[问题3]

试用 SQL 语言定义教师( TEACHER )模式。回答时字段的数据类型以及题中未指明的名字由考生自己定义。

[E-R]图

试题5

阅读下列说明和流程图5．3．4—8，回答问题1和2，把解答写在答卷的对应栏内。
[说明]

流程图对顺序存贮的二叉树按非递归形式进行后序遍历打印。顺序存贮的二叉树存放在数组 data(1：m) 和 right(1：m)中，data 存放结点的值，right 存放指针值。

本题中顺序存贮的二叉树是指对树中任意两个结点 nodel 和 node2 ( 它们在顺序存贮数组中的下标分别为 q₁和q₂)，它们的指针值满足下列条件：

(1)如果nodel是根结点，则q₁＝1。如果从nodel出发按前序遍历所得到的下一个结点是node2，则q₂＝q_l+1。

(2)如果 nodel 的右后件是 node2，则

如果 nodel 存在左后件，则 right(q₁)＝q₂+1；

如果 nodel 不存在左后件，则 right(q₁)＝-(q₂+1)；

(3)如果 nodel 没有右后件，则

如果 nodel 存在左后件，则 right(q₁)=1

如果 nodel 不存在左后件，则当 nodel 是按前序遍历的最后一个结点时，right(q₁)=0；否则right(q₁)=-1。

例如，二叉树( 下图 ) 的顺序存贮情况如右下表。

流程图中 stack(1：N) 是遍历过程中存放顺序存贮数组下标的栈，sign·(1：N) 是配合栈操作设立的标志位( 第一次进栈时值为1，第二次进栈时值为2 )，变量 top 是栈顶指针，变量 first 是顺序存贮二叉树的首指针。若树空，则 first＝0；否则，first＝1。指针 pointer 用来指出结点在数组中的下标。

假定给出的顺序存贮二叉树是正确的，且 stack 和 sign 都足够大，不会溢出。
[问题1]

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

将流程图中的“打印 data( pointer )”框移至⑤处，则流程图执行的结果是什么?

[流程图]

试题6

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

[程序说明]

子程序 MOVE 是将地址为 A 开始的 N 个存贮单元移动到地址为 B 开始的 N 个存贮单元中，对于两个区域互相重叠的情况也能正确处理。

主程序在 GR1 中给出存放子程序所需参数的起始地址，参数的存放形式如下图所示。

[程序]

试题7

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

[程序说明]

对于正整数 n ，输出其和等于 n 且满足以下限制条件的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如n=4，程序输出为

4 = 4

4 = 3 +1

4 = 2 +2

4 = 2 +1 +1

4 = 1 + 1 + 1 + 1

程序中给出了分别采用递归和非递归解法的两个函数 rd() 和 nd()。

函数 rd( )采用递归解法，它有两个参数n和k。其意义分别是被分解和式的数n，及当前第k深度分解。算法思想是对n的所有合理的和式分解，将分解出的数(称为和数)存于数组a[ ]中。当其中一个分解已不再需要进一步分解时，即找到一个解，将存于数组 a[] 中的一个完整和式的和数输出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调整用分解和式函数。

函数 nd( )以要分解的数为参数，另开设一个数组 r[]，用于存贮当前还未分解的余数。

在求一个解的第k步时，a[k] 为第 k 个和数，r[k] 为相应的余数。当找到一个分解后( 此步 r[k] 等于 0 )，输出解，并作回溯处理，从当前k退回到第－个不为1的和数，将其减1，并将其余数加1，准备去找另一个解；否则，生成下一步的分解和数与余数。

[程序]

#define MAXN 100

int a[MAXN]，r[MAXN]；

rd(int n，int k)

{ int j，i；

for ( j= __①__ ;j>=1：j-- )

{ a[k]=j；

if ( __②__ )

{ printf( "％d = ％d"，a[0]，a[1] )；

for ( i=2；i<=k；i++ )

printf( "+％d"，a[i] )；

printf( "\n" )；

}

else __③__

}

}

nd (int n)

{ int i，k；

k=0；r[0]=n；

do

{ if ( __④__ )

{ printf( "％d=％d"，a[0]，a[1] )；

for ( i=2；i<=ks i++ )

printf( "+％d"，'a[i] )；

print( "\n" )；

while ( k>0&& __⑤__ )k－－；

if ( k>0 ){ a[k]--；r[k]++；}

}

e1se { a[k+1]=__⑥__；

r[k+1]=r[k]-a[k+1]；

k ++；

} 

} while(k>0)；

} ；

int test_data[ ]={3，4，5}；

main()

{ int i；

for ( i=0；i<sizeof (test_data)/sizeof(int)；i++ )

{ a[0]=test_data[i]；

rd( test_data[i]，1 )；

printf( "\n__________\n\n" )；

nd( test_data[i] )；

printf( "\n_________\n\n" )；

}

}

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

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