中国科学院软件研究所 一九九四年招收硕士学位研究生入学考试试题 试题名称：软件基础 操作系统部分（30分） 填充（1分×14） 1．采用单级文件目录的主要缺陷是存在 问题。 2．在单道程序运行环境下，常用的作业调度算法有 、 和 。 3．特权指令是只能由 使用的指令。 4．存储器的保护机制（硬件）有 保护和 保护。 5．预防死锁中的预先分配法和标准分配法，它们分别破坏了产生死锁必要 条件中的 条件和 条件。 6．在段式虚拟存储管理中，段表设置“改变位”的目的是为了 。 7．进程有三种基本状态，即① 状态， ① ② 状态，③ 状态。 当进程由①演变为②或③时，就会立即引起 。 ② ③ 二．判断（1分×5，正确的打“√”,错误的打“×” ） 1．（ ）有了动态重定位机构，作业地址空间的代码就可以原封不动地装 入到给定的内存中。 2．（ ）任一时刻，若有执行状态的进程，就一定有就绪状态的进程。 3．（ ）文件系统中，设置OPEN操作的目的是为了将文件复制到内存中。 4．（ ）临界段是不可中断的程序。 5．（ ）作业由提交状态进入后备状态的过程是由作业调度程序完成的。 三．（5分）分页式存储管理与分段式存储管理的主要区别是什么？ 四．（6分）以下是高级通讯原语SEND和RECEIVE不完整的框图。请填充以 适当的P，V操作，并说明所用信号量的意义和初值。 SEND： ↓　　　　　　　　　RECEIVE： ↓ 申请一消息区 ③ ↓ ↓ 消息送消息区 ④ ↓ ↓ ① 　 从消息链上摘下一消息 ↓ ↓ 消息区挂入消息链 ⑤ ↓ ↓ ② 消息送接受区 ↓ ↓ V（S2） 释放消息区 ↓ ↓ 语言与编译部分（35分） 一．（7分）把下面不确定的有限自动机化为确定的有限自动机。 二．（8分）有文法： S （L）| a L L，S | S 给此文法配上语义动作子程序（或者说为此文法写一个语法制导定义），它 输出配对的括号的个数，如对于句子（a,(a,a)）输出是2。 三．（15分）为语言{ }写三个文法，它们分别是二义文法，LR(1) 文法和非LR(1)且非二义的文法。不必证明所写文法的正确性，但每个文 法的产生式不能超过4个。 四．（5分）右边是一个FORTRAN 77程序。 CALL SUB 按语言的语义，程序的输出结果是什么？ CALL SUB 在静态存储分配情况下，实际的输出结 END 果是什么？两者是否有区别？说明理由。 SUBROUTINE SUB DATA I/10/ WRITE （*，*）I I=100 END 程序设计与数据结构部分（35分） 一．（8分）下面的程序段是合并两条链（f和g）为一条链f的过程。作为参数 的两条链都是按节点上number值由大到小链接的。合并后新链仍按此方式 链接。请填写下述空框，使程序正确工作。 type pointer = ↑node； node = record number： integer； next　 ： pointer end； procedure combine（var f：pointer，g：pointer）； var h，p：pointer； begin new（h）； h↑.next：= nil； p：=h； while （f<>nil）and (g<>nil) do if f↑.number>=g↑.number then begin p↑.next:= ；p:= ； end else begin p↑.next:= ；p:= ； end； if f=nil then ； if g=nil then ； f:=h↑.next; dispose(h); 二.（12分）如果一个数列中的某一段（至少有两个元素）的各元素值均相同， 则称之为等值数列段。等值数列段中元素的个数叫做等值数列段的长度。 现有由N个元素组成的整数数列A，编一程序求A中长度最大的所 有等值数列段的始末位置。如果没有等值数列段，则输出特殊标志。 三.（15分）编一个程序，对输入的任意正整数n，打印出集合{0，1,…，n-1} 的所有子集。例如：输入为3时，输出是 {} {0} {1} {0，1} {2} {0，2} {1，2} {0，1，2}