2017年东华大学F1502C语言与数据结构算法上机测试之数据结构(C语言版)复试实战预测五套卷
● 摘要
一、应用题
1． 某文件系统空间的最大容量为4TB 以磁盘块为基本分配单位，磁盘块大小为1KB 。文件控制块（FCB ）包含一个512B 的索引表区。请回答下列问题。
（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节? 可支持的单个文件最大长度是多少字节？
（2）假设索引表区采用如下结构：第0〜7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B ，块数占2B ; 剩余504字节采用直接索引结构，一个索引项占6B ，则可支持的单个文件最大长度是多少字节? 为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理 值并说明理由。
【答案】
（1）文件系统存储空间共有块数可存放
（2） 为表示个块号，索引表项占512B 个索引项，每个索引项对应一个磁盘块，故最大文件长度：块号占6字节，块数占2字节的情形下，最大文件长度
：
理由：合理的起始块号和块数所占字节数分别为
块数占4B 或以上，就可表示4TB 大小的文件长度，达到文件系统的空间上限。
2． 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树；
（2）若查找元素54，需依次与哪些元素比较？
（3）若查找元素90，需依次与哪些元素比较？
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
【答案】（1）判定树如图所示：
图 判定树
（2）若查找元素54，需依次和元素30、63、42、54比较，查找成功。
（3）若查找元素90，需依次和元素30、63、87、95比较，查找失败。
（4）
3． 设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造3阶树。要求从空树开始，每插入一个关键字，画出一棵树。
【答案】如图所示：
图
4． 某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为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 命中，说明所在页一定命中
，（物理地址高12位）故访问该地址时Cache