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

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

1、关键路径是事件结点网络中（ ）。

A、最短的回路

B、从源点到汇点的最短路径

C、最长的回路

D、从源点到汇点的最长路径

2、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）。

A、按层遍历

B、后序遍历

C、中序遍历

D、先序遍历

3、有一棵二叉树如图1所示，该二叉树是（ ）。

A、堆的形状

B、平衡二叉树

C、二叉判定树

D、二叉排序树

4、快速排序在（ ）情况下最不利于发挥其特长。

A、被排序的数据量太大

B、被排序中含有多个相同的关键字

C、被排序的数据已基本有序

D、被排序的数据中有实数

5、对线性表进行折半查找时，要求线性表必须（ ）。

A、以顺序方式存储

B、以顺序方式存储，且数据元素有序

C、以链式方式存储

D、以链式方式存储，且数据元素有序

6、在数据结构中，从存储结构上可以将之分为（ ）。

A、动态结构和静态结构

B、紧凑结构和非紧凑结构

C、顺序存储和链式存储

D、线性结构和非线性结构

7、设栈S和队列Q的初始状态皆为空，元素b1，b2，b3，b4，b5，b6和b7依次通过一个元素出栈后即进入队列Q。若6个元素出队列的顺序是b3，b5，b4，b6，b7，b2，b1，则栈S最多同时容纳了（ ）个元素。

A、3

B、4

C、5

D、6

8、双向链表中，在指针p所指结点前插入一个指针q所指的结点，操作是（ ）。注：双向链表的结点结构为(prior,data,next)。

A、

B、

C、

D、

9、串是一种特殊的线性表，其特殊性体现在（ ）。

A、数据元素是字符

B、顺序存储

C、链式存储

D、逻辑结构是线性结构

10、已知广义表A=((a,b,c),(d,e,f))，从A中取出原子e的运算是（ ）。

A、tail(head(A))

B、head(tail(tail(head(A))))

C、head(tail(A))

D、head(tail(head(tail(A))))

1、试题答案：D

试题解析：

本题考查关键路径的定义。
关键路径是指从开始点到完成点的最长路径，该路径不能是回路。故本题选D。

2、试题答案：D

试题解析：

深度优先遍历算法是图的遍历方式之一，其遍历过程类似于二叉树的先序遍历。在深度优先遍历中，我们从某个顶点开始遍历，依次访问该顶点的所有邻接顶点，然后依次对每个邻接顶点进行递归遍历，直到所有能到达的顶点都被访问到。这个过程就类似于二叉树的先序遍历，先访问根节点，再递归遍历左子树和右子树。故本题选D。

3、试题答案：D

试题解析：

二叉排序树（Binary Search Tree，简称BST）是一种特殊的二叉树，它的每个节点都包含一个关键字（key），并满足以下性质：
（1）左子树上的所有节点的关键字都小于该节点的关键字；
（2）右子树上的所有节点的关键字都大于该节点的关键字；
（3）左子树和右子树都是二叉排序树。
故本题选D。

4、试题答案：C

试题解析：

在被排序的数据已基本有序的情况下，快速排序可能会出现极端的不平衡分割，使得排序时间复杂度变为O(n2)，而快速排序的优势正是在平均情况下的排序效率最高。故本题选C。

5、试题答案：B

试题解析：

折半查找需要在有序表中进行，而链式存储的元素在物理空间上是不连续的，所以不适合直接进行折半查找，需要将链式存储的有序表转换为顺序存储的有序表再进行折半查找。故本题选B。

6、试题答案：C

试题解析：

从存储结构上，数据结构可以分为顺序存储和链式存储。顺序存储指的是把数据元素存放在一块连续的存储空间中，通常使用数组实现；链式存储指的是把数据元素存放在任意的存储空间中，通过指针相连形成链表，通常使用指针实现。其他选项并不准确，动态结构和静态结构、紧凑结构和非紧凑结构、线性结构和非线性结构都是从不同的角度对数据结构进行分类的。故本题选C。

7、试题答案：B

试题解析：

栈的执行过程为b1入栈、b2入栈、b3入栈、b3出栈、b4入栈、b5入栈、b5出栈、b4出栈、b6入栈、b6出栈、b7入栈、b7出栈、b2出栈、b1出栈。当栈顶元素为b5，栈S最多同时容纳了4个元素。故本题选B。

8、试题答案：B

试题解析：

选项A中，插入操作的顺序是先将p的前驱结点指向q，再将q的后继结点指向p，接着将p的前驱结点的后继结点指向q，最后将q的前驱结点指向p。但是这个顺序是错误的，因为在将p的前驱结点的后继结点指向q之前，p的前驱结点就已经被修改为q了，导致指针的丢失。选项C和选项A的错误一致。选项D中，插入操作的顺序是先将q的前驱结点指向p的前驱结点，再将q的后继结点指向q，因此错误。故本题选B。

9、试题答案：A

试题解析：

串是由零个或多个字符组成的有限序列，其中字符可以是字母、数字、标点符号等。与线性表不同的是，串中的元素是字符，而不是普通的数据元素，因此串是一种特殊的线性表。另外，串中的元素之间具有前后顺序，即逻辑结构是线性结构，但与普通的线性表不同的是，串中的元素通常没有数值大小的比较关系，只有相等或不等的关系。串通常采用顺序存储或链式存储方式。故本题选A。

10、试题答案：D

试题解析：

可以运用head和tail函数取A中原子e的步骤如下：
（1）使用tail函数取出A中第二个元素构成的列表：tail(A)=((d,e,f))；
（2）使用head函数取出tail(A)的第一个元素：head(tail(A))=(d,e,f)；
（3）再使用tail函数取出head(tail(A))的尾巴部分：tail(head(tail(A)))=(e,f)
（4）最后使用head函数取出尾巴部分的第一个元素，即原子e：head(tail(head(tail(A))))=e
因此，A中原子e的运算为head(tail(head(tail(A))))=e。故本题选D。