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

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

1、m阶B-树是一棵（ ）。

A、m叉排序树

B、m叉平衡排序树

C、m-1叉平衡排序树

D、m+1叉平衡排序树

2、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（   ）。

A、求子串

B、联接

C、匹配

D、求串长

3、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）。

A、按层遍历

B、后序遍历

C、中序遍历

D、先序遍历

4、双向链表中，在结点p之前插入一个结点q的操作是（ ）。

A、

B、

C、

D、

5、下列程序的时间复杂度为（ ）。i=0;s=0;while(s<n){ i++; s=s+i;}

A、

B、

C、

D、

6、元素1，2，3，4依次入栈，出栈无限制，则以下（ ）是可能的出栈序列。

A、3，1，2，4

B、2，1，4，3

C、2，4，1，3

D、1，4，2，3

7、一个空间大小为N的顺序栈，top作为栈顶指针，假定以地址低端作为栈底（即初始化top=-1）。则当做进栈处理时，top的变化是（ ）。

A、top不变

B、top=0

C、top=top-1

D、top=top+1

8、设有一个二维数组A[m][n]，假设A[1][1]存放位置在644，A[3][3]存放位置在676，每个元素占一个字节，问A[4][4]的存放位置是（ ）。

A、688

B、678

C、692

D、696

9、对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是（ ）。

A、((e,f))

B、(e,f)

C、(f)

D、()

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

A、肯定发生变化

B、有时发生变化

C、肯定不发生变化

D、无法确定

1、试题答案：B

试题解析：

由B-树的性质可知，m阶B-树是一棵m叉平衡排序树。故本题选B。

2、试题答案：C

试题解析：

现在要求q在p中首次出现的位置，即在p中找到一个起始位置，使得从该位置开始的连续一段字符正好是q。这个过程称为字符串匹配。字符串匹配可以使用不同的算法来实现，其中比较常见的有暴力匹配算法、KMP算法、Boyer-Moore算法等。故本题选C。

3、试题答案：D

试题解析：

深度优先遍历算法是图的遍历方式之一，其遍历过程类似于二叉树的先序遍历。在深度优先遍历中，我们从某个顶点开始遍历，依次访问该顶点的所有邻接顶点，然后依次对每个邻接顶点进行递归遍历，直到所有能到达的顶点都被访问到。这个过程就类似于二叉树的先序遍历，先访问根节点，再递归遍历左子树和右子树。故本题选D。

4、试题答案：C

试题解析：

选项A中，插入操作的顺序是先将p的前驱结点指向q，再将q的后继结点指向p，接着将p的前驱结点的后继结点指向q，最后将q的前驱结点指向p。但是这个顺序是错误的，因为在将p的前驱结点的后继结点指向q之前，p的前驱结点就已经被修改为q了，导致指针的丢失。选项B和选项A的错误一致。选项D中，插入操作的顺序是先将q的前驱结点指向p的前驱结点，再将q的后继结点指向q，因此错误。故本题选C。

5、试题答案：A

试题解析：

6、试题答案：B

试题解析：

选项B中栈的执行过程是：1入栈、2入栈、2出栈、1出栈、3入栈、4入栈、4出栈、3出栈。故本题选B。

7、试题答案：D

试题解析：

在顺序栈中，元素是从数组的低端开始进栈的，也就是top指针始终指向栈顶元素在数组中的下标。因此，当有元素进栈时，需要将top指针加1，指向新的栈顶元素的位置。故本题选D。

8、试题答案：C

试题解析：

根据题目可知，无论是按行存储还是按列存储，A[4][4]的存放位置不会发生变化。不妨设按行存储时，A[i][j]的存放位置为：A[i][j] = A[1][1] + (i-1) * n + (j-1)。代入A[3][3]存放位置在676，可得n=15。将n代入A[4][4]的存放位置公式中，可得：A[4][4] = 644 + (4-1) * 15 + (4-1) = 692。故本题选C。

9、试题答案：A

试题解析：

执行操作tail(L)将得到广义表((c,d),(e,f))，再对其执行tail()操作将得到广义表((e,f))，因此执行tail(tail(L))操作将得到((e,f))。故本题选A。

10、试题答案：C

试题解析：

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