2017年空军工程大学566计算机专业基础综合之数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 已知n 阶下三角矩阵A （即当
时，有
，按照压缩存储的思想，可以将其主对角线以）
下所有元素（包括主对角线上元素）依次存放于一维数组B 中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素的存放位置的公式。
【答案】2
阶下三角矩阵元素第1列到第
列是梯形，元素数为
第1列有n 个元素，第j 列有而在第j 列上的位置是为
2． 某网络中的路由器运行0SPF 路由协议，如表是路由器R1维护的主要链路状态信息（LSI ），如图是根据表及R1的接口名构造出来的网络拓扑。
表R1所维护的
LSI
个元素，所以n
阶下三角矩阵A 按列存储，其元素在一维数组B 中的存储位置k 与i 和j 的关系为：
图R1构造的网络拓扑
请回答下列问题。
（1）本题中的网络可抽象为数据结构中的哪种逻辑结构？
（2）针对表中的内容，设计合理的链式存储结构，以保存表中的链路状态信息（LSI ）。要求给出链式存储结构的数据类型定义，并画出对应表的链式存储结构示意图（示意图中可仅以ID 标识节点）。
（3）按照迪杰斯特拉（Dijikstra ）算法的策略，依次给出R1到达图中子网192.1.x.x 的最短路径及费用。
【答案】（1）图
（2）使用图的邻接表存储结构进行存储，数据类型定义如下：
该弧指向路由器的位置，0为没有
该弧指向的网络的网络前缀，空为没有
路由的基础IP ，当adjvex 不为0才有效
指向下一条弧的指针
连接的权值
表结点
第一个结点地址
头节点
链式存储结构示意图如下图所示：
（3
）目标网络
记为
记为
记为
使用dijkstra 算法找最短路径步骤如下表所示：
所以R1到达子网192.1.1.0/24最短路径为：R1到达子网R1到达子网R1到达子网
的最短路径为
：的最短路径为
：的最短路径为
子网，费用为1 子网，费用为3 子网，费用为4 子网，费用为8
3． 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树； （2）若查找元素54，需依次与哪些元素比较？ （3）若查找元素90，需依次与哪些元素比较？
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。 【答案】（1）判定树如图所示：
相关内容
相关标签