2017年武汉大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有，2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构? 为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构? 为什么？
【答案】（1）应选择链式存储结构。因为它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O （1）。
（2）应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为O （1）。
2． 对于后序线索二叉树，怎样査找任意结点的直接后继? 对于中序线索二叉树，怎样査找任意结点的直接前驱？
【答案】（1）后序线索树中结点的后继的方法如下：根结点无后继：当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩于且双亲无右孩时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树种最左下的叶结点是其后继。
（2）对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则其前驱是其左子树上按中序遍历的最后一个结点。
3． 某计算机采用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 的值是多少？若该指令执行时
第 2 页，共 33 页 顺序执行时，下条指令地址
则该指令执行后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）部件①指令寄存器：用于存放当前指令；部件②移位寄存器：用于左移一位；部件③加法器：地址相加。
4． 某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节。请回答下列问题。
（1）若使用一级页表的分存储管理方式，逻辑地址结构为：
则页的大小是多少字节？页表最大占用多少字节？
（2）若使用二级页表的分存储管理方式，逻辑地址结构为：
设逻辑地址为LA ，请分别给出其对应的页目录号和表索引达式。
第 3 页，共 33 页
（3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为00008000H ，其长度为8KB ，被装载到从物理地址00900000H 开始的连续主存空间中。页表从主存0020 0000H 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这两个页表项中的框号以及代码页面2的起始物理地址。
【答案】
（1）因为页内偏移量是12位所以页大小为4KB 页表项数为页表索引可表示为：
表项，所以第8个页表项的物理地址=页表起始地
址
如下图所示。
该一级页表最大为 页表项的字节
数（2）页目录号可表示为：（3）代码页面1的逻辑地址为0000 8000H, 表明其位于第8个页处，对应页表中的第8个页
5． 设目标为模式为
（1）计算模式p 的nextval 函数值；
（2）不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。
【答案】（1）P 的nextval 函数值为0110132（P 的next 函数值为0111232）。
（2）利用KMP （改进的nextval ）算法，每趟匹配过程如下：
第一趟匹配：
abcab （i=5, j=5）
第二趟匹配：
abc （i=7，j=3）
第三趟匹配：
a （i=7，j=l）
第四趟匹配：
第 4 页，共 33 页
相关内容
相关标签