2017年东北师范大学数据结构(同等学力加试)复试实战预测五套卷
● 摘要
一、应用题
1． 假设Internet 的两个自治系统构成网络如题图所示，自治系统ASI 由路由器R1连接两个子网构成；自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口 IP 地址如题图所示。请回答下列问题。
题图网络拓扑结构
（1）假设路由表结构如下所示。请利用路由聚合技术，给出R2的路由表，要求包括到达题图中所有子网的路由，且路由表中的路由项尽可能少。
（2）若R2收到一个目的IP 地址为194.17.20.200的IP 分组，R2会通过哪个接口转发该IP 分组？
R1与R2之间利用哪个路由协议交换信息？该路由协议的报文被封装到哪个议的分组中（3）
进行传输？
【答案】
（1）在AS1中，子网中，子
网和子网单独连接到的接口可以聚合为子网但缺少子网
于是可以得到R2的路由表如下：
（2）该IP 分组的目的IP 地址194.17.20.200与路由表中194.17.20.0/23和194.17.20.128/25两个路由表项均匹配，根据最长匹配原则，R2将通过E0接口转发该1P 分组。
（3）R1与R2之间利用BGP4 （或BGP ）交换路由信息；BGP4的报文被封装到TCP 协议段中进行传输。2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此
和子网可以聚合为子网在AS2
基础综合真题及详解
2． 文件F 由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F 中，作为其第30条记录，请回答下列问题，并说明理由。
（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？
（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB ，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？
【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问
块存储块
F 的文件区的文件长度加1，起始块号减1
（2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29
块的链接地址存回磁盘又一次访存。一共就是
次。
4个字节的指针的地址范围为 所以此系统支撑文件的最大长度为
3． 某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个时钟周期。
相关内容
相关标签