天勤论坛_北航计算机考研专业课历年真题(2003-2008).pdf

天勤论坛，我们做最专业的计算机考研论坛 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 1) 2 条边。个顶点的无向图最多有 n (n 5、有人说，折半查找的时间效率一定比顺序查找的时间效率高，你怎么看待这种说法？为什么？ 二、算法设计题（10’） 1] 中，请写出中序遍历该二叉树的非递归算法。已知一非空完全二叉树存放于数组BT[0..n 三、算法设计题（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、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么？ xA,3、 xA, A 之间的真值关系是什么？ 4、如何判断公式中某个变元是约束变元还是自由变元？举例说明一个变元可以既是约束的又是自由的。 八、判断下列结论是否成立，并至少用两种方法证明你的判断（6’ + 8’） ( pq |q, r p 1、 r) R(x))x(P(x)R(x)) |x(Q(x)Q(x)), x(P(x)2、 天勤论坛，/ 天勤论坛，我们做最专业的计算机考研论坛 九、填空题（1’×8） 1、冯•诺依曼计算机体系包括存储器、运算器、控制器和输入输出设备。 2、在总线同步控制方式种，哪一种速度最快，哪一种对电路故障最敏感？ 3、在程序查询方式、程序中断方式和DMA 方式中，哪一种方式主存与设备间有数据通路，哪一种方式使 C PU 与外设串行化？ 4、指令中的操作数分别为立即寻址和寄存器直接寻址时 CPU 访问主存的次数分别为多少次？ 5、存储器分层体系是根据程序访问的局部性原理提出的。 十、存储器扩展的题（6’） 某机器字长为 16 位，最大物理内存为 64 KB，最低地址的 8 KB 存放 BIOS 程序，其他空间存放用户程序， 现有 4K×4 的ROM 和 4K×4 的 SRAM，问各需要多少片？ 十一、Cache 题（8’） 主存大小为 2 MB，Cache 大小为 8 KB，采用 2 路组相联方式，每个 Cache 块大小为 128 字节。 （1）求主存地址格式及各字段的位数和含义 （2）Cache 的格式 （3）Cache 的Tag 需多少位？ 十二、指令系统的设计（8’） 某机器字长为 16 位，有 8 个 16 位的通用寄存器，请设计一指令系统，要求： （1）共有 128 条双操作数指令，且必有一操作数为寄存器直接寻址，另一个操作数有 4 种寻址方式，可 以是立即寻址、寄存器直接寻址、 寄存器间接寻址或变址寻址，其中立即寻址和变址寻址的偏移量均为 16 位； （2）指令所占的位数必须是 16 的倍数且要尽可能地短。 要求： （1）写出影响指令系统设计的因素； （2）设计该机器的指令系统，写出各字段的位数和含义。 十三、微程序设计题（10’） 指令为 SUB R0, (R1)，其中R0 为目的操作数，采用寄存器直接寻址，R1 为源操作数，寻址方式为寄存器 间接寻址，每个机器周期包含 4 个节拍周期，写出该指令执行的详细微操作