2017年大连海事大学数据结构(同等学力加试)考研复试核心题库
● 摘要
一、应用题
1． 某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB , 主存（物理）地址空间大小为1MB , 页面大小为4KB ; Cache 采用直接映射方式，共8行；主存与Cache 之间交换的块大小为32B ，系 统运行到某一时刻时，页表的部分内容和Cache 的部分内容分别如题a 图、题b 所示：图中页框号及标记字段的内容为十六进制形式。
图
a
图b
请回答下列问题。
（1）虚拟地址共有几位，哪几位表示虚页号? 物理地址共有几位，哪几位表示页框号（物理页号）？
（2）使用物理地址访问Cache 时，物理地址应划分哪几个字段? 要求说明每个字段的位数及在物理地址中的位置。
（3）虚拟地址001C60H 所在的页面是否在主存中? 若在主存中，则该虚拟地址对应的物理地址是什么? 访问该地址时是否Cache 命中? 要求说明理由。
（4） 假定为该机配置一个4路组相联的TLB , 该TLB 共可存放8个页表项，若其当前内容
（十六进制）如题c 图所示，则此时虚拟地址024BACH 所在的页面是否在主存中? 要求说明理由。
题c 图TLB 的部分内容
【答案】（1）由于页面大小为4KB , 页内地址需要12位，所以虚拟地址24位，其中虚页号
占12位；物理地址 20位，其中页框号（实页号）占8位。
（2）主存物理地址20位，从左至右应划分3个字段：标记字段、块号字段、块内地址字段。其中标记12 位，块号3位，块内地址5位。
（3）虚拟地址001C60H=0000 0000 0001 1100 0110 0000B，该虚拟地址的虚页号为001H ，查
，表明此页在主存中，页框号为04H , 对应的20位页表可以发现，虚页号1对应的有效位为“1”
物理地址是04C60H = OOOOOlOOllOOOllOOOOOB。
访问该地址时，Cache 不命中，因为Cache 采用直接映射方式，对应的物理地址应该映射到Cache 的第3行 中，其有效位为1，标记值
不命中。
（4） 虚拟地址024BACH = 000000100100101110101100B ，虚页号为024H ，TLB 中存放8个页表项，采用4路组相联，即TLB 分为2组，每组4个页表项。12位虚页号字段中最低位作为组索引，其余11位为标记位。 现在最低位为0, 表明选择第0组，11位的标记为012H ，根据标记可以知道TLB 命中，所在的页面在主存中。 因为如果在TLB 中查到了页表项，即TLB 命中，说明所在页一定命中
2． 请回答下列关于堆（Heap ）的一些问题：
（1）堆的存储表示是顺序的还是链接的？
（2）设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？
（3）对n 个元素进行初始建堆的过程中，最多做多少次数据比较（不用大0表示法）？
【答案】（1）堆的存储是顺序的。
（2）最大值元素一定是叶结点，在最下两层上。
（3）在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下：
由于第i 层上的结点数至多是以它为根的二叉树的深度为则调用次筛选算法时总共进行的关键字比较次数不超过下式之值：
3． 某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节。请回答下列问题。
（1）若使用一级页表的分存储管理方式，逻辑地址结构为：
则页的大小是多少字节？页表最大占用多少字节？
（2）若使用二级页表的分存储管理方式，逻辑地址结构为：
设逻辑地址为LA ，请分别给出其对应的页目录号和表索引达式。
，（物理地址高12位）故访问该地址时Cache
（3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为00008000H ，其长度为8KB ，被装载到从物理地址00900000H 开始的连续主存空间中。页表从主存0020 0000H 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这两个页表项中的框号以及代码页面2的起始物理地址。
【答案】
（1）因为页内偏移量是12位所以页大小为4KB 页表项数为页表索引可表示为：
表项，所以第8个页表项的物理地址=页表起始地
址
如下图所示。
该一级页表最大为 页表项的字节
数（2）页目录号可表示为：（3）代码页面1的逻辑地址为0000 8000H, 表明其位于第8个页处，对应页表中的第8个页
4． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。
图1
【答案】森林转换为二叉树分以下三步：
（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。
（3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。
所以由上面三棵树转换得到的二叉树如图2所示：
相关内容
相关标签