2020年數(shù)據(jù)結(jié)構(gòu)考研真題答案及解析

本文提供2020年數(shù)據(jù)結(jié)構(gòu)考研真題答案及解析，以下為具體內(nèi)容

1、設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)。下面的算法1是將一維數(shù)組a中的n個數(shù)逆序存放到原數(shù)組中，該算法的空間復(fù)雜度是（ ）（要求用大O符號表示）。

A、O(1)

B、O(n)

C、O(2n)

D、O(n²)

2、在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是（ ）。

A、訪問第i個結(jié)點（1<=i<=n）和求第i個結(jié)點的直接前驅(qū)

B、在第i個結(jié)點后插入一個新結(jié)點（1<=i<=n）

C、刪除第i個結(jié)點（1<=i<=n）

D、將n個結(jié)點從小到大排序

3、在雙向鏈表中，刪除結(jié)點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的循環(huá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依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（ ）種情況。

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、二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以（ ）。

A、它不能用順序存儲結(jié)構(gòu)存儲

B、它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲

C、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲

D、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用

8、圖1是一個有向無環(huán)圖，其拓?fù)渑判蚪Y(jié)果為（ ）。

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網(wǎng)中，其關(guān)鍵路徑長度為（ ）。

A、16

B、17

C、18

D、19

10、對一組數(shù)據(jù)(2，12，16，88，5，10)進(jìn)行排序，若前三趟排序結(jié)果如下： 第一趟排序結(jié)果：2，12，16，88，5，10 第二趟排序結(jié)果：2，5，16，88，12，10第三趟排序結(jié)果：2，5，10，88，12，16 則采用的排序方法可能（ ）。

A、希爾排序

B、 快速排序

C、 簡單選擇排序

D、 直接插入排序