2022年东北电力大学信息工程学院852数据结构考研核心题库

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 32 页

目录

2018年东北电力大学信息工程学院852数据结构考研核心题库（一） (2)

2018年东北电力大学信息工程学院852数据结构考研核心题库（二） (10)

2018年东北电力大学信息工程学院852数据结构考研核心题库（三） (15)

2018年东北电力大学信息工程学院852数据结构考研核心题库（四） (20)

2018年东北电力大学信息工程学院852数据结构考研核心题库（五） (28)

专注考研专业课13年，提供海量考研优质文档！

第 2 页，共 32 页 2018年东北电力大学信息工程学院852数据结构考研核心题库（一）

说明：本套核心题库按照考试大纲、历年真题、指定参考书等结合考试侧重点和难度，精心整理编写。核心题库更突出针对性和实战性，考研冲刺必备资料。

——————————————————————————————————————————

一、综合题

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

页面大小为4KB ，一次内存的访问时间是100ns ，一次快表(TLB)的访问时间是10ns ，处理一次缺页的平均时间为108ns(已含更新TLB 和页表的时间)，进程的驻留集大小固定为2,采用最近最少使用置换算法(LRU)和局部淘汰策略。假设①TLB 初始为空；②地址转换时先访问TLB ,若TLB 未命中，再访问页表(忽略访问页表之后的TLB 更新时间)；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H 、1565H 、25A5H ,请问:

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

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

【答案】(1)210ns ;108ns ;110ns 。

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

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

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

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

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

专注考研专业课13年，提供海量考研优质文档！

第 3 页，共 32 页 的物理地址为101565H 。

2． 某文件系统为一级目录结构,文件的数据一次性写入磁盘,已写入的文件不可修改,但可多次创建新文件。请回答如下问题。

(1)在连续、链式、索引三种文件的数据块组织方式中,哪种更合适?要求说明理由。为定位文件数据块。需要在FCB 中设计哪些相关描述字段？

(2)为快速找到文件,对于FCB ,是集中存储好,还是与对应的文件数据块连续存储好?要求说明理由。

【答案】根据题目所给条件,文件系统为一级目录结构,文件的数据一次性写入磁盘,已写入的文件不可修改,但是可以多次创建新文件,我们得知该文件系统是不能修改原文件的,只能将修改后的文件按新文件来存储,这与一次刻录光盘的存储方式相似。对于这样的系统,因为不需要随时添加或删除文件的内容,所以一次写入的文件的大小是固定不变的,也是可预知的,而连续存放文件的方式就有其优点。这种方式只需要知道文件的起始地址和文件的大小,便可以通过计算的方法找到文件的任何位置。文件若需要修改,则原文件作废,修改以后的文件以新文件的形式重新写入,不会产生存储碎片,高效,高利用率。所以,如下作答。

(1)连续的数据块组织方式更合适,因为文件的数据一次性写入磁盘,已写入的文件不可修改,但是可以多次创建新文件,我们得知该文件系统是不能修改原文件的,只能将修改后的文件按新文件来存储。不需要随时添加或删除文件的内容,所以一次写入的文件的大小是固定不变的,也是可预知的。这样,只需要知道文件的起始地址和文件的大小,便可以通过计算的方法访问文件的任意位置。

为定位文件数据块。需要在FCB 中设计相关描述字段有:

<起始块号,块数>或者<起始块号,结束块号>。

(2)将所有的FCB 集中存放,文件数据集中存放。这样在随机查找文件名时,只需访问FCB 对应的块,可减少磁头移动和磁盘访问次数。

3． 两个字符串s1和s2的长度分别为m 和n 。求这两个字符串最大共同子串算法的时间复杂度为T(m ，n)。估算最优的T(m ，n)，并简要说明理由。

【答案】最优的T(m ，n)是D(n)。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度。一般情况下，

4． 下列关于堆(Heap)的一些问题:

(1)堆的存储表示是顺序的还是链接的？

(2)设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？

(3)对n 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O 表示法)？

【答案】(1)堆的存储是顺序的。

专注考研专业课13年，提供海量考研优质文档！

第 4 页，共 32 页 (2)最大值元素一定是叶结点，在最下两层上。

(3)在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下:

由于第i 层上的结点数至多是，以它为根的二叉树的深度为h －i+1，则调用次筛选算法时总共进行的关键字比较次数不超过下式之值:

5． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23,45,52,100,11

和19的存储空间，然后再顺序释放大小为45,52,11的占用块。假设以伙伴系统实现态存储管理。

(1)画出可利用空间表的初始状态。

(2)画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。

(3)画出在回收3个占用块之后可利用空间表的状态。

【答案】(1)因为，可利用空间表的初始状态图如图1所示:

图1可利用空间表的初始状态

(2)当用户申请大小为23的内存块时，因

，但没有大小为25的块，只有大小为29的块，故将29的块分裂成两个大小为28

的块，其中一块挂到可利用空间表上，另一块再分裂成两个大小为27的块。又将其中大小为27的一块挂到可利用空间表上，另一块再分裂成两个大小为2

6的块。其中一块26的块挂到可利用空间表上，另一块分裂成两个大小为25的块，其中一块挂到可

利用空间表上，另一块分给用户(地址0?31)。如此下去，最后每个用户得到的存储空间的起始地

址如图 …… 此处隐藏：1595字，全部文档内容请下载后查看。喜欢就下载吧 ……