勤思考研，计算机考研专业课权威辅导！

4．虚拟文件系统就是网络文件系统。

5．交换（SWAP）是由存储管理系统完成的。

6．输入输出的缓冲器（BUFFER）是为了提高外设的速度。

7．在中断机制中，中断都是可以被再中断的。

八．有5 个进程如下表。时间从0 开始，单位为1，最高优先级为0。

进程 到达时间 优先级 所需运行时间

A 0 2 3

B 2 3 8

C 4 4 6

D 6 1 5

E 8 0 4

绘图说明以下进程调度过程：（1 CPU 系统，所有进程只使用CPU）。

1．先来先服务（FCFS）。

2．轮转调度（Round-Robin） 时间片=2。

3．优先级轮转法（Priority Round-Robin） 时间片=2。

4．最短进程轮转发（Shortest Process Next）。

九．

1．某机字长16 位，CPU 内有16 个16 指令系统共包括32 条“寄存器—存储器”型双操作数

采用补码表示。

（1

（2

2

3．的256K 字节的存储器，应使用CACHE 容量为64KB，每

个数据块为256 20124H，58130H，201F5H 和381F0H 等4

CACHE 第1 组（组地址为1）的两数据块均已被占用

（如图，图中Tag 的内容为二进制），CACHE 采用LRU 替换策略。

1．CACHE 分多少组？

2．给出主存的地址格式，说明个部分的位数与含义；

勤思考研，计算机考研专业课权威辅导！

3．上述4 个数中哪些数能直接从CACHE 中读取？若能，说明实际访问的是CACHE 中哪一组的哪个数据块的哪一个字节。

4．4 个数访问结束时Tag 内容如何变化。

十一。某机结构如题所示，该机字长16 位，图中所有寄存器均为16 位，控制器采用同步控制方式，每个CPU 周期包括4 个节拍周期，

数据总线及内总线均为16 位，存储器周期与CPU 节拍周期时间相等。加法指令ADD R1，1000H（R2）源操作数1000H（R2）是基址寻

址，目的操作数R1 是寄存器直接寻址，指令编码长度32 位，第1 个16 位包含了操作码、寻址方式和寄存器编号等指令核心部分，第2

个16 位是基址寻址的位移量1000H。并详细列出每个节拍周期对应于有效状态的控制

信号。

2005年真题

一．若散列函数为H(key)= i MOD 7,其中，i 为关键字key 的第一个字母在英文字母表中的序号，并且采用线性探测再散列方法处理冲突。

请画出在一个初始状态为空、地址值域为[0..6]的散列表中依次插入下列关键字MON,TUE,WED,THU,FRI,SAT,SUN 以后的散列表。

勤思考研，计算机考研专业课权威辅导！

二、所谓二叉树等价，是指它们不仅具有相同的拓扑结构，而且对应结点中包含相同的数据信息。

假设二叉树采用二叉链表存储结构，链结点构造为[lchild|data|rchild], 请写一递归算法，判断根结点指针分别为T1 与T2 的两棵二叉树是否

等价。若它们等价，算法返回1，否则返回0。（写成非递归算法不得分）

三、已知一具有n 个顶点的有向图G=（V，E）采用邻接表存储方法，请写一算法，检查任意给定序列v1,v2,?，vn (vi 属于V，1≤i≤n)

是否为该有向图的一个拓扑序列。若是，算法给出信息1，否则，给出信息0。

四、

1．若p1，p2，??，pm 是m 个不同的命题变元，A1，A2，??，An，B，C1，C2Cm 是命题逻辑公式，并且A1，A2，????An|=B，

证明：

2．用演绎定理证明├（A→B）→((B→C) →(A→C))。

五、1．在谓词逻辑里，假设A，B x 不是的自由变元。

B??xA ???B）??x（A ?证明：

若x 是B B 不成立的例子。??B）??A ?

yP(x,y)|=?x?2．假设P（x是否成立？用解释方法（如以自然数为论域）及归结方法证明上述判断。?六、1

234七、 1

2

3

4

5．进程被创建后的初始状态为“阻塞状态”。

6．仅当一个进程退出临界区以后，另一进程才能进入相应的临界区。

7．打印机是一类典型的块设备。

8．虚拟存储器的最大存储空间为内存容量与硬盘容量之和。

八、我们将只读数据的进程称为“读者”进程，而写或修改数据的进程称为“写者”进程。允许多个“读者”同时读数据，但不允许“写

者”与其他“读者”或“写者”同时访问数据。另外，要保证：一旦有“写者”等待时，新到达的“读者”

勤思考研，计算机考研专业课权威辅导！

必须等待，直到该“写者”完

成数据访问为止。试用P，V 操作正确实现“读者”与“写者”的同步。

九、1．按传输信息类别，系统总线一般包括（），（）和（）。

2．DRAM 的刷新方式一般有（）和（）两种。

3．中断响应时的保护现场实际上是指保存（）和（）的内容。

4．常见的微指令编码方式包括（），（）和（）三种。

十、1．某计算机的存储系统由Cache、主存和用于虚拟存储的磁盘组成。CPU 总是从Cache 中获得数据。若所访问的字在Cache 中，则

存取它只需要10ns，将所访问的字从主存装入Cache 需要40ns10us，假定Cache 的命中率为0.9，主存的

命中率为0.6，计算该系统访问一个字的平均存取时间。

2．指令系统格式设计过程中需要考虑哪些要素？并给出简简要说明。

3．某磁盘系统采用DMA 方式进行数据传送，磁盘转速为7200 转/8 盘与主存传诵数据的宽度为16

位。假定一条指令执行最长需要10us 十一、假设某机的主要部件包括：程序计数器PCIRR0、R1、R2、R3，暂存器C、D，算术逻辑运算单元ALU，

位移器SR，存储器地址寄存器MAR，存储器数据寄存器MDRM机器采用单总线结构。

1）

2） ，（R1R1）的寄存器间接寻址方式，目的操作数R0 存器直接寻址方式）。

2004一、

1、在具有

2、将一个元素才行。

3、设n 、2、3、?、n。出栈序列为P1、P2、?、Pn。若P1=n，则Pi(1<=i<=n)的值为（）。

4、深度为h 的非空完全二叉树中至少有（）个结点。

5、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是（）。

6、若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问到该图的所有顶点，则该图一定是一个（）图。

7、若一个非连通的无向图最多有28 条边，则该无向图至少有（）个顶点。

8、已知某带权连通无向图采用邻接矩阵存储方法，邻接矩阵以三元组表形式给出，不包括主对角线元素在内的下三角部分元素对应的各个三元组分别为（2，1，7），（3，1，6），（3，2，8），（4，1，9），（4，2，4），（4，3，6），（5，1，MAX），（5，2，4），（5，3，MAX），（5，4，2）。该连通图的最小生成树的权值之和为（）。

9、顺序查找方法、折半查找方法、树型查找方法和散列查找方法这四种方法中，只能在顺序存储结构下才