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

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

1、逻辑结构可以分为（ ）。

A、有序和无序

B、顺序和链式

C、线性和非线性

D、动态和静态

2、影响时间复杂度O(n)的因素有（ ）。

A、问题规模

B、计算机软硬件

C、A、B都有

D、都没有

3、链式存储的内存地址（ ）。

A、必须连续

B、都连续

C、一定不连续

D、不一定连续

4、下列稀疏矩阵错误的是（ ）。

A、非零元素个数相对于矩阵元素个数非常少

B、采用常规的方法存储会浪费存储空间

C、只需要存储零元素，不需要存储行和列

D、压缩存储后会失去随机存取特性

5、由完全二叉树推广的完全三叉树，244个结点的树高为（ ）。

A、4

B、5

C、6

D、7

6、二叉树先序、中序、后序遍历序列中叶子节点的比较顺序（ ）。

A、部分相同

B、完全不相同

C、完全相同

D、无法判断

7、中序遍历后，元素按非递减顺序排列的是（ ）。

A、完全二叉树

B、满二叉树

C、AVL树

D、哈夫曼树

8、下列选项中邻接矩阵对称的是（ ）。

A、无向图

B、有向图

C、AOV

D、AOE

9、引入线索二叉树的目的是（ ）。

A、加快查找前驱和后继速度

B、在二叉树中方便插入和删除

C、方便找到双亲

D、使二叉树遍历结果唯一

1、试题答案：C

试题解析：

数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的具体存储形式无关，是独立于计算机的。数据逻辑结构通常分为线性结构和非线性结构。故本题选C。

2、试题答案：C

试题解析：

算法时间复杂度用来度量算法执行时间，而影响算法执行时间的因素有：算法选用的策略、问题的规模、程序设计语言、编译程序所产生的机器码的质量、计算机执行指令的速度。因此，问题规模、计算机软硬件都能够影响算法的时间复杂度。故本题选C。

3、试题答案：C

试题解析：

链式存储中，每次为结点随机开辟一块小空间，各个结点是通过指针连接的，其地址可以连续也可以不连续。故本题选C。

4、试题答案：C

试题解析：

在对稀疏矩阵进行压缩存储时，需要将非零元素以及它所在的行号、列号作为一个结点存放在一起，这样的结点组成的线性表叫做三元组。因此，选项C中说法错误。故本题选C。

5、试题答案：C

试题解析：

完全三叉树中，最多只有最下面两层的结点的度数可以小于3。满三叉树中，第一层有1个结点，第二层有3个结点，第三层有9个结点，…，第h层有3^h-1，由此得到高度为h的满三叉树有1+3+9+…+3^h-1= (3^h-1)/2。当h=5时，(3^h-1)/2=121；h=6时，(3^h-1)/2=364。而121＜244＜364，所以具有244个结点的完全三叉树的高度为6。故本题选C。

6、试题答案：C

试题解析：

前序遍历的次序是根左右，中序遍历的次序是左根右，后序遍历的次序是左右根，因此，遍历序列中相对次序发生变化的都是子树的根，也就是分支结点。而叶子结点在任一遍历序列中的相对次序是不发生改变的，其比较顺序完全相同。故本题选C。

7、试题答案：C

试题解析：

完全二叉树和满二叉树中序遍历后得到的序列不一定有序 ，而哈夫曼树中只有叶子结点具有关键字。AVL树也叫平衡二叉查找树，它一般是基于二叉排序树的，而二叉树排序树满足特点“左孩子＜根结点＜右节点”，所以对其进行中序遍历可以得到一个元素按非递减顺序排列的序列。故本题选C。

8、试题答案：A

试题解析：

在任一无向图中，若顶点a到顶点b之间有边，则顶点b到顶点a之间一定有边。因此，存储无向图的邻接矩阵一定是对称矩阵。故本题选A。

9、试题答案：A

试题解析：

用二叉链表存储时，只能得到结点的左右孩子信息，结点任一序列中的前驱和后继结点只能在遍历过程中获取，而引入线索二叉树可以快速查找结点的前驱和后继。故本题选A。