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

1、設某數據結構的二元組形式表示為A=（D，R）， D={01，02， 03，04， 05， 06，07，08，09}， R={（01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數據結構A是（ ）。

A、線性結構

B、樹型結構

C、物理結構

D、圖型結構

2、下面程序的時間復雜度為（ ）。for (i=1，s=0; i<=n; i++) {t=1; for(j=1; j<=i; j++)t=t*j; s=s+t; }

A、O（n）

B、O（n²）

C、O（n³）

D、O（n⁴）

3、設指針變量P指向單鏈表中結點A，若刪除單鏈表中結點A，則需要修改指針的操作序列為（ ）。

A、q=p->next;p->data=q->data; p->next=q->next; free(q);

B、q=p->next;q->data=p->data;p->next=q->next;free(q);

C、q=p->next;p->next=q->next;free(q);

D、q=p->next; p->data=q->data; fee(q);

4、設有n個待排序的記錄關鍵字，則在堆排序中需要（ ）個輔助記錄單元。

A、1

B、n

C、nlog₂n

D、n²

5、設一組初始關鍵字記錄關鍵字為（20，15，14，18，21，36，40，10）， 則以20為基準記錄的一趟快速排序結束后的結果為（ ）。

A、10，15，14，18，20，36，40，21

B、10，15，14，18，20，40，36，21

C、10，15，14，20，18，40，36，21

D、15，10，14，18，20，36，40，21

6、設二叉排序樹中有n個結點，則在二叉排序樹的平均查找長度為（ ）。

A、O（1）

B、O（log₂n）

C、無正確答案

D、O（n²）

7、設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為（ ）。

A、n，e

B、e，n

C、2n，e

D、n，2e

8、設某強連通圖中有n個頂點。則該強連通圖中至少有（ ）條邊。

A、n（n-1）

B、n+1

C、n

D、n（n+1）

9、設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（ ）方法可以達到此目的。

A、快速排序

B、堆排序

C、歸并排序

D、插入排序

10、下列四種排序中（ ）的空間復雜度最大。

A、插入排序

B、冒泡排序

C、堆排序

D、歸并排序