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

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

1、在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系（ ）。

A、不一定相同

B、互为逆序

C、都不相同

D、都相同

2、深度为4的二叉树至多有结点数为（ ）。

A、 18

B、14

C、15

D、16

3、在一个具有n个顶点的有向图中，若所有顶点的入度数之和为m，则所有顶点的度数之和为（ ）。

A、m

B、m-1

C、m+1

D、2m

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

A、被排序的数据量太大

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

C、被排序的数据完全无序

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

5、一组记录的关键字为（45，80，55，40，42，85）， 则利用堆排序的方法建立的初始堆为（ ）。

A、（80，45，55，40，42，85）

B、（85，80，55，40，42，45）

C、（85，80，55，45，42，40）

D、（85，55，80，42，45，40）

6、对有18个元素的有序表（下标为1~18）作折半查找，则查找A[3]的比较序列的下标为（ ）。

A、1，2，3

B、9，5，2，3

C、9，5，3

D、9，4，2，3

7、具有n个顶点的完全有向图的边数为（ ）。

A、n（n-1）/2

B、n（n-1）

C、n2

D、n2-1

8、利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素35要进行（ ）。

A、4次

B、5次

C、3次

D、2次

9、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（ ）。

A、求最短路径的Floyd方法

B、求最短路径的Dijkstra方法

C、广度优先遍历算法

D、深度优先遍历算法

10、对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（ ）。

A、0

B、1

C、n

D、n+1

1、试题答案：D

试题解析：

本题考查二叉树的遍历。
后序遍历二叉树先遍历左子树，再遍历右子树，最后访问根结点。中序遍历二叉树先遍历左子树，再访问根结点，最后遍历右子树。前序遍历二叉树先访问根结点，再遍历左子树，最后遍历右子树。因此叶子节点在前序、中序、后序遍历中的顺序一定是左叶子在前，右叶子在后，其相对次序相同。故本题选D。

2、试题答案：C

试题解析：

本题考查满二叉树的性质。
当这棵二叉树为一棵满二叉树时，其结点数最多。满二叉树的第一层有1个结点，第二层有2个结点，第三层有4个结点，第四层有8个结点。因此每层的结点数为2h-1个，深度为h的二叉树总的结点数=20+21+……+2h-1，带入h=4，总的结点数=1+2+4+8=15。故本题选C。

3、试题答案：D

试题解析：

本题考查有向图的度。
在一个有向图中，任意一条边连接两个顶点，该边必是一个顶点的入度，一个顶点的出度，因此有多少条边，就有多少个入度和出度，入度=出度=边数=1/2总度数。故本题选D。

4、试题答案：D

试题解析：

本题考查快速排序的思想。
快速排序是把序列分块，平均情况下其时间复杂度为O（nlogn）。若序列已经基本有序，则选取第一个数为枢纽时，第一块前面没有数，第二块除了第一个数以外的所有值，每次分块仅减少一个值。分块的时间复杂度是O（n），分了n次块，时间复杂度是O（n2）。故本题选D。

5、试题答案：B

试题解析：

本题考查初始堆的构造。
初始堆的含义为一棵完全二叉树调整成的大顶堆或者小顶堆。首先按照关键字构造一棵完全二叉树如下：

之后将这棵完全二叉树调整成大顶堆如下：

故本题选B。

6、试题答案：D

试题解析：

本题考查折半查找的应用。
根据折半查找的原理列出每一次的查找如下：
第一次：区间[1，18]，mid=（1+18）/2=9，A[9]>A[3]；第二次：区间[1，8]，mid=（1+8）/2=4，A[4]>A[3]；第三次：区间[1，3]，mid=（1+3）/2=2，A[2]<[3]；第四区间[3]，A[3]=A[3]。故本题选D。

7、试题答案：B

试题解析：

本题考查完全有向图的概念。
完全有向图是指图中各边均有方向，并且每两个顶点之间都有两条方向相反的边连接成图。因此，图中的各个顶点均需要与除自身顶点以外的各个顶点相连，每个顶点连接n-1个顶点需要n-1条边，n个顶点需要n（n-1）条边。故本题选B。

8、试题答案：A

试题解析：

本题考查二叉排序树的基本操作。
二叉排序树的基本概念为二叉排序树或者为空树，或者为具有如下特性的树：（1）若它的左子树不为空，则左子树上的所有结点的值均小于根结点的值；（2）若它的右子树不为空，则右子树上的所有结点的值均大于或等于根结点的值；（3）其左右子树也分别为二叉排序树。
根据逐点插入法建立的二叉排序树如下图所示：

根据这棵二叉排序树，查找35时，第1次和50比较，比50小，到左子树；第2次，和43比较，比43小，进入43的左子树；第3次，和20比较，比20大，进入20的右子树；第4次，和35比较，相等，查找结束。故本题选A。

9、试题答案：D

试题解析：

本题考查有向图回路判断。
判断有向图是否存在环有两种方法，分别为深度遍历和拓扑排序。若深度遍历中有结点被第二次访问到则证明有环。拓扑排序的思想为每次找入度为0的点，添加到输出队列，然后将与此点相连的结点入度减1，重复上述过程直至删除所有结点。若存在结点无法删除，则证明有环。而A、B、C选项涉及的最短路径算法、广度优先算法都是既可以适用于有环图也可以适用于无环图，因此无法判断回路。故本题选D。

10、试题答案：B

试题解析：

本题考查无向连通图的基本概念。
无向图的极大连通图为连通分量，对于连通图只有一个连通分量，即其本身。非连通的无向图含有多个连通分量。故本题选B。