2022年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库
2022年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（一）(2)
2022年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（二）(10)
2022年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（三）(19)
2022年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（四）(27)
2022年长春师范大学数据结构(同等学力及跨学科加试)考研复试核心题库（五）(35)
第1页，共39页
一、应用题
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位补码，其范围为-128127,故相对当前指令进行条件跳转，向后最多可跳转127条指令。
（2）指令中C=0,Z=l，N=l,故应根据ZF和NF的值来判断是否转移。当CF=0,ZF=0,NF=1
时需转移。已知指令中偏移量为11100011B=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．请阅读下列算法，回答问题。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。