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

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

1、下列程序段的時間復(fù)雜度是（ ）。

A、O（n）

B、O（logn）

C、O（nlogn）

D、O（n2）

2、設(shè)p指向一個非空雙向鏈表中的某個結(jié)點(diǎn)，將一個q所指新結(jié)點(diǎn)插入到該雙向鏈表中， 使其成為p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，能正確完成此要求的語句段是（ ）。

A、q->next=p; q->prior=p->prior; p->prior=q; p->prior->next=q;

B、p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;

C、q->prior=p->prior; q->next=p; p->prior->next=q; p->prior=q;

D、q->prior=p->next; q->next=p; p->prior->next=q;p->prior=q;

3、一個棧的入棧序列為1，2，3，… ， n，其出棧序列是P1，P2， P3， … ，Pn 。若P1=4，則P3可能取值的個數(shù)是多少？（ ）。

A、n-3

B、n-2

C、n-1

D、無法確定

4、二維數(shù)組SA中，每個元素的長度為3個字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲器內(nèi)，且采用行優(yōu)先順序存儲，元素A [4][5]的起始地址為（ ）。

A、SA+141

B、SA+ 111

C、SA+135

D、SA+ 165

5、一棵度為4的樹T中，若有10個度為4的結(jié)點(diǎn)，20個度為3的結(jié)點(diǎn)，1個度為2的結(jié)點(diǎn)， 12個度為1的結(jié)點(diǎn)，則樹T的葉子結(jié)點(diǎn)個數(shù)是（ ）。

A、63

B、81

C、105

D、72

6、設(shè)森林F中有4棵樹T1，T2，T3，T4，其結(jié)點(diǎn)個數(shù)分別為10、15、12、19，將森林F轉(zhuǎn)換成一棵二叉樹BT，BT的根結(jié)點(diǎn)R為T1上的結(jié)點(diǎn)，則R的左子樹上的結(jié)點(diǎn)個數(shù)是（ ）。

A、9

B、10

C、19

D、27

7、設(shè)哈夫曼編碼的長度不超過4，若己對兩個字符編碼為1和01，則最多還可對（ ）個字符編碼。

A、2

B、3

C、4

D、7

8、下列四個序列中，哪一個是堆（ ）。

A、65，55，40，10，30，25，20，15

B、65，55，30，15，25，40，20，10

C、65，40，55，10，25，30，20，15

D、65，55，40，30，15，25，20，10

9、在含有33個結(jié)點(diǎn)的二叉排序樹上，查找關(guān)鍵字為34的結(jié)點(diǎn)，以下（ ）是可能的關(guān)鍵字比較序列？

A、25，37，16，45，34

B、45，37，16，25，34

C、45，25，16，37，34

D、16，37，25，45，34

10、序列（5，3，12，9，4，2，6，8）是某排序方法第一趟后的結(jié)果，該排序算法可能是（ ）。

A、冒泡排序

B、堆排序

C、歸并排序

D、簡單選擇排序