当前位置：问答库＞考研试题

一、应用题

1． 三个进程P1、P2, P3互斥使用一个包含N P1每次用produce （N ＞0）个单元的缓冲区。（ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中；P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

【答案】定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区，程序如下：

2． 已知一棵二叉树的后序遍历序列为EICBGAHDF , 同时知道该二叉树的中序遍历序列为CEIFGBADH ， 试画出该二叉树。

【答案】该二叉树如图所示：

图

3． 设二叉树BT 的存储结构如表：

表 二叉树BT 的存储结构

其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分別为结点的左、右孩子指针域data 为结点的数据域。试完成下列各题：

（1）画出二叉树BT 逻辑结构；

（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列： （3）画出二叉树的后序线索树。

【答案】（1）二叉树的逻辑结构如图1所示：

图1

（2）前序序列：ABCEDFHGIJ 中序序列：ECBHFDJIGA 后序序列：ECHFJIGDBA

（3）:二叉树的后续线索树如图2所示：

图2

4． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

5． 请写出应填入下列叙述中（ ）内的正确答案。

某一工程作业的网络图如图1所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天 数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。

完成此工程的关键路径是（A ）完成此工程所需的最少天数为（B ）天，此工程中具有最大充，充裕天数是（D ）裕天数的事件是（C ）。关键路径上的事件的充裕天数是（E ）。

图1

【答案】A. 0-2-6-9-11; B. 20; C.事件顶点1、5和7各充裕两天；D. 4天；E. 0