北航2007年计算机专业硕士研究生入学考试基础真题
一．1．设abc三个元素的进栈次序是abc，符号PUSH与POP分别表示对堆栈进行一次进栈操作和一次出栈操作。（1）请分别写出所有可能的出栈序列以及获得该出栈序列的操作序列；（2）指出不可能出现的出栈序列。2．对于一个有向图，除了进行拓扑排序，还可以采用什么方法判断图中是否存在回路？请简述判断原则。3．请画出在右图3阶B树中插入关键字64以后的B树的状态。
4．在长度为
的线性表中进行顺序查找。查找第i个数据元素的概率为pi，且分布如下：p112，p214，…，p
112，p
12请求出在该线性表中查找成功的平均查找长度（要求写成关于
的简单表达式形式）。二．请写一非递归算法，该算法在按值严格递增排列的顺序表A1…
中采用折半查找法查找值不小于item的最小元素。若表中存在这样的元素，则算法给出该最小元素在表中的位置，否则，给出信息0。三．已知非空二叉树采用顺序存储结构，结点的数据信息依次存放于一维数组BT0…
1中（假设每个结点的数据信息为一个非0整数；若数组元素值为0，则表示该元素对应的结点在二叉树中不存在）。请写一算法，生成该二叉树的二叉链表结构。四．1．假设A是命题逻辑中的任意公式。证明：存在一个合取范式B，使得AB且BA。2．假设A是谓词逻辑中的公式，I是一个解释。假设v1v2是I的两个赋值。考虑以下两个性质：（1）对于A中的每个自由变元x，都有v1xv2x。（2）A在I，v1之下的真值等于A在I，v2之下的真值。构造A，I，v1，v2使得（1）不成立而（2）成立。判断当（1）成立时（2）是否成立，并证明所给出的判断。五．假设x是变元符号，P，Q是一元谓词符号，判断以下公式是否永真：xPx→Qx→xPx∧xQx。试分别使用解释赋值方法、公理化方法和归结方法证明所给出的判断。六．1．什么是PCB，它的三个主要组成部分是什么？2．进程与线程最根本的差别是什么？3．在分区式存储管理中，什么是“地址重新定位”？动态和静态重新定位的区别是什么？4．哪一种RAID保存两份数据？RAID4与RAID5的区别是什么？5．什么是FCB，它的三个主要组成部分是什么？
f七．判断题。1．实时操作系统必须比一般操作系统的速度快。2．分布式操作系统的可靠性要求比单机操作系统的高。3．中断是由CPU发出的。4．缓存（CACHE）一定能提高速度。5．段页式存储管理可以用于虚拟存储器的管理。6．死锁是不可避免的。八．假设有6个作业正在等待运行，它们所需的运行时间分别是：10r