当前位置：问答库＞考研试题

一、应用题

1． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式给出它的next 函数值及next 函数的修正值nextval 之值。

【答案】KMP 算法的时间复杂性是

p 的next 和nextval 值分别为01112212321和

01102201320。

2． 某16位计算机中，带符号整数用补码表示，数据Cache 和指令Cache 分离。题表给出了指令系统中部分指令格式，其中Rs 和Rd 表示寄存器，mem 表示存储单元地址，（X ）表示寄存器X 或存储单元X 的内容。

表 指令系统中部分指令格式

请

该计算机采用5段流水方式执行指令，各流水段分别是取指（IF ）、译码/读寄存器（ID ）、执行/计算有效地址（EX ）、访问存储器（M ）和结果写回寄存器（WB ）, 流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。

（1）若int 型变量x 的值为-513, 存放在寄存器R1中，则执行指令“SHR R1”后，R1的内容是多少？（用十六进制表示）

（2）若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少？

（3）若高级语言程序中某赋值语句为址分别表示为

和b 均为int 型变量，它们的存储单元地

该语句对应的指令序列及其在指令流水线中的执行过程如题图所示。

则这4条指令执行过程中，的ID 段和的IF 段被阻塞的原因各是什么？

图 指令序列及其执行过程示意图

（4）若高级语言程序中某赋值语句为储单元地址分别表示为

【答案】 （1）x 的机器码为1110 1111 1111B, 即指令执行后

（2）至少需要

即指令执行前（Rl ） =FDFFH, 右移lwei 后为1111

个时钟周期数。

x 和a 均为unsigned int 类型变量，它们的存

则执行这条语句至少需要多少个时钟周期? 要求模仿题图画出这

条语句对应的指令序列及其在流水线中的执行过程示意图。

（3）的ID 段被阻塞的原因：因为

与和都存在数据相关，需等到和将结果写回寄存器后，才能读寄存器内容，所以的ID 段被阻塞。

的IF 段被阻塞的原因：因为14的前一条指令在ID 段被阻塞，所以，的IF 段被阻塞。（4）

对应的指令序列为：

这5条指令在流水线中的执行过程如下图所示，执行

语句最少需要17个时钟周期。

3． 给出模式串

在KMP 算法中的next 和nextval 数组。

【答案】模式串的next 函数定义如下：

根据此定义，

可求解模式串

的next 和nextval 值如下：

4． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？

【答案】（1）动态存储分配伙伴系统的基本思想

在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容

量为

则空闲块大小只能是

由同一大块分裂而得的两个小块互称“伙伴空

（若

）

，

如内存大小为

间”或

的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若

（2）和边界标识法的不同

边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。

5． 为什么文件的倒排表比多重表组织方式节省空间？

【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。

6． 阅读下面的算法，说明算法实现的功能。

【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。Head1最后一个结点的链域指向head2, head2最后一个结点的链域指向headl ，headl 为结果循环链表的指针。

7． 已知有6个顶点（顶点编号为0--5）的有向带权图G , 其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。

要求：

（1）写出图G 的邻接矩阵A 。 （2）画出有向带权图G 。

空间。起始地址为P ，

大小为的内存块，其伙伴的起始地址为：

）。