2018年东北大学信息科学与工程学院842计算机专业基础之数据结构考研核心题库
● 摘要
目录
2018年东北大学信息科学与工程学院842计算机专业基础之数据结构考研核心题库（一） ... 2
2018年东北大学信息科学与工程学院842计算机专业基础之数据结构考研核心题库（二） ... 9 2018年东北大学信息科学与工程学院842计算机专业基础之数据结构考研核心题库（三） . 14 2018年东北大学信息科学与工程学院842计算机专业基础之数据结构考研核心题库（四） . 23 2018年东北大学信息科学与工程学院842计算机专业基础之数据结构考研核心题库（五） . 31
一、综合题
1． 对一个有t 个非零元素的矩阵，用的数组来表示，其中第0行的三个元素分别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素A[i][j]在B 中的位置并修改其值，应如何设计算法可以使时间得到改善？
【答案】题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，时间复杂度为0(n)。若使查找时间得到改善，可以建立索引，将各行行号及各行第一个非零元素在数组B 中的位置(下标) 放入一向量C 中。若查找非零元素，可先在数组C 中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B 中的位置，再到B 中顺序(或折半) 查找该元素，这时时间复杂度为0(logn)。
2． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？
【答案】(1)首次适配法
从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。
(2)最佳适配法
链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。
(3)最差适配法
链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。
3． 某网络中的路由器运行OSPF 路由协议, 下表是路由器R1维护的主要链路状态信息(LSI), 下图是根据下表及R1的接口名构造出来的网络拓扑。
表 R1所维护的
LSI
图 R1构造的网络拓扑
请回答下列问题。
本题中的网络可抽象为数据结构中的哪种逻辑结构？
针对上表中的内容, 设计合理的链式存储结构, 以保存上表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义, 并画出对应上表的链式存储结构示意图(示意图中可仅以ID 标识节点) 。
按照迪杰斯特拉(Dijiksta)算法的策略, 依次给出R1到达上图中子网
用。
的最短路径及费
【答案】(1)图
(2)使用图的邻接表存储结构进行存储, 数据类型定义如下:
该弧指向路由器的位置, 0为没有
该弧指向的网络的网络前缀, 空为没有
路由的基础IP , 当adjvex 不为0才有效
指向下一条弧的指针
连接的权值
表结点
第一个结点地址
头节点
链式存储结构示意图如下图所示:
(3)目标网络记为N1, 记为N2, 记为N3, 记为N4, 使用dijkstra 算法找最短路径步骤如下表所示:
相关内容
相关标签