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

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

1、在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是（ ）。

A、O(1)

B、O(n)

C、O(n²)

D、O(nlogn)

2、下列排序算法中，（ ）是穩(wěn)定的。

A、插入、希爾

B、冒泡、快速

C、選擇、堆排序

D、基數(shù)、歸并

3、循環(huán)隊(duì)列是空隊(duì)列的條件是（ ）。

A、(Q->rear+1)%maxsize==Q->front

B、Q->rear==Q->front

C、Q->rear==0

D、Q->front==0

4、有一個(gè)有序表{1，3，9，32，41，45，62，75，77，82，95，100}， 當(dāng)折半查找值為82的元素時(shí)，（ ）次比較后查找成功。

A、1

B、2

C、4

D、8

5、表達(dá)式aX(b+c)-d的前綴表達(dá)式是（ ）。

A、abcdX+-

B、abc+X d-

C、abcX +d-

D、-X a+bcd

6、深度為5的二叉樹(shù)至多有（ ）個(gè)結(jié)點(diǎn)。

A、16

B、32

C、31

D、10

7、設(shè)森林F中有三棵樹(shù)，第一、第二和第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3。 與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（ ）。

A、M1

B、M1+M2

C、M3

D、M2+M3

8、具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的深度為（ ）。

A、?log₂(n+1)?-1

B、log₂n+1

C、log₂n

D、?log₂n?