2017年沈阳建筑大学数据结构(同等学力加试)考研复试核心题库
● 摘要
一、应用题
1． 某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效，为0时表示无效，例如控制信号MDRinE 为1表示允许数据从DB 打入MDR ，MDRin 为1表示允许数据从内总线打入MDR 。假设MAR 的输出一直处于使能状态。加法指令“ADD （Rl ）, R0”的功能为（R0）+（（R1））－（R1）, 即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。
图
下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
表
【答案】执行阶段每个节拍（时钟周期）的功能和有效控制信号见下表。
表
2． 设
中。
（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；
（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。
【答案】（1）构造的哈希函数为：哈希函数（2）关键字在表中的位置如表所示：
表 关键字在表中的位置
3． 假设Internet 的两个自治系统构成网络如题图所示，自治系统ASI 由路由器R1连接两个子网构成；自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口 IP 地址如题图所示。请回答下列问题。
（关键字各字符编码之和） 五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现
：要求用哈希（Hash ）方法将它们存入具有10个位置的表
题图网络拓扑结构
（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年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此基础综合真题及详解
4． 已知有5个顶点的图G 如下图所示
和子网可以聚合为子网在AS2
请回答下列问题
（1）写出图G 的邻接矩阵A （行、列下标从0开始）。
（2）求什么？
【答案】（1）邻接矩阵为
矩阵中位于0行3列元素值的含义是什么？ 非零元素的含义是（3）若已知具有n （n>=2）个顶点的邻接矩阵为B ，则
（2）
为：