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

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

1、已知一个栈的进栈序列是1，2， 3， ...， n，其输出序列是p1，p2，p3，…，pn，若pn=1，则pi的值是（ ）。

A、i

B、n-i

C、n-i+1

D、不确定

2、设有向图G=（V，E），顶点集V={V0，V1，V2，V3}， 边集E={<v0，v1>，<v0，v2>，<v0，v3>，<v1，v3>}。若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（ ）。

A、2

B、3

C、4

D、5

3、对n（n≥2）个权值均不相同的字符构成哈夫曼树，下列关于该哈弗曼树的叙述中，错误的是（ ）。

A、该树一定是一棵完全二叉树

B、树中一定没有度为1的结点

C、树中两个权值最小的结点一定是兄弟结点

D、树中任一非叶结点的权值一定不小于下一层任一结点的权值

4、若无向图G=（V，E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（ ）。

A、6

B、15

C、16

D、21

5、已知循环队列存储在一维数组A[0..n-1]中， 且队列非空时front和rear分别指向队头和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（ ）。

A、0，0

B、0，n-1

C、n-1，0

D、n-1，n-1

6、下列关于最小生成树的说法中，正确的是（ ）。I. 最小生成树的代价唯一 II. 所有权值最小的边一定会出现在所有的最小生成树中III. 使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV. 使用普里姆算法和克鲁斯卡尔（ Kruskal）算法得到的最小生成树总不相同

A、仅I

B、仅II

C、仅I、III

D、仅II、IV

7、若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（ ）。

A、12

B、20

C、32

D、34

8、若散列表的长度为m，待散列的元素的个数为n，装填因子为α，则散列表的平均查找长度为（ ）。

A、与m直接相关

B、与n直接相关

C、与α直接相关

D、与m、n和α都直接相关

1、试题答案：D

试题解析：

栈具有“后进先出”的特点。根据栈的特性，若pn=1，则可能的出栈序列为2、3、4、…、n、1；或2、n、n-1、…1等，第1个出栈元素可能是2~n的任意一个值，只要保证pop(1)是栈的最后一步操作即可。因此pi的值无法确定，故本题选D。

【考点】本题考查栈的基本操作。

2、试题答案：D

试题解析：

根据题干所示的边集画出该有向图如下：

对上图进行深度优先遍历，从V0出发得到的全部遍历序列为：① V0->V1->V3->V2；② V0->V2->V3->V1；③ V0->V2->V1->V3；④ V0->V3->V2->V1；⑤ V0->V3->V1->V2，共5种深度遍历序列，故本题选D。

【考点】本题考查图的深度优先遍历。

3、试题答案：A

试题解析：

对于A，举出反例，设计字母A、B、C、D、E对应的权值分别为1、2、3、4、5，构造的哈夫曼树如下：

由上图可知，哈夫曼树的本质是带权路径最小的二叉树，哈夫曼树不一定是完全二叉树，因此A错误。对于B，根据哈夫曼树的构造规则，哈夫曼树中只有度为0或度为2的结点，没有度为1的结点，因此B正确。对于C，根据哈夫曼树中结点的添加规则树中两个权值最小的结点会一起添加到树中，因此C正确。对于D，非叶结点是其子结点的权值和，因此D正确。故本题选A。

【考点】本题考查哈夫曼树的性质。

4、试题答案：C

试题解析：

注意本题要求保证图G在任何情况下连通，因此图应当满足边的连接在任何可能情况下保证图是连通的。对于A，若图有6条边则在图中的7个顶点串联的情况下才能保证图的连通性，在其余情况下不能保证图的连通性，因此A错误。使得图中的6个顶点构成完全连通子图，则顶点个数=6*5/2=15，再增加一条边连接第7个顶点，此时边的个数=16。对于D，若7个顶点构成完全连通子图，则顶点个数=7*6/2=21，虽然可以保证在任何情况下连通，但不能保证最少的边，因此D错误。故本题选C。

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

5、试题答案：B

试题解析：

题干中已经说明队列非空时front和rear分别指向队头和队尾元素，第1个元素进入队列后存储在A[0]所在的位置，A[0]位置的元素既是队头元素，又是队尾元素，此时rear=0，front=0。入队操作时rear=(rear+1)%n，由此推导出初始时rear=n-1。而入队操作头指针不改变，因此初始时front=0，故本题选B。

【考点】本题考查循环队列的基本操作。

6、试题答案：A

试题解析：

对于I，最小生成树是代价最小的树，最小代价是唯一的，所以最小生成树的代价唯一，I正确。对于II，若出现相同权值，则可能会出现选择相同权值的边构成了环而舍弃其中一条的情况，因此并非所有权值最小的边出现在最小生成树中，II错误。对于III，最小生成树并不是唯一的，所以从不同的顶点出发，使用prim算法可能会得到不同的树，因此III错误。对于IV，对同一个图，使用不同的最小生成树算法，可能会得到相同的树，因此IV错误。故本题选A。

【考点】本题考查最小生成树的性质。

7、试题答案：B

试题解析：

结点的平衡因子的定义是该结点的左子树的深度减去右子树的深度。根据题干描述，平衡二叉树的高度为6且所有非叶子结点的平衡因子为1，画出这样的平衡二叉树如下：

故本题选B。

【考点】本题考查平衡二叉树的性质。

8、试题答案：C

试题解析：

装填因子指所有关键字填充哈希表后饱和的程度，它等于关键字的总数/表的长度=n/m。哈希表的饱和程度和平均查找长度直接相关，因此散列表的平均查找长度与α直接相关，与m和n间接相关，故本题选C。

【考点】本题考查散列表的平均查找长度。