软件所93-99试题-及答案.doc

《软件所93-99试题-及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、页码123456789101112试题1993软基1994软基1995软基.1996软基1997软基1998软基1999软基页码1314151617181920212223242526272829答案1993软基1994软基1995软基1996软基1997软基1998软基1993试题名称：软件基础一．填空（1分×20）1．使用数据库系统的主要优点有、、、等。2．顺序存储结构实现的队列存在着现象，因而采用环形的结构来克服。3．产生死锁的主要原因是和；预防死锁通常所采用的方法有和。4．在UNIX系统中，一个进程的进程控制块（PCB）是由和两部分组成的，其中常驻内存的是。5．图的遍历方式有和两种

2、。6．快速排序在最坏情况下的时间复杂度为。7．布尔表达式的计算可采用或方法。8．共有n个叶子的二叉树，每个叶子的权值为Wi（1≦i≦n），其中带权路径长度最小的二叉树被称之为。9．在UNIX系统中，一个目录项是由和组成的。二．简答（5分×6）1．什么叫DBMS？有几种典型的数据库模型？2．什么是地址重定位？动态地址重定位的特点是什么？3．给出下列自动机所描述的语言：4．进程之间有哪些基本的通讯方式？它们分别有什么特点？5．构造一文法产生任意长的a，b串，使得

3、a

4、≦

5、b

6、≦2

7、a

8、。其中：”

9、a

10、”表示a字符的个数；”

11、b

12、”表示b字符的个数。6．如果dag是二叉树的时候，可以为其生成最优

13、目标代码。试标志下列二叉树，并给出执行该代码段所需的最小寄存器数。三．（10分）写一算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表。四．（15分）已知一个二叉树的前序及中序遍历结果，请写一算法，恢复该二叉树。五．（15分）某操作系统将消息缓冲通讯作为进程之间的基本通讯手段，SEND和RECEIVE分别为发送消息和接受消息原语。请设计一种方案，用SEND和RECEIVE原语来实现基于信号量的P，V操作。六．（10分）请按语法制导的定义，将后缀表达式翻译成中缀表达式。注意，不允许出现冗余括号，后缀表达式的文法如下：EEE+EEE*Eid软件所1994试题名称：软件基础操作

14、系统部分（30分）一．填充（1分×14）1．采用单级文件目录的主要缺陷是存在问题。2．在单道程序运行环境下，常用的作业调度算法有、和。3．特权指令是只能由使用的指令。4．存储器的保护机制（硬件）有保护和保护。5．预防死锁中的预先分配法和标准分配法，它们分别破坏了产生死锁必要条件中的条件和条件。6．在段式虚拟存储管理中，段表设置“改变位”的目的是为了。7．进程有三种基本状态，即①状态，①②状态，③状态。当进程由①演变为②或③时，就会立即引起。②③二．判断（1分×5，正确的打“√”,错误的打“×”）1．（）有了动态重定位机构，作业地址空间的代码就可以原封不动地装入到给定的内存中。2．（）任一时

15、刻，若有执行状态的进程，就一定有就绪状态的进程。3．（）文件系统中，设置OPEN操作的目的是为了将文件复制到内存中。4．（）临界段是不可中断的程序。5．（）作业由提交状态进入后备状态的过程是由作业调度程序完成的。三．（5分）分页式存储管理与分段式存储管理的主要区别是什么？四．（6分）以下是高级通讯原语SEND和RECEIVE不完整的框图。请填充以适当的P，V操作，并说明所用信号量的意义和初值。SEND：↓　　　　　　　　　RECEIVE：↓申请一消息区③↓↓消息送消息区④↓↓①　从消息链上摘下一消息↓↓消息区挂入消息链⑤↓↓②消息送接受区↓↓V（S2）释放消息区↓↓语言与编译部分（35分）

16、一．（7分）把下面不确定的有限自动机化为确定的有限自动机。二．（8分）有文法：S（L）

17、aLL，S

18、S给此文法配上语义动作子程序（或者说为此文法写一个语法制导定义），它输出配对的括号的个数，如对于句子（a,(a,a)）输出是2。三．（15分）为语言{}写三个文法，它们分别是二义文法，LR(1)文法和非LR(1)且非二义的文法。不必证明所写文法的正确性，但每个文法的产生式不能超过4个。四．（5分）右边是一个FORTRAN77程序。CALLSUB按语言的语义，程序的输出结果是什么？CALLSUB在静态存储分配情况下，实际的输出结END果是什么？两者是否有区别？说明理由。SUBROUTINESU

19、BDATAI/10/WRITE（*，*）II=100END程序设计与数据结构部分（35分）一．（8分）下面的程序段是合并两条链（f和g）为一条链f的过程。作为参数的两条链都是按节点上number值由大到小链接的。合并后新链仍按此方式链接。请填写下述空框，使程序正确工作。typepointer=↑node；node=recordnumber：integer；next　：pointerend；procedurecombine