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、归并排序