2017年陕西科技大学902数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求
真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有为了不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
2． 某程序中有如下循环代码段p :
P 起始地址 为0804 8100H，对应的汇编代码和机器代码如下表所示
两头匹配的假设编译时变量sum 和i 分别分配在寄存器R1和R2中。常量N 在寄存器R6中，数组A 的首地址在寄存器R3中，程序段
执行上述代码的计算机M 采用32位定长指令字，其中分支指令Bne 采用如下格式，
Op 为操作码：Rs 和Rd 为寄存器编号：OFFSET 为偏移量，用补码表示。请回答下列问题，并说明理由。
（1）M 的存储器编址单位是什么？
（2）已知sll 指令实现左移功能，数组A 中每个元素占多少位？
（3）表中bne 指令的OFFSET 字段的值是多少？已知bne 指令采用相对寻址方式，当前PC 内容为bne 指令地址，通过分析表中指令地址和bne 指令内容，推断出bne 指令的转移目标地址计算公式。
（4）若M 采用如下“按序发射、按序完成”的5级指令流水线：IF （取指）、ID （译码及
，且硬件不采取任何转发措施，分取数）、EXE （执 行）、MEM （访存）、WB （写回寄存器）
支指令的执行均引起3个时钟周期阻塞，则P 中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1 的执行不会因为与指令5的数据相关而发生阻塞？
【答案】（1）由题可知，指令为32为即4个字节，而程序执行时是以4为间隔逐条取指令的，故可知M 的存储器是采用字节编址。
（2）32位，因为sll 中实现左移，而（R2） <<2 R4即左移两位就是乘以4，所以是
位
（3）由Bne 的指令格式可知其OFFSET 为指令的后16位，而Bne 的机器码码为1446 FFFAH，所以Bne 的OFFSET 为FFFAH 即-6。
由题可知Bne 采用相对寻址方式，故有效地址
为当前Bne 指令的地址
即而取完Bne 而PC 的值指令后
，
而要跳转到指令1的地址08048100H ，两者相差了18H 也
就是24个字节，而OFFSET 是-6, 故转移目标地址计算公式为（PC
）
（4）由指令序列可知，指令1需写R4而指令2需读R4, 故指令2会因为数据相关而发生阻塞，同理指令3、指令4也会因为数据相关而发生阻塞；而指令6为分支指令，故其存在控制冒险。因为分支指令会有3个时钟周期的阻塞，故指令1的执行不会因为指令5的数据相关而发生阻塞。
3． 某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB , 主存（物理）地址空间大小为1MB , 页面大小为4KB ; Cache 采用直接映射方式，共8行；主存与Cache 之间交换的块大小为32B ，系 统运行到某一时刻时，页表的部分内容和Cache 的部分内容分别如题a 图、题b 所示：图中页框号及标记字段的内容为十六进制形式。
图
a
图b
请回答下列问题。
（1）虚拟地址共有几位，哪几位表示虚页号? 物理地址共有几位，哪几位表示页框号（物理页号）？
（2）使用物理地址访问Cache 时，物理地址应划分哪几个字段? 要求说明每个字段的位数及在物理地址中的位置。
（3）虚拟地址001C60H 所在的页面是否在主存中? 若在主存中，则该虚拟地址对应的物理地址是什么? 访问该地址时是否Cache 命中? 要求说明理由。
（4） 假定为该机配置一个4路组相联的TLB , 该TLB 共可存放8个页表项，若其当前内容
（十六进制）如题c 图所示，则此时虚拟地址024BACH 所在的页面是否在主存中? 要求说明理由。
题c 图TLB 的部分内容
【答案】（1）由于页面大小为4KB , 页内地址需要12位，所以虚拟地址24位，其中虚页号占12位；物理地址 20位，其中页框号（实页号）占8位。
（2）主存物理地址20位，从左至右应划分3个字段：标记字段、块号字段、块内地址字段。其中标记12 位，块号3位，块内地址5位。
（3）虚拟地址001C60H=0000 0000 0001 1100 0110 0000B，该虚拟地址的虚页号为001H ，查
，表明此页在主存中，页框号为04H , 对应的20位页表可以发现，虚页号1对应的有效位为“1”
物理地址是04C60H = OOOOOlOOllOOOllOOOOOB。
访问该地址时，Cache 不命中，因为Cache 采用直接映射方式，对应的物理地址应该映射到Cache 的第3行 中，其有效位为1，标记值
不命中。
（4） 虚拟地址024BACH = 000000100100101110101100B ，虚页号为024H ，TLB 中存放8个页表项，采用4路组相联，即TLB 分为2组，每组4个页表项。12位虚页号字段中最低位作为组索引，其余11位为标记位。 现在最低位为0, 表明选择第0组，11位的标记为012H ，根据标记可以知道TLB 命中，所在的页面在主存中。 因为如果在TLB 中查到了页表项，即TLB 命中，说明所在页一定命中
4． S 是字符数组
，中存放的是该字符串的有效长度，
假设说明下列程序的功能及执行结果。
，（物理地址高12位）故访问该地址时Cache 中字符串的内容为
相关内容
相关标签