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

非淡泊无以明志，非宁静无以致远。——诸葛亮

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

时需转移。已知