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

阅读下列说明和流程图，回答问题 1 至问题 4，把答案填入答卷的对应栏内．
[说明]

某单位的职工工资单有如下格式：

其中：②～⑧是较稳定的项，只在特殊情况(如人事变动，工调，房调等)时才会因人不同面有所修改，

⑧～⑿项的金额只有部分职工才有，

⑥⑦两项的金额对所有职工都相同，

⑩⑾两项的金额是每月不同的，

⑿⒀两项的金额是由工资处理系统计算出来的。

为减少贮存数据的冗余度，将职工的工资信息分成三个文件：基本工资文件，月津贴文件，还歙文件．还软文件用采存贮借款职工的各月还款额。

当职工的月收入超过免征调节税限额时，要依法纳税，因此财会部门还要代征个人调节税，且把它话入纳税寓件后交税务部队
流程图是职工工资处理系统的部分流程（未包括基本工资文件的形成和修改，还款文件的形成和添加）。最后的工资清单是按部门顺序打印的。
[问题1]

根据说明，设计基本工资文件的记录格式。设计时要考虑尽量减少数据存贮的冗余度。
[问题2]

根据说明，设计月津贴文件和还款文件的记录格式。设计时要考虑在文件处理时能减少文件的读写次数。
[问题3]

为减少文件读写次数，基本工资文件，月津贴文件和还款文件应分别按哪些关键项目进行排序?
[问题4]

指出“处理3”中能发现哪些错误7 
[流程图]

试题二

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

流程图用以对长度为 20 的字符串进行如下变换： ·

① 将字符串中连续的多个空格压缩成一个空格；

② 删除字符串中所有的“；”字符；

③ 将字符串中每个“↑”字符替换成“**”（两个字符）；

④ 将字符串中所有连续出现的“：=”（看作两个字符）替换成单个字符“=”，

⑤ 字符串中的其它字符保持不变。

流程图中数组 CHAR 用来存放输入的字符串，每个数组元素存放一个字符， 数组 L 用来存放变换后的字符串，逻辑变量BLANK 取值为“true”或“false”。 
[问题1]

填充流程图2．1中的①～⑤，使之完成上述变换（每处只填一个“a→b”或“a:b”型的字句）。
[问题2]

若将流程图中的Ⅰ、Ⅱ、Ⅲ框分别作如下修改

则变换工作将在原数组 CHAR 中进行，但修改后的流程图对某些字符串不能变换出正确的结果。试用修改后的流程图分别对下列两个输入串的前 14 个字符进行变换，并写出它们变换后的结果，即 CHAR[I]～CHAR[J] 的内容。

(1)□□□X:=A↑B + C↑D；□□□□□□

(2) A:=B + C↑D↑E□□□；□□□□□□
其中□表示一个空格字符。

该流程图用于把文件 A 和文件 B 合并成按上升顺序分类（排序）的文件 C。已知文件 A 中的关键码小于 M。
[流程图]　

试题三

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

流程图3．1用来实现中序遍历二叉树的算法，二叉树存放在数组 tree 中，每个数组元素存放树中的一个结点，每个结点的形式如下所示；

分别用 tree[i].v，tree[i].1，tree[i].r 来表示第i个结点的“值”，“左指针”，“右指针”。其中左、右指针的值为所指结点在数组中的下标，若指针的值为零，表示它指向空树。图中指针 root，用以指向二叉树的根结点。
[问题1]

填充流程图中的①～⑨，使其按中序遍历二叉树（每处只填一个“a→b”或“a:b”型的字句）。·
[问题2]

将流程图中的 (A) 框移至哪个位置(用图中所示的Ⅰ～Ⅸ回答)，使该流程图的算法从中序遍历变成前序遍历。

[流程图]

试题四

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

在一维数组 A 中存放着 m+n 个整数（m，n≥1）。流程图给出了一种算法，使 A 中前 m 个元素（A[0]～A[m-1]）与后 n 个元素（A[m]～A[m+n-1]）互换位置，并保持其各自原有的内部顺序。

例如，若A为

则互换后A的内容变成

[问题1]

若 m=3，n=4 数组 A 中各元素的值依次为

5，7，4，8，1，2，3

则执行该流程图后，变量 t 和 x 的值是什么?
[问题2]

若 m=6，n=4，数组 A 中各元素的值依次为

0，1，2，3，4，5，6，7， 8，9

则执行该流程图后，将输出什么（每次输出的结果写成一行）？
[问题3]

m，n 满足什么条件时，该流程图中虚线部分的 k 循环只执行一遍

[流程图]

试题五

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

流程图5.1 描述了一个从键盘到打字机的字符（ASCII码）数据流处理流程，在该流程中有三个进程，各进程之间通过缓冲区和信号量交互作用。

设 n₁ 为输入缓冲区 buf1 的大小，n₂ 为输出缓冲区 buf2 的大小。

为了较好地实施多个进程的平行工作，引入了 P、V 操作（基本原语），设 S 是一个信号量，对信号量 S 的 P，操作记为 P(S)，它按下述方式工作

IF S>0

THEN S:=S-1

ELSE 将执行 P 操作的进程放到信号量 S 的等待队列中。

对信号量 S 的 V 操作记为 V(S)，它按下述方式工作

IF 信号量S的等待队列不为空

THEN 从信号量 S 的等待队列中取出一个进程，并唤醒它

ELSE S:=S+1

在流程图 5.2～流程图 5.3 中引入了六个信号量，它们是 nonempty1、nonfull1、nonempty2、nonfull2、S1、S2，其中S1、S2 分别用来实现对缓冲区 bufl、buf2 操作的互斥，S1，S2的初值皆为 1。
[问题1]

填充流程图 5.2～流程图 5.4 中的①～⑧，使之成为完整的流程图（每处只填一个操作）。
[问题2]

信号量 nonfull1，nonempty1，nonfull2，nonempty2的初值分别是什么?
[流程图5.1]

注：cps是精度要求

试题六 略 （CAP-14汇编）

试题七～九 略（FORTRAN、PASCAL、COBOL）

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