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

一、应用题

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

【答案】朴素的模式匹配(Brute.Force)时间复杂度是，KMP 算法有一定改进，时间复杂度达到O(m＋n) 。主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突出。

2． 对给定文件(28，07，39，10，65，14，61，17，50，21) 选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

【答案】快速排序的思想如下:首先将待排序记录序列中的所有记录作为当前待排序区域，以第一个记录的关键字作为枢轴(或支点) ，凡其关键字不大干枢轴的记录均移动至该记录之前，凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列

割成两部分:

和

和，且

进行快速排序。快速排序在记录有序时蜕变为起泡排序，

。假设编译时变量sum 和i 将分然后再递归地将初始序列:21移动:39移动:17移动:65移动:14移动:可用“三者取中”法改善其性能，避免最坏情况的出现。 3． 某程序中有如下循环代码段

P 起始地址为0804 8100H, 对应的汇编代码和机器代码如下表所示

分别分配在寄存器R1和R2中。常量N 在寄存器R6中, 数组A 的首地址在寄存器R3中, 程序段

表

执行上述代码的计算机M 采用32位定长指令字, 其中分支指令Bue 采用如下格式,

Op 为操作码:Rs 和Rd 为寄存器编号:OFFSET 为偏移量, 用补码表示。请回答下列问题, 并说明理由。

(1)M的存储器编址单位是什么？

(2)己知sll 指令实现左移功能, 数组A 中每个元素占多少位？

(3)上表中bne 指令的OFFSET 字段的值是多少？已知bne 指令采用相对寻址方式, 当前PC 内容为bne 指令地址, 通过分析上表中指令地址和bne 指令内容, 推断出bne 指令的转移目标地址计算公式。

(4)若M 采用如下“按序发射、ID(译码及取数) 、EXE(执按序完成”的5级指令流水线:IF(取指) 、

行) 、MEM(访存) 、WB(写回寄存器) , 且硬件不采取任何转发措施, 分支指令的执行均引起3个时钟周期阻塞, 则P 中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1的执行不会因为与指令5的数据相关而发生阻塞？

【答案】(1)由题可知, 指令为32为即4个字节, 而程序执行时是以4为间隔逐条取指令的, 故可知M 的存储器是采用字节编址。

(2)32位, 因为sll 中实现左移, 而

所以Bne 的OFFSET 为FFFAH 即-6。

由题可知Bne 采用相对寻址方式, 故有效地址

而PC 的值为当前Bne 指令的地址即

故

两者相差了18H 也就是24个字节, 而OFFSET 是-6,

故转移目标地址计算公式为(PC)。

(4)由指令序列可知, 指令1需写R4而指令2需读R4, 故指令2会因为数据相关而发生阻塞, 同理指令3、指令4也会因为数据相关而发生阻塞; 而指令6为分支指令, 故其存在控制冒险。因为分支指令会有3个时钟周期的阻塞, 故指令1的执行不会因为指令5的数据相关而发生阻塞。

4． 队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。

【答案】循环单链表若只设头指针，则出队操作时间复杂度是O (1)，而如对操作时间复杂度是O(n); 若只设尾指针，则出队和入队操作时间复杂度都是O (1)。因此，用循环单链表来实现队列，设置一个尾指针更合适。

, 而取完Bne 指令后, 。而要跳转到指令1的地址08048100H , , ,

即左移两位就是乘以4, 所以是位 (3)由Bne 的指令格式可知其OFFSET 为指令的后16位, 而Bne 的机器码码为1446 FFFAH ,

5． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23, 45, 52, 100, 11

和19的存储空间，然后再顺序释放大小为45, 52, 11的占用块。假设以伙伴系统实现态存储管理。

(1)画出可利用空间表的初始状态。

(2)画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。

(3)画出在回收3个占用块之后可利用空间表的状态。

【答案】(1)因为，可利用空间表的初始状态图如图1所示:

图1可利用空间表的初始状态

(2)当用户申请大小为23的内存块时，因

98

77，但没有大小为2的块，只有大小为2的596块，故将2的块分裂成两个大小为2的块，其中一块挂到可利用空间表上，另一块再分裂成两个大小为2的块。又将其中大小为2的一块挂到可利用空间表上，另一块再分裂成两个大小为2

65的块。其中一块2的块挂到可利用空间表上，另一块分裂成两个大小为2的块，其中一块挂到可

利用空间表上，另一块分给用户(地址0〜31) 。如此下去，最后每个用户得到的存储空间的起始地

址如图2所示，为6个用户分配所需要的存储空间后可利用空间表的状态如图3所示。

图2每个用户得到的存储空间的起始地址