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、 直接插入排序