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

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

1、串是一种特殊的线性表，其特殊性体现在（ ）。

A、可以顺序存储

B、数据元素是一个字符

C、可以链式存储

D、数据元素可以是多个字符

2、不带头结点的单链表head为空的判定条件是（ ）。

A、

B、

C、

D、

3、二叉树在线索化后，仍不能有效求解的问题是（ ）。

A、先序线索化二叉树中求先序后继

B、中序线索化二叉树中求中序后继

C、后序线索化二叉树中求后序后继

D、中序线索化二叉树中求中序前驱

4、任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置（ ）。

A、肯定发生变化

B、肯定不发生变化

C、有时发生变化

D、无法确定

5、在数据结构中，与所使用的计算机无关的是数据的（ ）结构。

A、逻辑

B、存储

C、逻辑和存储

D、物理

6、对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度为（ ）。

A、O(1)，O(1)

B、O(1)，O(N)

C、O(N)，O(1)

D、O(N)，O(N)

7、和顺序栈相比，链栈有一个比较明显的优势是（ ）。

A、通常不会出现栈满的情况

B、通常不会出现栈空的情况

C、入栈操作更容易实现

D、出栈操作更容易实现

8、将5个字母ooops按此顺序入栈，则有（ ）种不同的出栈顺序可以仍然得到ooops。

A、1

B、3

C、5

D、6

9、将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。

A、100

B、40

C、55

D、80

10、若某表长最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（ ）存储方式最节省运算时间。

A、单链表

B、给出表头指针的单循环链表

C、顺序表

D、带头结点的双向循环链表

1、试题答案：D

试题解析：

串是由多个字符组成的有限序列。它也被称为字符串，通常用于表示文本或二进制数据。串可以是任何长度，从空串（不含字符）到非常长的文本或数据。串的存储方式可以采用顺序存储方式或者链式存储方式，其中顺序存储方式是将串中的字符按照一定的次序依次存储在一个一维数组中，而链式存储方式是通过一个链表来存储串中的每一个字符。故本题选D。

2、试题答案：A

试题解析：

不带头结点的单链表head为空，表示该链表中没有任何节点，即链表为空。因此，判定该链表是否为空需要判断链表的头指针head是否为NULL。故本题选A。

3、试题答案：C

试题解析：

在二叉树的后序线索化过程中，如果要求某个结点的后继，则需要遍历整棵树，因为后序遍历的顺序是左子树、右子树、根节点，所以在后序线索化后的二叉树中，一个结点的后继可能在其右子树中，也可能在其祖先结点的右子树中，因此需要遍历整棵树才能找到后继。而对于其他线索化方式，都可以通过对结点的左、右指针进行判断来快速找到后继或前驱。对于先序线索化二叉树，可以通过判断结点的左指针是否为线索指针来找到先序后继；对于中序线索化二叉树，可以通过判断结点的右指针是否为线索指针来找到中序后继或前驱。故本题选C。

4、试题答案：B

试题解析：

由于二叉树中叶子节点没有子节点，所以它们在先序、中序、后序遍历中的位置是不会发生变化的。在先序遍历中，叶子节点会被最先遍历到，因此它们在先序序列中的相对位置是不变的；在中序遍历中，叶子节点位于左子树和右子树之间，因此它们在中序序列中的相对位置也是不变的；在后序遍历中，叶子节点会被最后遍历到，因此它们在后序序列中的相对位置同样是不变的。故本题选B。

5、试题答案：A

试题解析：

逻辑结构是指数据对象中数据元素之间的逻辑关系，与具体的计算机和存储器无关。常见的逻辑结构有线性结构、树形结构、图形结构等。而存储结构和物理结构则是与具体的计算机和存储器相关的。存储结构是指数据在计算机内部存储的方式，包括顺序存储结构和链式存储结构等。物理结构是指数据在计算机内部存储时所占用的实际存储空间，包括数据元素的存储方式、存储单元的长度等。故本题选A。

6、试题答案：B

试题解析：

对于顺序存储的长度为N的线性表，访问结点的时间复杂度为 O(1)，因为在顺序存储结构中，每个元素在内存中都是连续存放的，通过下标可以直接访问到对应的元素，不需要遍历。而增加结点的时间复杂度为 O(N)，因为需要在表的中间或者开头插入一个元素时，需要将插入位置之后的元素依次向后移动一个位置，所以平均需要移动 N/2 个元素，因此时间复杂度为 O(N)。故本题选B。

7、试题答案：A

试题解析：

链栈的存储空间不是预先分配的，可以根据需要动态申请内存，因此不会像顺序栈一样出现固定空间不足的情况。而栈空的情况在顺序栈和链栈中都可能出现，取决于栈中是否有元素。入栈和出栈操作在两种实现中都很容易实现。故本题选A。

8、试题答案：C

试题解析：

由于前面三个元素一致，因此导致了不同的出栈顺序均可以得到ooops。可能性如下表所示。

故本题选C。

9、试题答案：C

试题解析：

对于一个10阶对称矩阵，它的总元素数为10*10=100个，但是由于是对称矩阵，所以矩阵中对角线两侧的元素是相同的，总共有10+9+8+...+2+1=55个不同的元素。因此，可以将这55个不同的元素存储在一维数组A中。由于每个元素需要占用一个存储单元，因此数组A的长度最少为55。故本题选C。

10、试题答案：C

试题解析：

如果表长最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，那么采用顺序表存储方式最节省运算时间。在顺序表中，插入和删除最后一个结点的操作只需要在表尾进行一次插入或删除即可，时间复杂度为O(1)。故本题选C。