中国科学院软件研究所 一九九六年招收硕士学位研究生入学考试试题答案 试题名称：软件基础 一．1． 表达式 后缀式 ①．a+b*c abc*+ ②．a≦b+c∧a>d∨a+b≠e abc+≦ad>∧ab+e≠∨ 2．①．赋值语句﹤变量﹥：=﹤表达式﹥的逆波兰式表示为： ﹤变量﹥﹤表达式﹥：= ②．条件语句IF﹤表达式﹥THEN﹤语句1﹥ELSE﹤语句2﹥的逆波兰式 表示为： ﹤表达式﹥﹤语句1﹥﹤语句2﹥IF THEN ELSE 或﹤表达式﹥P1 Jez﹤语句1﹥P2 J P1：﹤语句2﹥P2：，其中Jez 是﹤表达式﹥和P1这两个运算对象的二元运算符，表示当﹤表达 式﹥等于0即取假值时转去执行由P1开始的﹤语句2﹥。否则，执 行﹤语句1﹥然后转至P2所指地方；J是无条件转移的一元运算符。 3． ①．四元式序列： ②．三元式序列： ⑴ （- C D T1） ⑴ （- C D） ⑵ （* B T1 T2） ⑵ （* B ⑴） ⑶ （+ A T2 T3） ⑶ （+ A ⑵） ⑷ （- C D T4） ⑷ （- C D） ⑸ （** T4 N T5） ⑸ （** ⑷ N） ⑹ （/ E T5 T6） ⑹ （/ E ⑸） ⑺ （+ T3 T6 T7） ⑺ （+ ⑶ ⑹） ③．间接三元式序列： 间接码表 ⑴ （- C D） ⑴ ⑵ （* B ⑴） ⑵ ⑶ （+ A ⑵） ⑶ ⑷ （** ⑴ N） ⑷ ⑸ （/ E ⑷） ⑸ ⑹ （+ ⑶ ⑸） ⑹ 二．解答：满足题意要求的文法G为： G ={VT，VN，﹤头为非零元整偶数﹥，ρ} 其中，ρ：﹤头为非零元整偶数﹥→ ﹤偶数字1﹥｜ ﹤非零数字﹥﹤偶数字﹥｜ ﹤非零数字﹥﹤数﹥﹤偶数字﹥ ﹤偶数字﹥ → 0｜2｜4｜6｜8 ﹤非零数字﹥ → 1｜2｜3｜4｜5｜6｜7｜8｜9 ﹤数﹥ → ﹤数字﹥｜﹤数﹥﹤数字﹥ ﹤数字﹥ → ﹤非零数字﹥｜0 ﹤偶数字1﹥ → 2｜4｜6｜8 VN={﹤头为非零元整偶数﹥、﹤偶数字﹥、﹤非零数字﹥、 ﹤数﹥、﹤数字﹥} VT={0，1，2，3，4，5，6，7，8，9} 或者 G =（VT，VN，N，ρ）， 其中ρ：N → AD’|D’ （或N→D’|DD’|DAD’） A → AD”|D （或A→AD”|D”） D’ → 2|4|6|8 D → 1|3|5|7|9|D’ D” → 0|D; VN={N,A,D’,D,D”} VT={0,1,2,3,4,5,6,7,8,9}, N—开始符号。 三．LRU算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过 去的页面访问踪迹来推测未来的行为。它认为过去一段时间不曾被访问过 的页面，在最近的将来可能也不会再被访问。所以该算法的实质是：当需 要置换一页面时，选择在最近一段时间内最久不用的页面予以淘汰。 缺点：实现起来比较困难，因为要对先前的访问历史时时加以记录和更新。 如果这种连续的修改完全由软件来做，系统开销太大；如编硬件执 行，则会增加机器成本。因此，在实际应用中得到推广的是一些简 单而有效的LRU算法。 近似LRU算法流程图： N Y 四．1．当缓冲区满时，A进程不可以写，必须等待； 当缓冲区空时，B进程不可以读，必须等待。 2．该算法有错，它对读进程进入临界区未加限制，当缓冲区为空时，也可 以进入临界区读信息； 当存在多个读进程多个写进程时，还需引入一个信号量S0以防止同时 读或同时写。 var S0，S1，S2：semaphore：=1，n，0； buffer：array [0..n-1] of message; in,out: 0..n-1:=0,…0; begin parbegin producer: begin repeat ┇ produce a new message m; ┇ P(S1); P(S0); buffer(in):=m; in:=(in+1) mod n; V(S0); V(S2); until false end consumer: begin repeat P(S2); P(S0); m:=buffer(out); out:=(out+1) mod n; V(S0); V(S1); consume message m; until false end parend end 五．解答：当用户创建或联接了一个文件并把它打开后,便可以对它执行读、写 操作。文件系统在进行读写操作时，需调用一系列读写有关的过程，如 ⑴ passc过程、cpass过程。前者用于把一字符从缓冲区送到用户区，后 者相反； ⑵ iomove过程用于实现用户区和缓冲区之间的信息传送； ⑶ readi过程用于把信息从磁盘读入内存； ⑷ writei过程用于把信息从 内存写入磁盘。 或： 1．读方式 在UNIX系统中有两种读方式：⑴ 一般读方式。把盘块中的信息读 入缓冲区，有bread过程完成；⑵ 提前读方式。在一个进程顺序地读入 一个文件的各个盘块时，会预见到所要读的下一个盘块，因而在请求读 出指定盘块（作为当前块）的同时，可要求提前将下一个盘块（提前块） 中的信息读入缓冲区。这样，当以后需要该盘块的数据时，因它已在内 存中，这就缩短了读数据时间，从而改善了系统性能。提前读功能由 breada过程完成。 2．写方式 UNIX系统有三种方式：⑴ 一般写方式。真正把缓冲区中的数据写 入磁盘上，且进程须等待写操作完成，由过程bwrite完成；⑵ 异步写 方式。进程无须等待写操作完成便可返回，异步写过程为bawrite；⑶ 延迟写方式。该方式并不真正启动磁盘，而只是在缓冲首部设置延迟写 标志，然后便释放该缓冲区，并将该缓冲区链入空闲链表的末尾，以后 当有进程申请到该缓冲区时，才将它写入磁盘。引入延迟写的目的是为 了减少不必要的磁盘I/O，因为只要没有进程申请到此缓冲区，其中的 数据便不会写入磁盘，倘若再有进程需要访问其中的数据时，便可直接 从空闲链表中摘下该缓冲区，而不必从磁盘读入。 六．解答： 设运算变量均为整数的某个简单算术表达式，已加工的为k个四元 式，n1是起始四元式号码，nk是终止四元式号码。由于是加工简单算术表 达式得到的四元式序列，因此这些四元式均为一目或二目算术运算的四元 式。为使存放中间结果的临时单元个数最少，我们设立一个计数器count。 当四元式的第2或第3项出现临时变量（即出现对临时变量的引用时），每 出现一个，计数器就减少1；当四元式的第4项（即存放运算结果的项） 出现临时变量时，计数器就应增加1。 正如前面所述，这些四元式是加工简单算术表达式得到的算术运算四 元式，因此每个四元式必然要把计算结果赋予某个临时变量，因此四元式 的第4项一定是临时变量。 于是对每个算术运算四元式来说，若四元式第2，第3项都是临时变 量时，计数器要减少1；当第2，第3项只有一个是临时变量，计数器不变； 当第2，第3项都不是临时变量时，计数器增加1。 下面给出的算法顺便也给出了临时变量分配的临时单元地址（假定当 前分配的临时变量的起始地址为a）。 Procedure PT（a，n1，nk）； begin count：=0； p：=0； /* p是临时变量个数*/ for i：=n1 to nk do begin if 四元式的第2、3项都是临时变量 then count：=count-1； if 四元式的第2、3项都不是临时变量 then count：=count+1； p：=max（p，count）； T[i].ADDR：=a + count –1 /* 保证起始地址为a */ end end 其中p记录这k个四元式所需临时单元的最大个数；count是计数器。 例如：设有整型的算术表达式为 A*B-C*D+E*F 生成的四元式以及所需最少临时单元如下表所示 四元式 地址 count p （*，A，B, T1） a 1 1 （*, C, D, T2） a+1 2 2 (-, T1,T2, T3) a 1 2 (*, E, F, T4) a+1 2 2 (+, T3,T4, T5) a 1 2 七． #define EPSINO 1.0E-10 int pass_plane(points,pno,plane) float * points; /* points[pno*3] */ int pno; float plane[4]; /* a,b,c,d for plane agu.*/ { int i; int pass_no=0; float x,y,z; float * cfp; for(i=0;i<pno;i++) { cfp = points + (i*3) x = *cfp; y = *(cfp+1); z = *(cfp+2); if ( (plane[0]*x+plane[1]*y+plane[2]*z+plane[3]) < EPSINO) pass_no++; } return(pass_no); } 八． Trans（mat，no） float *mat； /* matrix[no][no] */ int no； { int i，j，k，l； float sum，minf； float *p，*pt，*pk，*pi； p =（float *） malloc（no*sizeof（float））； for（i=0；i<no;i++） /* sum up each row */ { sum = 0.0; pt = mat + i*no; for(j=0;j<no;j++) { pt++; sum += (*pt); } *(p+i) = sum; } for(i=0;i<no-1;i++) { minf=*(p+i); k=i for(j=i+1;j<no;j++) /* seek for the index of mininum */ if (minf>p[j]) {k = j; minf = p[j];} if (k!=i) /* exchange the rows */ { ph= mat + (no+k); pi= mat + (no*i); for(l=0;l<no;l++) /* row k ( row i */ { sum = *(pi+l); *(pi+l) = *(pk+l); *(ph+l) = sum; } sum = p[i]; p[i]=p[k]; p[k]=sum; /* p[k] ( p[i] */ } } /* end of for i */ free(p); } 九． struct bintree { int ele; struct bintree *left; struct bintree *right; } binsort(a,n,p_tree); /* procedure START */ int *a; /* a[n] */ int n; struct bintree * p_tree; /* p_tree[n] */ { int i; boolean greater; float value; struct bintree *p_tree1,*p_treesave; for(i=0;i<n;i++) { p_tree[i].ele = a[i]; p_tree[i].left = NULL; p_tree[i].right = NULL; } for(i=1;i<n;i++) { value = a[i]; p_tree1 = p_tree; /* root of bin_tree */ while(p_tree1 != NULL) { p_treesave = p_tree1; if (greater = (p_tree1->ele > value)) p_tree1 = p_tree1->left; else p_tree1 = p_tree1->right; } if (greater) p_treesave->left = p_tree+i; /* chained onto the tree */ else p_treesave->right = p_tree+i; } }