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

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

1、冲突是散列表中不可避免的问题，以下解决冲突的方法不属于开放地址法的是（ ）。

A、除留余数法

B、线性探查法

C、二次探查法

D、再散列法

2、下列关键字不能构成二叉搜索树中一个搜索路径的是（ ）。

A、97，12，24，94，71

B、97，20，91，34，8，35

C、12，97，77，29，36，35

D、12，25，97，68，33，34

3、长度为11的有序表进行对半搜索，若每个元素搜索概率相等，则搜索成功的平均查找长度为（ ）。

A、2.9

B、2.8

C、3

D、29/11

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

A、5和1

B、1和5

C、4和2

D、2和4

5、设AVL的任意两个结点为t1与t2，则t1与t2的高度不能为（ ）。

A、11，10

B、10，11

C、3，4

D、6，8

6、设图G=<V，E>，V={0，1，2，3，4，5}，E={（0，2，8），（0，4，12），（1，2，5），（1，5，6），（2，3，1），（2，5，2），（3，4，16），（3，5，3），（4，5，1）}，利用prim算法计算最小生成树的权值（ ）。

A、12

B、17

C、14

D、22

E、无答案

7、一个有n个顶点的无向图包含四个连通分量，则至少有（ ）条边。

A、n-2

B、n-3

C、n-4

D、n-1

8、假设对46，79，56，25，76，38，40，80进行一趟快速排序，则分割元素右侧的元素个数（ ）。

A、2

B、3

C、4

D、1

9、以下说法错误的是（ ）。

A、在二叉平衡树插入一个新结点，新结点为叶子节点。

B、具有完全二叉树树形的树一定是平衡二叉树。

C、具有n个结点的二叉搜索树，树高越小搜索效率越低。

D、在B树中加入一个新元素，该元素可能被调整到根节点。

10、AOV图中存在两个顶点i和j，若i领先j，以下情况绝对不会发生的是（ ）。

A、存在一条j到i的路径

B、不存在一条j到i的路径

C、存在一条i到j的边

D、存在一条i到j的路径

1、试题答案：A

试题解析：

除留余数法此方法为最常用的构造散列函数方法，不属于开放地址法。故本题选A。

2、试题答案：B

试题解析：

二叉排序树，又叫二叉查找树，它或者是一棵空树；或者是具有以下性质的二叉树：
（1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
（2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
（3）它的左右子树也分别为二叉排序树。
先按照各选项所给的顺序画出搜索路径，该路径一定是一个单分支树，再判断该树是否满足二叉排序树的特点。由此发现选项B中的序列所构成的树并不是一个单分支树，所以该序列不能构成二叉排序树中的一个搜索路径。故本题选B。

3、试题答案：C

试题解析：

对长度为11的有序表进行折半查找的成功平均查找长度为（1+2×2+4×3+4×4）/11=3。故本题选C。

4、试题答案：C

试题解析：

在循环队列中，入队时队尾指针向后移动一位，即rear加一，出队时队头指针向后移动一位，即front加一。由题干信息知出队一个元素，front加1结果为4；入队两个元素，rear加2结果为2。故本题选C。

5、试题答案：D

试题解析：

平衡二叉树也叫AVL树，它或者是一棵空树，或者具有以下性质的二叉排序树：它的左子树和右子树的高度之差（平衡因子）的绝对值不超过1，且它的左子树和右子树都是一棵平衡二叉树。选项D中两个结点的高度之差为2，不满足AVL树的特点。故本题选D。

6、试题答案：E

试题解析：

本题存在问题，通过题干所给信息画出的图无法通过prim算法构造一棵生成树。

7、试题答案：C

试题解析：

无向图G的极大连通子图称为G的连通分量。一个图是连通图，最少边的情况下是一棵树，有n-1条边。每断掉一条边，一个连通分量就会变成了两个连通分量，断掉3条边，边数变成n-4，同时变成4个连通分量。因此，一个有n个顶点的无向图包含四个连通分量，则至少有n-4条边。故本题选C。

8、试题答案：C

试题解析：

对序列进行一趟快速排序后，整个序列被基准元素分为左、右两部分，左部分的元素均比基准元素小，右部分的元素均比基准元素大。本题以46为基准元素，经历一趟快速排序后，比46大的四个元素79、56、76、80均位于其右侧。故本题选C。

9、试题答案：C

试题解析：

在搜索树中查找元素时，树越低则比较次数越少，搜索效率越高，所以选项C中说法错误。故本题选C。

10、试题答案：A

试题解析：

AOV网是一个有向无环图，顶点表示活动，弧表示活动间的优先关系。若i先于j，则一定存在一条i到j的路径，又因为AOV中没有环，则一定不存在一条j到i的路径。故本题选A。