1.1 数据结构与算法

考点1 算法

真考链接

考核概率为45%。该知识点属于熟记内容，考生要熟记算法的概念，以及时间复杂度和空间复杂度的概念。

1.算法的基本概念

算法是指对解题方案准确而完整的描述。

（1）算法的基本特征。

●可行性：针对实际问题而设计的算法，执行后能够得到满意的结果，即必须有一个或多个输出。注意，即使某一算法在数学理论上是正确的，但如果在实际的计算工具上不能执行，则该算法也是不具有可行性的。

●确定性：指算法中每一步骤都必须是有明确定义的。

●有穷性：指算法必须能在有限的时间内做完。

●拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够。

（2）算法的基本要素。

算法一般由两种基本要素构成：

●对数据对象的运算和操作；

●算法的控制结构，即运算和操作时间的顺序。

算法中对数据的运算和操作：算法就是按解题要求从指令系统中选择合适的指令组成的指令序列。因此计算机算法就是计算机能执行的操作所组成的指令序列。不同的计算机系统，其指令系统是有差异的，但一般的计算机系统中都包括的运算和操作有4类，即算术运算、逻辑运算、关系运算和数据传输。

算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。算法的功能不仅取决于所选用的操作，还与各操作之间的执行顺序有关。基本的控制结构包括顺序结构、选择结构和循环结构。

（3）算法设计的基本方法。

算法设计的基本方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。

2.算法复杂度

算法的复杂度主要包括时间复杂度和空间复杂度。

（1）算法的时间复杂度。

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

一般情况下，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f（n）

其中n是问题的规模。这个表达式表示随着问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。

在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入，可以用两种方法来分析算法的工作量：平均性态分析和最坏情况分析。

（2）算法的空间复杂度。

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。算法执行期间所需要的存储空间包括3个部分：

●算法程序所占的空间；

●输入的初始数据所占的存储空间；

●算法执行过程中所需要的额外空间。

在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。

考点2 数据结构的基本概念

1.数据结构的定义

数据结构是指相互有关联的数据元素的集合，即数据的组织形式。

（1）数据的逻辑结构。

所谓数据的逻辑结构，是指反映数据元素之间逻辑关系（即前、后件关系）的数据结构。它包括数据元素的集合和数据元素之间的关系。

（2）数据的存储结构。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。数据结构的存储方式有顺序存储方法、链式存储方法、索引存储方法和散列存储方法。而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。

真考链接

在选择题中，考核概率 45%。该知识点属于熟记内容，熟记数据结构的定义、分类，能区分线性结构与非线性结构。

数据结构研究的内容主要包括3个方面：

●数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构；

●在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

●对各种数据结构进行的运算。

2.数据结构的图形表示

数据元素之间最基本的关系是前、后件关系。前、后件关系，即每一个二元组，都可以用图形来表示。用中间标有元素值的方框表示数据元素，一般称之为数据节点，简称为节点。对于每一个二元组，用一条有向线段从前件指向后件。

用图形表示数据结构具有直观易懂的特点，在不引起歧义的情况下，前件节点到后件节点连线上的箭头可以省去。例如，树形结构中，通常是用无向线段来表示前、后件关系的。

3.线性结构与非线性结构

根据数据结构中各数据元素之间前、后关系的复杂程度，一般将数据结构分为两大类型，即线性结构和非线性结构。

如果一个非空的数据结构有且只有一个根节点，并且每个节点最多有一个直接前驱或直接后继，则称该数据结构为线性结构，又称线性表。不满足上述条件的数据结构称为非线性结构。

小提示

需要注意的是，在一个线性结构中插入或删除任何一个节点后还应该是线性结构；否则，不能称之为线性结构。

真题精选

下列叙述中正确的是（　　）。

A.程序执行的效率与数据的存储结构密切相关

B.程序执行的效率只取决于程序的控制结构

C.程序执行的效率只取决于所处理的数据量

D.以上3种说法都不对

【答案】 A

【解析】在计算机中，数据的存储结构对数据的执行效率有较大影响，如在有序存储的表中查找某个数值比在无序存储的表中查找的效率高很多。

考点3 线性表及其顺序存储结构

真考链接

考核概率为45%。该知识点属于了解性内容，考生需要了解线性表的基本概念。

1.线性表的基本概念

在数据结构中，线性结构也称为线性表，线性表是最简单也是最常用的一种数据结构。

线性表是由n（n≥0）个数据元素a1，a2，…，an组成的一个有限序列，除表中的第一个元素外，其他元素有且只有一个前件，除了最后一个元素外，其他元素有且只有一个后件。

线性表要么是个空表，要么可以表示为

（a1，a2，…，an）

其中ai（i=1，2，…，n）是线性表的数据元素，也称为线性表的一个节点。

每个数据元素的具体含义，在不同情况下各不相同，它可以是一个数或一个字符，也可以是一个具体的事物，甚至其他更复杂的信息。但是需要注意的是，同一线性表中的数据元素必定具有相同的特性，即属于同一数据对象。

小提示

非空线性表具有以下一些结构特征：

●有且只有一个根节点，即头节点，它无前件；

●有且只有一个终节点，即尾节点，它无后件；

●除头节点与尾节点外，其他所有节点有且只有一个前件，也有且只有一个后件。节点个数n称为线性表的长度，当n=0时，称为空表。

2.线性表的顺序存储结构

将线性表中的元素一个接一个地存储在一片相邻的存储区域中。这种顺序表示的线性表也称为顺序表。

线性表的顺序存储结构具有以下两个基本特点：

●元素所占的存储空间必须是连续的；

●元素在存储空间的位置是按逻辑顺序存放的。

从这两个特点也可以看出，线性表是用元素在计算机内物理位置上的相邻关系来表示元素之间逻辑上的相邻关系。只要确定了首地址，线性表内任意元素的地址都可以方便地计算出来。

3.线性表的插入运算

在线性表的插入运算中，在第i个元素之前插入一个新元素，完成插入操作主要有以下3个步骤：

（1）把原来第n个节点至第i个节点依次往后移动一个元素位置；

（2）把新节点放在第i个位置上；

（3）修正线性表的节点个数。

小提示

一般会为线性表开辟一个大于线性表长度的存储空间，经过多次插入运算，可能出现存储空间已满的情况，如果此时仍继续做插入运算，将会产生错误，此类错误称为“上溢”。

如果需要在线性表末尾进行插入运算，则只需要在表的末尾增加一个元素即可，不需要移动线性表中的元素。

如果在第一个位置插入新的元素，则需要移动表中的所有数据。

4.线性表的删除运算

在线性表的删除运算中，删除第i个位置的元素，则要从第i+1个元素开始直到第n个元素之间，共n-i个元素依次向前移一个位置。完成删除运算主要有以下几个步骤：

（1）把第i个元素之后（不包括第i个元素）的n-i个元素依次前移一个位置；

（2）修正线性表的节点个数。

显然，如果删除运算在线性表的末尾进行，即删除第n个元素，则不需要移动线性表中的元素。

如果要删除第1个元素，则需要移动表中的所有数据。

小提示

由线性表的以上性质可以看出，线性表的顺序存储结构适合用于小线性表或者建立之后其中元素不常变动的线性表，而不适合用于需要经常进行插入和删除运算的线性表和长度较大的线性表。

真题精选

【例1】下列有关顺序存储结构的叙述，不正确的是（　　）。

A.存储密度大

B.逻辑上相邻的节点物理上不必邻接

C.可以通过计算机直接确定第i个节点的存储地址

D.插入、删除操作不方便

【答案】 B

【解析】顺序存储结构要求逻辑上相邻的元素物理上也相邻，所以只有选项B叙述错误。

【例2】在一个长度为n的顺序表中，向第i个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次移动（　　）个元素。

A.n-i　　　　B.i　　　　C.n-i-1　　　　D.n-i+1

【答案】 D

【解析】根据顺序表的插入运算的定义知道，在第i个位置上插入x，从ai到an 都要向后移动一个位置，共需要移动n-i+1个元素。

考点4 栈和队列

真考链接

考核概率为90%，属于必考知识点，该知识点较为基础，考生要理解栈和队列的概念和特点，掌握栈和队列的运算。

1.栈及其基本运算

（1）栈的基本概念。

栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删除运算都只在线性表的一端进行。

在栈中，允许插入与删除的一端称为栈顶（top），另一端称为栈底（bottom）。当栈中没有元素时称为空栈，栈也被称为“先进后出”表，或“后进先出”表。

（2）栈的特点。

根据栈的上述定义，可知栈具有以下特点：

●栈顶元素总是最后被插入的元素，也是最早被删除的元素；

●栈底元素总是最早被插入的元素，也是最晚才能被删除的元素；

●栈具有记忆功能；

●在顺序存储结构下，栈的插入和删除运算都不需要移动表中其他数据元素；

●栈顶指针top动态反映了栈中元素的变化情况。

（3）栈的顺序存储及其运算。

栈的状态如图1.1所示。

根据栈的状态，可以得知栈的基本运算有3种。

●入栈运算：在栈顶位置插入一个新元素。

●退栈运算：取出栈顶元素并赋给一个指定的变量。

●读栈顶元素：将栈顶元素赋给一个指定的变量。

2.队列及其基本运算

（1）队列的基本概念。

队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素；允许删除的一端称为队头，通常用一个头指针（front）指向头元素的前一个位置。

因此，队列又称为“先进先出”（FIFO，FirstIn FirstOut）的线性表。插入元素称为入队运算，删除元素称为退队运算。

队列的基本结构如图1.2所示。

（2）循环队列及其运算。

所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

在循环队列中，用尾指针指向队列的尾元素，用头指针指向头元素的前一个位置，因此，从头指针指向的后一个位置直到尾指针指向的位置之间所有的元素均为队列中的元素。循环队列的初始状态为空，即rear=front。

循环队列的基本运算主要有两种：入队运算与退队运算。

●入队运算是指在循环队列的队尾加入一个新的元素。

●退队运算是指在循环队列的队头位置退出一个元素，并赋给指定的变量。

小提示

栈是按照“先进后出”或“后进先出”的原则组织数据，而队列是按照“先进先出”或“后进后出”的原则组织数据。这就是栈和队列的不同点。

真题精选

【例1】下列对队列的叙述，正确的是（　　）。

A.队列属于非线性表　　　　B.队列按“先进后出”原则组织数据

C.队列在队尾删除数据　　　　D.队列按“先进先出”原则组织数据

【答案】 D

【解析】队列是一种特殊的线性表，它只能在一端进行插入，在另一端进行删除。允许插入的一端称为队尾，允许删除的一端称为队头。队列又称为“先进先出”或“后进后出”的线性表，体现了“先到先服务”的原则。

【例2】下列关于栈的描述，正确的是（　　）。

A.在栈中只能插入元素而不能删除元素

B.在栈中只能删除元素而不能插入元素

C.栈是特殊的线性表，只能在一端插入或删除元素

D.栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素

【答案】 C

【解析】栈是一种特殊的线性表。在这种特殊的线性表中，其插入和删除操作只在线性表的一端进行。

考点5 线性链表

真考链接

考核概率为35%，该知识点属于熟记性内容，考生主要熟记线性链表的概念和特点、顺序表和链表的优、缺点等。

1.线性链表的基本概念

线性表的链式存储结构称为线性链表。

为了存储线链性表中的每一个元素，一方面要存储数据元素的值；另一方面要存储各数据元素之间的前、后件关系。为此，在链式存储结构中，每个节点由两部分组成：一部分称为数据域，用于存放数据元素值；另一部分称为指针域，用于存放下一个数据元素的存储序号，即指向后件节点。链式存储结构既可以表示线性结构，也可以表示非线性结构。

线性表链式存储结构的特点是：用一组不连续的存储单元存储线性表中的各个元素。因为存储单元不连续，数据元素之间的逻辑关系，就不能依靠数据元素的存储单元之间的物理关系来表示。

2.线性链表的基本运算

线性链表主要包括以下几种运算：

●在线性链表中包含指定元素的节点之前插入一个新元素；

●在线性链表中删除包含指定元素的节点；

●将两个线性链表按要求合并成一个线性链表；

●将一个线性链表按要求进行分解；

●逆转线性链表；

●复制线性链表；

●线性链表的排序；

●线性链表的查找。

3.循环链表及其基本运算

（1）循环链表的定义。

在单链表的第一个节点前增加一个表头节点，队头指针指向表头节点，在最后一个节点的指针域的值由NULL改为指向表头节点，这样的链表称为循环链表。在循环链表中，所有节点的指针构成了一个环状链。

（2）循环链表与单链表的比较。

对单链表的访问是一种顺序访问，从其中某一个节点出发，只能找到它的直接后继，但无法找到它的直接前驱，而且对于空表和第一个节点的处理必须单独考虑，空表与非空表的操作不统一。

在循环链表中，只要指出表中任何一个节点的位置，就可以从它出发访问到表中其他所有的节点。并且，由于表头节点是循环链表所固有的节点，因此，即使在表中没有数据元素的情况下，表中也至少有一个节点存在，从而使空表和非空表的运算统一。

真题精选

下列叙述中，正确的是（　　）。

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

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

【答案】 A

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

考点6 树和二叉树

真考链接

考核概率为100%，本节属于必考知识点，特别是关于二叉树的遍历，该知识点属于熟记和掌握性内容，考生要熟记二叉树的概念及其相关术语，掌握二叉树的性质以及二叉树的3种遍历方法，本知识点是数据结构的重要组成部分。

1.树的基本概念

树是一种简单的非线性结构，直观地来看，树是以分支关系定义的层次结构。树是由n（n≥0）个节点构成的有限集合，n=0的树称为空树；当n≠0时，树中的节点应该满足以下两个条件：

●有且仅有一个没有前驱的节点称之为根；

●其余节点分成m（m＞0）个互不相交的有限集合T1，T2，…，Tm，其中每一个集合又都是一棵树，称T1，T2，…，Tm为根节点的子树。

在树的结构中主要涉及下面几个概念：

●每一个节点只有一个前件，称为父节点，没有前件的节点只有一个，称为树的根节点，简称树的根；

●每一个节点可以有多个后件，称为该节点的子节点。没有后件的节点称为叶子节点；

●一个节点所拥有的后继个数称为该节点的度；

●所有节点最大的度称为树的度；

●树的最大层次称为树的深度。

2.二叉树及其基本性质

（1）二叉树的定义。

二叉树是一种非线性结构，是一个有限的节点集合，该集合或者为空，或者由一个根节点及其两棵互不相交的左、右二叉子树所组成。当集合为空时，称该二叉树为空二叉树。

二叉树具有以下特点：

●二叉树可以为空，空的二叉树没有节点，非空二叉树有且只有一个根节点；

●每一个节点最多有两棵子树，且分别称为该节点的左子树与右子树。

（2）满二叉树和完全二叉树。

满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，即在满二叉树的第k层上有2k-1个节点，且深度为m的满二叉树中有2m-1个节点。

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

满二叉树与完全二叉树的关系：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

（3）二叉树的主要性质。

●一棵非空二叉树的第k层上最多有2k-1个节点（k≥1）。

●深度为m的满二叉树中有2m-1个节点。

●对任何一棵二叉树，度为0的节点（即叶子节点）总是比度为2的节点多一个。

●具有n个节点的完全二叉树的深度k为[log2 n] +1。

3.二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储节点由数据域和指针域组成。由于每一个元素可以有两个后件（即两个子节点），所以用于存储二叉树的存储节点的指针域有两个：一个指向该节点的左子节点的存储地址，称为左指针域；另一个指向该节点的右子节点的存储地址，称为右指针域。因此，二叉树的链式存储结构也称为二叉链表。

对于满二叉树与完全二叉树可以按层次进行顺序存储。

4.二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有节点。二叉树的遍历主要是针对非空二叉树的，对于空二叉树，则结束遍历并返回。

二叉树的遍历有前序遍历、中序遍历和后序遍历。

（1）前序遍序（DLR）。

首先访问根节点，然后遍历左子树，最后遍历右子树。

（2）中序遍历（LDR）。

首先遍历左子树，然后访问根节点，最后遍历右子树。

（3）后序遍历（LRD）。

首先遍历左子树，然后遍历右子树，最后访问根节点。

小提示

已知一棵二叉树的前序遍历序列和中序遍历序列，可以唯一地确定这棵二叉树。已知一棵二叉树的后序遍历序列和中序遍历序列，也可以唯一地确定这棵二叉树。已知一棵二叉树的前序遍历序列和后序遍历序列，不能唯一地确定这棵二叉树。

真题精选

对如图1.3所示二叉树进行后序遍历的结果为（　　）。

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

【答案】 D

【解析】执行后序遍历，依次执行以下操作：

①首先按照后序遍历的顺序遍历根节点的左子树；

②然后按照后序遍历的顺序遍历根节点的右子树；

③最后访问根节点。

考点7 查找技术

真考链接

考核概率为35%，该知识点属于理解性内容，考生要理解顺序查找与二分查找的概念以及一些查找的方法。

1.顺序查找

顺序查找一般是指在线性表中查找指定的元素。其基本思路是：从表中的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，直到两者相符，查到所要找的元素为止；否则，表中没有要找的元素，查找不成功。

在最好的情况下，第一个元素就是要查找的元素，则比较次数为1次。

在最坏的情况下，顺序查找需要比较n次。

在平均情况下，需要比较 n/2 次。因此，查找算法的时间复杂度为O（n）。

在下列两种情况下只能够采取顺序查找：

●如果线性表中元素的排列是无序的，则无论是顺序存储结构还是链式存储结构，都只能采用顺序查找；

●即便是有序线性表，若采用链式存储结构，则只能进行顺序查找。

2.二分查找

使用二分查找的线性表必须满足两个条件：

●顺序存储结构；

●线性表是有序表。

所谓有序表，是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。

对于长度为n的有序线性表，利用二分查找元素x的过程如下：

（1）将x与线性表的中间项进行比较；

（2）若中间项的值等于x，则查找成功，结束查找；

（3）若x小于中间项的值，则在线性表的前半部分以二分法继续查找；

（4）若x大于中间项的值，则在线性表的后半部分以二分法继续查找。

这样反复进行查找，直到查找成功或子表长度为0（说明线性表中没有这个元素）为止。

当有序线性表为顺序存储时采用二分查找的效率要比顺序查找高得多。对于长度为n的有序线性表，在最坏的情况下，二分查找只需要比较log2 n次，而顺序查找需要比较n次。

真题精选

下列数据结构中，能用二分法进行查找的是（　　）。

A.顺序存储的有序线性表　　　　B.线性链表

C.二叉链表　　　　D.有序线性链表

【答案】 A

【解析】二分查找只适用于顺序存储的有序表。所谓有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。

考点8 排序技术

真考链接

考核概率为25%，该知识点属于掌握性内容，考生要掌握各种排序方法的概念、基本思想及其复杂度。

1.交换类排序法

交换类排序法是指借助数据元素的“交换”来进行排序的一种方法。这里介绍的冒泡排序法和快速排序法就属于交换类排序法。

（1）冒泡排序法。

冒泡排序的思想如下：

在线性表中依次查找相邻的数据元素，将表中最大的元素不断往后移动，反复操作直到消除所有逆序，此时，该表已经排序结束。

冒泡排序法的基本过程如下：

①从表头开始往后查找线性表，在查找过程中逐次比较相邻两个元素的大小。若在相邻两个元素中，前面的元素大于后面的元素，则将它们交换；

②从后向前查找剩下的线性表（除去最后一个元素），同样，在查找过程中逐次比较相邻两个元素的大小。若在相邻两个元素中，后面的元素小于前面的元素，则将它们交换；

③对剩下的线性表重复上述过程，直到剩下的线性表变空为止，线性表排序完成。

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

（2）快速排序法。

快速排序法的基本思想如下：

在线性表中逐个选取元素，将线性表进行分割，直到所有元素全部选取完毕，此时线性表已经排序结束。

快速排序法的基本过程如下：

①从线性表中选取一个元素，设为T，将线性表后面小于T的元素移动到前面，而将大于T的元素移到后面，这样就将线性表分成了两部分（称为两个子表），T就是处于分界线的位置，将线性表分成了前、后两个子表，且前面子表中的所有元素均不大于T，而后面的子表中的所有元素均不小于T，此过程称为线性表的分割；

②对分割后的子表再按上述原则进行反复分割，直到所有子表为空为止，则此时的线性表就变成有序表。

2.插入类排序法

插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。这里主要介绍简单插入排序法和希尔排序法。

（1）简单插入排序法。

简单插入排序是把n个待排序的元素看成一个有序表和一个无序表，开始时，有序表只包含一个元素，而无序表包含n-1个元素，每次取无序表中的第一个元素插入到有序表中的正确位置，使之成为增加一个元素的新的有序表。插入元素时，插入位置及其后的记录依次向后移动。最后有序表的长度为n，而无序表为空，此时排序完成。

在简单插入排序中，每一次比较后最多移掉一个逆序，因此，该排序方法的效率与冒泡排序法相同。在最坏的情况下，简单插入排序需要n（n-1）/2次比较。

（2）希尔排序法。

希尔排序法的基本思路为：将整个无序序列分割成若干个小的子序列并分别进行插入排序。

分割方法如下：

①将相隔某个增量h的元素构成一个子序列；

②在排序过程中，逐次减少这个增量，直到h减少到1时，进行一次插入排序，排序即可完成。

希尔排序的效率与所选取的增量序列有关。

3.选择类排序法

选择排序的基本思想是通过每一趟从待排序序列中选出值最小的元素，按顺序放在已排好序的有序子表的后面，直到全部序列满足排序要求为止。下面就介绍选择类排序法中的简单选择排序法和堆排序法。

（1）简单选择排序法。

简单选择排序的基本思想是：首先从所有n个待排序的数据元素中选择最小的元素，将该元素与第一个元素交换，再从剩下的n-1个元素中选出最小的元素与第二个元素交换。重复这样的操作直到所有的元素有序为止。

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

（2）堆排序法。

堆排序的方法如下：

①将一个无序序列建成堆；

②将堆顶元素与堆中最后一个元素交换。忽略已经交换到最后的那个元素，考虑前n-1个元素构成的子序列，只有左、右子树是堆，可以将该子树调整为堆。这样重复去做第二步，直到剩下的子序列为空时止。

在最坏的情况下，堆排序需要比较的次数为nlog2 n。

真题精选

对于长度为n的线性表，在最坏的情况下，下列各排序法所对应的比较次数中正确的是（　　）。

A.冒泡排序为n/2　　　　B.冒泡排序为n

C.快速排序为n　　　　D.快速排序为n（n-1）/2

【答案】 D

【解析】假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较次数为n（n-1）/2。快速排序法在最坏的情况下，比较次数也是n（n-1）/2。

常见问题

为什么只有二叉树的前序遍历和后序遍历不能唯一确定一棵二叉树？

在二叉树遍历中前序和后序中都可以确定根节点，但中序是由左至根及右的顺序，所以知道前序（或后序）和中序肯定能唯一确定二叉树；在前序和后序中只能确定根节点而对于左、右子树的节点元素没办法正确选取，所以很难确定一棵二叉树。由此可见，需要确定一棵二叉树的基础是必须得知道中序遍历。