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

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

1、設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為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>}，則數(shù)據(jù)結(jié)構(gòu)A是（ ）。

A、線性結(jié)構(gòu)

B、樹型結(jié)構(gòu)

C、物理結(jié)構(gòu)

D、圖型結(jié)構(gòu)

2、下面程序的時間復(fù)雜度為（ ）。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、設(shè)指針變量P指向單鏈表中結(jié)點A，若刪除單鏈表中結(jié)點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、設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要（ ）個輔助記錄單元。

A、1

B、n

C、nlog₂n

D、n²

5、設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為（20，15，14，18，21，36，40，10）， 則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為（ ）。

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、設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均查找長度為（ ）。

A、O（1）

B、O（log₂n）

C、無正確答案

D、O（n²）

7、設(shè)無向圖G中有n個頂點e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為（ ）。

A、n，e

B、e，n

C、2n，e

D、n，2e

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

A、n（n-1）

B、n+1

C、n

D、n（n+1）

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

A、快速排序

B、堆排序

C、歸并排序

D、插入排序

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

A、插入排序

B、冒泡排序

C、堆排序

D、歸并排序