2018年北京师范大学政府管理学院986软件基础数据结构考研强化五套模拟题
● 摘要
一、应用题
1． 假定有下列，nxn 矩阵(n为奇数
)
如果用一维数组B 按行主次序存储A 的非零元素，问: (1)A中非零元素的行下标与列下标的关系； (2)给出A 中非零元素在B 中的位置公式。
(1)主对角线上元素的坐标是i ＝j ，【答案】副对角线上元素的坐标i 和j 有i ＋j ＝n ＋l 的关系，所以A 中非零元素的行下标和列下标的关系是i ＝j
或
余每行都有两个元素。主对角线上的元素，在向量B 中存储的下标是
副对角线上的元素，在中心元素前，在向量B 中存储的下标
是
(3)
在中心元素后，其下标如下:
在B 中的位置如下:
(2)非零元素分布在两条主、副对角线上，除对角线相交处一个元素(下称“中心元素”)外，其
的下标(i，j) 与B 中的下标R 的关系；
，给出利用
的下标(i，j) 定位
(3)假定矩阵中每个元素占一个存储单元且B 的起始地址为
2． 假设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 地址与路由表中和两个路由
表项均匹配, 根据最长匹配原则, R2将通过E0接口转发该1P 分组。
(3)R1与R2之间利用BGP4(或BGP) 交换路由信息; BGP4的报文被封装到TCP 协议段中进行传输。
3． 给出模式串
在KMP 算法中的next 和nextval 数组。
【答案】模式串的next 函数定义如下:
根据此定义，
可求解模式串
的next 和nextval 值如下:
4． 系统中有多个生产者进程和消费者进程, 共享用一个可以存1000个产品的缓冲区(初始为空) , 当缓冲区为未满时, 生产者进程可以放入一件其生产的产品, 否则等待; 当缓冲区为未空时, 消费者进程可以取走一件产品, 否则等待。要求一个消费者进程从缓冲区连续取出10件产品后, 其他消费者进程才可以取产品, 请用信号量P , V(wait, signed) 操作实现进程间的互斥和同步, 要求写出完整的过程; 并指出所用信号量的含义和初值
【答案】设置5个信号量
empty :表示缓冲区是否为空, 初值为1000 full :表示缓冲区是否为满, 初值为0 mutex1:生产者之间的互斥信号, 初值为1 mutex2:消费者之间的互斥信号, 初值为1 available :当前消费者能否访问缓冲区, 初值为1
定义变量in , out 分别为生产者和消费者进程所要使用的指针, 指向下一个可用的缓冲区单元, MaxNum=1000为缓冲区的大小, count 标志当前消费者已经取的产品的数量, 初值为0
生产者进程:
生产一个产品;
产品送入buffer(in);
消费者进程