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

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

1、算法的时间复杂度取决于（ ）。

A、问题的规模

B、待处理数据的初态

C、计算机的配置

D、A和B

2、线性表的顺序存储结构中，数据元素的逻辑位置和物理位置的关系是（ ）。

A、不一致的

B、一致的

C、大致相同

D、个别元素相同

3、在一个有n个元素的顺序表中，插入一个元素平均要移动的元素个数为（ ）。

A、(n-1)/2

B、n/2

C、(n+1)/2

D、n

4、若顺序栈S存储在数组stack[MAXSIZE]中，栈顶位置top初值为-1，则元素e进栈的操作是（ ）。

A、S.stack[S.top++]=e;

B、S.stack[++S.top]=e;

C、S.stack[S.top--]=e;

D、S.stack[--S.top]=e;

5、链队列Q的结点结构为：(data,link)，指针front指向队首元素，rear指向队尾元素，则出队元素到变量x中的操作（ ）。

A、x=Q.front->data; Q.front=Q.front->link;

B、Q.front=Q.front->link; x=Q.front->link;

C、x=Q.rear->data; Q.rear=Q.rear->link;

D、x=Q.rear->data; Q.rear=Q.front;

6、一个递归算法必须包括（ ）。

A、递归部分

B、终止条件和递归部分

C、迭代部分

D、终止条件和迭代部分

7、一棵非空二叉树的先序遍历序列和中序遍历序列相同，则该二叉树一定满足（ ）。

A、所有的结点均无左孩子

B、所有的结点均无右孩子

C、只有一个叶子结点

D、不存在这样的二叉树

8、按照满二叉树的编号顺序对深度为k的完全二叉树编号，则编号最小的叶结点的编号是（ ）。

A、2^k-1-1

B、2^k-1

C、2^k-2+1

D、2k-1

9、一棵完全二叉树的第7层有24个叶子结点，则整个二叉树的结点数至多为（ ）个。

A、87

B、206

C、207

D、231

10、G是一个非连通无向图，共有36条边，则该图至少有（ ）个顶点。

A、7

B、8

C、9

D、10

1、试题答案：D

试题解析：

【考点】本题考查算法时间复杂度的概念。 

【解析】算法的时间复杂度取决于问题的规模和待处理数据的初态。算法的执行时间随问题规模的增长而增长。故本题选D。

2、试题答案：B

试题解析：

【考点】本题考查顺序存储结构的概念。 

【解析】在顺序存储结构中，数据元素的逻辑位置和物理位置一致，逻辑上相邻的数，在物理存储结构中也相邻。链式存储结构用一组任意的存储单元存储线性表的数据元素，这个存储单元可以是连续的也可以是不连续的。故本题选B。

3、试题答案：B

试题解析：

【考点】本题考查顺序表的插入操作。 

【解析】顺序表插入时，若在第1个位置插入，需要移动n个元素，若在第2个位置插入，需要移动n-1个元素，……，在第n个位置插入，需要移动1个元素，在尾端插入，需要移动0个元素。因此，所有元素总的移动个数=n+(n-1)+……+1+0=n*(n+1)/2，需要n+1次插入操作，因此平均移动元素的个数为n/2。故本题选B。

4、试题答案：B

试题解析：

【考点】本题考查顺序栈的入栈操作。 

【解析】由于栈顶位置top初值为-1，在顺序栈中，元素入栈时top指针上移一位，之后指针指向的位置插入元素，其插入操作为S.stack[++S.top]=e;。若S的栈顶元素，用e为返回值，则删除操作为e=S.stack[S.top--];。删除故本题选B。

5、试题答案：B

试题解析：

【考点】本题考查链队列的出队操作。 

【解析】链队列出队时从队头出队，仅需要修改头指针，无需修改尾指针。因此，排除C和D选项。为了操作方便，链队列添加头结点。因此x=Q.front->link->link。故本题选B。

6、试题答案：B

试题解析：

【考点】本题考查递归算法的概念。 

【解析】一个递归算法包括终止条件和递归部分，结束条件不再进行递归调用，可以结束。递归部分将问题划分为子问题，多次递归从而解决问题。故本题选B。

7、试题答案：A

试题解析：

【考点】本题考查二叉树的遍历。 

【解析】先序遍历的顺序为根结点、左孩子、右孩子，中序遍历的顺序为左孩子、根结点、右孩子，因此，当没有左孩子时，二者的遍历顺序均为根结点、右孩子。故本题选A。

8、试题答案：B

试题解析：

9、试题答案：A

试题解析：

10、试题答案：D

试题解析：

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

【解析】在一个连通无向图中，最少的结点连接最多边时，边和结点的关系为e=n*(n-1)/2。带入e=36，求出n=9。由于本题是非连通图，因此至少有10个结点。故本题选D。