考研数据结构与操作系统在线题库每日一练（二十二）

本文提供考研数据结构与操作系统在线题库每日一练，以下为具体内容

1、采用线性探测再散列解决冲突的方式，若查找到一个关键字可能经过多次探测地址，则这些探测到的关键字？（ ）

A、一定是同义字

B、一定不是同义字

C、可能是同义字

D、以上说法均错误

2、冒泡排序最坏情况下的移动次数（ ）。

A、n（n-1）/2

B、3n（n-1）/2

C、n（n+1）/2

D、3n（n+1）/2

3、以下排序算法不稳定的是（ ）。

A、直接插入排序

B、简单选择排序

C、二路归并

D、基数排序

4、x为树T的非根结点，bt为x所在的二叉树。在bt中，x是双亲节点的右孩子，则在树T中x（ ）。

A、一定是叶子结点

B、一定有左兄弟

C、一定没有右兄弟

D、一定没有左兄弟

5、下列哪一项为稳定排序（ ）。

A、快速排序

B、堆排序

C、归并排序

D、选择排序

1、试题答案：C

试题解析：

线性探测再散列法：设Hash(x)=Hash(y)=i，则x与y发生冲突；根据线性探测再散列，则y查看下一位置i+1，若有Hash(z)=i+1，则z与y发生冲突，但z与y不是同义字；故可能是同义字，可能不是同义字。综上本题选C。
同义字：关键字x、y经过哈希函数映射到同一个地址，则称x和y产生了冲突，即x与y是同义字。

2、试题答案：A

试题解析：

【考点】本题考查数据结构--排序--内部排序--起/冒泡排序。
【解析】在冒泡排序的最坏情况下，即待排序序列完全逆序排列时，需要执行n-1趟排序才能将最大元素移动到正确的位置。在每一趟排序中，都会进行相邻元素的比较和可能的交换操作。每次比较都会产生一次移动操作。在第一趟排序中，需要比较n-1对相邻元素，并可能进行n-1次交换。在第二趟排序中，需要比较n-2对相邻元素，并可能进行n-2次交换。依此类推，直到最后一趟排序只需要比较1对相邻元素，并可能进行1次交换。因此，冒泡排序最坏情况下的移动次数可移动次数 = (n-1) + (n-2) + ... + 1 = n(n-1)/2。故本题选A。

3、试题答案：B

试题解析：

【考点】本题考查数据结构--排序--内部排序。
【解析】简单选择排序是一种选择排序算法，其基本思想是每次从待排序的元素中选择最小（或最大）的元素，放到已排序部分的末尾。在选择最小（或最大）元素的过程中，可能会改变具有相同关键字的元素的相对位置，因此简单选择排序是不稳定的排序算法。故本题选B。

4、试题答案：B

试题解析：

【考点】本题考查数据结构--树与二叉树--树与森林--树、森林、二叉树的相互转换--树转换为二叉树。
【解析】举例分析，下图中树转换为二叉树满足题干所给的条件。但是，在树中x不是叶子结点，有左兄弟，也有右兄弟。因此，可以排除选项A、C和D。故本题选B。

5、试题答案：C

试题解析：

【考点】本题考查数据结构--排序--内部排序。
【解析】由下表知，归并排序为稳定排序。故本题选C。