2017年沈阳师范大学数据结构(同等学力加试)考研复试核心题库
● 摘要
一、应用题
1． 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价，检索、插入、删除记录时的优点和缺点。
【答案】（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。
（2）索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，提高了索引的查找速度。
（3）散列文件也称直接存取文件，根据关键字的哈希函数值和处理冲突的方法，将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，这很费时。
2． 某计算机采用16位定长指令字格式，其CPU 中有一个标志寄存器，其中包含进位/借位标志CF 、零标志ZF 和符号标志NF 。假定为该机设计了条件转移指令，其格式如下：
其中，00000为操作码OP ; C、Z 和N 分别为CF 、ZF 和NF 的对应检测位，某测位为1时表示需检测对应标志，需检测的标志位中只要有一个为1就转移，否则就不转移，例如，
若
OFFSET 是相对偏移则需检测CF 和NF 的值，当CF=1或NF=1时发生转移；
量，用补码表示。转移执行时，转移目标地址为
为请回答下列问题。
（1）该计算机存储器按字节编址，还是按字编址？该条件转移指令向后（反向）最多可跳转最多少条指令？
（2） 某条件转移指令的地址为200CH ，指令内容如下图所示，若该执行
时
则该指令执行后PC 的值是多少？若该指令执行时
则该指令执行后PC 的值又是多少？请给出计算过程。
（3）实现“无符号数比较小于等时转移”功能的指令中，C 、Z 和N 应各是什么？
顺序执行时，下条指令地址
（4）以下是该指令对应的数据通路示意图，要求给出中部件①〜③的名称或功能说明。
【答案】
（1）因为指令长度为16位且下条指令地址为
向后最多可跳转127条指令。
N=l, 故应根据ZF 和NF 的值来判断是否转移。（2）指令中C = 0, Z=l，当CF=0, ZF=0, NF=1
时需转移。已知指令中偏移量为1110 0011B=E3H, 符号扩展后为FFE3H , 左移一位（乘2）后为FFC6H , 故PC 的值（即转移目标地址）为
PC
的值为
（3）指令中的C 、Z 和N 应分别设置为时不转移。故编址单位是字节。 题中给出偏移量OFFSET 为8位补码，其范围为-128〜127, 故相对当前指令进行条件跳转，
（4）部件①指令寄存器：用于存放当前指令；部件②移位寄存器：用于左移一位；部件③加法器：地址相加。
3． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？
【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于査找结点的前驱和后继，因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便. 但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定：当ltag=0时，lchild 指向左子树，当ltag=1时，lchild 指向前驱：当rtag=0时，rchild 指向右子树，当rtag=l时，rctiild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（利用后序线索二叉树査后扔继续要栈）。
4． 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？
【答案】有两种方法，具体如下：
（1）对该算术表达式（二叉树> 进行后序遍历. 得到表达式的后序遍历序列，再按后缀表达
式求值。
（2）递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、
一、*、/等） 进行求值。
5． 写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。
【答案】此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。
第一趟：12，23，35，16，25，36， 19，21，16， 47
第二趟：12，16，23，35，16，25，36， 19，21，47
第三趟：12，16，23，16，25，35， 19，21，36， 47
第四趟：12， 16， 16，23， 19， 25， 35， 21， 36，47
第五趟：12，16，16，19，23，25，21，35， 36， 47
第六趟：12，16，16，19，21， 23，25，35， 36， 47
第七趟：12，16，16，19，21，23，25，35， 36， 47
6． 用一个数组S （设大小为MAX ）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的
，其中i 为0或1，用判断条件，并用C 语言或PASCAL 语言设计公用的入栈操作push （i ，x ）
于表示栈号，x 为入栈值。
，栈底设在数组的两端，两栈顶相邻时为栈满。设【答案】两栈共享一向量空间（一维数组）
共享数组为S[MAX]，则一个栈顶指针为一1，另一个栈顶指针为MAX 时，栈为空。用C 语言写的入栈操作push （i ，x ）如下：