历。
a.前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树。 b.中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。 c.后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。
F 1 5 F C 2 E 6 2 C G 7 6 E F 9 C 4 8 G E 8 A 3 D 4 1 A 4 D A 1 D 3 G 7 H 5 B 5 H 8 P 9 3 B 7 H 9 P B 2 P 6 前序：FCADBEGHP 中序：ACBDFEHGP 后序：ABDCHPGEF
注意：在树结构中，每一个结点都代表一棵子树。前序遍历中一定以根结点开头，后序遍历一定以根结点结尾， 而中序遍历中，根结点前面的为树的左子树，而其后面的为树的右子树。
历届的考题：
1、在深度为 7 的满二叉树中，叶子结点的个数为()[2006.4]
A)32 B)31 C)64 D)63 2、对下图 1 所示二叉树
图 1 图 2 进行中序遍历的结果是________。[2006.9]
A)ACBDFEG B)ACBDFGE C)ABDCGEF D)FCADBEG
3、对如下图 2 所示二叉树，进行后序遍历的结果为()[2006.4]
A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA
4、某二叉树中，度为 2 的结点有 18 个，则该二叉树中有___个叶子结点。[2005.4] 5、一棵二叉树第六层（根结点为第一层）的结点数最多为____个。[2005.9]
1.7 查找技术
7.1 顺序查找：
顺序查找的方法是：用被查元素与线性表中的元素逐一比较， 直到找出相等的元素， 则查找成功；或者找遍
所有元素都不相等，则查找失败。
顺序查找的优点： 对线性表的元素的逻辑次序无要求 （不必对元素进行排序） ， 对线性表的存储结构无要求(顺
序存储、链接存储皆可)。
顺序查找的效率很低，但在以下情况下，只能采用顺序查找：
a.如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。 b.即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 7.2 二分法查找：
第7页，共 26 页
二分法查找是一种效率较高的线性表查找方法。要进行二分法查找， 则线性表结点必须是排好序的， 且线性
表以顺序方式存储。
二分法查找的方法：首先用要查找的元素值与线性表中间位置的元素值相比较， 这个中间结点把线性表分成
了两个子表， 比较相等则查找完成， 不等则根据比较结果确定下一步的查找应在哪一个子表中进行， 如此进行下
去，直到找到满足条件的结点，或者确定表中没有这样的结点。
对于二分法查找的缺点是线性表排序需花费时间，顺序方式存储的插入、删除不便。
注意：对于长度为 n 的有序线性表，在最坏的情况下，二分查找只需要比较比较[log2n] 次，而顺序查找需
要比较 n 次。二分查找的效率要比顺序查找高得多。
历届的考题：
1、在长度为 64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为(____)[2006.9]
A)63 B)64 C)6 D)7 2、下列数据结构中，能用二分法进行查找的是(_____)[2005.9] A)顺序存储的有序线性表 B)线性链表 C)二叉链表 D)有序线性链表
3、对长度为 n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为(____)[2005.4]
A)log2n
B) n/2 C) n D) n+1
1.8 排序技术(记住每种排序的比较次数)
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。 8.1 交换类排序法
交换类排序的基本思想:两两比较待排序线性表的元素值 ,并对不满足顺序要求的元素进行位置交换 ,直到全 部满足为止. 1、冒泡排序法
将相邻的元素进行两两比较， 若为逆序则进行交换。 将线性表照此方法从头到尾处理一遍称作一趟起泡，一
趟起泡的效果是将元素值最大的记录交换到了最后的位置， 即该线性表的最终位置。 若某一趟起泡过程中没有发
生任何交换，则排序过程结束。
在最坏情况下，需要的比较 N(N-1)/2 次。 2、快速排序法
快速排序又称分区交换排序，是对冒泡排序的一种改进。其基本方法是：在待排序线性表中任取一个元素， 以它为基准用交换的方法将所
有的元素分成两部分， 元素值比它小的在一个部分， 元素值比它大的在另一个部分。 再分别对两个部分实施上述
过程，一直重复到排序完成。
在最坏的情况下与冒泡排序相当，然而快速排序的平均执行时间为O(nlog2n)。 8.2 插入类排序法
插入排序的基本思想是：每步将一个待排序元素按其元素值的大小插入到前面已排序的元素中的适当位置 上，直到全部记录插入完为止。 1、简单插入排序
它是指将无序序列中的各元素依次插入到已经有序的线性表中。 在最坏情况下比较需要 N(N-1)/2 次。 2、希尔排序法
希尔排序的基本思想是把元素按下标的一定增量分组， 对每组元素使用插入排序， 随增量的逐渐减小， 所分 成的组包含的记录越来越多， 到增量的值减小到1 时， 整个数据合成一组， 构成一组有序元素，故其属于插入排
序方法。
在最坏情况下需要的比较 O(n1.5)次。 8.3 选择类排序法
选择排序的基本思想是： 每次从待排序的元素中选出元素值最小 （或最大） 的记录，顺序放在已排序的记录
第8页，共 26 页
序列的最后，直到全部排完。 1、简单选择排序
对线性表进行 n-1 趟扫描，第 i 趟扫描从剩下的 n-i+1 个记录中选出元素值最小的记录，与第i 个记录交换。
最坏情况下需要比较 N(N-1)/2 次。 2、堆排序
堆排序的基本思想是：对待排序的线性表，首先把它们按堆的定义排成一个序列（称为建堆） ，这就找到了 最小的元素，然后将最小的元素取出，用剩下的元素再建堆，便得到次最小的的元素，如此反复进行，直到将全 部元素排好序为止。
在最坏怀况下需要比较 O(nlog2n)次。 8.4 总结
假设线性表的长度为 n，在最坏的情况下进行比较的次数： 1、交换类排序法 1、冒泡排序法: n(n-1)/2 2、快速排序法: n(n-1)/2 3、简单插入排序法: n(n-1)/2 4、希尔排序法: O(n1.5) 5、简单选择排序法: n(n-1)/2 2、插入类排序法 3、选择类排序法
6、堆排序法: O(nlog2n) 历届的考题：
1、对于长度为 n 的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是(_)[2005.4]
A）冒泡排序为 n/2 B）冒泡排序为 n C）快速排序为 n D）快速排序为 n(n-1)/2 2、对长度为 10 的线性表进行冒泡排序，最坏情况下需要比较的次数为_____。[2006.4] 总复习图：
定义：是指解题方案的准确而完整的描述
算 特征：是可行性、 确定性、 有穷性和拥有足够 法
的情报
复杂度：包括时间复杂度和空间复杂度
数
据 结 构 与 算 法
线性结构
数据的逻辑结构 数 据 结 构 非线性结构
顺序存储：栈与队列 链式存储： 链表、双向 链表、带链的栈、带链 的队列
数据的存储结构
顺序存储 链式存储
排序：交换类、插入类和选择类 查找：顺序查找、二分查找 插入与删除
数据的运算
1.9 精典模拟题
一．选择题
1.算法的时间复杂度是指______。
B.算法程序的长度 A.执行算法程序所需要的时间
C.算法执行过程中所需要的基本运算次数 D.算法程序中的指令条数 2.算法的空间复杂度是指______。 A.算法程序的长度 B.算法程序中的指令条数