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

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

1、设N是描述问题规模的非负整数，下列程序段的时间复杂度是（ ）。static int fun(int N){ if(N==1) return 0; return 1 + fun(N/2);}

A、O(logN)

B、O(N)

C、(NlogN)

D、O(N)

2、一些随机产生的数采用线性链表存储，在下面这些排序方法中，（ ）的时间复杂度是最小的。

A、插入排序

B、快速排序

C、堆排序

D、归并排序

3、一个栈的输入序列为a，b，c，d，e，则下列序列中不可能是栈的输出序列的是（ ）。

A、b c d a e

B、e d a c b

C、b c a d e

D、a e d c b

4、实现一个队列需要（ ）个栈。

A、1

B、2

C、3

D、4

5、下面（ ）是一棵满二叉树的结点个数。

A、8

B、13

C、14

D、15

6、下列序列中，哪一个是堆（ ）？

A、75，65，30，15，25，45，20，10

B、75，65，45，10，30，25，20，15

C、75，45，65，30，15，25，20，15

D、75，45，65，10，25，30，20，15

7、一棵Huffman树共有203个结点，对其Huffman编码，共能得到（ ）个不同的码字。

A、100

B、102

C、200

D、203

8、下面说法错误的是（ ）。

A、一个有n个顶点和n条边的无向图一定是有环的。

B、建立十字链表的时间复杂度和建立邻接表是相同的。

C、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

D、在某些图的应用问题中，如果需要找到表示同一条边的两个结点，那么采用邻接多重表比邻接表作为储存结构更为适宜。

9、图的广度优先遍历算法中使用列作为其辅助数据结构，那么在算法执行过程中每个顶点进队次数最多为（ ）。

A、1

B、2

C、3

D、4

10、设一个有向图G=（V，E），其中V={v1，v2，v3，v4，v5，v6}E={<v1，v2>，<v2，v3>，<v3，v6>，<v4，v2>，<v4，v5>，<v5，v6>}不属于该图的拓扑排序有序序列是（ ）。

A、v1 v2 v3 v4 v5 v6

B、v1 v4 v2 v3 v5 v6

C、v4 v5 v1 v2 v3 v6

D、v4 v1 v2 v3 v5 v6

1、试题答案：A

试题解析：

2、试题答案：D

试题解析：

3、试题答案：B

试题解析：

【考点】本题考查数据结构--栈和队列--栈--栈的基本概念--栈的基本操作。
【解析】
对于A，可以采用这样的操作来实现：push(a)、push(b)、pop(b)、push(c)、pop(c)、push(d)、pop(d)、pop(a)、push(e)、pop(e)，因此A正确；对于B，若e为第一个出栈元素，则根据栈“后进先出”的特性，其出栈的序列必为e、d、c、b、a，因此B错误；对于C，可以采用这样的操作来实现：push(a)、push(b)、pop(b)、push(c)、pop(c)pop(a)、push(d)、pop(d)、push(e)、pop(e)，因此C正确；对于D，可以采用这样的操作来实现：push(a)、pop(a)、push(b)、push(c)、push(d)、push(e)、pop(e)、pop(d)、pop(c)、pop(b)，因此D正确。故本题选B。

4、试题答案：B

试题解析：

【考点】本题考查数据结构--栈和队列--栈和队列的综合应用。
【解析】
栈具有“后进先出”的特性，而队列具有“先进先出”的特性。采用栈实现队列时，通常需要两个栈，入队操作即数据进入栈S1；出栈操作首先判断栈S2是否为空，若不为空，则从栈S2出栈，否则元素从栈S1出栈进入栈S2，再从栈S2出栈。故本题选B。

5、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--满二叉树--满二叉树的性质。
【解析】
本题需要正确区分满二叉树和完全二叉树。如果二叉树中除了叶子结点，每个结点的度都为2，则此二叉树称为满二叉树。而一棵高度为d的完全二叉树除了d-1层以外，每一层都是满的，底层叶结点集中在左边的若干位置上。将上述选项按照结点自上而下、自左往右的方式填充，画出树的结构如下：

根据上图可知，A、B、C均为完全二叉树，而D为满二叉树，故本题选D。

6、试题答案：C

试题解析：

【考点】本题考查数据结构--排序--内部排序--选择排序--堆排序--堆--堆的性质。
【解析】
堆总是满足这两个性质：① 堆中某个结点的值总是不大于或不小于其父结点的值；② 堆总是一棵完全二叉树。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。画出各选项对应的二叉树结构并判断是否符合堆的性质如下：


由上图可知，只有C选项符合堆的性质，故本题选C。

7、试题答案：B

试题解析：

【考点】本题考查数据结构--树与二叉树--树与二叉树的应用--哈/赫夫曼树及其编码--哈/赫夫曼树--哈/赫夫曼树的性质。
【解析】
一棵哈夫曼树中仅有度为0和度为2的结点，n=n0+n2。Huffman树的本质是一棵二叉树，因此符合二叉树的性质，n0=n2+1。哈夫曼树的权值与树的叶子结点一一对应，因此本题实际上求的是树的叶子结点的个数。n=n0+n0-1=203，求得n0=102，故本题选B。

8、试题答案：C

试题解析：

【考点】本题考查数据结构--图--图的基本概念。
【解析】
对于A，n-1条边可以构成树，再增加一条边会使得图中存在环，因此A正确；对于B，十字链表把邻接表和逆邻接表整合在一起，建立十字链表和建立邻接表的时间复杂度是相同的，因此B正确；对于C，邻接表既适用于有向图的存储，又适用于无向图的存储，因此C错误；对于D，邻接多重表在针对于删除无向图中的某边等操作时比邻接表更方便，因此D正确。故本题选C。

9、试题答案：A

试题解析：

【考点】本题考查数据结构--图--图的遍历--图的广度优先遍历/搜索--图的广度优先遍历/搜索的算法思想。
【解析】
广度优先的遍历方法为：从某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若图中仍有未被访问的顶点，从该顶点出发重复上述过程。分析上述算法，设队列存储已被访问的顶点，因此每个顶点最多进入队列一次，故本题选A。

10、试题答案：A

试题解析：

【考点】本题考查数据结构--图--有向无环图--拓扑排序--拓扑排序算法--拓扑排序算法的应用。
【解析】
（1）拓扑排序是针对有向图的排序方法，求拓扑排序的方法为：
① 初始时拓扑序列为空；
② 任选一个入度为0的点放入拓扑序列中，同时删除该顶点以及从该顶点出发的弧；
③ 重复上述步骤②直至不存在入度为0的顶点。

（2）画出题干所示的有向图如下：

由上图可知，A选项不符合，v2的入度是2，v1放入拓扑序列后，v2的入度为1，并非为0，其余各选项均正确，故本题选A。