北京航空航天大学2008年计算机专业综合考研试题.doc

北京航空航天大学2008年计算机专业综合考研试题一、简答题(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位,最后又问该机器的最大物理内存是多少(答案:256KB)。)七、简答题(4’×4)1、利用等值演算的方法,写出求命题逻辑公式的主范式的方法。2、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么?3、之间的真值关系是什么?4、如何判断公式中某个变元是约束变元还是自由变元?举例说明一个变元可以既是约束的又是自由的。八、判断下列结论是否成立,并至少用两种方法证明你的判断(6’+8’)1、2、九、填空题(1’×8)1、冯·诺依曼计算机体系包括存储器、运算器、控制器和输入输出设备。2、在总线同步控制方式种,哪一种速度最快,哪一种对电路故障最敏感?3、在程序查询方式、程序中断方式和DMA方式中,哪一种方式主存与设备间有数据通路,哪一种方式使CPU与外设串行化?4、指令中的操作数分别为立即寻址和寄存器直接寻址时CPU访问主存的次数分别为多少次?5、存储器分层体系是根据程序访问的局部性原理提出的。十、存储器扩展的题(6’)某机器字长为16位,最大物理内存为64KB,最低地址的8KB存放BI