2022年数据结构考研真题答案及解析

本文提供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、归并排序

1、试题答案：D

试题解析：

【考点】本题考查数据结构的形式。 

【解析】对于A，线性结构指数据元素之间存在“一对一”的线性关系的数据结构。对于B，树形结构指数据元素之间存在“一对多”的树形关系的数据结构。对于C，物理结构是数据结构在计算机中的表示。对于D，图型结构指数据元素之间存在“多对多”的网络关系的数据结构。图中D存放的图的顶点，R存放的是图的关系。从题干中可以看出D、R是多对多的关系，因此题干所示的数据结构是图结构。故本题选D。

2、试题答案：B

试题解析：

【考点】本题考查程序时间复杂度的计算。 

【解析】程序中的代码是一个双层for循环，第一层循环i从1递增到n，因此第一层for循环的时间复杂度为O（n），第二层for循环j从1递增到i，因此第二层for循环的时间复杂度为O（n），双层嵌套for循环的时间复杂度即为O（n²）。故本题选B。

3、试题答案：C

试题解析：

【考点】本题考查单链表的删除操作。 

【解析】单链表的删除操作通常将p的next指向p的next的next结点即可，其操作如下图所示：

故本题选C。

4、试题答案：A

试题解析：

【考点】本题考查堆排序的辅助空间。 

【解析】堆排序算法只需要一个记录大小的辅助空间，每个待排记录仅占有一个存储空间。故本题选A。

5、试题答案：A

试题解析：

【考点】本题考查快速排序的应用。

【解析】快速排序的基本思想是以基准元素为中心，将待排序表分成两个子表，然后继续对子表进行划分，直到所有子表的长度为1。第一趟排序后的结果应当是比20小的在20的左边，比20大的在20的右边。因此，首先排除C选项。接下来对关键字进行排序，左指针指向首元素，右指针指向尾元素。10比20小，交换。第一个元素为10，排除D选项。左指针右移，15比20小，不交换，14比20小，不交换，18比20小，不交换，21比20大，交换。21放在最后一位，右指针左移，40比20大，不交换，36比20大，不交换。36和40位置不变，排除B选项。左右指针相遇，第一趟排序结束。故本题选A。

6、试题答案：C

试题解析：

【考点】本题考查二叉排序树的平均查找长度的计算。 

【解析】含n个结点的二叉排序树的平均查找长度和树的形态有关。最坏情况下，树为单支树，此时平均查找长度为（n+1）/2。最好情况下，二叉树的形态和折半查找的判定树形态一致，其平均查找长度和log₂n成正比。因此，其平均性能在树随机的情况下，二叉排序树的平均查找长度和logn是等数量级的。故本题无正确答案。

7、试题答案：D

试题解析：

【考点】本题考查无向图的邻接表存储。

 【解析】无向图的邻接表中，表头结点的个数即为图中的顶点数，因此大小为n。边表结点个数为每个顶点连接的顶点，即该顶点连接的边数，无向图中每条边在顶点中出现两次，因此边表结点的个数是2*e。故本题选D。

8、试题答案：C

试题解析：

【考点】本题考查图的连通性。 

【解析】连通图指从图中的任一结点出发能够访问图的所有顶点。因此，当n个顶点连接成一个环时，能够满足连通性，此时需要的边数最少，n个顶点需要n条边。故本题选C。

9、试题答案：B

试题解析：

【考点】本题考查排序算法的对比。 

【解析】对于A，快速排序的每一趟排序结果是将数据分在基准值的两边，每一趟的排序结果并不能得出最小值，因此要想从5000个数据中选出最小的10个关键字，只能对整个数据进行完整的快速排序，此时平均时间复杂度为O（nlogn）。对于B，堆排序可以通过创建10次小根堆，每次建堆后的堆顶元素即为最小关键字，因此其时间复杂度为10*logn。对于C，归并排序每一趟的排序结果并不能得出最小值，因此要想从5000个数据中选出最小的10个关键字，只能对整个数据进行完整的归并排序，此时时间复杂度为O（nlogn）。对于D，插入排序的每一趟排序结果并不能得出最小值，因此其平均时间复杂度为O（n²）。故本题选B。

10、试题答案：D

试题解析：

【考点】本题考查排序算法的空间复杂度。 

【解析】算法的空间复杂度是指算法所需存储空间的量度。插入排序、冒泡排序、堆排序所需的空间复杂度均为O（1），而归并排序的空间复杂度为O（n）。故本题选D。