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

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

1、在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点，则执行（ ）。

A、s→next=p; p→next=s;

B、p→next=s; s→next=p;

C、p=s; s→next=p→next;

D、s→next=p→next; p→next=s;

2、下面关于线性表的叙述中，错误的是哪一个（ ）。

A、线性表采用顺序存储，必须占用一片连续的存储单元

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

C、线性表采用链式存储，不必占用一片连续的存储单元

D、线性表采用链式存储，便于插入和删除操作

3、执行（ ）操作时，需要使用队列作辅助存储空间。

A、查找哈希（Hash）

B、广度优先搜索图

C、先序（根）遍历二叉树

D、深度优先搜索图

4、在定义ATD时，除数据对象和数据关系外，还需说明（ ）。

A、数据元素

B、算法

C、基本操作

D、数据项

5、程序段：for (i = n-1; i < 1; i--) for (j = 1; j < i; j++) if (A[j] > A[j + 1]) swap(A[j], A[j + 1]);其中n为正整数，则最后一行语句执行，在最坏情况下是（ ）。

A、

B、

C、

D、

6、若已知一个栈的入栈序列是1，2，3，4，其出栈序列为P1，P2，P3，P4，则P2，P4不可能为：（ ）。

A、2，4

B、2，1

C、4，3

D、3，4

7、要连通具有n个顶点的有向图，至少需要边（ ）。

A、n-1

B、n

C、n+1

D、2n

8、已知有向图G=（V，E），其中V={ V1，V2，V3，V4，V5，V6，V7}，E={<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>}，G的拓扑序列是（ ）。

A、V1，V3，V4，V6，V2，V5，V7

B、V1，V3，V2，V6，V4，V5，V7

C、V1，V3，V4，V5，V2，V6，V7

D、V1，V2，V5，V3，V4，V6，V7

9、循环队列A[0…m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中元素数是（ ）。

A、(rear-front+m)%m

B、rear-front-1

C、rear-front+1

D、rear-front

10、已知一颗完全二叉树的第5层（设根为第一层）有4个叶结点，则完全二叉树的结点个数最多是（ ）。

A、39

B、55

C、59

D、19

1、试题答案：D

试题解析：

【考点】本题考查单链表的删除操作。
【解析】在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点的示意图如下所示。故本题选D。

2、试题答案：B

试题解析：

【考点】本题考查顺序表和链表的特点。
【解析】线性表采用顺序存储，即顺序表，系统必须为其分配一片连续的空间，可以随机查找，但是不便于进行插入和删除操作。因为，在顺序表中进行插入和删除操作时，可能需要移动大量元素。线性表采用链式存储，即链表，其中各个结点通过指针两两连接，不需要占用一片连续的存储单元。在链表中进行插入和删除操作时，只需要修改指针指向即可，非常方便。故本题选B。

3、试题答案：B

试题解析：

【考点】本题考查广度优先搜索图的特点。
【解析】
A.哈希查找不需要辅助队列，直接查找哈希表即可。
B.广度优先搜索图从某一顶点出发，依次访问已被访问顶点的未被访问过的邻接点，为保证“先被访问的邻接点”先于“后被访问的邻接点”被访问，所以需要在访问结点时将其邻接点依次入队列，需要队列作为辅助空间。
C.D. 先序（根）遍历二叉树和深度优先搜索图都需要栈作为辅助空间。
综上所述，本题选B。

4、试题答案：C

试题解析：

【考点】本题考查ATD。
【解析】ATD即抽象数据类型，ATD可以看作一些数据对象以及附加在这些数据对象上的操作的集合。因此，在定义ATD时，除数据对象和数据关系外，还需说明基本操作。故本题选C。

5、试题答案：C

试题解析：

【考点】本题考查时间复杂度。
【解析】本程序段的本质是冒泡排序的核心代码，而冒泡排序在全部逆序的情况下，即最坏的情况的时间复杂度为O(n2)。故本题选C。

6、试题答案：C

试题解析：

【考点】本题考查正确的出栈序列。
【解析】第一个出栈元素是4的话，说明在此之前所有元素均已全部入栈。出栈4后，此时栈中剩余元素依次是1、2、3，那么出栈顺序只可能是4、3、2、1，P2，P4不可能为4，3。故本题选C。
（注：根据卡特兰数公式可知，n个元素入栈，则有C(2n,n)/(n+1)种合法的出栈顺序。）

7、试题答案：B

试题解析：

【考点】本题考查有向图的连通。
【解析】在有向图中，连通是指存在顶点i到顶点j的路径，也存在顶点j到顶点i的路径。因此，有向图构成一个环时能保证是连通的，且此时边最少。故本题选B。

8、试题答案：B

试题解析：

【考点】本题考查拓扑排序。
【解析】拓扑序列构建过程如下所示，G的拓扑序列是V1，V3，V4，V6，V2，V5，V7。故本题选A。

9、试题答案：A

试题解析：

【考点】本题考查循环队列中元素个数。
【解析】循环队列中，可能出现rear小于front的情况，所以需要加m再对m取余。因此，当前队列中元素数是（rear-front+m）%m。故本题选A。

10、试题答案：B

试题解析：