2017年重庆师范大学计算机与信息科学学院数据结构(加试)复试实战预测五套卷
● 摘要
一、应用题
1． 假设利用边界标识法，并以首次拟合策略分配，己知在某个时刻可利用空间表的状态如图所示（注：存储块头部域的值和申请分配的存储量均包括头部和尾部的存储空间）请画出：
（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；
（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。
【答案】（1）系统回收一个起始地址为559，大小为45的空闲块后，因右侧起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示：
图1
（2）系统在接受存储块大小为100的请求后，将大小为117的空闲块分出100给予用户。在回收一个起始地址为515，大小为44的空闲块之后，因左侧起始地址为462、大小为53和右侧起始地址为559、大小为167均为空闲块，应与之合并。合并后，起始地址为462、大小为264的空闲块。链表状态如图2所示：
图2
2． 下列广义表，可以唯一对应一棵二叉树的有？并归纳出唯一对应的条件。
【答案】唯一对应一棵二叉树的有（2）、（3）和（5）。唯一对应的条件：空表、只有一个元素的表、每个子表个数是零或是2的表。
3． 在一棵表示有序集S 的二叉搜索树（binary search tree ）中，任意一条从根到叶结点的路径将S 分为3部分：在该路径左边结点中的元素组成的集合S1:在该路径上的结点中的元素组成的集合S2:在该路径右边结点中的元素组成的集合S3; S=S1US2US3, 若对于任意的
是否总有a ≤b ≤c? 为什么？
【答案】该结论不成立。例如，本题中对于任一
f 的左子树上。对于从a 到根结点路径上的所有，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在b 的右子树上，这时a>b，因此a 均有a 4． 输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。 （1）按次序构造一棵二叉排序树BS 。 （2）依此二叉排序树，如何得到一个从大到小的有序序列？ （3）画出在此二叉排序树中删除“66”后的树结构。 【答案】（1）构造的二叉排序树如图1所示： 图1 二叉排序树 （2）若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。 （3）如图2所示： 图2 5． 某计算机采用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）后为 故编址单位是字节。 题中给出偏移量OFFSET 为8位补码，其范围为-128〜127, 故相对当前指令进行条件跳转，