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

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

1、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3 ，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。

A、1和5

B、2和4

C、4和2

D、5和1

2、栈在（ ）中应用。

A、递归调用

B、子程序调用

C、表达式求值

D、A，B，C

4、已知P结点是某双向链表的一个结点，在P结点后插入一个新结点S的语句序列是（ ）。

A、S->prior=P->prior;P->prior=S;S->next=P;P->prior->next=S;

B、S->prior=P;S->next=P->next;P->next->prior=S;P->next=S;

C、S->prior=P->prior;P->prior->next=S;P->prior=S;S->next=P;

D、S->prior=P;S->next=P->next;P->next=S;P->next->prior=S;

5、设完全二叉树的第i=6层有24个叶结点，则此树最多有（）个结点。（i≥1）

A、55

B、79

C、81

D、127

6、下列序列（）不是堆？

A、12，35，39，57，86，48，42，73，66，100

B、12，70，33，65，24，56，48，92，86，33

C、06，12，20，30，52，23，42，38，103，97，66，56

D、05，23，20，35，28，38，29，61，56，76，40，100

7、将下图中二叉树按中序线索化，结点f的右指针和结点g的左指针分别指向结点（）。

A、d，e

B、b，d

C、d，b

D、a，e

8、在Huffman编码中，若编码长度只允许小于等于5，则除了已对两个字符编码为0和10外，还可以最多对（）个字符编码。

A、5

B、6

C、7

D、8

9、设G是一个非连通无向图，有28条边，则该图的顶点数至少有（）个。

A、7

B、8

C、9

D、10

1、试题答案：B

试题解析：

【考点】本题考查数据结构--栈和队列--队列--队列的应用--循环队列--循环队列的基本操作。
【解析】
将顺序队列首尾相接成环状空间即为循环队列。在循环队列中增加一个元素时，尾指针加1；删除一个元素时，头指针加1。本题先删除一个元素，头指针由3变4，再加入两个元素，尾指针由0变为2，故本题选B。

2、试题答案：D

试题解析：

4、试题答案：B

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的链式存储结构--双链表--双链表的基本操作--双链表的插入。
【解析】对于A，若在P结点之后插入S，则S->prior==P，因此A错误；对于C，与A同理，因此C错误；对于D，执行P->next=S后，无法正确执行P->next->prior=S，因为P->next=S会导致P原本的后继结点丢失，因此D错误。B选项正确，各步骤如下图所示：

故本题选B。

5、试题答案：B

试题解析：

6、试题答案：B

试题解析：

（1）堆是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。堆总是满足下列性质：
① 堆中某个结点的值总是不大于或不小于其父结点的值；
② 堆总是一棵完全二叉树。

（2）判断上述各选项是否满足堆性质如下：


故本题选B。

7、试题答案：D

试题解析：

上述二叉树的中序遍历结果为：c，b，e，g，d，f，a，画出中序线索二叉树如下：

由上述树结构可知，结点f的右指针指向结点a，而结点g的左指针指向结点e。故本题选D。

8、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--树与二叉树的应用--哈/赫夫曼树及其编码--哈/赫夫曼编码。
【解析】
哈夫曼编码的特点是每个字母对应的结点都是叶子结点，每个结点的编码不会是其他结点的前缀。因此字符编码还有这几种可能性：11010、11011、11000、11001、11101、11100、11110、11111，故本题选D。

9、试题答案：C

试题解析：

【考点】本题考查数据结构--图--图的基本概念--图的术语--连通性--无向图连通性--连通图。
【解析】
当该图是一个完全连通图时顶点数最少，含有n个顶点完全连通图的边数=n*(n-1)/2，代入边数=28，求出顶点数为8，而题干要求此图是非连通图，因此顶点数应当为9，故本题选C。