2017年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库

目录

2017年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（一） (2)

2017年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（二） (10)

2017年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（三） (19)

2017年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（四） (27)

2017年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（五） (35)

第1 页，共39 页

第 2 页，共 39 页 2017年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（一） 说明：本资料为学员内部使用，整理汇编了2017考研复试重点题及历年复试常考题型。 ————————————————————————————————————————

一、应用题

1． 阅读下列算法，指出算法A 的功能和时间复杂性。

【答案】功能：将原单循环链表分解成两个单循环链表：其一包括结点h 到结点g 的前驱结点；另一个包括结点g 到结点h 的前驱结点。

时间复杂度：0（n ）。

2． 索引顺序存取方法（ISAM ）中，主文件已按关键字排序，为何还需要主关键字索引？

【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道（盘面）三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道（盘面）三级索引。在ISAM 文件上检索记录时，先从主索引（柱面索引的索引）找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。

3． 某计算机采用16位定长指令字格式，其CPU 中有一个标志寄存器，其中包含进位/借位标志CF 、零标志ZF 和符号标志NF 。假定为该机设计了条件转移指令，其格式如下：

其中，00000为操作码OP ; C 、Z 和N 分别为CF 、ZF 和NF 的对应检测位，某测位为1时表示需检测对应标志，需检测的标志位中只要有一个为1就转移，否则就不转移，例如，

若

则需检测CF 和NF 的值，当CF=1或NF=1时发生转移；

OFFSET 是相对偏移量，用补码表示。转移执行时，转移目标地址为

顺序执行时，下条指令地址

为请回答下列问题。

（1）该计算机存储器按字节编址，还是按字编址？该条件转移指令向后（反向）最多可跳转最多少条指令？

（2） 某条件转移指令的地址为200CH ，指令内容如下图所示，若该执行时

第 3 页，共 39 页

则该指令执行后PC 的值是多少？若该指令执行时

则该指令执行后PC 的值又是多少？请给出计算过程。

（3）实现“无符号数比较小于等时转移”功能的指令中，C 、Z 和N 应各是什么？

（4）以下是该指令对应的数据通路示意图，要求给出中部件①?③的名称或功能说明。

【答案】

（1）因为指令长度为16位且下条指令地址为

故编址单位是字节。 题中给出偏移量OFFSET 为8位补码，其范围为-128?127,故相对当前指令进行条件跳转，向后最多可跳转127条指令。

（2）指令中C = 0, Z=l ，N=l ,故应根据ZF 和NF 的值来判断是否转移。当CF=0, ZF=0, NF=1

时需转移。已知指令中偏移量为1110 0011B=E3H ,符号扩展后为FFE3H ,左移一位（乘2）后为FFC6H ,故PC 的值（即转移目标地址）为

时不转移。PC

的值为

（3）指令中的C 、Z 和N 应分别设置为

（4）部件①指令寄存器：用于存放当前指令；部件②移位寄存器：用于左移一位；部件③加

法器：地址相加。

第 4 页，共 39 页 4． 设某计算机的逻辑地址空间和物理地址空间均为64KB ,按字节编址。若某进程最多需要6页（Page ）数据存储空间，页的大小为1KB ,操作系统采用固定分配局部置换策略为此进程分配4个页框（PageFrame ）。在时刻260前的该进程访问情况如下表所示（访问位即使用位）。

当该进程执行到时刻260时，要访问的逻辑地址为17CAH 的数据，请回答下列问题： （1）该逻辑地址对应的页号是多少？

（2）若采用先进先出（FIFO ）置换算法，该逻辑地址对应的物理地址是多少?要求给出计算过程。

（3）若采用时钟（CLOCK ）置换算法，该逻辑地址对应的物理地址是多少?要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如图所示）

图

【答案】（1）由题可知计算机的逻辑地址空间和物理地址空间均为64KB=216B ,按字节编址，并且页的大小为IK=210,故逻辑地址和物理地址的地址格式均为：

地址17CA=0001011111001010B ，故可知其逻辑页号为000101B=5。

（2）根据FIFO 算法，需要替换出最早装入的页，故需置换0号页，将5号页装入7号页框中，所以物理地址为0001111111001010B=1FCAH 。

（3）根据CLOCK 算法，如果当前指针所指页框的使用位为0,则替换该页，否则将使用位清零，并将指针指向下一个页框，继续查找。由题可知，将从2号页框开始，前4次查找页框号的顺序为2、4、7、9,并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位已经为0,故将2号页框的页将5号装入2号页框，并将其对应使用位设置为1,所以对应的物理地址为0000101111001010B=0BCAH 。

5． 请阅读下列算法，回答问题。

本文来源：https://www.bwwdw.com/article/qzgi.html