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

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

1、設(shè)N是描述問題規(guī)模的非負整數(shù)，下列程序段的時間復(fù)雜度是（ ）。static int fun(int N){ if(N==1) return 0; return 1 + fun(N/2);}

A、O(logN)

B、O(N)

C、(NlogN)

D、O(N)

2、一些隨機產(chǎn)生的數(shù)采用線性鏈表存儲，在下面這些排序方法中，（ ）的時間復(fù)雜度是最小的。

A、插入排序

B、快速排序

C、堆排序

D、歸并排序

3、一個棧的輸入序列為a，b，c，d，e，則下列序列中不可能是棧的輸出序列的是（ ）。

A、b c d a e

B、e d a c b

C、b c a d e

D、a e d c b

4、實現(xiàn)一個隊列需要（ ）個棧。

A、1

B、2

C、3

D、4

5、下面（ ）是一棵滿二叉樹的結(jié)點個數(shù)。

A、8

B、13

C、14

D、15

6、下列序列中，哪一個是堆（ ）？

A、75，65，30，15，25，45，20，10

B、75，65，45，10，30，25，20，15

C、75，45，65，30，15，25，20，15

D、75，45，65，10，25，30，20，15

7、一棵Huffman樹共有203個結(jié)點，對其Huffman編碼，共能得到（ ）個不同的碼字。

A、100

B、102

C、200

D、203

8、下面說法錯誤的是（ ）。

A、一個有n個頂點和n條邊的無向圖一定是有環(huán)的。

B、建立十字鏈表的時間復(fù)雜度和建立鄰接表是相同的。

C、鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。

D、在某些圖的應(yīng)用問題中，如果需要找到表示同一條邊的兩個結(jié)點，那么采用鄰接多重表比鄰接表作為儲存結(jié)構(gòu)更為適宜。

9、圖的廣度優(yōu)先遍歷算法中使用列作為其輔助數(shù)據(jù)結(jié)構(gòu)，那么在算法執(zhí)行過程中每個頂點進隊次數(shù)最多為（ ）。

A、1

B、2

C、3

D、4

10、設(shè)一個有向圖G=（V，E），其中V={v1，v2，v3，v4，v5，v6}E={<v1，v2>，<v2，v3>，<v3，v6>，<v4，v2>，<v4，v5>，<v5，v6>}不屬于該圖的拓撲排序有序序列是（ ）。

A、v1 v2 v3 v4 v5 v6

B、v1 v4 v2 v3 v5 v6

C、v4 v5 v1 v2 v3 v6

D、v4 v1 v2 v3 v5 v6