选择类排序法

2.8.3　选择类排序法

1．简单选择排序法

选择排序法的基本思想如下：

扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。

对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将最小的元素与子表中的第一个元素进行交换。如图2-39所示是这种排序法的示意图，图中有方框的元素是刚被选出来的最小元素。

图2-39　简单选择排序法示意图

简单选择排序法在最坏情况下需要比较n(n-1)/2次。

2．堆排序法

堆排序法属于选择类的排序方法。

堆的定义如下：

具有n个元素的序列（h₁，h₂，…，h_n），当且仅当满足

时称之为堆。本节只讨论满足前者条件的堆。

由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。

在实际处理中，可以用一维数组H（1:n）来存储堆序列中的元素，也可以用完全二叉树来直观地表示堆的结构。例如，序列（91，85，53，36，47，30，24，12）是一个堆，它所对应的完全二叉树如图2-40所示。由图2-40可以看出，在用完全二叉树表示堆时，树中所有非叶子节点值均不小于其左、右子树的根节点值。因此，堆顶（完全二叉树的根节点）元素必为序列的n个元素中的最大项。

图2-40　堆顶元素为最大的堆

在具体讨论堆排序法之前，先讨论这样一个问题：在一棵具有n个节点的完全二叉树用一维数组H（1:n）表示，假设节点H（m）的左右子树均为堆，现要将以H（m）为根节点的子树也调整为堆。这是调整建堆的问题。

例如，假设如图2-41(a)所示是某完全二叉树的一棵子树。显然，在这棵子树中，根节点47的左、右子树均为堆。现在为了将整个子树调整为堆，首先将根节点47与其左、右子树的根节点值进行比较，此时由于左子树根节点9l大于右子树根节点53，且它又大于根节点47。因此，根据堆的条件，应将元素47与91交换，如图2-41(b)所示。经过这一次交换后，破坏了原来左子树的堆结构，需要对左子树再进行调整，将元素85与47进行交换，调整后的结果如图2-41(c)所示。

由这个例子可以看出，在调整建堆的过程中，总是将根节点值与左、右子树的根节点值进行比较，若不满足堆的条件，则将左、右子树根节点值中的大者与根节点值进行交换。这个调整过程一直做到所有子树均为堆为止。有了调整建堆的算法后，就可以将一个无序序列建成为堆。

假设无序序列H（1：n）以完全二叉树表示。从完全二叉树的最后一个非叶子节点（即第n/2个元素）开始，直到根节点（即第一个元素）为止，对每一个节点进行调整建堆，最后就可以得到与该序列对应的堆。

图2-41　调整建堆示意图

根据堆的定义，可以得到堆排序的方法如下：

（1）首先将一个无序序列建成堆。

（2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。

不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第（2）步，直到剩下的子序列空为止。

堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为nlog₂n。

【典型例题】

（1）按照“后进先出”原则组织数据的数据结构是______。

A．队列　　B．栈　　C．双向链表　　D．二叉树

参考答案：B。

解析：栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种“后进先出”的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出”的线性表。

（2）下列描述中正确的是______。

A．线性链表是线性表的链式存储结构　　B．栈与队列是非线性结构

C．双向链表是非线性结构　　D．只有根节点的二叉树是线性结构

参考答案：A。

解析：根据数据结构中各数据元素之间前后关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：①有且只有一个根节点；②每个节点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。

（3）对下面的二叉树进行后序遍历的结果为______。

A．ABCDEF　　B．DBEAFC　　C．ABDECF　　D．DEBFCA

参考答案：D。

解析：后序遍历指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根节点；并且遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根节点。

（4）设有下列二叉树：

对此二叉树中序遍历的结果为______。

A．ABCDEF　　B．DBEAFC　　C．ABDECF　　D．DEBFCA

参考答案：B。

解析：所谓中序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根节点，最后遍历右子树；并且在遍历左、右子树时，仍然先遍历左子树，然后访问根节点，最后遍历右子树。

（5）在深度为7的满二叉树中，叶子节点的个数为______。

A．32　　B．31　　C．64　　D．63

参考答案：C。

解析：所谓满二叉树是指这样的一棵二叉树：除最后一层外，每层上的所有节点都有两个子节点。这就是说，在满二叉树中，每一层上的节点数都达到最大值，即在满二叉树的第K层上有2^K-1个节点，且深度为m的满二叉树有2^m-1个节点。树的最大层次称为树的深度。本题中深度为7，故叶子节点数为2^7-1=2⁶=64。

（6）算法的时间复杂度是指______。

A．执行算法程序所需要的时间　　B．算法程序的长度

C．算法执行过程中所需要的基本运算次数　　D．算法程序中的指令条数

参考答案：C。

解析：所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

（7）设一棵完全二叉树共有699个节点，则在该二叉树中的叶子节点数为______。

A．349　　B．350　　C．255　　D．351

参考答案：B。

解析：所谓完全二叉树是指除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。

具有n个节点的完全二叉树，其父节点数为int(n/2)，而叶子节点数等于总节点数减去父节点数。本题n=699，故父节点数等于int(699/2)=349，叶子节点数等于699-349=350。

（8）算法的空间复杂度是指______。

A．算法程序的长度

B．算法程序中的指令条数

C．算法程序所占的存储空间

D．算法执行过程中所需要的存储空间

参考答案：D。

解析：一个算法的空间复杂度，一般是指执行这个算法所需的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。

（9）在深度为5的满二叉树中，叶子节点的个数为______。

A．32　　B．31　　C．16　　D．15

参考答案：C。

解析：所谓满二叉树是指：除最后一层外，每层上的所有节点都有两个子节点。这就是说，在满二叉树中，每一层上的节点数都达到最大值，即在满二叉树的第K层上有2^K-1个节点，且深度为m的满二叉树有2^m-1个节点。

在满二叉树中，最后一层的节点个数就是叶子节点的个数，本题中深度为5，故叶子节点数为2^5-1=2⁴=16。

（10）数据的存储结构是指______。

A．数据所占的存储空间量

B．数据的逻辑结构在计算机中的表示

C．数据在计算机中的顺序存储方式

D．存储在外存中的数据

参考答案：B。

解析：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。

（11）在下列选项中，哪个不是一个算法一般应该具有的基本特征______。

A．确定性　　B．可行性　　C．无穷性　　D．拥有足够的情报

参考答案：C。

解析：作为一个算法，一般应具有以下几个基本特征：

①可行性；②确定性；③有穷性；④拥有足够的情报。

（12）希尔排序法属于哪一种类型的排序法______。

A．交换类排序法　　B．插入类排序法　　C．选择类排序法　　D．建堆排序法

参考答案：B。

解析：希尔排序法的基本思想是：将整个无序序列分割成若干小的子序列分别进行插入排序。所以希尔排序法属于插入类排序，但它对简单插入排序作了很大的改进。

（13）对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。

A．N+1　　B．N　　C．(N+1)/2　　D．N/2

参考答案：B。

解析：在进行顺序查找过程中，如果线性表中被查的元素是线性表中的最后一个，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有元素进行比较，这是顺序查找最坏的情况。

（14）已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是______。

A．cedba　　B．acbed　　C．decab　　D．deabc

参考答案：A。

解析：依据后序遍历序列可确定根节点为c；再依据中序遍历序列可知其左子树由deba构成，右子树为空；又由左子树的后序遍历序列可知其根节点为e，由中序遍历序列可知其左子树为d，右子树由ba构成。求得该二叉树的前序遍历序列为选项A。

（15）在下列几种排序方法中，要求内存量最大的是______。

A．插入排序　　B．选择排序　　C．快速排序　　D．归并排序

参考答案：D。

解析：快速排序的基本思想是：通过一次排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续进行排序，以达到整个序列有序。插入排序的基本操作是指将无序序列中的各元素依次插入到已经有序的线性表中，从而得到一个新的序列。选择排序的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置），然后对剩下的子表采用同样的方法，直到表为空为止。归并排序是将两个或两个以上的有序表组合成一个新的有序表。

（16）算法分析的目的是______。

A．找出数据结构的合理性　　B．找出算法中输入和输出之间的关系

C．分析算法的易懂性和可靠性　　D．分析算法的效率以求改进

参考答案：D。

解析：算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。

（17）n个顶点的强连通图的边数至少有______。

A．n-1　　B．n(n-1)

C．n　　D．n+1

参考答案：C。

解析：在有向图中，若任意两个顶点都连通，则称该图是强连通图，这样的有向图的形状是环状，因而至少应有n条边。

（18）用链表表示线性表的优点是______。

A．便于插入和删除操作　　B．数据元素的物理顺序与逻辑顺序相同

C．花费的存储空间较顺序存储少　　D．便于随机存取

参考答案：A。

解析：链式存储结构克服了顺序存储结构的缺点：它的节点空间可以动态申请和释放；它的数据元素的逻辑次序靠节点的指针来指示，不需要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。

（19）对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数______。

参考答案：45次。

解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较次数为n(n-1)/2。

（20）设一棵完全二叉树共有500个节点，则在该二叉树中有______个叶子节点。

参考答案：250。

解析：所谓完全二叉树是指除最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干节点。

具有n个节点的完全二叉树，其父节点数为int(n/2)，而叶子节点数等于总节点数减去父节点数。本题n=500，故父节点数等于int(500/2)=250，叶子节点数等于500-250=250。

（21）在最坏情况下，冒泡排序的时间复杂度为______。

标准答案为：n(n-1)/2或n*(n-1)/2或O(n(n-1)/2)或O(n*(n-1)/2)

解析：冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序表。

假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。

（22）在先左后右的原则下，根据访问根节点的次序，二叉树的遍历可以分为三种：前序遍历、______遍历和后序遍历。

参考答案：中序。

解析：二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。

前序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先访问根节点，然后遍历左子树，最后遍历右子树；并且遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。

中序遍历指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根节点，最后遍历右子树；并且遍历左、右子树时，仍然先遍历左子树，然后访问根节点，最后遍历右子树。

后序遍历指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历右子树，然后访问根节点，最后遍历左子树；并且遍历左、右子树时，仍然先遍历右子树，然后访问根节点，最后遍历左子树。

（23）数据结构包括数据的______结构和数据的存储结构。

参考答案：逻辑。

解析：数据结构是指带有结构的数据元素的集合。它包括数据的逻辑结构和数据的存储结构。

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构；数据的存储结构是指在计算机存储空间中的存放形式。

（24）栈的基本运算有三种：入栈、退栈和______。

参考答案：读栈顶元素、读栈顶的元素或读出栈顶元素。

解析：

入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进一（即top加1），然后将新元素插入到栈顶指针指向的位置。

退栈运算是指取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针退一（即top减1）。

读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它的值赋给一个变量。

（25）实现算法所需的存储单元多少和算法的工作量大小分别称为算法的______。

参考答案：空间复杂度和时间复杂度。

解析：算法的复杂性是指对一个在有限步骤内终止算法和所需存储空间大小的估计。算法所需存储空间大小是算法的空间复杂性，算法的计算量是算法的时间复杂性。

（26）数据结构包括数据的逻辑结构、数据的______以及对数据的操作运算。

参考答案：存储结构。

解析：数据结构包括3个方面，即数据的逻辑结构、数据的存储结构及对数据的操作运算。

（27）算法的基本特征是可行性、确定性、______和拥有足够的情报。

参考答案：有穷性。

解析：算法是指解题方案的准确而完整的描述。它有4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报。

（28）顺序存储方法是把逻辑上相邻的节点存储在物理位置______的存储单元中。

参考答案：相邻。

解析：常用的存储表示方法有4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的节点存储在物理位置也相邻的存储单元中。

（29）在最坏情况下，堆排序需要比较的次数为______。

参考答案：O(nlog₂n)。

解析：在最坏情况下，冒泡排序所需要的比较次数为n(n-1)/2；简单插入排序所需要的比较次数为n(n-1)/2；希尔排序所需要的比较次数为O(n^1.5)；堆排序所需要的比较次数为O(nlog₂n)。