中国科学院计算技术研究所 一九九三年招收硕士学位研究生入学考试试题答案 试题名称：软件基础 填空 逆波兰表示、二元式、三元式、四元式。 系统资源有限，进程推进次序非法；静态分配，有序分配。 假溢出。 深度优先，广度优先。 proc结构和user结构，proc。 O（ ）。 严格计算，短路计算/优化计算。 文件名，索引节点号。 哈夫曼树/最优二叉树。 简答 重定位是指作业装入到与其地址空间不同的物理空间所引起的地址变换 过程；动态重定位的特点：①由硬件实现；②在程序运行过程中进行地 址变换。 S aSBS | BsaS | ε B bb|b 高级通讯方式（如消息传递）和低级通讯方式（互斥与同步）；高级通 讯一次传递大批数据，而低级通讯则一次交换少量信息。 活动 ei li a1 0 0 a2 0 2 a3 0 3 a4 6 6 a5 4 6 a6 5 8 a7 7 7 a8 7 7 a9 7 10 a10 16 16 a11 14 14 最少需要2个寄存器 三. h: function reverse（h） begin p：=h； q：=p↑.next；p↑.next:=nil; if (q↑.next==nil) then begin q↑.next:=p; return(q); end r:=q↑.next; while (r↑.next≠nil ) do begin q↑.next:=p; p:=q; q:=r; r:=r↑.next end; q↑.next:=p; r↑.next:=q; return(r); end; 四．function restore(in) /* in is a string */ begin lth:=strlen(in); if (lth=0) return(nil) i:=i+1; if (lth=1) then begin new(p); p↑.data:=substr(in,1,1); p↑.left:=p↑.right:=nil; end else begin r:=substr(preorder,i,1); new(p); p↑.data:=r; j:=index(in,r); p↑.left:=restore(substr(in,1,j-1)); p↑.right:=restore(substr(in,j+1,lth-j)); end return(p) end; begin /* main */ i:=0; root:=restore(inorder); end. 五．①所有信号量由一个叫同步进程的进程来管理，对应每个信号量设置一个 计数器（记录信号量的值）和一个等待进程链表。 ②P、V操作通过调用p和v过程来实现。p和v过程将信号量S和操作 作为消息发给同步进程。然后做一个receive等待同步进程的回答。 ③同步进程接收到消息后，看所要求的操作能否完成。P操作当S的值为 0时，同步进程把调用者推入队列；不发回消息，则调用者处于等待状态。 V操作总能完成，所以发回一空消息给调用者，将其解冻，同时检查S的 值是否为1和相应等待队列空否。若S=1且队列不空，则从队列中移出一 个进程，向他发送一空消息，将它解冻。 六． S E { print（E.code） } E E1E2+ { E.code:= E1.code‖’+’‖E2.code; E.op=’+’; } E E1E2* { if E1.op=’+’ and E2.op=’+’ then E.code:= ‘(’‖E1.code‖‘)’‖‘*’‖‘(’‖ E2.code‖‘)’; else if E1.op=’+’ then E.code:= ‘(’‖E1.code‖‘)’‖‘*’‖E2.code; else if E2.op=’+’ then E.code:= E1.code‖‘*’‖‘(’‖E2.code ‖‘)’; else E.code:= E1.code‖‘*’‖E2.code; E.op:=’*’; } E id { E.code:=id.lexeme; E.code:=’$’; }