中国科学院软件研究所 一九九六年招收硕士学位研究生入学考试试题 试题名称：软件基础 一．（10分） 1．给出下列表达式的逆波兰表示（后缀式）：（各1分） a+b*c； a≦b+c∧a>d∨a+b≠e 2．写出下列语句的逆波兰式表示（后缀式）：（各1分） ﹤变量﹥：=﹤表达式﹥ IF ﹤表达式﹥ THEN ﹤语句1﹥ ELSE ﹤语句2﹥ 3．写出算术表达式 A+B*（C-D）+E/（C-D）**N 的四元式、三元式和间接三元式序列。（各2分） 二．（10分）写一文法，使其语言是偶数的集合，但不允许有以0居首的偶 整数。 三．（10分）LRU算法的基本思想是什么？有什么缺点？给出该算法的流程图。 四．（10分）设有一个具有n个信息元素的环形缓冲区，A进程顺序地把信息写 入缓冲区，B进程依次地从缓冲区读出信息，回答下列问题： 叙述A、B两进程的相互制约关系； 判别下列用P、V操作表示的同步算法是否正确？如果不正确，试说明 理由，并修改成正确算法。 var buffer：array 0..N-1 of T; in,out: 0..N-1; var S1,S2:Semaphore; S1:==0; s2:=N; in:=out:=0; Procedure A: begin repeat 生产数据m; P(S2); buffer(in):=m; in:=(in+1) mod N; V(S1); forever end Procedure B: begin repeat V(S2); m:=buffer(out); 消费m; out:=(out+1) mod N; P(S1); forever end 五．（10分）试简述UNIX的文件读写过程。 六．（10分）试给出运算变量均为整数的简单算术表达式所需最少临时单元个 数的算法（假定不许用代数规则变更表达式的计值顺序）。 例如：A+B*C需要一个临时单元为（B*C）；（A+B）*（C+D）+E则 需要两个临时单元，一个为C+D，另一个既为A+B又为（A+B）*（C+D）。 七．（10分）已知三维空间（直角坐标系）有n个点，请编写一个函数过程， 求通过某一特定平面的点数。 八．（13分）编写一过程，对一个n×n矩阵，通过行变换，使其每行元素的平 均值按递增顺序排列。 九．（17分）请编写一过程，对具有n个整数的序列进行二叉树排序。