文档库

最新最全的文档下载
当前位置:文档库 > 北航2005年计算机考研专业课真题

北航2005年计算机考研专业课真题

北航2005年计算机考研专业课真题

一.若散列函数为H(key)= i MOD 7,其中,i 为关键字key 的第一个字母在英文字母表中的序号,并且采用线性探测再散列方法处理冲突。

请画出在一个初始状态为空、地址值域为[0..6]的散列表中依次插入下列关键字MON,TUE,WED,THU,FRI,SAT,SUN 以后的散列表。

二、所谓二叉树等价,是指它们不仅具有相同的拓扑结构,而且对应结点中包含相同的数据信息。

假设二叉树采用二叉链表存储结构,链结点构造为[lchild|data|rchild], 请写一递归算法,判断根结点指针分别为T1 与T2 的两棵二叉树是否

等价。若它们等价,算法返回1,否则返回0。(写成非递归算法不得分)

三、已知一具有n 个顶点的有向图G=(V,E)采用邻接表存储方法,请写一算法,检查任意给定序列v1,v2,…,vn (vi 属于V,1≤i≤n)

是否为该有向图的一个拓扑序列。若是,算法给出信息1,否则,给出信息0。

四、

1.若p1,p2,……,pm 是m 个不同的命题变元,A1,A2,……,An,B,C1,C2,……,Cm 是命题逻辑公式,并且A1,A2,…………An|=B,

证明:

北航2005年计算机考研专业课真题

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)是二元谓词,判断?x?yP(x,y)|= ?y?xP(x,y)是否成立?用解释方法(如以自然数为论域)及归结方法证明上述判断。

六、1.进程与线程的区别?为什么要引入线程?

2.什么是死锁?

3.什么是文件系统?

4.什么是中断?

七、1.由于最优算法(OPT)造成缺页率最小,是非常实用的存储管理算法。

2.预防死锁的发生可以通过破坏产生死锁的四个必要条件之一来实现。

3.请求页式存储管理系统中,若把页面的大小增加一倍,则缺页中断次数会减少一半。4.在有虚拟存储器的系统中,可以运行比主存容量还大的程序。

5.进程被创建后的初始状态为“阻塞状态”。

6.仅当一个进程退出临界区以后,另一进程才能进入相应的临界区。

7.打印机是一类典型的块设备。

8.虚拟存储器的最大存储空间为内存容量与硬盘容量之和。

八、我们将只读数据的进程称为“读者”进程,而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据,但不允许“写

者”与其他“读者”或“写者”同时访问数据。另外,要保证:一旦有“写者”等待时,新到达的“读者”必须等待,直到该“写者”完

成数据访问为止。试用P,V 操作正确实现“读者”与“写者”的同步。