北航2005年计算机专业硕士研究生入学考试基础真题

发布时间：2011-03-13 12:53:08 来源：文档文库

小中大

字号：

手机查看

一．若散列函数为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，证明：

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 操作正确实现“读者”与“写者”的同步。

九、1．按传输信息类别，系统总线一般包括（），（）和（）。

2．DRAM 的刷新方式一般有（）和（）两种。

3．中断响应时的保护现场实际上是指保存（）和（）的内容。

4．常见的微指令编码方式包括（），（）和（）三种。

十、1．某计算机的存储系统由Cache、主存和用于虚拟存储的磁盘组成。CPU 总是从Cache 中获得数据。若所访问的字在Cache 中，则存取它只需要10ns，将所访问的字从主存装入Cache 需要40ns，而将它从磁盘装入主存则需要10us，假定Cache 的命中率为0.9，主存的命中率为0.6，计算该系统访问一个字的平均存取时间。