2016年浙江理工大学机械与自动控制学院计算机专业基础之数据结构考研复试题库
● 摘要
目录
2016年浙江理工大学机械与自动控制学院计算机专业基础之数据结构考研复试题库（一） . .... 2
2016年浙江理工大学机械与自动控制学院计算机专业基础之数据结构考研复试题库（二） . .. 10
2016年浙江理工大学机械与自动控制学院计算机专业基础之数据结构考研复试题库（三） . .. 19
2016年浙江理工大学机械与自动控制学院计算机专业基础之数据结构考研复试题库（四） . .. 28
2016年浙江理工大学机械与自动控制学院计算机专业基础之数据结构考研复试题库（五） . .. 37
一、选择题
1． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0（n ） B.0（n+e） C.0（n*n） D.0（n*n*n）
答:B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0（n+e）
2． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法。
A. 分块
B. 顺序
C. 折半
D. 哈希
答:A
【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。
3． 下列关于UDP 协议的叙述中，正确的是（ ）
I 提供无连接服务
II 提供复用/分用服务
III 通过差错校验，保障可靠数据传输
A. 仅I
B. 仅 I 、II
C. 仅 II 、III
D.I 、II 、III
答:B
【解析】UDP 无连接创建，提供多路复用服务。虽然有差错检验，但是不能保证可靠数据传输，所以III 错误。
4． 某基于动态分区存储管理的计算机，，其主存容量为55MB （初始为空闲）采用最佳适配（Bestfit ）算法，分配和释放的顺序为：分配15MB 、分配30MB 、释放15MB 、分配8MB 、分配6MB , 此时主存中最大空闲分，区的大小是（ ）。
A.7MB
B.9MB
C.10MB
D.15MB
答:B
【解析】对于简单分区内存分配，需要将进程的所有代码和数据装入内存。故55MB 先分配15MB 余40MB , 再分配30MB 后余10MB , 释放15MB 后出现一个15MB 和一个10MB 的空闲空间，分配8MB 时按最佳适配（BestFit ）算法应该使用10MB 的空闲块，余2MB 的碎片，分配6MB
，因此最大空闲区为9MB 。 时占用15MB 的空间余9MB 的碎片（空闲空间）
5． 有向带权图如题图所示，若采用迪杰斯特拉（Dijkstra ）算法求从源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b ，第二条最短路径的目标顶点是c ，后续得到的其余各最短路径的目标顶点依次是（ ）。
题图有向带权图
A.d , e , f
B.e , d , f
C.f , d , e
D.f , e , d
答:C 。
【解析】本题主要考查Dijkstra 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。
执行Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为f ，d , e 。