北京航空航天大学计算机专业综合2008年考研试题研究生入学考试试题考研真题
● 摘要
2008年北京航空航天大学961计算机专业综合考研试题
一、简答题（4’×5）
1、写出影响算法执行的时间效率的主要因素，并指出哪些因素与算法的时间效率直接相关。
2、已知元素的入栈顺序为A,B,C,D,E ，在所有可能的出栈顺序中，写出第一个出栈的元素为C 且第二个出栈的元素为D 的所有组合。
3、根据单词（Nov, Jul, Sept, Feb, Oct, Mar, May, Jun, Jan, Dec, Aug, Apr）的第一个字母在字母表中的顺序建立二叉排序树，当每个元素的查找概率相等时，求查找成功时的平均查找长度ASL 。
4、证明：具有n 个顶点的无向图最多有n(n-1)/2条边。
5、有人说，折半查找的时间效率一定比顺序查找的时间效率高，你怎么看待这种说法？为什么？
二、算法设计题（10’）
已知一非空完全二叉树存放于数组BT[0..n-1]中，请写出中序遍历该二叉树的非递归算法。
三、算法设计题（10’）
写出不带头结点的双向链表的插入排序算法。
四、简答题（4’×5）
1、数据传输控制方式有哪些？
2、引入线程的目的是什么？
3、P, V操作是如何实现互斥的的？
4、什么是死锁？产生死锁的原因是什么？
5、什么是文件系统？
五、判断题（1’×10）
略。（基本上来自于历年真题）
六、解答题（10’）
某机器字长为16位，采用段页式存储管理算法，页内偏移为12位，段表和页表内容如下，给出4个虚拟地址（二进制形式），问哪个地址产生缺段中断，哪个地址产生缺页中断，哪些地址可以转换为物理地址，并求转换后的物理地址。（地址格式中段号占1位，段内页号占3位，页内偏移为12位，另外，在给出的页表中，物理块号占6位，最后又问该机器的最大物理内存是多少（答案：256 KB）。）
七、简答题（4’×4）
1、利用等值演算的方法，写出求命题逻辑公式的主范式的方法。
2、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么？
3、之间的真值关系是什么？
4、如何判断公式中某个变元是约束变元还是自由变元？举例说明一个变元可以既是约束的
相关内容
相关标签