试题 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 )”框移至⑤处，则流程图执行的结果是什么?

[流程图]