考研专业课资料、辅导、答疑一站式服务平台
第 1 页，共 70 页
目录
2019年上海海事大学信息工程学院821数据结构考研冲刺五套模拟题（一） (2)
2019年上海海事大学信息工程学院821数据结构考研冲刺五套模拟题（二） (15)
2019年上海海事大学信息工程学院821数据结构考研冲刺五套模拟题（三） (30)
2019年上海海事大学信息工程学院821数据结构考研冲刺五套模拟题（四） (41)
2019年上海海事大学信息工程学院821数据结构考研冲刺五套模拟题（五） (54)
考研专业课资料、辅导、答疑一站式服务平台
第 2 页，共 70 页 2019年上海海事大学信息工程学院821数据结构考研冲刺五套模拟题（一） 特别说明：
1-本资料为2019考研冲刺点题班学员考研冲刺模拟题，查漏补缺，实战检测考研复习效果。
2-仅供2019考研复习参考，与目标学校及研究生院官方无关，如有侵权、请联系我们立即处理。 ————————————————————————————————————————
一、填空题
1． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有
检索和_____检索。 【答案】关键字；记录号；记录号；顺序；直接
2． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
要加“虚结点”。 设编号为i 和j 的结点在顺序存储中的下标为s 和t ,则结点i 和j 在同一层上的条件是
。
3． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
4． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。
【答案】2(n －1)
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。
5． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
6． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
考研专业课资料、辅导、答疑一站式服务平台
第 3 页，共 70 页 7． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0,则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。
8． 设广义表L ＝(（ ），（ ）)，则head(L)是_____tail(L)是_____L 的长度是_____；深度是_____。
【答案】（ ）；(（ ）)；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
9． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
10．组成串的数据元素只能是_____。
【答案】字符
11．如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。
12．高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】
【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为。当最后一层只有
一个元素时，此时堆的元素个数最少，元素个数为
。
二、单项选择题
13．若X 是后序线索二叉树中的叶结点,且X 存在左兄弟结点Y,则X 的右线索指向的是（ ） A.X 的父结点
B.以Y 为根的子树的最左下结点
C.X 的左兄弟结点Y
D.以Y 为根的子树的最右下结点
【答案】A
【解析】根据后续线索二叉树的定义,X 结点为叶子结点且有左兄弟,那么这个结点为右孩子结点,利用后续遍历的方式可知X 结点的后继是其父结点,即其右线索指向的是父结点。
考研专业课资料、辅导、答疑一站式服务平台
第 4 页，共 70 页
14．用户在删除某文件的过程中,操作系统不可能执行是（ ）
A.删除此文件所在的目录
B.删除与此文件关联的目录项
C.删除与此文件对应的控制块
D.释放与此文件关联的内存级冲区
【答案】A
【解析】删除文件不需要删除文件所在的目录,而文件的关联目录项和文件控制块需要随着文件一同删除,同时释放文件的关联缓冲区。
15．主机甲和乙已建立了TCP 连接,甲始终以MSS=1KB 大小的段发送数据,并一直有数据发送;乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗口为8KB,则从t 时刻起,不再发生超时的情况下,经过10个RTT 后,甲的发送窗口是（ ）
A.10KB
B.12KB
C.14KB
D.15KB
【答案】A
【解析】发送窗口是接受窗口和拥塞窗口的最小值,这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的,取最小值。
16．已知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。
A.CBEFDA
B.FEDCBA
C.CBEDFA
D.不定
【答案】A
【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。
17．n 个顶点的无向图的邻接表最多有（ ）个表结点。
A.n 2
B.n(n －1)
C.n(n+1)
D.
【答案】B
【解析】当n 个顶点构成的无向图是无向完全图时，则每一个结点都会和其余的n －1个结点连接，从而会产生n(n －1)个表结点。
考研专业课资料、辅导、答疑一站式服务平台
第 5 页，共 70 页
18．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A.选择排序法
B.插入排序法
C.快速排序法
D.堆排序法
【答案】A
【解析】选择排序的基本思想是:
第i 趟排序开始时，当前有序区和无序区分别为和，该趟排序则是从当前无序区中选出关键字最小的记录
，将它与无序区的第1个记录R[i]交换，使和分别变为新的有序区和新的无序区。
19．下列选项中,能缩短程序执行时间的措施是（ ）。
Ⅰ.提高CPU 时钟频率
Ⅱ.优化数据通路结构
Ⅲ.对程序进行编译优化
A.仅Ⅰ和Ⅱ
b.仅Ⅰ和Ⅲ
c.仅Ⅱ和Ⅲ
d.Ⅰ、Ⅱ和Ⅲ
【答案】D
【解析】一般说来,CPU 时钟频率(主频)越高,CPU 的速度就越快;优化数据通路结构,可以有效提高计算机系统的吞吐量;编译优化可得到更优的指令序列。所以Ⅰ、Ⅱ、Ⅲ都是有效措施。
20．有向带权图如下图图所示,若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径,则得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其佘各最短路径的目标顶点依次是（ ）。
图 有向带权图
A.d,e,f
B.e,d,f
C.f,d,e
D.f,e,d
【答案】C 。
考研专业课资料、辅导、答疑一站式服务平台
第 6 页，共 70 页 【解析】本题主要考查Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表,故后续目标顶点依次为f ,d ,e 。
21．下列选项中的英文缩写均为总线标准的是（ ）。
A.PCI 、CRT 、USB 、EISA
B.ISA 、CPI 、VESA 、EISA
C.ISA 、SCSI 、RAM 、MIPS
D.ISA 、EISA 、PCI 、PCI-Express
【答案】D
【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线标准的英文缩写,只有选项D 中的英文缩写均为总线标准。
22．基于比较方法的n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（ ）。
A. B.
C. O (n)
D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为
。
三、判断题
23．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ） 【答案】×
【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序存储的表。
24．倒排文件是对次关键字建立索引。（ ）
【答案】√
【解析】倒排文件是对每一个次关键字项建立次关键字索引(称为倒排表)，将所有具有相同
