考研数据结构及程序设计在线题库每日一练（一十二）

本文提供考研数据结构及程序设计在线题库每日一练，以下为具体内容

1、希尔排序的组内排序采用的是（  ）。

A、 直接插入排序

B、 折半插入排序

C、 快速排序

D、 归并排序

2、含有4个元素值均不相同的结点的二叉排序树有（ ）种。

A、4

B、6

C、10

D、14

3、散列函数有一个共同性质，即函数值应按（ ）取其值域的每一个值。

A、最大概率

B、最小概率

C、同等概率

D、平均概率

5、设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。

A、11

B、6

C、7

D、8

1、试题答案：A

试题解析：

【考点】本题考查希尔排序。
【解析】希尔排序的基本思想是现将整个待排序列分割成若干子序列，对子序列分别进行插入排序，待整个序列中的记录基本有序之后，再对整个序列进行一次插入排序。希尔排序的组内排序采用的是直接插入排序。故本题选A。

2、试题答案：D

试题解析：

【考点】本题考查二叉排序树。
【解析】
假设4个元素值均不相同的结点值为1、2、3、4，分析其构成二叉排序树的种类过程如下所示：
① 若结点1为根结点，构成的二叉排序树有5种，如下所示：

② 若结点2为根结点，构成的二叉排序树有2种，如下所示：

③ 若结点3为根结点，构成的二叉排序树有2种，如下所示：

④ 若结点4为根结点，构成的二叉排序树有5种，如下所示：

综上所述，含有4个元素值均不相同的结点的二叉排序树有5+2+2+5=14种。故本题选D。

3、试题答案：C

试题解析：

【考点】本题考查散列函数的性质。
【解析】构造哈希函数的原则是：① 函数本身便于计算；② 计算出来的地址分布均匀，即对任一关键字，哈希值对应不同地址的概率相等，目的是尽可能减少冲突。故本题选C。

5、试题答案：A

试题解析：

【考点】本题考查图的连通性。
【解析】一个有n个顶点的无向完全图，其边数至少为n(n-1)/2 。对于有6个结点的无向图，若其中5个结点构成的图是完全图，剩余的一个结点与这个完全图相连，那么这个具有6个结点的无向图确保是一个连通图。因此，该有6个结点的无向图至少应有5×4÷2+1=11条边才能确保是一个连通图。故本题选A。