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的路径