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和α都直接相关