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