中国科学院计算技术研究所 一九九二年招收硕士学位研究生入学考试试题答案 试题名称：软件基础 填空 顺序结构、链表结构 有向无环图 程序共行（并发）、资源共享（共享） 综合属性、继承属性 互斥、同步 系统资源不足、进程推进顺序非法 严格计算（直接计算）、短路计算 O（m+n） 先序、中序、后序、深度优先、广度优先 由关键字直接计算记录存放位置的查找方法称为哈希查找。（3分） UNIX系统中设备管理的特点有：（4分） 块设备管理和字符设备管理具有相似的层次结构； 把字符设备作为特别文件处理； 采用了完善的缓冲技术； 引入了“预先读”、“异步写”和“延迟写”方式。 直接插入排序第二趟的结果 [38 49] 65 97 76 13 27 49 快速排序第二趟的结果 [13] 27 [38] 49 [49 65] 76 [97] 由于一个作业装入到与其地址空间不一致的存储空间所引起的、有关地址部分的填整过程，称之为地址重定位。动态重定位的特点是：在程序执行时才进行重定位，它需要硬件的支持。 逻辑结构指数据元素之间的逻辑关系；物理结构指数据结构在计算机存储中的映像。 活动记录包含（答对4个即可得分） 临时工作单元：用于存放计算过程中所需的临时变量； 局部数据：用于存放对应当前活动记录的程序单元的局部数据； 保存机器态部分：用于保存当前的程序计数器、寄存器的值等等； 访问链：把当前执行的程序单元可访问的活动记录联结起来； 控制链：把所有活动记录按它们生成的次序联结起来； 实在参数 返回值 该变量在编译时被优化掉了，所以无法检查其值。 问答题： Fortran的词法分析比Pascal的词法分析复杂； Fortran语言将一行分为标号、续行、语句、注释四个区，出现在不同区域的符号具有不同的含义。词法分析器必须结合符号出现的位置才可判定其属性；而Pascal语言中的记号识别则与位置无关； Fortran语言认为空格无意义，使得对某些符号的识别取决于后面的符号；而在Pascal语言中，每遇过一个空白字符，则认为一个记号已识别完毕。 该文法不是LR（1）文法。因为其为二义文法。 S A1A2 可将任意输入串aa……a截取任意长度的前缀归约为A1，而将剩下的全部归约为A2。 发送进程在发送消息之前，先在自己的内存空间设置一发送区，填入消息正文等信息，然后调用发送原语（Send）。进入发送程序后，先找到接受进程的PCB，再申请获得一消息缓冲区空间，然后互斥进入接受进程的消息队列，找到队尾，把消息缓冲区挂在队尾，把消息正文及长度等从发送区复制到消息缓冲区，最后通过V操作通知接收进程，并退出发送程序，发送进程继续执行。 接收进程在读取消息之前，先在自己的内存空间设置一接收区，然后使用Read原语，在进入读取程序后，先通过P操作检查有无消息，然后互斥进入消息队列，移出队列中的第一个消息，并把消息从缓冲区复制到接收区，最后释放缓冲区，退出读取程序，接收进程继续执行。 锁原语的原定义： Lock（w）： L：if w = 1 then goto L else w ：=1 Unlock（w）： w：=0 用SWAP指令实现的锁原语： Lock（w）： key：=1； repeat swap（w，key） until key=0； Unlock（w） key：=0； swap（w，key）； 算法设计 设全局变量n存放当前树的最大深度，则程序为： procedure visit（lev：integer；root：bitreptr）； begin case root↑.left = nil and root↑.right =nil: if lev > n then n := lev; return; root↑.left = nil: call visit(lev+1;root↑.right); root↑.right = nil: call visit(lev+1;root↑.left); else call visit(lev+1;root↑.left); call visit(lev+1;root↑.right); end /*case*/ end begin /* main */ n := 0; call visit(0 , root); write(n); end /*main*/ 堆排序的算法 数据结构定义 type rectype = record key : keytype end; filetype = array [0..n] of rectype; 算法描述 procedure heapsort(var r : filetype); begin for i := n div 2 downto 1 do call sift(r , i , n); for i :=n downto 2 do [ r[1] ( r[i]; call sift(r , 1 , i-1);] end; {heapsort} procedure sift(var r : filetype; l , m : integer); begin i := l; j := 2*i; x := r[i]; while j≤m do [ if (j<m) and (r[j].key>r[j+1].key) then j:=j+1; if x.key>r[j].key then [ r[i]:=r[j]; i:=j; j:=2*i;] else j := m+1; ] r[i] := x; end; /*sift*/ 最坏情况下的时间复杂度为O(nlogn)。