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

1、設(shè)N是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下列程序段的時(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、一些隨機(jī)產(chǎn)生的數(shù)采用線性鏈表存儲(chǔ)，在下面這些排序方法中，（ ）的時(shí)間復(fù)雜度是最小的。

A、插入排序

B、快速排序

C、堆排序

D、歸并排序

3、一個(gè)棧的輸入序列為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、實(shí)現(xiàn)一個(gè)隊(duì)列需要（ ）個(gè)棧。

A、1

B、2

C、3

D、4

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

A、8

B、13

C、14

D、15

6、下列序列中，哪一個(gè)是堆（ ）？

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樹(shù)共有203個(gè)結(jié)點(diǎn)，對(duì)其Huffman編碼，共能得到（ ）個(gè)不同的碼字。

A、100

B、102

C、200

D、203

8、下面說(shuō)法錯(cuò)誤的是（ ）。

A、一個(gè)有n個(gè)頂點(diǎn)和n條邊的無(wú)向圖一定是有環(huán)的。

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

C、鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用。

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

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

A、1

B、2

C、3

D、4

10、設(shè)一個(gè)有向圖G=（V，E），其中V={v1，v2，v3，v4，v5，v6}E={<v1，v2>，<v2，v3>，<v3，v6>，<v4，v2>，<v4，v5>，<v5，v6>}不屬于該圖的拓?fù)渑判蛴行蛐蛄惺牵?）。

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