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

一、应用题

1． KMP 算法（字符串匹配算法）较Brute （朴素的字符串匹配）算法有哪些改进？

【答案】朴素的模式匹配度达到

时，KMP 算法的优点更为突出。

2． 下面程序段的时间复杂度是什么？

【答案】赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O （m*n）。

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

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

时间复杂度是

KMP 算法有一定改进，时间复杂

主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配

该计算机采用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个时钟周期。

4． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。

图1

【答案】森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：

图2

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

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