本文提供2022年數據結構考研真題答案及解析，以下為具體內容

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

A、O（n）

B、O（logn）

C、O（nlogn）

D、O（n2）

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

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可能取值的個數是多少？（ ）。

A、n-3

B、n-2

C、n-1

D、無法確定

4、二維數組SA中，每個元素的長度為3個字節，行下標i從0到7，列下標j從0到9，從首地址SA開始連續存放在存儲器內，且采用行優先順序存儲，元素A [4][5]的起始地址為（ ）。

A、SA+141

B、SA+ 111

C、SA+135

D、SA+ 165

5、一棵度為4的樹T中，若有10個度為4的結點，20個度為3的結點，1個度為2的結點， 12個度為1的結點，則樹T的葉子結點個數是（ ）。

A、63

B、81

C、105

D、72

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

A、9

B、10

C、19

D、27

7、設哈夫曼編碼的長度不超過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個結點的二叉排序樹上，查找關鍵字為34的結點，以下（ ）是可能的關鍵字比較序列？

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）是某排序方法第一趟后的結果，該排序算法可能是（ ）。

A、冒泡排序

B、堆排序

C、歸并排序

D、簡單選擇排序