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

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

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

A、O(1)

B、O(n)

C、O(2n)

D、O(n²)

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

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

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

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

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

3、在雙向鏈表中，刪除結(jié)點(diǎn)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)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（ ）。

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

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

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

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

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

8、圖1是一個(gè)有向無(wú)環(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)鍵路徑長(zhǎng)度為（ ）。

A、16

B、17

C、18

D、19

10、對(duì)一組數(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、 簡(jiǎn)單選擇排序

D、 直接插入排序