北航2005年计算机专业硕士研究生入学考试基础真题
一．若散列函数为HkeyiMOD7其中，i为关键字key的第一个字母在英文字母表中的序号，并且采用线性探测再散列方法处理冲突。请画出在一个初始状态为空、地址值域为06的散列表中依次插入下列关键字MONTUEWEDTHUFRISATSUN以后的散列表。二、所谓二叉树等价，是指它们不仅具有相同的拓扑结构，而且对应结点中包含相同的数据信息。假设二叉树采用二叉链表存储结构，链结点构造为lchilddatarchild请写一递归算法，判断根结点指针分别为T1与T2的两棵二叉树是否等价。若它们等价，算法返回1，否则返回0。（写成非递归算法不得分）三、已知一具有
个顶点的有向图G（V，E）采用邻接表存储方法，请写一算法，检查任意给定序列v1v2…，v
vi属于V，1≤i≤
是否为该有向图的一个拓扑序列。若是，算法给出信息1，否则，给出信息0。四、1．若p1，p2，……，pm是m个不同的命题变元，A1，A2，……，A
，B，C1，C2，……，Cm是命题逻辑公式，并且A1，A2，…………A
B，证明：
2．用演绎定理证明├（A→B）→B→C→A→C。五、1．在谓词逻辑里，假设A，B是公式，x不是B的自由变元。证明：x（A∧B）xA∧B若x是B的自由变元，举出一个使得x（A∧B）xA∧B不成立的例子。2．假设P（x，y）是二元谓词，判断xyPxyyxPxy是否成立？用解释方法（如以自然数为论域）及归结方法证明上述判断。六、1．进程与线程的区别？为什么要引入线程？2．什么是死锁？3．什么是文件系统？4．什么是中断？七、1．由于最优算法（OPT）造成缺页率最小，是非常实用的存储管理算法。2．预防死锁的发生可以通过破坏产生死锁的四个必要条件之一来实现。3．请求页式存储管理系统中，若把页面的大小增加一倍，则缺页中断次数会减少一半。4．在有虚拟存储器的系统中，可以运行比主存容量还大的程序。5．进程被创建后的初始状态为“阻塞状态”。6．仅当一个进程退出临界区以后，另一进程才能进入相应的临界区。7．打印机是一类典型的块设备。8．虚拟存储器的最大存储空间为内存容量与硬盘容量之和。八、我们将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”必须等待，直到该“写者”完成数据访问为止。试用P，V操作正确实现“读者”与“写者”r