中国科学院软件研究所 一九九四年招收硕士学位研究生入学考试试题答案 试题名称：软件基础 操作系统部分： 一．填空 1．重名。 2．先进先出，最短作业优先，最高响应比优先。 3．操作系统。 4．界地址，存储键。 5．保持和请求，环路。 6．避免将被淘汰段不必要地写回外存，减少信息传输量。 7．执行，就绪，封锁（阻塞），进程调度。 二．判断 1．√ 2．× 3．× 4．× 5．× 三． 分页式 分段式  1 单一连续地址空间  三维地址空间  2 页是信息的物理单位  段是信息的逻辑单位  3 页的大小固定，由系统 划分，对用户透明  段长度不定，且可变， 用户可见  4 （不具有右边特点）  便于动态连接、存储保护， 便于增长、修改和共享  5 分配页面大小的空间  分配段大小的空间，为此 采用拼接技术   四．① P（S1） ② V（S1） ③ P（S2） ④ P（S1） ⑤ V（S1） S1是（消息链）互斥信号量，初值为1。 S2是（记录消息个数）同步信号量，初值为0。 语言与编译部分： 一． 二．拓广文法，加入新开始符号S’和产生式S’ S。 S’ S print（S.num） S (L) S.num:=L.num+1 S a S.num:=0 L L1,S L.num:=L1.num+S.num L S L.num:=S.num 三．必须有S aSb型的产生式，以保证b的个数不少于a的个数。还要 有S Sb或S bS型的产生式，以保证b的个数多余a的个 数。句子前缀中的a和后缀中的b的配对方式不同导致不同性质的文法。 二义文法： S aSb|Sb|b 例： ← 一种方式 ←另一种方式 LR（1）文法： S Sb|S’b S’ aS’b|ε 例： ←取前面的b 与a配对 非LR（1）且非二义文法：S aSb|S’ S’ S’b|b 例： ←取后面的b 与a配对 ∟若只向前看一个 符号，不知后面还有多少个b。因此不能确定是做S’ 到S的归约呢，还是移进b再做S’b到S’的归约。 四．按FORTRAN77的语义，子程序SUB的第一次执行输出10，第二次输出的值 不确定。FORTRAN语言的实现一般都采用静态存储分配，变量和存储单元 的结合（binding）是静态决定的，在程序运行期间不会改变，因此SUB的 两次执行的输出分别是10，100。 程序设计和数据结构部分 A: f E: p↑.next B: p↑.next F: g:=g↑.next C: f:=f↑.next G: p↑.next:=g D: g H: p↑.next:=f program MAXL（input，output） var len，m，n，l，j：integer； A：array[1..100] of integer; //假定N为100 begin for j:=1 to 100 do read(A[j]); len:=1; l:=1; for m:=2 to 100 do begin if A[m] = A[m-1] then l:=l+1 else l:=1; if l>len then len:=l; end; if len=1 then writeln(‘not have’) else begin l:=1; for m:=2 to 100 do begin if A[m] = A[m-1] then l:=l+1 else l:=1; if l=len then begin n:=m+1-l; write(n,m) end end end end. program powerset(input,output); var m,n,i,j,k : integer; begin read(n); m:=1; for i:=1 to n do m:=m*2; m:=m-1; // m= for i:=0 to m do begin write(‘{‘); j:=i; k:=0; while (j<>0) do begin if j mod 2 <>0 then write(k:5); k:=k+1; j:=j div 2 end; //数据间没有逗号 writeln(‘}’) end end. 若明白下面的对应关系，程序不难编出： 二进制： 0 十进制： 0 集合： {} 1 1 {0} 10 2 {1} 11 3 {0，1} 100 4 {2} 101 5 {0，2} 110 6 {1，2} 111 7 {0，1，2}