下载掌阅APP，畅读海量书库
立即打开
（1）算法的定义
算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。它是一组严谨定义运算顺序的规则，且每个规则都是明确有效的，此顺序将在有限的次数下终止。需要注意的是：算法不等于程序，也不等于计算方法。
（2）算法的基本特征
①可行性
a．算法中的每一步骤都必须能够实现；
b．算法执行的结果要能够达到预期的目的。
②确定性
确定性是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释，也不允许有多义性。
③有穷性
有穷性是指算法必须能在有限的时间内做完，即必须能在执行有限个步骤之后终止，且必须有合理的执行时间。
④拥有足够的情报
算法是否有效，取决于为算法所提供的情报是否足够。一般而言，当算法有足够的情报时，此算法有效，而当提供的情报不够时，算法可能无效。
【真题演练】
算法的有穷性是指（
）。
[2013年9月真题]
A．算法程序的运行时间是有限的
B．算法程序所处理的数据量是有限的
C．算法程序的长度是有限的
D．算法只能被有限的用户使用
（1）列举法
①基本思想
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。常用于解决“是否存在”或“有多少种可能”等类型的问题。
②主要特点
算法比较简单，但列举情况较多时，算法工作量很大。
③注意事项
例举算法时，通过对实际问题进行详细分析，将与问题有关的知识条理化、完备化、系统化，并从中找出规律，或对所有可能的情况进行分类，从而引出一些有用的信息，减少列举量。
（2）归纳法
①基本思想
通过列举少量的特殊情况，经过分析，最后找出一般的关系。
②主要特点
a．比列举法更能反映问题的本质，可解决列举量为无限的问题；
b．可操作性低，不易归纳出一个具体数学模型；
c．归纳得出的结论只是一种猜测，须对这种猜测加以必要的证明。
（3）递推
①基本思想
从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。
②主要特点
a．初始条件或问题本身已给定，或通过对问题的分析化简得到；
b．递推本质上属于归纳法，递推关系式往往是归纳的结果；
c．数值型递推算法计算过程中必须注意数值计算的稳定性问题。
（4）递归
①基本思想
将复杂问题逐层分解，归结为一些简单的问题，将简单问题解决掉，再沿着原来分解的逆过程逐步进行综合。
②主要特点
a．递归的基础是归纳，对问题逐层分解的过程实际上并没有对问题进行求解；
b．在可计算性理论和算法设计中占有重要地位；
c．递归算法比递推算法清晰易读，结构简练；
d．设计递归算法比递推算法容易，但是其执行效率较低。
③分类
a．直接递归。一个算法P显式地调用自己。
b．间接递归。算法P调用另一个算法Q，而算法Q又调用算法P。
④递归与递推的区别
递归与递推的区别主要在于二者实现方法的不同，表现为：
a．递归是从算法本身到达递归的边界的；
b．递推是从初始条件出发，逐次推出所需求的结果。
（5）减半递推技术
减半递推技术是工程上常用的分治法，其中，“减半”指将问题的规模减半，而问题的性质不变；“递推”指重复“减半”的过程。
（6）回溯法
回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，则问题得到解决，若试探失败，则逐步回退换别的路线再进行试探。
【真题演练】
1．下列叙述中正确的是（
）。
[2013年9月真题]
A．所谓算法就是计算方法
B．程序可以作为算法的一种描述方法
C．算法设计只需考虑得到计算结果
D．算法设计可以忽略算法的运算时间
2．下列关于算法的描述中错误的是（
）。
[2014年3月真题]
A．算法强调动态的执行过程，不同于静态的计算公式
B．算法必须能在有限个步骤之后终止
C．算法设计必须考虑算法的复杂度
D．算法的优劣取决于运行算法程序的环境
（1）时间复杂度
①定义
算法的时间复杂度是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即
算法的工作量＝f（n）
其中，n是问题的规模。
②在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以下两种方法来分析算法的工作量：
a．平均性态
其中，x是所有可能输入中的某个特定输入，p（x）是x出现的概率，即输入为x的概率，t（x）是算法在输入为x时所执行的基本运算次数，D n 表示当规模为n时，算法执行时所有可能输入的集合。
b．最坏情况复杂性
最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。其定义为：
（2）空间复杂度
①定义
算法的空间复杂度一般是指执行这个算法所需要的内存空间。
②存储空间组成
一个算法的存储空间包括以下几种：
a．算法程序占用的空间；
b．输入的初始数据占用的存储空间；
c．算法执行过程中所需要的额外空间。
额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间，若额外空间相对于问题规模来说是常数，则称该算法是原地工作的。
【真题演练】
1．下列叙述中正确的是（
）。
[2015年3月真题]
A．算法的效率只与问题的规模有关，而与数据的存储结构无关
B．算法的时间复杂度是指执行算法所需要的计算工作量
C．数据的逻辑结构与存储结构是一一对应的
D．算法的时间复杂度与空间复杂度一定相关
2．算法的空间复杂度是指（
）。
[2013年9月真题]
A．算法在执行过程中所需要的计算机存储空间
B．算法所处理的数据量
C．算法程序中的语句或指令条数
D．算法在执行过程中所需要的临时工作单元数
3．算法空间复杂度的度量方法是（
）。
[2014年9月真题]
A．算法程序的长度
B．算法所处理的数据量
C．执行算法所需要的工作单元
D．执行算法所需要的存储空间
（1）数据处理概述
①定义
数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。
②关键问题
大量数据元素在计算机中如何组织，以便提高数据处理的效率，从而节省计算机的存储空间，这是进行数据结构处理的关键问题。
（2）数据结构研究概述
①研究问题
a．数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
b．在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
c．对各种数据结构进行的运算。
②研究目的
数据结构研究和讨论上述3个问题的主要目的在于提高数据处理效率，包括：a．提高数据处理的速度；b．尽量节省在数据处理过程中所占用的计算机存储空间。
（1）数据结构的定义
数据结构是指相互有关联的数据元素的集合，即它是反映数据元素之间关系的数据元素集合的表示。简言之，数据结构是指带有结构的数据元素的集合，这里的“结构”指数据元素之间的前后件关系。一个数据结构应包含以下两方面内容：
①表述数据元素的信息；
②表示各数据元素之间的前后件关系。
（2）数据的逻辑结构
①定义
数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。
②要素：
a．数据元素的集合，通常记为D；
b．D上的关系，通常记为R，它反映了D中各数据元素之间的前后件关系。
③表示
一个数据结构B可表示为：
B＝（D，R）
为反映D中个数据元素之间的前后件关系，一般用二元组来表示。
（3）数据的存储结构
①定义
数据的存储结构，也称数据的物理结构，是指数据逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，而且要存放各数据元素之间的前后件信息。
②常用的存储结构：a．顺序；b．链接；c．索引。
采用不同的存储结构，数据处理的效率是不同的。
【真题演练】
下列叙述中正确的是（
）。
[2014年3月真题]
A．有且只有一个根结点的数据结构一定是线性结构
B．每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构
C．有且只有一个根结点的数据结构一定是非线性结构
D．有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构
（1）在数据结构的图形表示中，数据集合D中每个元素用中间标有元素值的方框表示，称为数据结点（简称结点）；对关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。
（2）在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点（也称叶子结点），其余结点都称为内部结点。
（3）数据结构中的元素结点可能是在动态变化的，这种变化体现在结点数量的增减以及各结点之间的前后件关系的动态变化上。
根据数据结构中各数据元素之间的前后件关系的复杂程度，可将数据结构分为：
（1）线性结构（线性表）
一个非空的数据结构满足下列两个条件时，称其为线性结构：
①有且只有一个根结点；
②每个结点最多只有一个前件，也最多只有一个后件。
线性结构中插入或删除任何一个结点还应是线性结构，如果不满足这个条件就不能称之为线性结构。
（2）非线性结构
如果一个数据结构不是线性结构，则称之为非线性结构。
注：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构属于线性结构还是非线性结构，需要根据对该数据结构的运算是否按照线性结构的规则来处理进行判断。
（1）线性表是一种最常见最简单的数据结构，由一组数据元素构成。数据元素在线性表中的位置值只取决于它们自己的序号，即数据元素之间的相对位置是线性的。
（2）非空线性表的结构特征：
①有且只有一个根结点a 1 ，它无前件；
②有且只有一个终端结点a n ，它无后件；
③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表中结点的个数n称为线性表的长度。当n＝0时，称为空表。
【真题演练】
下列叙述中正确的是（
）。
[2014年9月真题]
A．结点中具有两个指针域的链表一定是二叉链表
B．结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C．二叉树只能采用链式存储结构
D．循环链表是非线性结构
（1）概述
顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。
（2）特点：
①线性表中所有元素所占的存储空间是连续的；
②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
（3）运算
在线性表的顺序存储结构下，可对线性表进行以下运算：
①插入：在线性表的指定位置处加入一个新的元素；
②删除：在线性表中删除指定的元素；
③查找：在线性表中查找某个（或某些）特定的元素；
④排序：对线性表中的元素进行整序；
⑤分解：按要求将一个线性表分解成多个线性表；
⑥合并：按要求将多个线性表合并成一个线性表；
⑦复制：复制一个线性表；
⑧逆转：逆转一个线性表等。
【真题演练】
在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数（
）。
[2014年3月真题]
A．相同，元素的存储顺序与逻辑顺序一致
B．相同，但其元素的存储顺序可以与逻辑顺序不一致
C．不同，但元素的存储顺序与逻辑顺序一致
D．不同，且其元素的存储顺序可以与逻辑顺序不一致
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），插入的位置为i（表示在第i个位置插入元素），则顺序表插入新元素过程如下：
（1）首先处理以下三种异常情况：
①当存储空间已满（即n＝m）时为“上溢”错误，不能进行插入，算法结束；
②当i>n时，认为在最后一个元素之后（即第n＋1个元素之前）插入；
③当i<1时，认为在第1个元素之前插入。
（2）从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。
（3）最后将新元素插入到第i个位置，并且将线性表的长度增加1。
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），删除的位置为i（表示删除第i个元素），则顺序表删除元素的过程如下：
（1）首先处理以下两种异常情况：
①当线性表为空（即n＝0）时为“上溢”错误，不能进行插入，算法结束；
②当i<1或i>n时，认为在最后一个元素之后（即第n＋1个元素之前）插入。
（2）然后从第i＋1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。
（3）最后将线性表的长度减小1。
（1）栈的定义
栈是限定在一端进行插入与删除的线性表。
（2）栈的特点：
①允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入也是最后被删除的。
②栈遵循“先进后出”或“后进先出”的原则，具有记忆功能。
③通常用指针top来指示栈顶位置，用指针bottom指向栈底，栈顶指针top动态反映了栈中元素的变化情况。
（3）栈的顺序存储及其运算
在栈的顺序存储空间S（1:m）中，top＝0表示栈空；top＝m表示栈满。
栈的三种运算：
①入栈运算
人栈运算是指在栈顶位置插入一个新元素。操作过程如下：
a．首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。
b．然后将栈顶指针进一（即top加1）。
c．最后将新元素x插入栈顶指针指向的位置。
②退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：
a．首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈 “ 下溢 ” 错误），算法结束。
b．然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。
c．最后将栈顶指针退一（即top减1）。
③读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：
a．首先判断栈顶指针是否为0。如果是，则说明栈空，读不到栈顶元素，算法结束。
b．然后将栈顶元素赋给指定的变量y。
这个运算不删除栈顶元素，只是将它的值赋给一个变量，栈顶指针不会变。
【真题演练】
1．支持子程序调用的数据结构是（
）。
[2013年9月真题]
A．栈
B．树
C．队列
D．二叉树
2．下列与栈结构有关联的是（
）。
[2013年3月真题]
A．数组的定义域使用
B．操作系统的进程调度
C．函数的递归调用
D．选择结构的执行
3．设栈的顺序存储空间为S（1：50），初始状态为top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（
）。
[2014年3月真题]
A．30
B．29
C．20
D．19
4．一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（
）。
[2013年9月真题]
A．12345ABCDE
B．EDCBA54321
C．ABCDE12345
D．54321FDCBA
（1）什么是队列
队列（Queue）是指允许在一端进行插入、而在另一端进行删除的线性表。
（2）队列的特点
①允许插入的一端称为队尾，用队尾指针指向队尾元素；允许删除的一端称为队头，用排头指针指向排头元素的前一个位置。
②最先插入的元素最先被删除，最后插入的元素最后被删除，遵循“先进先出”或“后进后出”原则。
③队尾指针rear和排头指针front共同反映队列中元素变动情况。
④入队运算指只涉及队尾指针rear变化，退队运算只涉及排头指针front变化。
（3）循环队列及其运算
循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队尾元素，用排头指针front指向排头元素的前一个位置，从排头指针front指向的后一个位置到队尾指针rear指向的位置均是队列中元素。队列空的条件是s＝0；队列满的条件是s＝1且front＝rear。
队列的两种运算
假设循环队列的初始状态为空，即：s＝0，且front＝rear＝m。
①入队运算
入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：
a．首先判断循环队列是否满。当循环队列非空（S＝1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。
b．然后将队尾指针进一（即rear＝rear＋1），并当rear＝m＋1时置rear＝1。
c．最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。
②退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：
a．首先判断循环队列是否为空。当循环队列为空（s＝0）时，不能进行退队运算。这种情况称为 “ 下溢 ” 。此时算法结束。
b．然后将排头指针进一（即front＝front＋1），并当front＝m＋1时置front＝1。
c．再将排头指针指向的元素赋给指定的变量。
d．最后判断退队后循环队列是否为空。当front＝rear时置循环队列空标志（即s＝0）。
【真题演练】
1．下列叙述中正确的是（
）。
[2013年9月真题]
A．栈是“先进先出”的线性表
B．队列是“先进后出”的线性表
C．循环队列是非线性结构
D．有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
2．下列叙述中正确的是（
）。
[2014年3月真题]
A．循环队列是顺序存储结构
B．循环队列是链式存储结构
C．循环队列是非线性结构
D．循环队列的插入运算不会发生溢出现象
3．对于循环队列，下列叙述中正确的是（
）。
[2013年9月真题]
A．队头指针是固定不变的
B．队头指针一定大于队尾指针
C．队头指针一定小于队尾指针
D．队头指针可以大于队尾指针，也可以小于队尾指针
4．下列叙述中正确的是（
）。
[2013年9月真题]
A．循环队列有队头和队尾两个指针，因此，循环队列是非线性结构
B．在循环队列中，只需要队头指针就能反映队列中元索的动态变化情况
C．在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
D．循环队列中元素的个数是由队头指针和队尾指针共同决定
（1）线性表的顺序存储结构存在的缺陷：
①在插入或删除元素时，为保证操作后的线性表仍然是顺序存储，需要大量移动数据元素，效率很低。
②在顺序存储结构下，线性表的存储空间不便于扩充，易产生上溢现象。
③线性表的顺序存储结构不便于对存储空间的动态分配。
（2）链式存储结点组成：
①数据域：用于存放数据元素值；
②指针域：用于存放指针。
指针用于指向该结点的前一个或后一个结点，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。
（3）线性链表
①定义：线性链表是线性表的链式存储结构。
②特点
a．各数据结点的存储序号是不连续的，各结点在存储空间中的位置关系与逻辑关系也不一致；
b．各数据元素之间的前后件关系是由各结点的指针域来指示的；
c．每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到前件结点，只能顺指针向链尾进行扫描。
为了弥补线性单链表的缺陷，在某些应用中为线性链表每个结点设置两个指针，左指针用以指向其前件结点，右指针指向其后件结点。
（4）带链的栈
带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。
与顺序栈一样，带链栈的基本操作有以下几个：
①栈的初始化：建立一个空栈的顺序存储空间；
②入栈运算：在栈顶位置插入一个新元素；
③退栈运算：取出栈顶元素并赋给一个指定的变量；
④读栈顶元素：将栈顶元素赋给一个指定的变量。
（5）带链的队列
与顺序队列一样，带链队列的基本操作有以下几个：
①队列的初始化：建立一个空队列的顺序存储空间；
②入队运算：在循环队列的队尾加入一个新元素；
③退队运算：在循环队列的排头位置退出一个元素并赋给指定的变量。
【真题演练】
1．下列叙述中正确的是（
）。
[2014年9月真题]
A．所谓有序表是指在顺序存储空间内连续存放的元素序列
B．有序表只能顺序存储在连续的存储空间内
C．有序表可以用链式存储方式存储在不连续的存储空间内
D．任何存储方式的有序表均能采用二分法进行查找
2．线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（
）。
[2014年9月真题]
A．节省存储空间
B．插入与删除运算效率高
C．便于查找
D．排序时减少元素的比较次数
【解析】 线性表的链式存储结构与顺序存储结构的优缺点比较如下：
3．下列叙述中正确的是（
）。
[2013年9月真题]
A．顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的
B．顺序存储结构只针对线性结构，链式存储结构只针对非线性结构
C．顺序存储结构能存储有序表，链式存储结构不能存储有序表
D．链式存储结构比顺序存储结构节省存储空间
（1）常见的线性表的运算
线性链表的运算主要有以下几个：
①在线性链表中包含指定元素的结点之前插入一个新元素；
②在线性链表中删除包含指定元素的结点；
③将两个线性链表按要求合并成一个线性链表；
④将一个线性链表按要求进行分解；
⑤逆转线性链表；
⑥复制线性链表；
⑦线性链表的排序；
⑧线性链表的查找。
（2）在线性链表中查找指定元素
非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法：
从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。
（3）线性链表的插入
①定义：线性链表的插入是指在链式储存结构下的线性表中插入一个新元素。
②插入过程：
在线性链表中包含元素x的结点之前插入一个新元素b。
a．从可利用栈取得一个结点，设该结点号为p，并置结点p的数据域为插入的元素值b。b．在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。
c．最后将结点p插入到结点q之后。为了实现这一步，只要改变以下两个结点的指针域内容：
第一，使结点P指向包含元素x的结点；
第二，使结点q的指针域内容改为指向结点p。
③插入特点：
a．不会发生上溢现象；
b．可方便实现存储空间动态分配；
c．不发生数据元素移动现象，只改变结点指针，提高插入效率。
（4）线性链表的删除
①定义：线性链表的删除是指在链式储存结构下的线性表中删除包含指定元素的结点。
②删除过程：
在线性链表中删除包含元素x的结点。
a．在线性链表中寻找包含元素x的前一个结点，设该结点序号为q；
b．将结点q后的结点p从线性链表中删除，即让结点q的指针指向包含元素x的结点p的指针指向的结点；
c．将包含元素x的结点p送回可利用栈。
在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。
（1）与线性链表相比，循环链表具有的特点：
①在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
②循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。
（2）与线性单链表相比，循环链表具有两方面优点：
①在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。而线性单链表做不到这一点。
②由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。
循环链表的插入与删除运算要比一般单链表简单，不用考虑在空链表和在第一个结点前插入以及空链表的删除等特殊情况，从而实现了空表与非空表运算的统一。
【真题演练】
下列叙述中错误的是（
）。
[2014年3月真题]
A．在双向链表中，可以从任何一个结点开始直接遍历到所有结点
B．在循环链表中，可以从任何一个结点开始直接遍历到所有结点
C．在线性单链表中，可以从任何一个结点开始直接遍历到所有结点
D．在二叉链表中，可以从根结点开始遍历到所有结点
（1）树是一种简单的非线性结构，在这种结构中，所有数据元素之间的关系具有明显的层次特性。在树的图形表示中，上端结点是前件，下端结点是后件。
（2）在树结构中，每个结点只有一个前件（父结点），没有前件的结点只有一个，称为树的根结点。每个结点都可以有多个后件（子结点），没有后件的结点称为叶子结点。
（3）一个结点拥有的后件个数称为该结点的度。某结点的度为n，表示该结点有n个分支，每个分支指向一个后件，除根结点外，每个结点都有一个唯一的分支指向它。树中的结点数为树中所有结点的度之和再加1。
（4）根结点在第1层，同一层上所有结点的所有子结点都在下一层，树的最大层次称为树的深度。
（5）在树中，叶子结点没有子树。
（6）用树来表示算术表达式的原则：
①表达式中的每一个运算符在树中对应一个结点，称为运算符结点；
②运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）；
③运算对象中的单变量均为叶子结点。
在树中，叶子结点没有子树。
【真题演练】
1．下列数据结构中，属于非线性结构的是（
）。
[2013年3月真题]
A．循环队列
B．带链队列
C．二叉树
D．带链栈
2．某二叉树的中序序列为DCBAEFG，后序序列为DCBGFEA，则该二叉树的深度（根节点在第1层）为（
）。
[2015年3月真题]
A．5
B．4
C．3
D．2
（1）二叉树定义
二叉树是一种很有用的非线性结构，与树结构很相似，树结构的所有术语都可以用到叉树这种数据结构上。
（2）二叉树的两个特点
①非空二叉树只有一个根结点；
②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
（3）二叉树的基本性质
①在二叉树的第k层上，最多有2 k-1 （k≥1）个结点。
②深度为m的二叉树最多有2 m -1个结点。
③在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
④具有n个结点的二叉树，其深度至少为[log 2 n]＋1，其中[[log 2 n]表示取log 2 n的整数部分。
（4）满二叉树与完全二叉树
满二叉树与完全二叉树是两种特殊形态的二叉树。
①满二叉树
除最后一层外，每一层上的所有结点都有两个子结点。
②完全二叉树
a．除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
b．更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。
对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为P，则其左分支下的子孙结点的最大层次或为P，或为p＋1。
c．满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。
完全二叉树具有以下两个性质：
a．具有n个结点的完全二叉树的深度为[log 2 n]＋1。
b．设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k＝1，2，…，n）的结点有以下结论：
第一，若k＝1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT（k/2）。
第二，若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。
第三，若2k＋1≤n，则编号为k的结点的右子结点编号为2k＋1；否则该结点无右子结点。
根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左子结点和右子结点的位置。
【真题演练】
1．某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为（
）。
[2014年3月真题]
A．5
B．4
C．3
D．2
2．某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为（
）。
[2014年9月真题]
A．32
B．46
C．48
D．49
3．某二叉树中共有935个结点，其中叶子结点有435个，则该二叉树中度为2的结点个数为（
）。
[2014年3月真题]
A．64
B．66
C．436
D．434
4．深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为（
）。
[2014年9月真题]
A．62
B．63
C．64
D．65
（1）在计算机中，二叉树采用链式存储结构。
（2）用于存储二叉树中各元素的存储结点由两部分组成：
①数据域
②指针域
a．左指针：用于指向该结点的左子结点的存储地址；
b．右指针：指向该结点的右指结点的存储地址。
【真题演练】
下列叙述中正确的是（
）。
[2014年9月真题]
A．结点中具有两个指针域的链表一定是二叉链表
B．结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C．二叉树只能采用链式存储结构
D．循环链表是非线性结构
二叉树的遍历是指不重复地访问二叉树中的所有结点。在遍历二叉树结点中遵循先左后右的原则。二叉树的遍历可分为三种：
（1）前序遍历（DLR）
在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。该过程是一个递归的过程。
（2）中序遍历（LDR）
在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。
（3）后序遍历（LRD）
在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。因此，后序遍历二叉树的过程也是一个递归的过程。
如果知道了某二叉树的前序序列和中序序列，则可以唯一地恢复该二叉树，如果知道了某二叉树的后序序列和中序序列，则也可以唯一地恢复该二叉树。但如果只知道某二叉树的前序序列和后序序列，是不能唯一恢复该二叉树的。
【真题演练】
1．设二叉树如下：
则后序遍历为（
）。
[2014年9月真题]
A．ABDEGCFH
B．DBGEAFHC
C．DGEBHFCA
D．ABCDEFGH
2．某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为（
）。
[2014年9月真题]
A．BADC
B．DCBA
C．CDAB
D．ABCD
（1）基本方法
从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。
（2）以下两种情况只能采用顺序查找：
①线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。
②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
（3）顺序查找的缺陷：效率太低
（1）适用范围
只适用于顺序存储的有序表，在此所说的有序表是指线性表中元素按值非递减排列。
（2）具体方法
设有序线性表的长度为n，被查元素为x，则：
①将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束；
②若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找
③若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找
④这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。
【真题演练】
在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（
）。
[2013年9月真题]
A．O（n）
B．O（n 2 ）
C．O（log 2 n）
D．O（nlog 2 n）
【解析】 在最坏情况下，对于长度为n的有序线性表，二分法查找只需要比较log 2 n次。
（1）冒泡排序法
①定义：冒泡排序法是一种最简单的交换类排序方法，通过相邻数据元素的交换逐步将线性表变成有序。
②基本过程：
a．从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。
b．从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。
c．对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。
③在上述排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头。冒泡排序由此而得名，且冒泡排序又称下沉排序。
假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n（n-1）/2。
（2）快速排序法
①基本思想
从线性表中选取一个元素T，将线性表后面小于T的元素移到前面，前面大于T的元素移到后面，这样就以T为分割线将线性表分割成前后两个子表。再将得到的子表按照这个过程继续下去，直到所有子表为空为止。
②快速排序在最坏情况下需要进行n（n-1）/2次比较，但实际的排序效率要比冒泡排序高得多。
（1）简单插入排序法
①定义:所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。
②插入过程：
将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。
③这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n（n-1）/2次比较。
（2）希尔排序法
①基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。
②子序列的分割方法：
将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般取ht＝n/2 k （k＝1，2，…，[log 2 n]，其中n为待排序序列的长度。
③如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为0（n 1.5 ）。
【真题演练】
在最坏情况下（
）。
[2015年3月真题]
A．快速排序的时间复杂度比冒泡排序的时间复杂度要小
B．快速排序的时间复杂度比希尔排序的时间复杂度要小
C．希尔排序的时间复杂度比直接插入排序的时间复杂度要小
D．快速排序的时间复杂度与希尔排序的时间复杂度是一样的
（1）简单选择排序法
①基本思想：
扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。
②简单选择排序法在最坏情况下需要比较n（n-1）/2次。
（2）堆排序法
①堆的定义
具有n个元素的序列（h 1 ，h 2 ，…，h n ），当且仅当满足
（i＝1，2，…，n/2）时称之为堆。
②堆排序的方法：
a．将一个无序序列建成堆；
b．将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）；
c．反复做上一步，直到剩下的子序列为空为止。
③在最坏情况下，堆排序需要比较的次数为0（nlog 2 n）。
【真题演练】
1．下列各序列中不是堆的是（
）。
[2014年9月真题]
A．（91，85，53，36，47，30，24，12）
B．（91，85，53，47，36，30，24，12）
C．（47，91，53，85，30，12，24，36）
D．（91，85，53，47，30，12，24，36）
2．对长度为n的线性表排序，在最坏情况下，比较次数不是n（n-1）/2的排序方法是（
）。
[2013年9月真题]
A．快速排序
B．冒泡排序
C．直接插入排序
D．堆排序
【解析】 在最坏情况下，快速排序、冒泡排序、直接插入排序与简单选择排序法均需要比较n（n-1）/2次。堆排序需要比较的次数最少，为nlog 2 n。
3．堆排序最坏情况下的时间复杂度为（
）。
[2014年9月真题]
A．O（n15）
B．O（nlog 2 n）
C．
D．O（log 2 n）
【解析】 堆排序是指利用堆积树这种数据结构所设计的一种排序算法，属于选择排序。在对长度为n的线性表排序时，最坏情况下，冒泡排序、快速排序、直接插入排序的时间复杂度均为O（n 2 ），而堆排序时间复杂度为O（nlog 2 n），复杂度最小。