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

考研希赛网 2023-07-07 浏览 508 来源：希赛网

考研真题，是用来研究考试规律的。考生可通过真题，来确定自己的复习范围，来研究考试的重点、难点是哪些内容。希赛网为大家整理2021年数据结构考研真题答案及解析，供大家参考!

本文提供2021年数据结构考研真题答案及解析，以下为具体内容

1、关于线性表的说法正确的是（）。

A、线性表的特点是每个元素都有一个前驱和一个后继元素

B、线性表是特征相同的n（n≥0）个元素构成的有限序列

C、线性表采用顺序存储便于进行插入和删除操作

D、线性表采用链式存储便于进行随机查找操作

2、表长为n的顺序存储的线性表，当在任何位置删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为（）。

A、(n-1)/2

B、n/2

C、(n+1)/2

D、n

3、假设单链表结点结构为（data,next），删除指针p所指结点的后继结点q的语句序列是（）。

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

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

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

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

5、若循环队列Q存储在数组queue[0..n]中，front是队首位置，rear是队尾位置（初始rear=front=0），则元素e入队的操作是（）。

A、Q.queue[Q.rear]=e; Q.rear=(Q.rear+1)%n;

B、Q.queue[Q.rear]=e; Q.rear=(Q.rear+1)%(n+1);

C、Q.rear=(Q.rear+1)%n; Q.queue[Q.rear]=e;

D、Q.rear=(Q.rear+1)%(n+1); Q.queue[Q.rear]=e;

6、关于串的叙述中不正确的是（）。

A、串是字符的有限序列

B、空串是由空格构成的串

C、串既可以采用顺序存储，也可以采用链式存储

D、模式匹配是串的一种重要运算

7、按照从上至下、由左至右的顺序依次编号，深度为7的完全二叉树编号最大的叶结点编号是（）。

A、63

B、64

C、126

D、127

8、已知完全二叉树的第7层有20个叶结点，则该二叉树最多有（）个结点。

A、83

B、147

C、214

D、215

9、设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端，则B中右指针域为空的结点有（）个。

A、n-1

B、n

C、n+1

D、n+2

10、由权值为15,3,5,10的四个叶结点构成的哈夫曼树的带权路径长度为（）。

A、46

B、59

C、66

D、88

1、试题答案：B

试题解析：

【考点】本题考查线性表的基本特性。

【解析】单向线性表中头元素无前驱结点，尾元素无后继结点，因此A选项错误。线性表的顺序存储结构的插入和删除的时间复杂度均为O(n)，因此C选项错误。线性表的链式存储结构不支持随机存取，因此D选项错误。线性表是特征相同元素的有限序列，B选项描述正确。故本题选B。

2、试题答案：A

试题解析：

【考点】本题考查顺序表的删除操作。

【解析】顺序表的删除操作是指在删除第i个元素，需要将第i+1至第n个元素依次向前移动一位。由于在任何位置删除一个元素的概率相等，平均移动个数=[(n-1)+(n-2)+…+0]/n=(n-1)/2，故本题选A。

3、试题答案：A

试题解析：

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

【解析】单链表的基本操作总结如下：
指针p所指结点后插入指针s所指结点：
s->next=p->next; p->next=s；
删除p指针之后的结点：
p->next=p->next->next；或：q=p->next; p->next=q->next; free(q)。
单链表删除操作首先将p指针指向其后继的后继结点，之后释放删除结点。故本题选A。

5、试题答案：C

试题解析：

【考点】本题考查循环队列的基本操作。【解析】将顺序队列首尾相接成环状空间即为循环队列。由题干可知rear是队尾位置，因此入队操作首先移动尾指针，再在尾指针指向的位置插入元素。入队操作队尾指针应该更新为： rear=(rear+1)%maxsize; rear=e; 根据题干maxsize=n+1，故本题选C。

6、试题答案：B

试题解析：

【考点】本题考查串的相关概念。【解析】空串值不含任何字符的串，空格属于字符，因此含空格的串不是空串，其余A、C、D的表述均符合串的相关概念，故本题选B。

7、试题答案：D

试题解析：