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