2018年东北大学计算机科学与工程学院842计算机专业基础之数据结构考研仿真模拟五套题
● 摘要
一、综合题
1． 假设Internet 的两个自治系统构成网络如下图所示, 自治系统ASI 由路由器R1连接两个子网构成; 自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口IP 地址如下图所示。请回答下列问题。
图 网络拓扑结构
(1)假设路由表结构如下所示。请利用路由聚合技术, 给出R2的路由表, 要求包括到达上图中所有子网的路由, 且路由表中的路由项尽可能少。
(2)若R2收到一个目的IP 地址为
行传输？
【答案】(1)在AS1中, 子网AS2中, 子
网
; 子网和子
网和子网可以聚合为子网可以聚合为子
网, 在, 但缺
少的IP 分组, R2会通过哪个接口转发该IP 分组？ (3)R1与R2之间利用哪个路由协议交换信息？该路由协议的报文被封装到哪个议的分组中进单独连接到R2的接口E0。
于是可以得到R2的路由表如下:
(2)该IP 分组的目的IP 地址与路由表中第 2 页，共 32 页 和两个路由表项均匹配, 根据最长匹配原则, R2将通过E0接口转发该1P 分组。
(3)R1与R2之间利用BGP4(或BGP) 交换路由信息; BGP4的报文被封装到TCP 协议段中进行传输。
2． 证明:具有n 个顶点和多于n －1条边的无向连通图G —定不是树。
【答案】证明:具有n 个顶点n －1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n －1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。
3． 请求分页管理系统中，假设某进程的页表内容如下表所示:
页面大小为4KB ，一次内存的访问时间是100ns ，一次快表(TLB)的访问时间是10ns ，处理一次缺页的平均时间为108ns(已含更新TLB 和页表的时间) ，进程的驻留集大小固定为2, 采用最近最少使用置换算法(LRU)和局部淘汰策略。假设①TLB 初始为空；②地址转换时先访问TLB , 若TLB 未命中，再访问页表(忽略访问页表之后的TLB 更新时间) ；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H 、1565H 、25A5H , 请问:
(1)依次访问上述三个虚地址，各需多少时间? 给出计算过程。
(2)基于上述访问序列，虚地址1565H 的物理地址是多少? 请说明理由。
8【答案】(1)210ns; 10ns ; 110ns 。
页面大小为4KB ，因此，虚地址的低12位是页内偏移，其余高位是页号。
访问虚地址2362H , 虚页号为2，页内偏移362H 。查找TLB ，TLB 初始为空，未命中，耗时10ns ; 访问页表，2号页面所在页框号为254H , 耗时100ns ; 计算得到的物理地址254362H , 访问内存，耗时100ns 。因此，总共用时10＋100＋100＝210ns 。
访问虚地址1565H ，虚页号为1，页内偏移565H 。查找TLB ，未命中，耗时10ns ; 访问页表，有效位是0, 未命中，耗时100ns ; 产生缺页中断，进行缺页中断处理，耗时108ns ; 采用LRU 置换算法，虚页1装入页帧号101H ，缺页中断处理完后，再次访问页表，命中，耗时100ns ; 计算得到物理地址101565H ，再次访问内存，耗时100ns 。因此，总共用时10＋100＋108＋100≈108ns 。
访问虚地址25A5H , 虚页号为2, 页内偏移5A5H 。查找TLB ，命中，耗时10ns ; 虚页2对应的页帧为254H , 因此计算得物理地址为2545A5H , 访问内存，耗时100ns 。因此，总共用时10＋100＝110ns 。
第 3 页，共 32 页
(2)当访问虚地址1565H 时，产生缺页中断，合法驻留集为2, 必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H 的对应的页框号为101H ，故可知虚地址1565H 的物理地址为101565H 。
4． 某程序中有如下循环代码段
P 起始地址为0804 8100H, 对应的汇编代码和机器代码如下表所示
。假设编译时变量sum 和i 分别分配在寄存器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 指令的地址即
第 4 页，共 32 页 即左移两位就是乘以4, 所以是位 (3)由Bne 的指令格式可知其OFFSET 为指令的后16位, 而Bne 的机器码码为1446 FFFAH , , , 而取完Bne 指令后, ,