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

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

1、以下排序空间复杂度最大的是？（ ）

A、希尔排序

B、快速排序

C、堆排序

D、归并排序

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

A、直接插入排序

B、简单选择排序

C、二路归并

D、基数排序

3、在平衡二叉树中，A是最小不平衡子树，它的左孩子平衡因子为1，右孩子平衡因子为0，其中平衡因子为左子树高度-右子树高度，问需要对失衡子树做（ ）调整？

A、LR

B、RR

C、RL

D、LL

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

A、快速排序

B、堆排序

C、归并排序

D、选择排序

1、试题答案：D

试题解析：

由下表可知，题中各种排序中空间复杂度最大的是归并排序，故本题选D。

2、试题答案：B

试题解析：

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

3、试题答案：D

试题解析：

【考点】本题考查数据结构--查找--动态查找表--平衡二叉树--平衡二叉树的应用。
【解析】下图满足题干条件，其中h代表子树的高度。由此可知是在A的左孩子的左子树中插入结点导致A这棵子树不平衡的，所以应该进行LL型调整。故本题选D。

4、试题答案：C

试题解析：

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