资源描述：
《北航计算机考研专业课历年真题(2003-2008)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、勤思考研，计算机考研专业课权威辅导！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、证明：具有n1)2条边。-个顶点的无向图最多有n(n5、有人说，折半
2、查找的时间效率一定比顺序查找的时间效率高，你怎么看待这种说法？为什么？二、算法设计题（10’）1]中，请写出中序遍历该二叉树的非递归算法。-已知一非空完全二叉树存放于数组BT[0..n三、算法设计题（10’）写出不带头结点的双向链表的插入排序算法。四、简答题（4’×5）1、数据传输控制方式有哪些？2、引入线程的目的是什么？3、P,V操作是如何实现互斥的的？4、什么是死锁？产生死锁的原因是什么？5、什么是文件系统？五、判断题（1’×10）略。（基本上来自于历年真题）六、解答题（10’）某机器字长为16位，采用段页式存储管理算法，页内偏移为12位，段表和页表内容如下，
3、给出4个虚拟地址（二进制形式），问哪个地址产生缺段中断，哪个地址产生缺页中断，哪些地址可以转换为物理地址，并求转换后的物理地址。（地址格式中段号占1位，段内页号占3位，页内偏移为12位，另外，在给出的页表中，物理块号占6位，最后又问该机器的最大物理内存是多少（答案：256KB）。）七、简答题（4’×4）1、利用等值演算的方法，写出求命题逻辑公式的主范式的方法。2、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么？xA,"3、xA,A之间的真值关系是什么？$4、如何判断公式中某个变元是约束变元还是自由变元？举例说明一个变元可以既是约束的又是自由的。八、判
4、断下列结论是否成立，并至少用两种方法证明你的判断（6’+8’）(pØ-q
5、Ø®q,rÚpØ1、r)Ø®R(x))®x(P(x)"-R(x))
6、®x(Q(x)"Q(x)),®x(P(x)"2、勤思考研，www.qsiedu.com勤思考研，计算机考研专业课权威辅导！九、填空题（1’×8）1、冯•诺依曼计算机体系包括存储器、运算器、控制器和输入输出设备。2、在总线同步控制方式种，哪一种速度最快，哪一种对电路故障最敏感？3、在程序查询方式、程序中断方式和DMA方式中，哪一种方式主存与设备间有数据通路，哪一种方式使CPU与外设串行化？4、指令中的操作数分别为立即寻址和寄存
7、器直接寻址时CPU访问主存的次数分别为多少次？5、存储器分层体系是根据程序访问的局部性原理提出的。十、存储器扩展的题（6’）某机器字长为16位，最大物理内存为64KB，最低地址的8KB存放BIOS程序，其他空间存放用户程序，现有4K×4的ROM和4K×4的SRAM，问各需要多少片？十一、Cache题（8’）主存大小为2MB，Cache大小为8KB，采用2路组相联方式，每个Cache块大小为128字节。（1）求主存地址格式及各字段的位数和含义（2）Cache的格式（3）Cache的Tag需多少位？十二、指令系统的设计（8’）某机器字长为16位，有8个16位的通用寄存
8、器，请设计一指令系统，要求：（1）共有128条双操作数指令，且必有一操作数为寄存器直接寻址，另一个操作数有4种寻址方式，可以是立即寻址、寄存器直接寻址、寄存器间接寻址或变址寻址，其中立即寻址和变址寻址的偏移量均为16位；（2）指令所占的位数必须是16的倍数且要尽可能地短。要求：（1）写出影响指令系统设计的因素；（2）设计该机器的指令系统，写出各字段的位数和含义。十三、微程序设计题（10’）指令为SUBR0,(R1)，其中R0为目的操作数，采用寄存器直接寻址，R1为源操作数，寻址方式为寄存器间接寻址，每个机器周期包含4个节拍周期，写出该指令执行的详细微操作流程和对应
9、处于有效状态的控制信号。2007年真题一．1．设a,b,c三个元素的进栈次序是a,b,c，符号PUSH与POP分别表示对堆栈进行一次进栈操作和一次出栈操作。（1）请分别写出所有可能的出栈序列以及获得该出栈序列的操作序列；（2）指出不可能出现的出栈序列。2．对于一个有向图，除了进行拓扑排序，还可以采用什么方法判断图中是否存在回路？请简述判断原则。勤思考研，www.qsiedu.com勤思考研，计算机考研专业课权威辅导！3．请画出在右图3阶B-树中插入关键字64以后的B-树的状态。4．在长度为n的线性表中进行顺序查找。查找第i个数据元素的概率为pi，且分布如下：p1=
10、1/2，p
