当前位置：问答库＞考研试题

一、应用题

1． 在树和树中查找关键字时，有什么不同？

树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。字后，要继续查到最下层结点，得到查找成功与否的结论。另外，

键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

2． 已知图的邻接矩阵为：

当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：

（1）以顶点V1为出发点的唯一的深度优先遍历序列；

（2）以顶点V1为出发点的唯一的广度优先遍历序列；

（3）该图唯一的拓扑有序序列。

1）V1，V4，V9, V10，V7, V6, V8，V3，V2, V5 【答案】（

（2） V1, V4, V3, V2, V9, V7, V6, Y5, V10, V8

（3） V1, V2, V5, V3, V4, V6, V8, V7, V9, VIO

3． 请求分页管理系统中，假设某进程的页表内容如下表所示:

页面大小为4KB ，一次内存的访问时间是100ns ，一次快表（TLB ）的访问时间是10ns ，处

，进程的驻留集大小固定为2, 采理一次缺页的平均时间为108ns （已含更新TLB 和页表的时间）

用最近最少使用置换算法（LRU ）和局部淘汰策略。假设①TLB 初始为空；②地址转换时先访问

TLB , 若TLB 未命中，再访问页表（忽略访问页表之后的TLB 更新时间）；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列请问：

（1）依次访问上述三个虚地址，各需多少时间? 给出计算过程。

（2）基于上述访问序列，虚地址1565H 的物理地址是多少? 请说明理由。

【答案】⑴

页面大小为4KB ，因此，虚地址的低12位是页内偏移，其余高位是页号。

访问虚地址2362H , 虚页号为2，页内偏移362H 。查找TLB , TLB 初始为空，未命中，耗时10ns ; 访问页表，2号页面所在页框号为254H ，耗时100ns ; 计算得到的物理地址254362H ，访问内存，耗时100ns 。因此，总共用时

访问虚地址1565H ，虚页号为1, 页内偏移565H 。查找TLB ，未命中，耗时10ns ; 访问页表，有效位是0，未命中，耗时100m ; 产生缺页中断，进行缺页中断处理，耗时108m ; 采用LRU 置换算法，虚页1装入页帧号101H , 缺页中断处理完后，再次访问页表，命中，耗时100m ; 计算得到物理地址101565H ，再次访问内存，耗时100ns 。因此，总共用时

访问虚地址25A5H ，虚页号为2, 页内偏移5A5H 。查找TLB , 命中，耗时10ns ; 虚页2对应的页帧为254H ，因此计算得物理地址为2545A5H , 访问内存，耗时100ns 。因此，

总共用时

（2）当访问虚地址1565H 时，产生缺页中断，合法驻留集为2, 必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H 的对应的页框号为101H ，故可知虚地址1565H 的物理地址为101565H 。

4． 某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效，为0时表示无效，例如控制信号MDRinE 为1表示允许数据从DB 打入MDR ，MDRin 为1表示允许数据从内总线打入MDR 。假设MAR 的输出一直处于使能状态。加法指令“ADD （Rl ）, R0”的功能为（R0）+（（R1））－（R1）, 即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。

图

下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。

表

【答案】执行阶段每个节拍（时钟周期）的功能和有效控制信号见下表。

表