勤思考研，计算机考研专业课权威辅导！
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] 中，请写出中序遍历该二叉树的非递归算法。?已知一非空完全二叉树存放于数组三、算法设计题（10’）
写出不带头结点的双向链表的插入排序算法。
四、简答题（4’×5）
1、数据传输控制方式有哪些？
2、引入线程的目的是什么？
3、P, V 操作是如何实现互斥的的？
45、什么是文件系统？
五、判断题（1’×10）
略。（基本上来自于历年真题）
某机器字长为16 12 位，段表和页表内容如下，给出4 个虚
占3 6 位，最后又问该机器的最大物理内存是多少（答案：
七、简答题（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 方式中，哪一种方式主存与设备间有数据通路，哪一种方式使CPU 与外设串行化？
4、指令中的操作数分别为立即寻址和寄存器直接寻址时CPU 访问主存的次数分别为多少次？
5、存储器分层体系是根据程序访问的局部性原理提出的。
十、存储器扩展的题（6’）
某机器字长为16 位，最大物理内存为64 KB，最低地址的8 KB 存放BIOS 程序，其他空间存放用户程序，现有4K×4 的ROM 和4K×4
的SRAM，问各需要多少片？
十一、Cache 题（8’）
主存大小为2 MB，Cache 大小为8 KB，采用2 路组相联方式，每个
（1）求主存地址格式及各字段的位数和含义
（2）Cache 的格式
（3）Cache 的Tag 需多少位？
十二、指令系统的设计（8’）
某机器字长为16 位，有8 个16
（1）共有128 4 种寻址方式，可以是立即寻址、寄存器直接寻址、
16 位；
（2要求：
（1（2
指令为R1 为源操作数，寻址方式为寄存器
4
2007年真题
一．
1．设a,b,c 三个元素的进栈次序是a,b,c，符号PUSH 与POP 分别表示对堆栈进行一次进栈操作和一次出栈操作。
（1）请分别写出所有可能的出栈序列以及获得该出栈序列的操作序列；
（2）指出不可能出现的出栈序列。
2．对于一个有向图，除了进行拓扑排序，还可以采用什么方法判断图中是否
存在回路？请简述判断原则。
勤思考研，计算机考研专业课权威辅导！
3．请画出在右图3 阶B-树中插入关键字64 以后的B-树的状态。
4．在长度为n 的线性表中进行顺序查找。查找第i 个数据元素的概率为pi，
且分布如下：p1=1/2，p2=1/4，?，pn-1=1/2，pn=1/2
请求出在该线性表中查找成功的平均查找长度（要求写成关于n 的简单表达式形式）
二．请写一非递归算法，该算法在按值严格递增排列的顺序表item 的最小元素。若表中存在这样
的元素，则算法给出该最小元素在表中的位置，否则，给出信息0。
点的数据信息为一个非0 整数；
若数组元素值为0表结构。
四．
1．假设A B且B|=A。
2．假设A 是谓词逻辑中的公式，I 是I 的两个赋值。考虑以下两个性质：
（1）对于A 中的每个自由变元。
（2）A 在I，v1 A I，
构造A，I，v1，v2 使得（121）成立时（2）是否成立，并证明所给出的判断。
五．假设PQ
x(P(x)→Q(x))?????→(
六．1
2
3
4．哪一种RAID RAID4 与RAID5 的区别是什么？
5．什么是FCB，它的三个主要组成部分是什么？
七．判断题。
1．实时操作系统必须比一般操作系统的速度快。
2．分布式操作系统的可靠性要求比单机操作系统的高。
3．中断是由CPU 发出的。
4．缓存（CACHE）一定能提高速度。
5．段页式存储管理可以用于虚拟存储器的管理。
6．死锁是不可避免的。
勤思考研，计算机考研专业课权威辅导！
八．假设有6 个作业正在等待运行，它们所需的运行时间分别是：10，8，6，4，2 和X。不考虑并行、基于X、在追求最小平均相应时间
（Minimal average response time）的前提下，请给出它们的运行顺序。（提示：共有六种顺序，先确定运行方法）
九．1．运算器的核心是（）。
2．常见的集中式总线判优控制方式有（）、（）和（）三种。
3．CPU 响应中断时需要保护程序断点，这里断点指的是（）的内容，它一般被保存到（）中。
4．浮点数加减法的基本运算过程是（）、（）和（）。
5．条件转移指令所依据的条件来自（）寄存器。
十．
1 用16K*8 的SRAM 芯片组成64K*16 的存储器，该存储器按16
2．某8 位计算机主存容量32K 字节，组相联Cache 容量2K 字节，每组4 Blocks,每个字节。假设Cache 开始是空的，CPU 从主
存存储单元0 开始顺序读取2176 个字节数据（即按地址0、1、2 后再重复这样的读数过程7 遍（共
8 遍），Cache 速度是主存速度的10 倍，采用LRU Cache 后的加速比。
3．某机字长为16 16 64 条单地址指令和4 条无操作数指令；每个地址字
段占5
控制器的基本工作原理。
2006年真题
一．填空题
1i
2
} *LinkList;
LinkList p;
for (p=lista; p->link; p=p->link);
p->link=listb;
}
3．若某堆栈初始为空，PUSH 与POP 分别表示对堆栈进行一次进栈与出栈操作，那么，对于输入序列a,b,c,d,e，经过PUSH，PUSH，POP，
PUSH，POP，PUSH，PUSH 以后，输出序列是（）。
4．在具有n 个元素的非空队列中插入一个元素或者删除一个元素的操作的时间复杂度采用大O 形式表示为（）。
5．若一棵度为7 的树中有8 个度为1 个结点，有7 个度为2 的结点，有6 个度为3 的结点，有5 个度