软件基础

软件基础 L/5nDOyvm  
一．（10分） z
7Mhfhc  
1．给出下列表达式的逆波兰表示（后缀式）：（各1分） ^bxjnF$V  
a+b*c； K|ZAf  
a≦b+c∧a>d∨a+b≠e @! !-S  
2．写出下列语句的逆波兰式表示（后缀式）：（各1分） Em94\=R  
﹤变量﹥：=﹤表达式﹥ &q^aL^aj  
IF ﹤表达式﹥ THEN ﹤语句1﹥ ELSE ﹤语句2﹥ jaG:'G~  
3．写出算术表达式 55GC ^/  
A+B*（C-D）+E/（C-D）**N S_<mCJ>.-  
的四元式、三元式和间接三元式序列。（各2分） S<o3T`  
jPh!c5&P  
二．（10分）写一文法，使其语言是偶数的集合，但不允许有以0居首的偶 %7(#J#@  
整数。 M,[fKG&u  
)7'fZx?%  
三．（10分）LRU算法的基本思想是什么？有什么缺点？给出该算法的流程图。 = ucH"n;  
hay"-O},M  
四．（10分）设有一个具有n个信息元素的环形缓冲区，A进程顺序地把信息写 pLbx# cj  
入缓冲区，B进程依次地从缓冲区读出信息，回答下列问题： kr%|)"IZH  
1． 叙述A、B两进程的相互制约关系； /^6v7Y+qo  
2． 判别下列用P、V操作表示的同步算法是否正确？如果不正确，试说明 Bru4'?  
理由，并修改成正确算法。 y]8E0i`  
&%HC`U  
var buffer：array 0..N-1 of T; ~WjeH[}o  
in,out: 0..N-1; B+aGqVa M  
var S1,S2:Semaphore; o&k.C`Ge  
S1:==0; s2:=N; M H8ee  
in:=out:=0; vy?/U01i  
^6bz-mu  
Procedure A: &M!o>Sbk.s  
begin L, Lx !  
repeat 1=p(t+l^  
生产数据m; BTmraQ_5%  
P(S2); 2 ZH/5!/  
buffer(in):=m; (L%T]Noom  
in:=(in+1) mod N; ,wx?7p  
V(S1); HrTV ^#iE  
forever X3@q5L8)  
end Rkxo5/#I  
Procedure B: mFYa9)Qc'  
begin 'd>%1vmO}  
repeat !_C6gW9  
V(S2);
]tVGBj&  
m:=buffer(out); &MSfZ;  
消费m; q;UB 3p3Q  
out:=(out+1) mod N; ~!Mw[%W A  
P(S1); >sx ^]`  
forever m`nT}@z5 ;  
end GHX2q&  
2dzgwQh  
五．（10分）试简述UNIX的文件读写过程。 C)IbLG9(  
N8';p[0  
六．（10分）试给出运算变量均为整数的简单算术表达式所需最少临时单元个 @UBycXK  
数的算法（假定不许用代数规则变更表达式的计值顺序）。 .n>-Ne  
例如：A+B*C需要一个临时单元为（B*C）；（A+B）*（C+D）+E则 %G/rK9 0  
需要两个临时单元，一个为C+D，另一个既为A+B又为（A+B）*（C+D）。 |4~K|>Eb&  
,^%2/Z  
七．（10分）已知三维空间（直角坐标系）有n个点，请编写一个函数过程， \|:9[[  
求通过某一特定平面的点数。 <zb pYzdW  
$Nvv3G~ld  
八．（13分）编写一过程，对一个n×n矩阵，通过行变换，使其每行元素的平 OUC=|~z)t  
均值按递增顺序排列。 T06hOrYI_  
b(F<5"q.