2020年数据结构考研真题答案及解析

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

1、设n是描述问题规模的非负整数。下面的算法1是将一维数组a中的n个数逆序存放到原数组中，该算法的空间复杂度是（ ）（要求用大O符号表示）。

A、O(1)

B、O(n)

C、O(2n)

D、O(n²)

2、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。

A、访问第i个结点（1<=i<=n）和求第i个结点的直接前驱

B、在第i个结点后插入一个新结点（1<=i<=n）

C、删除第i个结点（1<=i<=n）

D、将n个结点从小到大排序

3、在双向链表中，删除结点p的操作是（ ）。

A、p->prior->next=p->next; p->next->prior=p->prior;

B、p->next=p->next->next; p->next->prior=p;

C、p->priort=p->next->next; p->next=p->prior->prior;

D、p->prior-next=p; p->prior=p->prior->prior;

4、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。

A、 (rear+1)%n==front

B、 rear==front

C、rear+1==front

D、 (rear-1)%n==front

5、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。

A、5，4，3，2，1

B、4，3，1，2，5

C、2，1，5，4，3

D、2，3，5，4，1

6、串“ababaabab”的nextval为（ ）。

A、010104101

B、010102101

C、010100011

D、010101011

7、二叉树是非线性数据结构，所以（ ）。

A、它不能用顺序存储结构存储

B、它不能用链式存储结构存储

C、顺序存储结构和链式存储结构都能存储

D、顺序存储结构和链式存储结构都不能使用

8、图1是一个有向无环图，其拓扑排序结果为（ ）。

A、v0、v1、v2、v4、v5、v3、v6

B、v1、v0、v3、v4、v5、v2、v6

C、v1、v0、v3、v4、v5、v6、v2

D、v1、v0、v3、v4、v6、v2、v5

9、在图2所示AOE网中，其关键路径长度为（ ）。

A、16

B、17

C、18

D、19

10、对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，88，5，10 第二趟排序结果：2，5，16，88，12，10第三趟排序结果：2，5，10，88，12，16 则采用的排序方法可能（ ）。

A、希尔排序

B、 快速排序

C、 简单选择排序

D、 直接插入排序

1、试题答案：B

试题解析：

【考点】本题考查空间复杂度的思想。 

【解析】注意题干问的是空间复杂度而非时间复杂度，上述算法实现的功能是逆序，在该过程中需要额外开辟n的空间，因此算法的空间复杂度为0(n)，故本题选B。

2、试题答案：A

试题解析：

【考点】本题考查顺序表操作的时间复杂度。 

【解析】对于A，顺序表支持随机访问，因此访问第i个结点及前驱的时间复杂度为O(1)。对于B和C，插入和删除操作平均时间复杂度为0(n)。对于D，排序的时间复杂度取决于所选择的排序算法。故本题选A。

3、试题答案：B

试题解析：

【考点】本题考查双向链表的删除。 

【解析】双向链表的删除操作涉及两个方向的指针，第一步是p的next指针指向其后继的后继。此时，原本的p->next->next更新为p->next。第二步p->next的前驱指针指向p，由此就删除了原本的p->next结点。故本题选B。

4、试题答案：B

试题解析：

【考点】本题考查循环队列的判空操作。 

【解析】在循环队列中，队头指针指向头元素，队尾指针指向尾元素的下一个位置。若循环队列中存放n个元素，则rear==front，此时无法判断是队空的条件还是队满的条件。为了区分这两者，规定循环队列中当元素个数为n-1个时，判定队列已满的条件为队头指针front在队尾指针rear的下一个位置上，因此最大容量为s的循环队列，队满条件为（rear+1）%s==front；队空条件为rear==front。故本题选B。

5、试题答案：B

试题解析：

【考点】本题考查出栈和入栈。 

【解析】栈具有后进先出的特性。根据该特性，B选项中的2一定在1的前面出栈。其余选项均符合栈的特性，故本题选B。

6、试题答案：A

试题解析：

【考点】本题考查串和数组的应用。 

【解析】第一位的next的值是0，第二位的next的值为1，后面求解每一位的next的值时，首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容与前一位进行比较，直到找到某个位上的内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。所以中心思想则是递进查看前一位的next对应的是否和前一位相同。找到相同的则在找到的基础上加1。根据上述思想求出该字符串所对应的next值。故本题选A。

7、试题答案：C

试题解析：

【考点】本题考查二叉树的存储。 

【解析】二叉树既能够使用顺序存储结构，也能够使用链式存储结构。线性结构和非线性结构是一种逻辑结构，而顺序存储和链式存储是基于物理结构，二者之间并无之间关系，因此A、B、D错误。故本题选C。

8、试题答案：D

试题解析：

【考点】本题考查拓扑排序的思想。 

【解析】拓扑排序中，只有入度为0的点才可以添加到拓扑序列中。A选项中，V5的入度来自结点V2 V3 V4，而V3不在V5之前的拓扑序列中，因此A选项错误。同理，B选项中V5之前的拓扑序列中应该有V2。C选项与B选项问题一致。故本题选D。

9、试题答案：C

试题解析：

【考点】本题考查关键路径的求解。 【解析】 AOE网指在一个带权有向图中，用顶点代表事件，用有向边表示活动，边上的权值表示活动的持续时间。事件的最早时间：从前往后，前驱节点到当前结点所需时间，取最大值。事件的最晚时间：从后往前，后继结点的最迟发生时间-边权值，取最小值。结束结点的最早发生时间和最晚发生时间相同。最早发生时间和最晚发生时间相同的点即为关键路径的点。
根据上述AOE图给出图中事件的最早发生时间和最晚发生时间如下图所示：

由此得出其关键路径为V0->V1->V4->V6->V8或V0->V1->V4->V7->V8，将路径上的权值相加，求出其路径长度为18。故本题选C。

10、试题答案：C

试题解析：

【考点】本题考查排序算法的基本思想。 

【解析】一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换。因此其第一趟、第二趟、第三趟应当分别选出序列中的最小值，题干中的排序符合该特点。故本题选C。