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

一、应用题

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

页面大小为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 。

2． 画出对算术表达式求值时操作数栈和运算符栈的变化过程。

求值，过程如【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式

表所示。

表 操作数栈和运算符找的变化过程

3． 将算术表达式（（a+b）+c*（d+e）+f）*（g+h）转化为二叉树。

【答案】该算术表达式转化的二叉树如图所示。

图

4． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。

（1）试问这种二叉树的结点总数是多少？

（2）试证明 。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。

【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结

点且非叶子结点均有左子树的二叉树的结点数是2n-l 。

（2）证明：当i=l时，

成立。

设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公

，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为

5． 已知一个带有表头结点的单链表，结点结构为datalink , 假设该链表只给出了头指针list 。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的data 域的值，并返回1; 否则，只返回0。要求：

（1）描述算法的基本设计思想；

（2）描述算法的详细实现步骤；

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C 或

，关键之处请给出简要注释。 现）

【答案】（1）算法的基本设计思想定义两个指针变量p 和q ，初始时均指向头结点的下一个结点。p 指针沿链表移动；当p 指针移动到第k 个结点时，q 指针开始与p 指针同步移动；当p 指针移动到链表最后一个结点时，因为p 和q 相隔k ，故q 指针所指元素为倒数第k 个结点。以上过程对链表仅进行一遍扫描。

（2）算法的详细实现步骤

①count=0, p 和q 指向链表表头结点的下一个结点；

②若p 为空，转⑤; ，

③若count 等于k ，则q 指向下一个结点；否则，count=count+l;

④p 指向下一个结点，转步骤②；

⑤若count 等于k ，则查找成功，输出该结点的data 域的值，返回1; 否则，查找失败，返回0;

⑥算法结束。

（3）算法实现

, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍或JA V A 语言实