中国科学院计算技术研究所 一九九三年招收硕士学位研究生入学考试试题 试题名称：软件基础 填空（1分×20） 编译过程中，比较常见的中间语言有 、 、 和 。 产生死锁的主要原因是 和 ；预防死锁通常所采用 的方法有 和 。 顺序存储结构实现的队列存在着 现象，因而采用环形的结 构来克服。 图的遍历方式有 和 两种。 在UNIX系统中，一个进程的进程控制块（PCB）是由 和 两部分组成的，其中常驻内存的是 。 快速排序在最坏情况下的时间复杂度为 。 布尔表达式的计算可采用 或 方法。 在UNIX系统中，一个目录项是由 和 组成的。 共有n个叶子的二叉树，每个叶子的权值为Wi（1≦i≦n），其中带权路径长度最小的二叉树被称之为 。 简答（5分×6） 什么是地址重定位？动态地址重定位的特点是什么？ 给出下列自动机所描述的语言： 构造一文法产生任意长的a，b串，使得|a|≦|b|≦2|a|。其中：“|a|” 表示a字符的个数；“|b|”表示b字符的个数。 进程之间有哪些基本的通讯方式？它们分别有什么特点？ 已知下列AOE网络，请给出每个事件ai最早开始时间ei及最迟开始时间li。 如果dag是二叉树的时候，可以为其生成最优目标代码。试标志下列二 叉树，并给出执行该代码段所需的最小寄存器数。 （10分）写一算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表。 （15分）已知一个二叉树的前序及中序遍历结果，请写一算法，恢复该二叉树。 （15分）某操作系统将消息缓冲通讯作为进程之间的基本通讯手段，SEND和RECEIVE分别为发送消息和接受消息原语。请设计一种方案，用SEND和RECEIVE原语来实现基于信号量的P，V操作。 （10分）请按语法制导的定义，将后缀表达式翻译成中缀表达式。注意，不允许出现冗余括号，后缀表达式的文法如下： E EE+ E EE* E id