1.1 考点精讲

根据考试大纲，本章主要考查以下知识点：

1）算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。

2）数据结构的定义；数据的逻辑结构与存储结构，数据结构的图形表示，线性结构与非线性结构的概念。

3）线性表的定义；线性表的顺序存储结构及其插入与删除运算。

4）栈和队列的定义；栈和队列的顺序存储结构及其基本运算。

5）线性单链表、双向链表与循环链表的结构及其基本运算。

6）树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

7）顺序查找与二分法查找算法；基本排序算法（交换类排序、选择类排序、插入类排序）。

1.1.1 算法与数据结构概述

本节的主要考点集中在算法与数据结构的基本概念上，包括算法的基本特征、复杂度，以及数据结构的表示等。

1.算法的概念

算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内得到所要求的输出的步骤。如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法完成同样的任务可能有不同的时间、空间或效率。

（1）算法的基本特征

1）有穷性（Finiteness）：算法必须能在执行有限个步骤之后终止。

2）确定性（Definiteness）：算法的每一步骤必须有确切的定义。

3）输入项（Input）：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。

4）输出项（Output）：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。

5）可行性（Effectiveness）：也称有效性，算法中执行的任何计算步都可以被分解为基本的、可执行的操作步，即每个计算步都可以在有限时间内完成。

（2）算法的基本要素

算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。

计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有以下4类。

1）算术运算：主要包括加、减、乘、除等运算。

2）逻辑运算：主要包括与、或、非等运算。

3）关系运算：主要包括大于、小于、等于、不等于等运算。

4）数据传输：主要包括赋值、输入、输出等操作。

算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。

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

计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计。在实际应用时，各种方法之间往往存在着一定的联系。

1）递推法：递推法是利用问题本身所具有的一种递推关系求解问题的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的。

2）递归法：递归法指的是一个过程。函数不断引用自身，直到引用的对象已知。

3）穷举搜索法：穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。

4）贪婪法：贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。

5）分治法：分治法是把一个复杂的问题分成两个或更多相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。

6）动态规划法：动态规划法是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

7）迭代法：迭代法是数值分析中通过从一个初始估计解出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。

（4）良好的算法设计的要求

一个良好的算法应达到如下目标。

1）正确性（Correctness）：算法的计算结果必须是正确的。

2）可读性（Readability）：可读性好有助于用户对算法的理解；不易理解的程序容易隐藏较多错误，难以调试和修改。

3）健壮性（Robustness）：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

4）效率与低存储量需求：效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高；存储量需求指算法执行过程中所需要的最大存储空间。

2.算法的复杂度

算法复杂度分为空间复杂度和时间复杂度。

（1）算法的时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。

（2）算法的空间复杂度

算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的存储空间、输入的初始数据所占的存储空间，以及算法执行中所需要的额外空间。

3.数据结构的定义

数据结构（Data Structure）是指相互之间存在一种或多种特定关系的数据元素的集合。

数据（Data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素（Data Element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

在一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在某种关系（即连续），这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。

一般来说，数据元素之间的任何关系都可以用前后件关系来描述。

（1）数据的逻辑结构

数据结构是指反映数据元素之间的关系的数据元素集合的表示。通俗地说，数据结构是指带有结构的数据元素的集合。所谓结构实际上就是指数据元素之间的前后件关系。

一个数据结构应包含两方面信息：表示数据元素的信息和表示各数据元素之间的前后件关系的信息。

数据的逻辑结果是对数据元素之间的逻辑关系的描述。它可以用一个数据元素的集合和在此集合中定义的若干关系来表示。用D表示数据元素的集合，用R表示数据元素之间的前后件关系，即一个数据结构可以表示为B=（D，R），这是一个二元关系的表示方式。

（2）数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式，称为数据的存储结构（也称为数据的物理结构）。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等，而采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。

4.数据结构的表示

数据结构的表示除了用二元关系表示外，还可以直观地用图形表示。

在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据节点，简称为节点。为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件节点指向后件节点。

在数据结构中，没有前件的节点称为根节点；没有后件的节点称为终端节点（也称为叶子节点）。

一个数据结构中的节点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新节点（称为插入运算），也可以删除数据结构中的某个节点（称为删除运算）。插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。

5.线性结构与非线性结构

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

线性结构满足以下条件：

1）有且只有一个根节点。

2）每一个节点最多有一个前件，也最多只有一个后件。

如果一个数据结构不是线性结构，则称之为非线性结构。如果在一个数据结构中一个数据元素都没有，则称该数据结构为空。线性结构与非线性结构都可以是空的数据结构。对于空的数据结构，如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构，否则属于非线性结构。

1.1.2 线性表

本节主要考查线性表的基本概念，以及线性表的顺序存储方式。

1.线性表概述

线性表是一种常用的数据结构。

在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。

线性表是一个线性结构，它是一个含有n（n≥0）个节点的有限序列，对于其中的节点，有且仅有一个开始节点没有前驱（前件）节点但有一个后继（后件）节点，有且仅有一个终端节点没有后继节点但有一个前驱节点，其他的节点都有且仅有一个前驱节点和一个后继节点。一般来说，一个线性表可以表示成一个线性序列：k1，k2，…，kn，其中k1是开始节点，kn是终端节点。

线性结构的基本特征如下：

1）集合中必存在唯一的一个“第一元素”。

2）集合中必存在唯一的一个“最后元素”。

3）除最后一个元素之外，每个元素均有唯一的后继。

4）除第一个元素之外，每个元素均有唯一的前驱。

由n（n≥0）个数据元素（节点）a1，a2，…，an组成的有限序列，数据元素的个数n定义为表的长度。当n=0时称为空表。常常将非空的线性表（n﹥0）记作：（a1，a2，…，an）。

2.线性表的顺序存储

线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储又叫作顺序表。

（1）线性表的顺序存储基本概念

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

1）线性表中的所有元素所占的存储空间是连续的。

2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

假设线性表的每个元素需要占用k个存储单元，并且所占的存储位置ADR（ai+1）和第i个数据元素的存储位置ADR（ai）之间满足下列关系：

ADR（ai+1）=ADR（ai）+k

线性表第i个元素ai的存储位置为：

ADR（ai）=ADR（a1）+（i-1）×k

公式中ADR（a1）是线性表的第一个数据元素的存储位置，通常称为线性表的起始位置或基址。

在C语言中，通常定义一个一维数组来表示线性表的顺序存储空间，如图1-1所示。

在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。

在线性表的顺序存储结构下，可以对线性表做以下运算：

1）在线性表的指定位置处加入一个新的元素（即线性表的插入）。

2）在线性表中删除指定的元素（即线性表的删除）。

3）在线性表中查找某个（或某些）特定的元素（即线性表的查找）。

4）对线性表中的元素进行排序（即线性表的排序）。

5）将一个线性表分解成多个线性表（即线性表的分解）。

6）将多个线性表合并成一个线性表（即线性表的合并）。

7）复制一个线性表（即线性表的复制）。

8）逆转一个线性表（即线性表的逆转）。

（2）顺序表的基本操作

顺序表的基本操作包括插入运算和删除运算。

1）顺序表的插入运算：线性表的插入运算是指在表的第i（1≤i≤n+l）个位置上，插入一个新节点x，使长度为n的线性表（a1，…，ai-1，ai，…，an）变成长度为n+1的线性表（a1，…，ai-1，x，ai，…，an+1）。

现在分析算法的复杂度。设它的值为n。该算法的时间主要花费在循环节点后移语句上，该语句的执行次数（即移动节点的次数）是n-1+1。由此可看出，所需移动节点的次数不仅依赖于表的长度，而且还与插入位置有关。

当i=n+1时，由于循环变量的终值大于初值，节点后移语句将不执行。这是最好的情况，其时间复杂度为O（1）。

当i=1时，节点后移语句将循环执行n次，需移动表中所有节点。这是最坏的情况，其时间复杂度为O（n）。

综合以上的情况，得出算法的平均时间复杂度为O（n）。

2）顺序表的删除运算：线性表的删除运算是指将表的第i（1≤i≤n）个节点删除，使长度为n的线性表（a1，…，ai-1，ai，ai+1，…，an）变成长度为n-l的线性表（a1，…，ai-1，ai+1，…，an-1）。

该算法的时间分析与插入算法相似，节点的移动次数也是由表长n和位置i决定的。

若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动节点。

若i=1，则前移语句将循环执行n-1次，需移动表中除开始节点外的所有节点。这两种情况下算法的时间复杂度分别为O（1）和O（n）。

综合以上的情况得出，在顺序表上做删除运算，平均要移动表中约一半的节点，平均时间复杂度也是O（n）。

1.1.3 栈和队列

栈和队列都是特殊的线性表，其定义符合线性表的定义，其操作也类似于线性表的操作，只不过增加了一些限定而已。

1.栈的定义与操作

栈（Stack）是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表。通常称插入、删除的这一端为栈顶（Top），另一端为栈底（Bottom），如图1-2所示。当表中没有元素时称为空栈。栈顶元素总是后插入的元素，也是最先被删除的元素；栈底元素总是最先被插入的元素，也是最后才能被删除的元素。

假设栈S=（al，a2，a3，…，an），则a1为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…，an的次序进栈，退栈的第一个元素应为栈顶元素，换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为先进后出表（First In Last Out，FILO），或后进先出表（Last In First Out，LIFO）。

栈的操作主要有入栈运算、退栈运算（出栈）和读栈顶元素。

1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加1（即Top加1），然后将元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不能再进行入栈操作，这种情况称为栈“上溢”错误。

2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针减1（即Top减1）。当栈顶指针为0时，说明栈空，不可进行退栈操作，这种情况称为栈的“下溢”错误。

3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。

2.队列的定义与操作

队列（Queue）是只允许在一端删除、在另一端插入的顺序表。允许删除的一端叫作队头（Front），允许插入的一端叫作队尾（Rear），如图1-3所示。

（1）队列的运算

当队列中没有元素时称为空队列。在空队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1，a2，…，an，也就是说队列的修改是按先进先出的原则进行的。因此队列亦称为先进先出的线性表，或后进后出的线性表。

1）入队操作：往队列队尾插入一个元素称为入队运算。

2）出队操作：从队列队头删除一个元素称为出队运算。

（2）循环队列的运算

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

在循环队列中，用队尾指针Rear指向队列中的队尾元素，用队头指针Front指向排头元素的前一个位置。因此，从排头指针Front指向的后一个位置直到队尾指针Rear指向的位置之间的所有元素均为队列中的元素。

在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（Queuesize-l）时，其加1操作的结果是指向向量的下界0。

由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过Front=Rear来判断队列是空还是满。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志值，其定义如下：当s=0时表示队列空，当s=1时表示队列非空。

入队运算：入队运算是指在循环队列的队尾加入一个新元素。首先将队尾指针进1（即Rear=Rear+1），且当Rear=m+l时置Rear=1；然后将新元素插入到队尾指针指向的位置。当循环队列非空（s=l）且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。

出队运算：出队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针进1（即From=Front+1），且当Front=m+1时置Front=1，然后将排头指针指向的元素赋给指定的变量。当循环队列为空（s=0）时，不能进行出队运算，这种情况称为“下溢”。

1.1.4 线性链表

本节主要考查线性链表的存储方式和基本操作。

1.线性表的链式存储

在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表，如图1-4所示。

在链式存储方式中，要求每个节点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该节点的前一个或后一个节点（即前件节点或后件节点）。

（1）线性链表的存储结构

用一组任意的存储单元来依次存放线性表的节点，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零散分布在内存中的任意位置上的。因此，链表中节点的逻辑次序和物理次序不一定相同。为了能正确表示节点间的逻辑关系，在存储每个节点值的同时，还必须存储指示其后件节点的地址（或位置）信息，这个信息称为指针（Pointer）或链（Link）。这两部分组成了链表中的节点结构，链表正是通过每个节点的链域将线性表的n个节点按其逻辑次序链接在一起。由于上述链表的每一个节点只有一个链域，故将这种链表称为单链表（Single Linked）。

显然，单链表中每个节点的存储地址存放在其前驱节点Next域中，而开始节点无前驱节点，故应设头指针HEAD指向开始节点。同时，由于终端节点无后继节点，故终端节点的指针域为空，即NULL。

（2）线性链表的基本运算

线性链表的基本运算包括在线性链表中查找指定元素、在线性链表中插入元素、在线性链表中删除元素。

1）在线性链表中查找指定元素：在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素的前一个节点。

在链表中，查找是否有节点值等于给定值x的节点，若有的话，则返回首次找到的其值为x的节点的存储位置；否则返回NULL。查找过程从开始节点出发，顺着链表逐个将节点的值与给定值x做比较。

2）在线性链表中插入元素：线性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。

插入运算是将值为x的新节点插入到表的第i-1个节点和第i个节点之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新节点*p，并令节点p的指针域指向新节点，新节点的指针域指向节点ai。

由线性链表的插入过程可以看出，由于插入的新节点取自于可利用栈，因此，只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新节点，不会发生“上溢”的情况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而可很方便地实现存储空间的动态分配。另外，线性链表在插入过程中不发生数据元素移动的现象，只要改变有关节点的指针即可，从而提高了插入的效率。

3）在线性链表中删除元素：线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的节点。

删除运算是将表的第i个节点删去。因为在单链表中节点ai的存储地址是在其直接前驱节点ai-1的指针域Next中，所以必须先找到ai-1的存储位置p，然后令p-﹥Next指向ai的直接后继节点，即把ai从链上摘下，最后释放节点ai的空间。

从线性链表的删除过程可以看出，从线性链表中删除一个元素后，不需要移动表中的数据元素，只要改变被删除元素所在节点的前驱节点的指针域即可。另外，可利用栈收集计算机中所有的空闲节点，当从线性链表中删除一个元素后，该元素的存储节点就变为空闲，应将空闲节点送回到可利用栈。

2.双向链表的结构及其基本运算

双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接后继节点和直接前驱节点，如图1-5所示。所以，从双向链表中的任意一个节点开始，都可以很方便地访问它的前驱节点和后继节点。

（1）双向链表的基本运算

1）插入：在双向链表的第i个元素前插入一个新节点的时候，首先，找到待插入的位置，用指针p指向该节点；然后，将新节点的前驱指针指向p节点的前一个节点；之后，将p节点的前一个节点的后驱指针指向新的节点；接下来，将新节点的后驱指针指向p节点；最后，将p节点的前驱指针指向新节点。

2）删除：在双向链表中删除一个节点时，可用指针p指向该节点。首先，将p节点的前一个节点的Next指向p节点的下一个节点；然后，将p的下一个节点的前驱指针指向p的上一个节点。

（2）双链表的结构及其基本运算

在前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个节点的处理必须单独考虑，使空表与非空表的运算不统一。

因此，可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存储空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活。从单链表可知，最后一个节点的指针域为NULL，表示单链表已经结束。如果将单链表最后一个节点的指针域改为存放链表中头节点（或第一个节点）的地址，就使得整个链表构成一个环，又没有增加额外的存储空间，而满足这样条件的链表叫循环链表。

循环链表具有以下两个特点：

1）在循环链表中增加了一个表头节点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的节点。循环链表的头指针指向表头节点。

2）循环链表中最后一个节点的指针域不是空，而是指向表头节点。即在循环链表中，所有节点的指针构成了一个环状链。

在循环链表中，只要指出表中任何一个节点的位置，就可以从它出发访问到表中其他所有的节点，而线性单链表做不到这一点。

由于在循环链表中设置了一个表头节点，因此，在任何情况下，循环链表中至少有一个节点存在，从而使空表的运算与非空表统一。

1.1.5 树与二叉树

本节要求考生掌握树和二叉树的基本定义，重点考查二叉树的基本性质和二叉树的遍历。

1.树的定义

树是由n（n≥0）个节点组成的有限集合。若n=0，称为空树；若n＞0，则：

1）有一个特定的称为根（Root）的节点。它只有直接后继节点，而没有直接前驱节点。

2）除根节点以外的其他节点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0，1，…，m-l）又是一棵树，称为根的子树；每棵子树的根节点有且仅有一个直接前驱节点，但可以有0个或多个直接后继节点。

如图1-6所示是一棵树的示例。

2.二叉树的定义及其性质

二叉树（Binary Tree）是由n（n≥0）个节点的有限集合构成，此集合或者为空集，或者由一个根节点及两棵互不相交的左右子树组成，并且左右子树都是二叉树，如图1-7所示。二叉树可以是空集合，根可以有空的左子树或空的右子树。

（1）二叉树的特点

二叉树具有以下两个特点：

1）非空二叉树只有一个根节点。

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

在二叉树中，一个节点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个节点既没有左子树也没有右子树时，该节点即为叶子节点。

（2）满二叉树与完全二叉树

1）满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，如图1-8所示。

2）完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点，如图1-9所示。

如果有一棵具有n个节点的深度为k的完全二叉树，则它的每一个节点都与深度为k的满二叉树中编号为1～n的节点一一对应。

（3）二叉树的基本性质

性质1：在二叉树的第k层上至多有2 k-1个节点（k≥1）。

性质2：深度为m的二叉树至多有2 m-1个节点。

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

性质4：具有n个节点的完全二叉树的深度至少为【log2n】+1，其中【log2n】表示log2n的整数部分。

性质5：具有n个节点的完全二叉树深度为【log2n】+1或【log2（n+1）】。

性质6：如果对一棵有n个节点的完全二叉树的节点按层序编号（从第1层到第【log2n】+1层，每层从左到右），则对任一节点i（1≤i≤n）有：

1）如果i=1，则节点i无双亲，是二叉树的根；如果i﹥1，则其双亲是节点【i/2】。

2）如果2i≤n，则节点i为叶子节点，无左孩子；否则，其左孩子是节点2i。

3）如果2i+1≤n，则节点i无右孩子；否则，其右孩子是节点2i+1。

（4）二叉树的存储结构

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

3.二叉树的遍历

所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有节点，使得每个节点仅被访问一次。

（1）前序遍历

前序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先访问根节点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。图1-10中的二叉树，前序遍历序列：ABCDEF。

（2）中序遍历

中序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根节点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根节点，最后遍历右子树。图1-10中的二叉树，中序遍历序列：CBDAEF。

（3）后序遍历

后序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根节点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根节点。图1-10中的二叉树，后序遍历序列：CDBFEA。

例，已知二叉树的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则前序遍历序列是什么？

解题过程如下：

1）从后序中，可以先得到根节点是E，然后再看中序的序列：ABCDEFG，可以发现ABCD位于根节点的左边，而FG位于根节点的右边，于是得到图1-11所示的图形。

2）先来看ABCD这部分，然后看后序序列，在后序序列中有BDCA这一部分，可以确定A是这部分的根，再看中序序列中的ABCD，发现BCD都在A的后面。因此，可以画出如图1-12所示的图形。

3）再看BCD这部分，从后序中看到的顺序是BDC，所以C是这部分的根节点，中序序列是BCD，可以断定B在C的左边，D在C的右边。这样，得到如图1-13所示的图形。

4）再看看右边的FG这部分，从后序序列FG和中序FG中，可以推出，G是这部分的根节点，而F位于G的左边。得到如图1-14所示的图形。

5）根据以上步骤合成一个二叉树，如图1-15所示。

6）写出前序遍历序列：EACBDGF。

1.1.6 查找技术

所谓查找是指在一个给定的数据结构中查找某个指定的元素。在查找的过程中，涉及查找的方法等问题，通常，根据不同的数据结构，应采用不同的查找方法。

1.顺序查找

顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：

从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。

在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比较即可查找成功，查找效率最高；但如果被查找的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。

由此可以看出，对于大的线性表来说，顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找。

1）如果线性表为无序线性表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。

2）即使是有序线性表，如果线性表采用链式存储结构，也只能用顺序查找。

2.二分法查找

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

设有序线性表的长度为n，被查元素为x，则二分查找的方法如下。

将x与线性表的中间项进行比较。

1）若中间项的值等于x，则说明查找成功，查找结束。

2）若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找。

3）若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。

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

1.1.7 排序技术

在排序技术方面，主要考查插入排序、选择排序、冒泡排序、快速排序和堆排序等方法。

1.插入排序

每次将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置，使数列依然有序，直到待排序数据元素全部插入完为止。

例，使用插入排序对3、4、2、1、5按照从小到大的顺序排序。

排序过程分析：

第一趟3 4 2 1 5

第二趟2 3 4 1 5

第三趟1 2 3 4 5

第四趟1 2 3 45

2.选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最前，直到全部待排序的数据元素排完。

例，使用选择排序对3、4、2、1、5按照从小到大的顺序排序。

排序过程分析：

第一趟1 4 2 3 5

第二趟 1 2 4 3 5

第三趟1 2 34 5

第四趟1 2 3 4 5

3.冒泡排序

两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

设想被排序的数组R[1..N]垂直竖立，将每个数据元素看成有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直至最后任何两个气泡都是轻者在上、重者在下为止。

例，使用冒泡排序对3、4、2、1、5按照从小到大的顺序排序。

排序过程分析：

第一趟 3 2 1 4 5

第二趟 2 1 3 4 5

第三趟 1 2 3 4 5

第四趟 1 2 3 4 5

4.快速排序

在当前无序区R[1..H]中任取一个数据元素作为比较的“基准”（不妨记为X），用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H]（1≤I≤H），当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。

例如，使用快速排序对7、8、3、4、9、1进行从小到大的排序（仅写出第一趟的结果，以第一个元素为主）。

排序过程分析：

第一趟 7 8 3 4 9 1

第二趟 1 8 3 4 9 7

第三趟 1 7 3 4 9 8

第四趟 1 4 3 7 9 8

第五趟 1 4 3 7 9 8

一般来说，在考试的时候，只问第一趟的结果，也就是以第一个元素为主排列的结果。

5.堆排序

堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系来选择最小的元素。

N个元素的序列K1，K2，K3，…，KN称为堆，当且仅当该序列满足以下特性：

Ki≤K2i，Ki≤K2i+1（1≤i≤[N/2]）

堆实质上是满足如下性质的完全二叉树：树中任一非叶子节点的关键字均大于等于其孩子节点的关键字。

堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字最小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。

例如，使用堆排序对7、8、3、4、9、1进行从小到大的排序，仅写出第一趟排序的结果。

排序过程分析：

因为有6个数，首先取6/2=3，然后看看k3≤k6是否成立（此处没有k7），因为k3的值是3，而k6的值是1，显然不满足条件，要将k3和k6进行交换，就变成如下形式：

然后再看k2≤k4和k2≤k5是否成立。因为k2的值是8，k4的值是4，而k5的值是9，所以，将k2的值和k4的值交换，得到如下序列：

再看k1≤k2和k1≤k3，发现不满足，此时的k1要和k2与k3中最小的一个进行交换，所以得到序列如下：

堆建好了吗？检查每个位置是否满足上面的条件，答案是“没有”。因为此时k3≤k6又不成立了，所以要进行交换，得到如下的序列：

以上是第一趟排列的结果，如果要进行第二趟堆排序的话，就从剩下的4、3、8、9、7开始。

6.各种排序方法的比较

各种排序方法的比较如表1-1所示。

表1-1 各种排序算法的比较