全国计算机等级考试二级公共基础知识1

1、计算机二级考试公共基础之计算机二级考试公共基础之数据结构与算法数据结构与算法14 算法与算法分析算法与算法分析算法与算法分析一一 算法的概念算法的概念 算法是对特定问题求解步骤的一种描述算法是对特定问题求解步骤的一种描述 算法的基本特征：算法的基本特征：1 1）可行性可行性：组成算法的操作必须能够在计算机上实现。：组成算法的操作必须能够在计算机上实现。2 2）确定性确定性：算法的每一步操作必须清晰无二义性。：算法的每一步操作必须清晰无二义性。3 3）有穷性有穷性：算法必须在有限步内结束；：算法必须在有限步内结束；4 4）有足够的情报有足够的情报：0 0个或多个输入；个或多个输入；1 1个或多个

2、输出；个或多个输出； 算法描述的方法很多，如自然语言、框图、类算法描述的方法很多，如自然语言、框图、类C C等等例例: : 求两个正整数求两个正整数 m m，n n 中的最大数中的最大数MAXMAX的算法的算法 （1 1）若若 m n m n 则则 max=mmax=m （2 2）若若 m = n m = n 则则 max=nmax=n 程序程序=算法算法+数据结构数据结构1、正确性正确性： (1) 没有语法错误； (2) 对于几组输入数据能够得出满足要求的结果； (3) 对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果。 (4) 对于一切合法的输入数据都能产生满足要求的结果。 2

3、、可读性：可读性：便于阅读、理解、调试、修改；3、健壮性：健壮性：对不合法的输入能作出正确的反映与处理；4、高效性：高效性：执行时间短（时间复杂度时间复杂度）、 需求存储空间省（空间复杂度空间复杂度）评价算法标准评价算法标准1 时间复杂度时间复杂度T（n） 以求解问题的基本操作的以求解问题的基本操作的执行次数执行次数作为算法时间的度量。作为算法时间的度量。算法与算法分析算法与算法分析O（n3） 称为矩阵相乘算法时间复杂度；称为矩阵相乘算法时间复杂度；O（n3）表示矩阵相乘算法执行时间与）表示矩阵相乘算法执行时间与n3成正比成正比, 即即O（n3）与）与n3 同一数量级；同一数量级； 例：例：n

4、 阶矩阵相乘的算法阶矩阵相乘的算法For ( i = 1; i=n; i+ ) For (j = 1; j=n; j+ ) c i j = 0 ; For (k = 1; k= n; k+ ) c i j += a i k * b k j 乘法乘法 加法加法执行次数均为执行次数均为 n3 矩阵相乘的基本运算：乘法矩阵相乘的基本运算：乘法 加法；加法；数据结构中常用的时间复杂度频率计数有数据结构中常用的时间复杂度频率计数有7个：个： O(1) 常数型常数型 O(n)线性型线性型 O(n2)平方型平方型 O(n3)立方型立方型 O(2n)指数型指数型 O(log2n)对数型对数型 O(nlog2n

5、)二维型二维型2 算法空间复杂度算法空间复杂度 用执行算法所需的用执行算法所需的内存空间的大小内存空间的大小作为算法所需空间的度量。作为算法所需空间的度量。 设执行算法所需的内存空间是问题规模设执行算法所需的内存空间是问题规模n的某个函数的某个函数g(n),则算法空间复杂则算法空间复杂度记作：度记作： S（n）= O(g(n)表示算法内存空间的增长率表示算法内存空间的增长率与与g(n) 的增长率相同的增长率相同例计算例计算 解法解法1 先计算先计算x 的幂的幂, 存于存于power 中中,再分别乘以相应的系数再分别乘以相应的系数 # define N 100 float evaluate (f

6、loat coef , float x , int n ) float powerN, f; int i; for (power 0=1, i = 1; i=n; i+ ) poweri=x*poweri-1; for (f = 0, i=0; ideta=a; q-next=p- next; p- next =q;headheadzyxp pyxzp pheadheada q q插入操作功能：在线性链表的第插入操作功能：在线性链表的第i个元素结点之前插入一个个元素结点之前插入一个新元素结点新元素结点e； 插入操作图示：插入前插入后 ai-1aia2a1ai+1nanheadheadai-1a

7、ia2a1ai+1naneheadhead 4）删除结点删除结点q=p-next; p- next =q- next; free(q);headheadzyxq qyxzq qheadheadp pp p删除前删除后ai-1aia2a1ai+1nanheadheadai-1aia2a1ai+1nanheadp pp pq qq q线性链表小结线性链表小结线性链表是线性表的一种链式存储结构 线性链表的特点 1 通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系； 2 插入、删除操作通过修改结点的指针实现； 3 不能随机存取元素；1 循环链表的概念循环链表的概念 循环链表的特点是将线性链

8、表的最后一个结点的指循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点（首尾相连的单链表）针指向链表的第一个结点（首尾相连的单链表）2 循环链表图示循环链表图示循环链表循环链表(a)非空表 （b）空表headheadheadheada1an循环链表循环链表说明在解决某些实际问题时循环链表可能要比线性链表在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；方便些。如将一个链表链在另一个链表的后面； 对循环链表，有时不给出头指针，而是给出尾指针对循环链表，有时不给出头指针，而是给出尾指针a aa1ana-next给出尾指针的循环链表双向链表双向链表

9、 循环单链表，虽然从任一结点出发沿着指针链能找到其前循环单链表，虽然从任一结点出发沿着指针链能找到其前件，但时间耗费是件，但时间耗费是O(n) 。如果希望从表中快速确定某一个结点。如果希望从表中快速确定某一个结点的前件，另一个解决方法是在链表的每个结点里再增加一个指的前件，另一个解决方法是在链表的每个结点里再增加一个指向其前件的指针域向其前件的指针域prior。 这样形成的链表中就有两条方向不这样形成的链表中就有两条方向不同的链，称为双向链表。同的链，称为双向链表。线性表小结线性表小结 线性表的顺序存储结构线性表的顺序存储结构顺序表，顺序表， 链式存储结构链式存储结构-线性链表线性链表,循环链

10、表循环链表, 双向链双向链表表.不同的存储结构，线性表的同一操作的算不同的存储结构，线性表的同一操作的算法是不同的法是不同的:在顺序存储结构下，线性表的插入、删除在顺序存储结构下，线性表的插入、删除操作，通过移动元素实现操作，通过移动元素实现;在线性链表存储结构下，线性表的插入、在线性链表存储结构下，线性表的插入、删除操作，通过修改指针实现。删除操作，通过修改指针实现。2 栈栈 栈是限定仅能在表尾一端进行插入、删除操作栈是限定仅能在表尾一端进行插入、删除操作的线性表的线性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入删除2.1栈的概念栈的概念一一 什么是栈什么

11、是栈?将表中允许进行插入、删除操作的一端称为将表中允许进行插入、删除操作的一端称为栈顶栈顶(Top)，栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。表的另一端称为栈底表的另一端称为栈底(Bottom)。当栈中没有元素时称为空栈。当栈中没有元素时称为空栈。栈的插入操作称为栈的插入操作称为进栈或入栈进栈或入栈，删除操作称为，删除操作称为出栈或退栈出栈或退栈。 栈栈 ana2a1进栈出栈栈顶栈底进栈出栈(a) 栈的示意图(b) 铁路调序栈的表示栈的示意图栈的示意图出栈出栈进栈进栈栈的特点栈的特点后进先出后进先出第一个进栈的元素在栈底，第一

12、个进栈的元素在栈底，最后一个进栈的元素在栈顶，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素最后一个出栈的元素为栈底元素栈栈顶顶栈栈底底ana2a1 小小 结结 1 栈是限定仅能在表尾一端进行插入、栈是限定仅能在表尾一端进行插入、 删除操作的线性表；删除操作的线性表； 2 栈的元素具有后进先出的特点；栈的元素具有后进先出的特点； 3 栈顶元素的位置由一个称为栈顶指针的栈顶元素的位置由一个称为栈顶指针的 变量指示，变量指示， 进栈、出栈操作要修改栈顶指针；进栈、出栈操作要修改栈顶指针； 2 栈栈3 队列队列3.1 队列的概念队列的概

13、念一一 什么是队列什么是队列队列是限定仅能在表头进行删除，表尾进行插入的线性表队列是限定仅能在表头进行删除，表尾进行插入的线性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入插入删除删除3 队列队列 a a1 1 a a2 2 a a3 3 a an n入队列入队列队队头头队队尾尾出队列出队列队队 列列 的的 示示 意意 图图队列的特点队列的特点先进先出先进先出第一个入队的元素在队头，第一个入队的元素在队头，最后一个入队的元素在队尾，最后一个入队的元素在队尾，第一个出队的元素为队头元素，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素最后一个出队的元素为

14、队尾元素rearrearfrontfrontJ1rearrearfrontfrontJ2（a)a)空队列空队列(b)J1,J2(b)J1,J2相继相继入队列入队列(c)J1(c)J1出队出队(d)J3,J4, J5(d)J3,J4, J5和和J6J6相继入队之后相继入队之后,J2,J2出队出队rearrearfrontfront0 01 12 23 34 45 5rearrearfrontfrontJ5J4J3front,rearfront,rear为整为整数数 又有又有J7入队入队, 怎么办？怎么办？J2J63 . 循环队列循环队列frontfrontrearJ6J6J4J4J5J53 12

15、4 05rearrear54 03 12frontfrontJ6J6J7J7J8J8J9J9J4J4J5J5frontfrontrearrear54 03 12(b)(b)队空队空(a)(a)队满队满J7J7rearrear判分队空、队满方法：判分队空、队满方法：1）另设一个标志）另设一个标志S以区分队空、队满。以区分队空、队满。2）S=0 队空：队空： front=rear; S=1 队满：队满： front=rear;或少用一个空间或少用一个空间Real+1=front 为满为满frontfront54 03 12J6J6J7J7J8J8J4J4J5J5（c c）rearrear入队操作入

16、队操作 ：将元素将元素 x 插入队尾插入队尾 frontfrontrearrear54 03 12J1J1J3J3J2J2x xfrontfrontrearrear54 03 12J1J1J3J3J2J2元素元素 x x 入队前入队前元素元素 x x 入队后入队后出队操作出队操作 ：删除队头：删除队头元素；元素； frontfrontrearrear54 03 12J1J1J3J3J2J2出队操作前出队操作前frontfrontrearrear54 03 12J1J1J3J3J2J2出队操作后出队操作后 小小 结结 1 队列是限定仅能在表尾一端进行插入，表头队列是限定仅能在表尾一端进行插入，表

17、头一端删除一端删除 操作的线性表；操作的线性表； 2 队列中的元素具有先进先出的特点；队列中的元素具有先进先出的特点； 3 队头、队尾元素的位置分别由称为队头指针队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示，和队尾指针的变量指示， 4 入队操作要修改队尾指针，出队操作要修改入队操作要修改队尾指针，出队操作要修改队头指针；队头指针； 数据存储结构方面的考题数据存储结构方面的考题 1：数据的存储结构是指：数据的存储结构是指 （ ）。）。A) 存储在外存中的数据存储在外存中的数据 B) 数据所占的存储空间量数据所占的存储空间量C) 数据在计算机中的顺序存储方式数据在计算机中的顺序存储方

18、式 D) 数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示2. 下列叙述中正确的是下列叙述中正确的是 （ ）。）。 A）栈是）栈是“先进先出先进先出”的线性表的线性表 B）队列是）队列是“先进后出先进后出”的线性表的线性表 C）循环队列是非线性结构）循环队列是非线性结构 D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 3. 数据结构分为线性结构和非线性结构，带链的队列属于（数据结构分为线性结构和非线性结构，带链的队列属于（ ）。）。4. 下列数据结构中，属于非线性结构的是（下列数据结构中，属于非线性结构的是（

19、）。）。A）循环队列）循环队列 B) 带链队列带链队列C) 二叉树二叉树 D）带链栈）带链栈答案：答案：D。答案：答案：D。答案：线性结构。答案：线性结构。答案：答案：c5.下列叙述中正确的是（下列叙述中正确的是（ ）。）。 A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表）顺序存储结构能存储有序表，链式存储结构不能存储有序表

20、 D）链式存储结构比顺序存储结构节省存储空间）链式存储结构比顺序存储结构节省存储空间答案：答案：A。6.6.下列关于栈的叙述正确的是下列关于栈的叙述正确的是 （ ） A A）栈按）栈按“先进先出先进先出”组织数据组织数据 B)B)栈按栈按“先进后出先进后出”组织数据组织数据 C C）只能在栈底插入数据）只能在栈底插入数据 D D）不能删除数据）不能删除数据 答案：答案：B。7. 一个队列的初始状态为空。现将元素一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，则元素退队的顺序为依次入队，然后再依次退队，则元素退队的顺序为 【1】 。（。（ ）

21、答案：答案：A，B，C，D，E，F，5，4，3，2，19. 设某循环队列的容量为设某循环队列的容量为50，如果头指针，如果头指针front=45(指向队头元素的前一指向队头元素的前一位置位置)，尾指针，尾指针rear=10(指向队尾元素指向队尾元素)，则该循环队列中共有，则该循环队列中共有 【2】 个个元素。元素。 （ ） 8.假设用一个长度为假设用一个长度为50的数组（数组元索的下标从的数组（数组元索的下标从0到到49）作为栈的存）作为栈的存储空间，栈底指针储空间，栈底指针bottom指间栈底元素，栈顶指针指间栈底元素，栈顶指针top指向栈顶元素，指向栈顶元素，如果如果bottom=49，t

22、op=30（数组下标），则栈中具有（数组下标），则栈中具有【 】个元素。个元素。 （2009年年3月）月） 答案：答案：19答案：答案：154 树和二叉树 1树的定义树的定义 树是树是n个结点的有限集合个结点的有限集合T，当，当n=0时，称为空树；当时，称为空树；当n0时，时，T满足如下条件：在任一棵非空树中：满足如下条件：在任一棵非空树中：（1）有且仅有一个称为根的结点。）有且仅有一个称为根的结点。（2）其余结点可分为）其余结点可分为M个互不相交的子集合，而且这些子集个互不相交的子集合，而且这些子集中的每一个本身又是一棵树，也称为根的子树。中的每一个本身又是一棵树，也称为根的子树。J JI

23、IA AC CB BD DH HG GF FE EK KL LM M2树的实例树的实例树可表示具有分枝结构关系的对象树可表示具有分枝结构关系的对象例例1家族族谱家族族谱 设某家庭有设某家庭有13个成员个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可用树表示：，他们之间的关系可用树表示：J JI IA AC CB BD DH HG GF FE EK KL LM M计算机中树是常用的数据组织形式计算机中树是常用的数据组织形式 尽管有些应用中数据元素之间并不存在分支结构关系，但尽管有些应用中数据元素之间并不存在分支结构关系，但为了便于管理和使用数据，将它们用树的形式来组织。

24、为了便于管理和使用数据，将它们用树的形式来组织。例例2 计算机的文件系统计算机的文件系统 不论是不论是DOS文件系统还是文件系统还是window文件系统，所有的文件都是用文件系统，所有的文件都是用树的形式来组织的。树的形式来组织的。文件夹文件夹1 1 文件夹文件夹n n 文件文件1 1 文件文件2 2文件夹文件夹11 11 文件夹文件夹12 12 文件文件11 11 文件文件1212C C盘盘3、树的、树的 基本术语基本术语 树的结点：包含一个数据元素及若干指树的结点：包含一个数据元素及若干指向子树的分支；向子树的分支；孩子结点：结点的子树的根称为该结点孩子结点：结点的子树的根称为该结点的孩子

25、，的孩子， B、C是是A的孩子；的孩子；双亲结点：双亲结点：B 结点是结点是A 结点的孩子，则结点的孩子，则A结点是结点是B 结点的双亲；结点的双亲；兄弟结点：同一双亲的孩子结点，兄弟结点：同一双亲的孩子结点， H、I、 J互为兄弟；互为兄弟；堂兄结点堂兄结点：同一层上结点，同一层上结点， E E、F F、G G、H H、I I、J J、互为堂兄弟；互为堂兄弟；J JI IA AC CB BD DH HG GF FE EK KL LM M3、树的、树的 基本术语基本术语结点的层次：根结点的层次定义为结点的层次：根结点的层次定义为1；根的孩子为第；根的孩子为第二层，依此类推；二层，依此类推；树的

26、深度：树的深度：树中所有结点的层次的最大值树中所有结点的层次的最大值结点的度：结点的度：结点子树的个数结点子树的个数树的度：树的度： 树中结点度的最大值。树中结点度的最大值。叶子结点叶子结点：度为：度为 0 的结点；的结点；分枝结点：分枝结点：度不为度不为0的结点；的结点；J JI IA AC CB BD DH HG GF FE EK KL LM M一一 二叉树的概念二叉树的概念1 1 二叉树的定义二叉树的定义二叉树：二叉树： 或为空树，或由根及两颗互不相交的左子树、或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。右子树构成，并且左、右子树本身也是二叉树。 A

27、 A F F G G E E D D C C B B一一 二叉树的概念二叉树的概念二叉树说明说明1 1）二叉树中每个结点最多有两个子树；）二叉树中每个结点最多有两个子树；既：二叉树每个结点度小于等于既：二叉树每个结点度小于等于2;2;2 2）左、右子树不能颠倒）左、右子树不能颠倒有序树有序树; ;3 3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念概念; ; (a)(a)、(b)(b)是不同的二叉树，是不同的二叉树， (a)(a)的左子树有四个结点的左子树有四个结点，(b)(b)的左子树有两个结点的左子树有两个结点(a)(b) G

28、G E E D D C C B B A A F F G G E E D D C C B B F FA A 2 二叉树的基本形态二叉树的基本形态(a)空树(b)只有根(c) 右子树空(e) 左子树空(d) 左、右子树非空二、二、 二叉树的性质二叉树的性质 性质性质1: 在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点个结点(i1)。 性质性质2: 深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点（个结点（k1）。）。 性质性质3: 对任意一棵二叉树对任意一棵二叉树T，若叶结点数为，若叶结点数为n0，而其度为，而其度为2的结的结点数为点数为n2，则，则n0=n2+1。两种特殊的

29、二叉树两种特殊的二叉树满二叉树：深度为满二叉树：深度为k k的二叉树，如有的二叉树，如有2 2k k-1-1个结点则称为满二叉树；个结点则称为满二叉树； A A G G F F E E D D C C B B A A C C B BK=3的满二叉树K=2的满二叉树满二叉树的顺序表示：满二叉树的顺序表示： 从二叉树的根开始，从二叉树的根开始， 从上到下，从上到下， 从左到右，逐层进行编号（从左到右，逐层进行编号（1， 2， ， n）。例如图（）。例如图（a）所示的满二叉树的顺序表示为）所示的满二叉树的顺序表示为:(1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11， 12， 13

30、， 14， 15)。 891011 1213452136714158910111213452136714(a) 满二叉树(b) 完全二叉树 完全二叉树：完全二叉树： 深度为深度为k，结点数为，结点数为n的二叉树，如果其结点的二叉树，如果其结点1n的位置序号分别与满二叉树的结点的位置序号分别与满二叉树的结点1n的位置序号的位置序号一一对应，则为完全二叉树，一一对应，则为完全二叉树， 如上图如上图 (b)所示。所示。 满二叉树必为完全二叉树，满二叉树必为完全二叉树， 而完全二叉树不一而完全二叉树不一定是满二叉树。定是满二叉树。 性质性质4：具有：具有n个结点的完全二叉树的深度个结点的完全二叉树的深

31、度为为log2n+1。 性质性质5: 对于有对于有n个结点的完全二叉树，个结点的完全二叉树， 按照从上到下、从按照从上到下、从左到右的顺序对二叉树中的所有结点从左到右的顺序对二叉树中的所有结点从1开始顺序编号，开始顺序编号， 则对则对于任意的序号为于任意的序号为i的结点有：的结点有： （1） 如如i=1，则序号为，则序号为i的结点是根结点，的结点是根结点， 无双亲结点；无双亲结点； 如如i1， 则序号为则序号为i的结点的双亲结点序号为的结点的双亲结点序号为i/2 （下取整） （2） 如如2in，则序号为，则序号为i的结点无左孩子；如的结点无左孩子；如2in，则序号，则序号为为i的结点的左孩子结

32、点的序号为的结点的左孩子结点的序号为2i。 （3） 如如2i1n，则序号为，则序号为i的结点无右孩子；如的结点无右孩子；如2i1n， 则序号为则序号为i的结点的右孩子结点的序号为的结点的右孩子结点的序号为2i1。 二叉树二叉树存储结构存储结构-二叉链表二叉链表 二叉链表中每个结点包含三个域：数据域、左指针域、右二叉链表中每个结点包含三个域：数据域、左指针域、右指针域指针域 A A F F E E D D C C B B二叉链表图示二叉链表图示 D D A A B B C C E E F F 若一个二叉树含有若一个二叉树含有n个结点，则它的二叉链表中必含有个结点，则它的二叉链表中必含有2n个指针

33、域，个指针域， 其中必有其中必有n+1个空的指针域。个空的指针域。 二、二叉树的遍历（必考）二、二叉树的遍历（必考）遍历遍历：按某种顺序访问二叉树的每个结点，而且每个结点仅被按某种顺序访问二叉树的每个结点，而且每个结点仅被访问一次。访问一次。访问：含义很广，可以是对结点的各种处理含义很广，可以是对结点的各种处理，如修改结点数据，如修改结点数据、输出结点数据。、输出结点数据。 如何访问二叉树的每个结点， 而且每个结点仅被访问一次？二叉树的遍历方法（必考）二叉树的遍历方法（必考） 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：L L：遍历左子树 T

34、：访问根结点 R R：遍历右子树 约定先左后右,有三种遍历方法： T L R L R前序遍历、 L L T R R中序遍历、 L R L R T后序遍历。 A A F F G G E E D D C C B B 先序遍历（T L L R R） 若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树； 先序遍历序列：A, ,B,D,B,D,E E,G,G,C C, ,F F例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按 T L L R R 的顺序遍历左子树 （3）先序遍历右子树：即按 T L L R R 的顺序遍历右子树 A A F F G

35、G E E D D C C B B中序遍历（L L T R R）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树 中序遍历序列： D,B,G,D,B,G,E E, ,A, ,C,FC,F例：中序遍历右图所示的二叉树 （1）中序遍历左子树：即按 L L T R R 的顺序遍历左子树 （2）访问根结点A （3）中序遍历右子树：即按 L L T R R 的顺序遍历右子树 A A F F G G E E D D C C B B后序遍历（L L R R T）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点 后序遍历序列： D,G,D,G,E E,B,B,F,CF,

36、C, ,A例：后序遍历右图所示的二叉树 （1）后序遍历左子树：即按 L L R R T 的顺序遍历左子树 （2）后序遍历右子树：即按 L L R R T 的顺序遍历右子树 （3）访问根结点A A A F F G G E E D D C C B B 后序遍历序列：a,b,c,d,-,a,b,c,d,-,* *,+,+,e,f,/e,f,/, ,-中序遍历序列：a,+,b,a,+,b,* *,c,-,d,c,-,d,-, ,e,/,fe,/,f 例：例：中序遍历、中序遍历、后后序序遍历下图所示的二叉树 e e d d c c b b f f a a + + * * / / - - - -例例:已知

37、一棵二叉树前序遍历和中序遍历分别为已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和和DBGEACHF，则该二叉树，则该二叉树的后序遍历为的后序遍历为? A) GEDHFBCA B) DGEBHFCAC) ABCDEFGH D) ACBFEDHG B二叉树1 1 二叉树：二叉树： 或为空树，或由根及两颗互不相交或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身的左子树、右子树构成，并且左、右子树本身也是二叉树；也是二叉树； 2 2 二叉树可以用链式结构存储；二叉树可以用链式结构存储；遍历：按某种搜索路径访问二叉树的每个结点遍历：按某种搜索路径访问二叉树的每个结点，每个

38、结点仅被访问一次。，每个结点仅被访问一次。 3 3二叉树的遍历可以分解为：访问根，遍历二叉树的遍历可以分解为：访问根，遍历左子左子树和树和遍历遍历右子树，常用的三种遍历算法：右子树，常用的三种遍历算法：先序先序遍历、中序遍历、后序遍历；遍历、中序遍历、后序遍历；5 查找 5.1 查找的基本概念查找的基本概念 查找（列）表：由同一类型的数据元素（或记录）构成的查找（列）表：由同一类型的数据元素（或记录）构成的集合，集合， 可利用任意数据结构实现。可利用任意数据结构实现。 关键字：关键字：数据元素的某个（几个）数据项的值。如果一个数据元素的某个（几个）数据项的值。如果一个数据项可以数据项可以唯一标

39、识列表中的一个数据元素唯一标识列表中的一个数据元素， 则称其为关键则称其为关键字。字。 查找：查找： 根据给定的关键字值，在特定的查找（列）表中根据给定的关键字值，在特定的查找（列）表中确定一个其关键字与给定值相同的数据元素，并返回该数据元确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。素在列表中的位置。若找到相应的数据元素，若找到相应的数据元素， 称查找成功，否则称查找失败称查找成功，否则称查找失败 52 线性表的查找线性表的查找5.2.1 顺序查找顺序查找-最简单的查找方法顺序查找的基本思想顺序查找的基本思想 从表的一端开始，顺序扫描线性表，从表的一端开始，顺序扫描

40、线性表，依次将扫描到的依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。败。 顺序查找既适用于顺序表，也适用于链表。若用顺序表，顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。序的。顺序查找算法的性能。顺序查找算

41、法的性能。假设列表长度为假设列表长度为n，那么查找第，那么查找第i个数据个数据元素时需进行元素时需进行n-i+1次比较，即次比较，即Ci=n-i+1。又假设查找每个数据。又假设查找每个数据元素的概率相等，即元素的概率相等，即Pi=1/n， 则顺序查找算法的平均查找长度则顺序查找算法的平均查找长度为：为： niniiniiininnCnCPASL111) 1(21) 1(11顺序查找的特点顺序查找的特点 顺序查找的顺序查找的优点是算法简单优点是算法简单，对查找表结构无任何，对查找表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结要求，无论是用向量还是用链表来存放结点，也无论结点之间是否

42、按关键字有序或无序排，它都同样适用。点之间是否按关键字有序或无序排，它都同样适用。顺序查找的缺点是顺序查找的缺点是查找效率低查找效率低，当，当 n 较大时，不较大时，不宜采用顺序查找宜采用顺序查找。 5.2.2二分二分查找（折半查找）查找（折半查找）1.二分查找的基本思想二分查找的基本思想高效率的查找方法。要求表中元素按关键字有序高效率的查找方法。要求表中元素按关键字有序(升序或降序升序或降序)。假设表中元素为升序排列。假设表中元素为升序排列。二分查找的基本思想是：二分查找的基本思想是：首先将表首先将表中间位置记录的关键字与查找关键字中间位置记录的关键字与查找关键字比较，比较，如果两者相等，则

43、查找成功；如果两者相等，则查找成功；否则利用中间位置记录否则利用中间位置记录将表分成前、后两个子表，将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，如果中间位置记录的关键字大于查找关键字，则进一步查则进一步查找前一子表，否则进一步查找后一子表。找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。成功，或直到子表不存在为止，此时查找不成功。例如，假设给定有序表中关键字为：例如，假设给定有序表中关键字为：05,13,19,21,37,56,64,74,80,88,9

44、2，查找，查找K=21的情况：的情况： 05 13 19 21 37 56 64 74 80 88 92 low hig (a) 初初始始情情形形 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 74 80 88 92 low hig mid (b) 经经过过一一次次比比较较后后的的情情形形 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 05 13 19 21 37 56 64 74 80 88 92 (c ) 经经过过二二次次比比较较后后的的情情形形 (arraymid.key=19) low mid hi

45、g 图图 6-1 查查找找 K=21 的的示示意意图图 05 13 19 21 37 56 64 74 80 88 92 (d ) 经经过过三三次次比比较较后后的的情情形形 (arraymid.key=21) mid low hig 图图 6-1 查查找找 K=21 的的示示意意图图 (查查找找成成功功) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 103.二分查找的性能分析 二分查找的过程可以用二叉树来描述。把当前查找区间的二分查找的过程可以用二叉树来描述。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子中点作为根结点，左子区间和右

46、子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。得到的二叉树称为二分查找的判定树。例如，给定的关键字序列例如，给定的关键字序列05,13,19,21,37,56,64,74,80,88,92，的判定树。的判定树。 0 1 2 3 4 5 6 7 8 9 10 4 0 3 2 7 6 5 8 9 1 0 图图6 -3 具具 有有11 个个 关关 键键 字字 序序 列列 的的 二二 分分 查查 找找 判判 定定 树树 1 在长度为在长度为n n的有序线性表中进行二分查找。的有序线性表中进行二

47、分查找。最坏的情况下，需要的比较次数为最坏的情况下，需要的比较次数为 loglog2 2n n 6 排序 61 基本概念基本概念 6.1.1 排序定义排序定义 排序就是把一组记录（元素）按照某个域的值的递增或递减的排序就是把一组记录（元素）按照某个域的值的递增或递减的次序重新排列的过程。次序重新排列的过程。(按学号的递增按学号的递增)表7-1 学生档案表学号学号姓名姓名年龄年龄性别性别99001王晓佳王晓佳18男男99002林一鹏林一鹏19男男99003谢宁谢宁17女女99004张丽娟张丽娟18女女99005周涛周涛20男男99006李小燕李小燕16女女为讨论方便，我们直接将排序码写成一个一维

48、数组的形式，并且在没有声明的情形下，所有排序都按排序码的值递增排列。 排序排序 插入排序（直插排序、希尔排序）插入排序（直插排序、希尔排序） 交换排序（冒泡排序、快速排序）交换排序（冒泡排序、快速排序） 选择排序选择排序 （直选排序、堆排序）（直选排序、堆排序） 归并排序（二路归并排序）归并排序（二路归并排序） 62 插入排序插入排序 6.2.1直接插入排序1直接插入排序（Straight Insertion Sorting）基本思想：把基本思想：把n个待排序的元素看成一个有序表和一个无序表，个待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有开始时有序表中只

49、包含一个元素，无序表中包含有n-1个元素，个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。的适当位置，使之成为新的有序表。例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如图7-1所示。 0 1 2 3 4 5 初始状态 (17 ) 3 25 14 20 9 第一次插入 (3 17 ) 25 14 20 9 第二次插入 (3 17 25 ) 14

50、20 9 第三次插入 (3 14 17 25 ) 20 9 第四次插入 (3 14 17 20 25 ) 9 第五次插入 (3 9 14 17 20 25) 图 7-1 直接插入排序示例 3直接插入排序的效率分析直接插入排序的效率分析直接插入排序算法十分简单。直接插入排序算法十分简单。空间空间:只需要一个元素的辅助空间，用于元素的位置交换只需要一个元素的辅助空间，用于元素的位置交换。时间时间:外层循环要进行外层循环要进行n-1次插入，每次插入最少比较一次次插入，每次插入最少比较一次（正序），移动两次；最多比较（正序），移动两次；最多比较i次，移动次，移动i2次（逆序）次（逆序）（i=1，2，n

51、-1）。）。直接插入排序的时间复杂度为直接插入排序的时间复杂度为O（n2）。）。最坏情况比较最坏情况比较n(n-1)/26.2.2希尔排序希尔排序希尔排序希尔排序(缩小增量排序缩小增量排序):1959年由年由D.L.Shell提出来的。提出来的。基本思想：先将整个待排元素序列分割成若干个子序列（由基本思想：先将整个待排元素序列分割成若干个子序列（由 “增量增量”确定）分别进行直接插入排序，待整个序列中的元素确定）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序

52、的情况下（接近最好排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。情况），效率是很高的。例如，n=8，数组array 的八个元素分别为：91，67，35，62，29，72，46，57。下面用图7-2给出希尔排序算法的执行过程。 91 67 35 62 29 72 46 57 初始状态， setp=4 29 57 35 62 46 67 91 72 第二趟结果，step=1 29 35 46 57 62 67 72 91 第三趟结果 29 67 35 57 91 72 46 62 第一趟结果,step=2 图 7-2 希尔排序算法的执行过程 希尔排序的效率分析希尔排序

53、的效率分析与增量有关，与增量有关，最坏情况，希尔排序的时间复杂性在最坏情况，希尔排序的时间复杂性在O（nlog2n）。）。63 交换排序交换排序6.3.1 冒泡排序冒泡排序基本思想:对待排序序列从后向前（从下标较大的元素开始），对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部，就象水底下的气泡一样逐较小的元素逐渐从后部移向前部，就象水底下的气泡一样逐渐向上冒。渐向上冒。例如，例如，n=6，数组，数组R的六个排序码分别为：的六个排序码分别为：17，3，25，14，20

54、，9。下面用图。下面用图7-3给出冒泡排序算法的执行过程。给出冒泡排序算法的执行过程。 图 7-3 冒泡排序示例 0 1 2 3 4 5 第一趟排序 3 (17 9 25 14 20) 第二趟排序 3 9 (17 14 25 20) 第三趟排序 3 9 14 (17 20 25) 第四趟排序 3 9 14 17 20 25 初始状态 （17 3 25 14 20 9) 冒泡排序的效率分析冒泡排序的效率分析若待排序的元素为正序，则只需进行一趟排序，比较次数为若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为）次，移动元素次数为0；若待排序的元素为逆序，则需进行若待排

55、序的元素为逆序，则需进行n-1趟排序，比较次数为趟排序，比较次数为(n2-n)/2，移动次数为，移动次数为3(n2-n )/2，最坏情况比较最坏情况比较n(n-1)/2因此冒泡排序算法的时间复杂度为因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。素移动较多，所以属于内排序中速度较慢的一种。6.3.2 快速排序快速排序基本思想是：取待排序序列中的某个元素（一般第一个元素）基本思想是：取待排序序列中的某个元素（一般第一个元素）作为基准，通过一趟排序，将待排元素分为左右两个子序列，作为基准，通过一趟排序，将待排元素分为左右两个子序列，

56、左子序列元素的排序码均小于或等于基准元素的排序码，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行然后分别对两个子序列继续进行快速快速排序，直至整个序列有序。排序，直至整个序列有序。元素的比较和交换是从两端向中间进行的，排序码较大的元素元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面，排序码较小的记录一次就能够交换到一次就能够交换到后面，排序码较小的记录一次就能够交换到前面，记录每次移动的距离较远，因而总的比较和移动次数较前面，记录每次移动的距离较远，因而总的

57、比较和移动次数较少。少。 例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图7-4所示。 4 6 5 5 1 3 4 2 9 4 0 5 1 7 7 0 i j 4 6 5 5 1 3 4 2 9 4 0 5 1 7 7 0 i j 1 7 5 5 1 3 4 2 9 4 0 5 4 6 7 0 i j 1 7 4 6 1 3 4 2 9 4 0 5 5 5 7 0 i j 1 7 0 5 1 3 4 2 9 4 4 6 5 5 7 0 i j 1 7 0 5 1 3 4 2 9 4 4 6 5 5 7 0 i j 1 7 0 5 1 3 4 2 9 4 4

58、6 5 5 7 0 i j 1 7 0 5 1 3 4 2 4 6 9 4 5 5 7 0 i j 图7 - 4 快 速 排 序 的 一 次 划 分 3快速排序的效率分析快速排序的效率分析若快速排序出现最好的情形（左、右子区间的长度大致相若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数等），则结点数n与二叉树深度与二叉树深度h应满足应满足log2nhlog2n+1 ，所，所以总的比较次数不会超过以总的比较次数不会超过(n+1) log2n。因此，。因此，快速排序的最快速排序的最好时间复杂度应为好时间复杂度应为O（nlog2n）。）。已经证明，快速排序的平均时间复杂度也为O（nl

59、og2n）。若快速排序出现最坏的情形（每次能划分成两个子区间，但若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，总其中一个是空），则这时得到的二叉树是一棵单分枝树，总的比较次数为的比较次数为n(n-1)/2 。因此，。因此，快速排序的最坏时间复杂度为O(n2)。快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。快速排序是一种不稳定的排序方法。 64 选择排序选择排序 6 . 4.1 直接选择排序基本思想基本思想直接选择排序是一种简单的排序方法。基本思想是：第一次直接选择排序是一种简单的排序

60、方法。基本思想是：第一次从从array0arrayn-1中选取最小值，与中选取最小值，与array0交换，第二交换，第二次从次从array1arrayn-1中选取最小值，与中选取最小值，与array1交换，第交换，第三次从三次从array2arrayn-1中选取最小值，与中选取最小值，与array2交交换，换，第，第i次从次从arrayi-1arrayn-1中选取最小值，与中选取最小值，与arrayi-1交换，交换，, 第第n-1次从次从arrayn-2arrayn-1中选取最中选取最小值，与小值，与arrayn-2交换，总共通过交换，总共通过n-1次，得到一个按排序次，得到一个按排序码从小到