2021年数据结构考研真题答案及解析（一）

本文提供2021年数据结构考研真题答案及解析，以下为具体内容

1、以下数据结构中哪一个是非线性结构？（ ）

A、二叉树　　

B、栈

C、线性表 　　

D、队列

2、当要对线性表进行折半查找时，线性表必须满足以下条件（ ）。

A、以顺序方式存储

B、以链表方式存储

C、以顺序方式存储且按关键字有序排列

D、以链表方式存储且按关键字有序排列

3、为了提高哈希表的查找效率，以下方法说法不正确的是（ ）。

A、设计好的哈希函数

B、增加哈希函数的个数

C、增大存储空间

D、采用更好的地址冲突解决方法

4、用单向链表来实现容量为n的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是（ ）。

A、入栈操作的复杂度为O（1）

B、出栈操作的复杂度为O（1）

C、插入一个新的堆栈底部元素复杂度为O（1）

D、删除底部元素的复杂度为O（1）

5、设一个顺序有序的一维数组A[1：14]中有14个元素，采用二分查找算法查找到A[4]中的元素过程中需要比较的元素的顺序是（ ）。

A、A[1]，A[2]，A[3]，A[4]

B、A[7]，A[3]，A[5]，A[4]

C、A[1]，A[14]，A[7]，A[4]

D、A[7]，A[5]，A[3]，A[4]

6、稀疏矩阵一般采用的压缩存储方法有两种，即（ ）。

A、二维数组和三维数组

B、三元组和散列

C、三元组和十字链表

D、十字链表和散列

7、设a，b为一棵二叉树上的两个结点，在中序遍历时先访问a后访问b的条件是（ ）。

A、a在B的左边 　

B、a在b的右边

C、a是b的祖先

D、a是b的子孙

8、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树结点数为（ ）。

A、5　

B、4

C、3 　

D、2

9、判断一个有向图中是否存在环（回路），可采用以下方法（ ）。

A、广度优先遍历 　

B、求关键路径

C、求最短路径　

D、拓扑排序

10、用哈希表存储7个整数18，25，63，50，42，32，9，如果哈希函数为H（x）=x mod 9，则与18发生地址冲突的整数有（ ）个。

A、1 　

B、2

C、3 　　

D、4

1、试题答案：A

试题解析：

本题考查逻辑结构的分类。
逻辑结构通常有四种类型，分别为线性结构：数据元素之间存在“一对一”的线性关系的数据结构；树形结构：数据元素之间存在“一对多”的树形关系的数据结构；图状或网状结构：数据元素之间存在“多对多”的网络关系的数据结构。纯集合结构：指数据元素之间除了“同属一个集合”之外，别无其他关系。后三种结构统称为非线性结构。二叉树属于树形结构，因此是非线性结构，而栈、线性表、队列的数据元素均为“一对一”的线性关系，故本题选A。

2、试题答案：C

试题解析：

本题考查折半查找的适用性。
折半查找法是针对顺序有序表设计的查找方法，其查找过程为：先确定待查记录所在的范围（区间），后逐步缩小范围直到找到或找不到该记录为止。故本题选C。

3、试题答案：B

试题解析：

本题考查哈希表的性质。
A选项设定一个好的哈希函数可以减少冲突的个数，即减少计算的次数，可以提高效率；C选项增大存储空间，记录的集合增大，减少冲突，提高效率；D选项减少冲突次数，减少计算时间，提高查找效率。而B选项哈希函数增加，会相应增加哈希计算的时间，降低哈希表的查找效率。故本题选B。

4、试题答案：D

试题解析：

本题考查栈的基本操作的时间复杂度。
栈具有后进先出的特性，只允许在表的一端进行插入和删除。在栈头部插入和删除的时间复杂度均为O（1），存在尾部指针时，在栈底插入的时间复杂度为O（1），删除O（n）。若不存在尾指针，在栈底插入和删除的时间复杂度均为O（n）。故本题选D。

5、试题答案：B

试题解析：

本题考查二分查找的应用。
第一次：（1+14）/2=7； A[4]<A[7]； 查找空间缩小为[1：6]；第二次：（1+6）/2=3；A[4]>A[3]；查找空间缩小到[4，6]；第三次：（4+6）/2=5；A[4]>A[5]；查找空间缩小到[4]第四次：A[4]=A[4]。 故本题选B。

6、试题答案：C

试题解析：

本题考查稀疏矩阵的存储方法。
稀疏矩阵是指矩阵中非零元素<=50%，且分布无规律。在存储稀疏矩阵时，仅存储非零元素即可。存储非零元素的行坐标、列坐标、元素值。三元组存储方法的每个元素有三个域，分别为i，j，k，代表非零元素的行号、列号、值。十字链表的每一行是一个链表，代表行坐标，每一个列是一个链表代表列坐标。故本题选C。

7、试题答案：A

试题解析：

本题考查二叉树的遍历。
中序遍历先访问左子结点，再访问根结点，最后访问右子结点。A选项若a，b同为子结点，且a在b的左边，则a必然比b先访问，因此A选项正确，B选项错误。C选项中若b是左子结点，则先访问b，后访问a，因此C选项错误。D选项若a为b的右子结点，则b比a先访问，因此D选项错误。故本题选A。

8、试题答案：B

试题解析：

本题考查二叉树的遍历。
后序遍历先访问左子结点，再访问右子结点，最后访问根结点。因此E为树的根结点。而中序遍历先访问左子结点，再访问根结点，最后访问右子结点。因此在E左边的序列即为左子树，分别为ABCD。故本题选B。

9、试题答案：D

试题解析：

本题考查图的基本应用。
判断有向图是否存在环有两种方法，分别为深度遍历和拓扑排序。若深度遍历中有结点被第二次访问到则证明有环。拓扑排序的思想为每次找入度为0的点，添加到输出队列，然后将与此点相连的结点入度减1，重复上述过程直至删除所有结点。若存在结点无法删除，则证明有环。故本题选D。

10、试题答案：B

试题解析：

本题考查哈希表的查找。
构建哈希表的基本思想为记录的关键字和其存储的位置之间存在一个确定的函数关系f，即将关键字的记录存储在f（key）的位置上。根据该思想构建哈希表如下：

故本题选B。