二级公共基础知识(数据结构与算法).ppt

全国计算机等级考试全国计算机等级考试二级公共基础知识二级公共基础知识考试形式1、公共基本知识部份只考选择题，没有操作题2、公共基本知识占10分，共10道题，每题1分注意事项注意事项公共基础知识部份的内容是属于计算机专业本科生的专业课，知识点特别散，而且有一定的难度所以考生在学习的过程中，一定要克服畏难情绪，跟上老师的节奏老师让记的，要记住没做要求的，要学会放弃放弃该放弃的，选择轻装上阵放弃该放弃的，选择轻装上阵一、 数据结构与算法 1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）与空间复杂度）2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念的图形表示；线性结构与非线性结构的概念3. 线性表的定义；线性表的顺序存储结构及其插入与删除运线性表的定义；线性表的顺序存储结构及其插入与删除运算4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算栈和队列的定义；栈和队列的顺序存储结构及其基本运算5. 线性单链表、双向链表与循环链表的结构及其基本运算。

线性单链表、双向链表与循环链表的结构及其基本运算6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历序、中序和后序遍历7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，顺序查找与二分法查找算法；基本排序算法（交换类排序，插入类排序，选择类排序）插入类排序，选择类排序） 1.1 算法1.1.1 算法算法(algorithm)基本概念基本概念　　　　　　　　它是指令的有限序列，其中每一条指令表示一个或多个操作它是指令的有限序列，其中每一条指令表示一个或多个操作对解题方案准确而完整的描述称为算法对解题方案准确而完整的描述称为算法对解题方案准确而完整的描述称为算法对解题方案准确而完整的描述称为算法算法算法计算机解题的过程实际上是在实施某种算法，这种算法称为计计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法算机算法算法的基本特征算法的基本特征:(1)有穷性有穷性(2)确定性确定性(3)可行性可行性(4)拥有足够的情报拥有足够的情报（有零个或多个（有零个或多个输入，输入，有一个或多个有一个或多个输出输出））一个算法有零个或多个输入有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身定出了初始条件；一个算法有一个或多个输出有一个或多个输出，以反映对输入数据加工后的结果。

没有输出的算法是毫无意义的；伪代码伪代码:S1:输入圆的半径输入圆的半径R;S2:求面积求面积 ∏R2;S3:输出面积输出面积;例例1:已知圆的半径已知圆的半径,求圆的面积求圆的面积.描述算法的工具通常有传统流程图、描述算法的工具通常有传统流程图、N-S结构化流程结构化流程图、伪代码等图、伪代码等开始开始输入输入R RS=3.14 * R*R输出输出S S结束结束传统流程图传统流程图第8页n算法与计算机程序算法与计算机程序 算法算法——是一组逻辑步骤是一组逻辑步骤 程序程序——用计算机语言描述的算法用计算机语言描述的算法算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计算法是程序设计的核心算法是程序设计的核心算法算法:S1:输入圆的半径输入圆的半径R;S2:求面积求面积∏R2;S3:输出面积输出面积;例题例题:已知圆的半径已知圆的半径,求圆的面积求圆的面积.程序程序#include #define PI 3.14159int main(){    float r, s;      do{          printf("Please input r:");          scanf("%f", &r);          if (r<0) printf("Error！！\n");      }while(r<=0);      s=PI*r*r;      printf("Area=%f\n", s);       return 0;}1.1.2 算法的基本要素算法的基本要素 1、对数据对象的运算和操作、对数据对象的运算和操作n算术运算算术运算n逻辑运算逻辑运算n关系运算关系运算n数据传输数据传输2、算法的控制结构、算法的控制结构n算法中各操作之间的执行顺序算法中各操作之间的执行顺序n一个算法一般可以用一个算法一般可以用顺序、选择、循环顺序、选择、循环3种基本结种基本结构组合而成。

构组合而成算术运算算术运算逻辑运算逻辑运算关系运算关系运算数据传输数据传输顺序、选择、顺序、选择、循环循环3种基种基本结构本结构#include #define PI 3.14159int main(){    float R, S;      do{          printf("Please input R:");          scanf("%f", &R);          if (R<0) printf("Error！！\n");      }while(R<=0);      s=PI*R*R;      printf("Area=%f\n", S);     return 0;}1.1.3 算法设计基本方法算法设计基本方法n列举法列举法n归纳法归纳法n递推递推n递归（以简洁的形式设计和描述算法）递归（以简洁的形式设计和描述算法）n减半递推技术减半递推技术n回溯法回溯法1.2 算法复杂度算法复杂度1.2.1 时间复杂度时间复杂度n是指执行算法所需要的计算工作量是指执行算法所需要的计算工作量n通常有事后统计法和通常有事后统计法和事前分析估算法事前分析估算法。

★★算法的工作量用算法所执行的算法的工作量用算法所执行的基本运算基本运算次数来度量次数来度量.★★算法所执行的基本运算次数与算法所执行的基本运算次数与问题的规模问题的规模n有关（即算有关（即算法所执行的基本次数是问题规模的函数）法所执行的基本次数是问题规模的函数）.执行算法所需要的计算工作量和执行算法所需要的计算工作量和f(n)同步增长，记为同步增长，记为:算法的工作量算法的工作量=f(n)时间复杂度时间复杂度=O(f(n))而对于一个固定的规模，算法所执行的基本次数还与特定的输入有关例子例子4：：for ( i=2;i<=n;++i)                    for   (j=2;j<=i-1;++j)  ++x   ;基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：X增增1i=2      0i=3      1i=4      2…i=n     n-2    1+2+3+…+(n-2)= (n-1)(n-2)/2O（（        ））例子例子2：：++x;O（（  1  ））例子例子3：： for (i=1;i<=n;++i)  ++x;O（（  n  ））时间复杂度：时间复杂度：O((n*n-3n+2)/2)基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：1X增增1基本运算：基本运算：基本运算的执行次数：基本运算的执行次数：时间复杂度：时间复杂度：X增增1n1.2.2 算法的空间复杂度算法的空间复杂度n 一般是指执行这个算法所需要的内存空间一般是指执行这个算法所需要的内存空间n一个算法所占用的内存空间包括一个算法所占用的内存空间包括算法程序算法程序所占所占的空间、的空间、输入的初始数据输入的初始数据所占的存储空间以及所占的存储空间以及算法在执行过程中所需要的额外空间这算法在执行过程中所需要的额外空间这3部分。

部分n 算法的时间复杂度是指算法的时间复杂度是指A) 执行算法程序所需要的时间执行算法程序所需要的时间 B) 算法程序的长度算法程序的长度C) 算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数算法程序中的指令条数n算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、 【【1】】 和拥有足够的情报和拥有足够的情报n算法的空间复杂度是指算法的空间复杂度是指 A) 算法程序的长度算法程序的长度 B) 算法程序中的指令条数算法程序中的指令条数 C) 算法程序所占的存储空间算法程序所占的存储空间 D) 执行过程中所需要的存储空间执行过程中所需要的存储空间n在计算机中，算法是指在计算机中，算法是指 A) 加工方法加工方法B) 解题方案的准确而完整的描述解题方案的准确而完整的描述 C) 排序方法排序方法D) 查询方法查询方法例题讲解例题讲解有穷性有穷性n算法分析的目的是算法分析的目的是 A) 找出数据结构的合理性找出数据结构的合理性 B) 找出算法中输入和输出之间的关系找出算法中输入和输出之间的关系 C) 分析算法的易懂性和可靠性分析算法的易懂性和可靠性 D) 分析算法的效率以求改进分析算法的效率以求改进n算法的工作量大小和实现算法所需的存储单元多少分别称为算法算法的工作量大小和实现算法所需的存储单元多少分别称为算法的的 【【1】】 。

时间复杂度和空间复杂度时间复杂度和空间复杂度1.2 数据结构n数据结构的定义n数据的逻辑结构和存储结构n数据结构的图形表示n线性结构与非线性结构能输入到计算机中能输入到计算机中并能被计算机程序处理的并能被计算机程序处理的符号的集合符号的集合整数整数(1,2)(1,2)、实数、实数(1.1,1.2)(1.1,1.2)字符串字符串(Beijing)(Beijing)、、图形、声音图形、声音1.2.2 基本概念和术语        数据结构是一门研究数据结构是一门研究数据数据组织组织、、存储存储和和运算运算的一般方法的学科的一般方法的学科计算机管理图书问题计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间既要考虑查询时间短，又要考虑节省空间        数据结构是一门研究数据结构是一门研究数据数据组织组织、、存储存储和和运算运算的一般方法的学科。

的一般方法的学科最简单的办法之一是建立一张表，最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如每一本书的信息在表中占一行，如 如何将如何将0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9这这1010个数存放在个数存放在计算机中能最快地达到你所需要的目的？计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同目的不同，最佳的存储方方法就不同 从大到小排列：从大到小排列：9,8,7,6,5,4,3,2,1,09,8,7,6,5,4,3,2,1,0输出偶数：输出偶数：0,2,4,6,8,1,3,5,7,9 0,2,4,6,8,1,3,5,7,9 数据元素在数据元素在计算机中的表示计算机中的表示        数据结构是一门研究数据结构是一门研究数据数据组织组织、、存储存储和和运算运算的一般方法的学科的一般方法的学科对数据结构中的节点进行对数据结构中的节点进行操作处理操作处理(插入、删除、修改、查找、排序插入、删除、修改、查找、排序) 1．数据的逻辑结构．数据的逻辑结构  2、数据的存储结构、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。

数据的运算：检索、排序、插入、删除、修改等 A．线性结构．线性结构 B．非线性结构．非线性结构A    顺序存储顺序存储 B    链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面 数据结构可描述为数据结构可描述为   Group=（（D，，R））1.数据的逻辑结构数据的逻辑结构：：是指反映数据元素之间逻辑关系是指反映数据元素之间逻辑关系的数据结构它包括的数据结构它包括数据元素的集合和数据元素之间数据元素的集合和数据元素之间的前后关系两个因素的前后关系两个因素有限个数据元素的集合有限个数据元素的集合有限个数据元素有限个数据元素间关系的集合间关系的集合数据的逻辑结构数据的逻辑结构简称简称数据结构数据结构数据元素数据元素(Data Element)(Data Element) 数据元素是数据的基本单位，即数据数据元素是数据的基本单位，即数据集合中的个体集合中的个体 有时一个数据元素可由若干有时一个数据元素可由若干数据项数据项(Data Item)(Data Item)组成数据项是数据的最小组成数据项是数据的最小单位。

单位数据元素亦称数据元素亦称结点结点或或记录记录线性线性树树图图常用数据结构常用数据结构:A.线性结构线性结构 (A , B , C , ······· ，X ,Y , Z)例例:学生成绩表学生成绩表8686胡孝臣胡孝臣986110398611039595刘忠赏刘忠赏98611079861107100100张卓张卓98611099861109成绩成绩姓名姓名学号学号①①线性表线性表②②栈栈——后进先出后进先出③③队列队列——先进先出先进先出例例: :英文字母表英文字母表数据结构数据结构S=(D,R)D={春春,夏夏,秋秋,冬冬}R={<春春,夏夏>,<夏夏,秋秋>,<秋秋,冬冬>}什么型的数据结构什么型的数据结构?用图形工具用图形工具线性结构线性结构数据元素：用中间标有元素值的方框表示，称为结点数据元素：用中间标有元素值的方框表示，称为结点逻辑关系：用有向线段从前件指向后件（不引起误会逻辑关系：用有向线段从前件指向后件（不引起误会情况下，箭头可以省去）情况下，箭头可以省去）冬冬春春夏夏秋秋①①树形结构树形结构例例:家庭成员数据结构可表示成家庭成员数据结构可表示成例例:计算机文件管理系统也是典型的树形结构计算机文件管理系统也是典型的树形结构B．非线性结构．非线性结构父亲父亲儿子儿子女儿女儿没有前件的结点称为根结点；没有前件的结点称为根结点；没有后件的结点称为终端结点没有后件的结点称为终端结点（叶子结点）（叶子结点）1423      例例:数据结构数据结构B(D,R)      D={ 1 , 2 , 3 , 4}      R={(1,2) , (1,3) , (1,4) , (2,3), (3,4) , (2,4) }    213例例:数据结构数据结构C(D,R)D={ 1 , 2 , 3 }R={ <1,2>, <2,3>, <3,2>, <1,3>} ②②图形结构图形结构元素元素n n……..元素元素i i……..元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（（n-1)*m存储地址存储地址存储内容存储内容Loc(ai)=Lo+（（i-1)*m1、顺序存储、顺序存储每个元素所占用每个元素所占用的存储单元个数的存储单元个数（（3）存储结构）存储结构例：线性表例：线性表(zhao,qian,sun,li,zhou,wu,zheng,wang) 顺序存储结构：顺序存储结构：存储地址存储地址数据数据7891011121314zhaoqiansunlizhouwuzhengwang7基地址基地址顺序存储结构，将逻辑上相邻的顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存数据元素存储在物理上相邻的存储单元里储单元里,具有以下特点具有以下特点:1.随机存取。

随机存取2.作插入或删除操作时，需移动作插入或删除操作时，需移动大量元数大量元数3.长度变化较大时，需按最大空长度变化较大时，需按最大空间分配4.表的容量难以扩充表的容量难以扩充 2、链式存储、链式存储 每个节点都由两部分组成：每个节点都由两部分组成：      数据域数据域和和指针域指针域数据域数据域存放元素本身的数据，存放元素本身的数据，指针域指针域存放指针存放指针数据元素之间逻辑上的联系由数据元素之间逻辑上的联系由指针来体现指针来体现例：线性表例：线性表(zhao,qian,sun,li,zhou,wu,zheng,wang)链式存储结构：链式存储结构：存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针通常我们把链表画成用通常我们把链表画成用箭头箭头相链接的结点的序列，结点相链接的结点的序列，结点之间的箭头表示链域中的指针之间的箭头表示链域中的指针zhaoqiansunlizhouwuzhengwang /H存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针1.比顺序存储结构多用空间比顺序存储结构多用空间(存储密度小存储密度小)   (每个节点都由数据域和指针每个节点都由数据域和指针域域组成组成)。

2.逻辑上相邻的节点物理上不必相邻逻辑上相邻的节点物理上不必相邻3.插入、删除灵活插入、删除灵活        (不必移动节点，只要改变节点中的指针不必移动节点，只要改变节点中的指针)4.非随机存取非随机存取链接存储结构特点：链接存储结构特点： 1．数据的逻辑结构．数据的逻辑结构  2、数据的存储结构、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 A．线性结构．线性结构 B．非线性结构．非线性结构A    顺序存储顺序存储 B    链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面 (亦称物理结构亦称物理结构)……n链表不具有的特点是链表不具有的特点是A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比n数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【【1】】 n数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的 A) 存储结构存储结构B) 物理结构物理结构 C) 逻辑结构逻辑结构D) 物理和存储结构物理和存储结构 n数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【【1】】 两大类。

两大类n数据的存储结构是指数据的存储结构是指A）数据所占的存储空间）数据所占的存储空间B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D）存储在外存中的数据）存储在外存中的数据 例题讲解例题讲解存储结构存储结构 非线性结构非线性结构n顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【【2】】 的存储单元中的存储单元中 n数据处理的最小单位是数据处理的最小单位是 A) 数据数据 B) 数据元素数据元素 C) 数据项数据项 D) 数据结构数据结构n数据结构作为计算机的一门学科，主要研究数据的逻辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及 A) 数据的存储结构数据的存储结构 B) 计算方法计算方法 C) 数据映象数据映象 D) 逻辑存储逻辑存储n线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 相邻相邻n根据数据结构中各数据元素之间前后件关系的复杂程度，一根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成般将数据结构分成 A) 动态结构和静态结构动态结构和静态结构 B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) 线性结构和非线性结构线性结构和非线性结构 D) 内部结构和外部结构内部结构和外部结构 n数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 【【2】】 以及对数据以及对数据的操作运算。

的操作运算n数据的基本单位是数据的基本单位是 【【5】】 n下列叙述中，错误的是下列叙述中，错误的是 A) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构存储结构存储结构数据元素数据元素1.3 线性表线性表1.3.1 线性表的概念线性表的概念线性表的定义：线性表的定义： 线性表线性表是是n个元素的有限序列，它们之间的关系可以排成一个元素的有限序列，它们之间的关系可以排成一 个线性序列：个线性序列： (a1，，a2，，…… ，，ai，，…… ，，an) 其中其中n称作表的称作表的长度长度，当，当n=0时，称作时，称作空表空表线性表的特点：线性表的特点：1.线性表中所有元素的性质相同线性表中所有元素的性质相同2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继前驱和一个后继.第一个数据元素无前驱第一个数据元素无前驱,最后一个数据元素无后继。

最后一个数据元素无后继3.数据元素在表中的位置只取决于它自身的序号数据元素在表中的位置只取决于它自身的序号性表上常用的运算有：性表上常用的运算有：初始化、求长度、取元素、修改、前插、删除、查找、排序初始化、求长度、取元素、修改、前插、删除、查找、排序1.4 线性表的顺序存储结构及其插入与删除操作线性表的顺序存储结构及其插入与删除操作n特点：特点： 1.线性表中数据元素类型一致，只有数线性表中数据元素类型一致，只有数据域，存储空间利用率高据域，存储空间利用率高 2.所有元素所占的存储空间是连续的所有元素所占的存储空间是连续的 3.各数据元素在存储空间中是按逻辑顺各数据元素在存储空间中是按逻辑顺序依次存放的序依次存放的 4. 做插入、删除时需移动大量元素做插入、删除时需移动大量元素 5. 空间估计不明时，按最大空间分配空间估计不明时，按最大空间分配 顺序存储结构：顺序存储结构：存储地址存储地址数据数据7891011121314zhaoqiansunlizhouwuzhengwang7基地址基地址元素元素a an n……..元素元素a ai i……..元素元素a a2 2元素元素a a1 1bb+mb+(i-1)*m    b+(maxlen-1)*m存储地址存储地址内存状态内存状态Loc(元素元素i)=b +（（i-1)*m顺序存储结构示意图顺序存储结构示意图(顺序表顺序表)：：首地址首地址起始地址起始地址基地址基地址每个元素所占用每个元素所占用的存储单元个数的存储单元个数 1- 1插入运算插入运算ai-1…..a2a1alength…ai+1ai  xai-1…..a2a1alength…ai+1ai X插入算法的分析插入算法的分析: 假设线性表中含有假设线性表中含有n个数据元素，在进行插入操作个数据元素，在进行插入操作时，若假定在时，若假定在n+1个位置上插入元素的可能性均等，则个位置上插入元素的可能性均等，则平均移动元素的个数为：平均移动元素的个数为： 1- 2删除运算删除运算ai-1…..a2a1alength…ai+1aiai-1…..a2a1alength…ai+1删除算法的分析删除算法的分析: 在进行删除操作时，若假定删除每个元素的可能性均等，则在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：平均移动元素的个数为：总结总结: 顺序存储结构表示的线性表，在做插入或删除操作时，平均需顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。

当线性表的数据元素量较大，并且经要移动大约一半的数据元素当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑常要对其做插入或删除操作时，这一点需要值得考虑n链表不具有的特点是链表不具有的特点是A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比n顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【【2】】 的存储单元中的存储单元中n长度为长度为n的顺序存储线性表中，当在任何位置上插入一个元的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为素概率都相等时，插入一个元素所需移动元素的平均个数为 【【1】】 n线性表若采用顺序存储结构时，要求内存中可用存储单元的线性表若采用顺序存储结构时，要求内存中可用存储单元的地址地址 A) 必须是连续的必须是连续的 B) 部分地址必须是连续的部分地址必须是连续的 C) 一定是不连续的一定是不连续的 D) 连续不连续都可以连续不连续都可以例题讲解例题讲解相邻相邻n线性表线性表L=(a1,a2,a3,…ai，，…an)，下列说法正确的是，下列说法正确的是 A) 每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 B) 线性表中至少要有一个元素线性表中至少要有一个元素 C) 表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 D) 除第一个元素和最后一个元素外，其余每个元素都有一个除第一个元素和最后一个元素外，其余每个元素都有一个 且只有一个直接前件和直接后件且只有一个直接前件和直接后件n线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 n下列叙述中，错误的是下列叙述中，错误的是 A) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 B) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 C) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 D) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结构可以有多种存储结构 n根据数据结构中各数据元素之间前后件关系的复杂程根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成度，一般将数据结构分成 A) 动态结构和静态结构动态结构和静态结构 B) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 C) 线性结构和非线性结构线性结构和非线性结构 D) 内部结构和外部结构内部结构和外部结构n当线性表采用顺序存储结构实现存储时，其主要特点当线性表采用顺序存储结构实现存储时，其主要特点是是 【【1】】 。

随机存取随机存取1.5线性表的链式存储结构及其插入与删除操作线性表的链式存储结构及其插入与删除操作zhaoqiansunlizhouwuzhengwang /H存储地址存储地址数据数据17131925313743liqiansunwangwuzhaozhengzhou指针指针43131null377192531头指针头指针单链表单链表baPbaP1-1单链表的插入运算单链表的插入运算xS在在P所指向的结点之后插入新的结点所指向的结点之后插入新的结点1-2单链表单链表删除运算删除运算La…aian ^…ai-1ai+1要求要求:删除结点删除结点ai1-3. 循环链表循环链表: 首尾相接的链表首尾相接的链表     将将最最后后一一个个结结点点的的空空指指针针改改为为指指向向头头结结点点，，从从任任一一结结点点出出发发均均可可找到其它结点找到其它结点a1a2an∧a3L…..带头结点的单链表带头结点的单链表a1a2ana3L…..循环单链表循环单链表特点特点: 可以从任何一个结点开始访问链表的所有结点可以从任何一个结点开始访问链表的所有结点.1-4 双向链表双向链表         在在每每个个结结点点中中设设置置两两个个指指针针，，一一个个指指向向后后继继，，一一个个指指向向前前驱驱。

可可直直接接确确定定一一个个结结点点的的前前驱驱和和后后继继结点可提高效率可提高效率datanextbeforen链表不具有的特点是链表不具有的特点是A) 不必事先估计存储空间不必事先估计存储空间 B) 可随机访问任一元素可随机访问任一元素C) 插入删除不需要移动元素插入删除不需要移动元素D) 所需空间与线性表长度成正比所需空间与线性表长度成正比n用链表表示线性表的优点是用链表表示线性表的优点是A) 便于随机存取便于随机存取 B) 花费的存储空间较顺序存储少花费的存储空间较顺序存储少C) 便于插入和删除操作便于插入和删除操作 D) 数据元素的物理顺序与逻辑顺序相同数据元素的物理顺序与逻辑顺序相同n长度为长度为n的顺序存储线性表中的顺序存储线性表中,当在任何位置上插入一个元素概当在任何位置上插入一个元素概率都相等时率都相等时,插入一个元素所需移动元素的平均个数为插入一个元素所需移动元素的平均个数为 【【1】】 n在单链表中，增加头结点的目的是在单链表中，增加头结点的目的是 A) 方便运算的实现方便运算的实现 B) 使单链表至少有一个结点使单链表至少有一个结点 C) 标识表结点中首结点的位置标识表结点中首结点的位置 D) 说明单链表是线性表的链式存储实现说明单链表是线性表的链式存储实现例题讲解例题讲解n非空的循环单链表非空的循环单链表head的尾结点的尾结点(由由p所指向所指向) ，满足，满足 A) p->next==NULLB) p==NULL C) p->next=head D) p=head n循环链表的主要优点是循环链表的主要优点是 A) 不再需要头指针了不再需要头指针了 B) 从表中任一结点出发都能访问到整个链表从表中任一结点出发都能访问到整个链表 C) 在进行插入、删除运算时，能更好的保证链表不断开在进行插入、删除运算时，能更好的保证链表不断开 D) 已知某个结点的位置后，能够容易的找到它的直接前件已知某个结点的位置后，能够容易的找到它的直接前件n当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。

这种情况称为不能进行入队运算这种情况称为 【【2】】 n用链表表示线性表的突出优点是用链表表示线性表的突出优点是 【【1】】 上溢上溢插入、删除灵活插入、删除灵活1.6 栈和队列栈和队列1.6.1 栈和队列的定义栈和队列的定义 栈和队列栈和队列是两种特殊的线性表，它们是运算时是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为要受到某些限制的线性表，故也称为限定性的数据限定性的数据结构结构1 .栈栈栈栈——是限定仅在表尾进行插入或删除操作的线性表是限定仅在表尾进行插入或删除操作的线性表栈顶栈顶——表尾栈底栈底——表头空栈空栈——不含元素的空表不含元素的空表…a1a2an栈底栈底栈顶栈顶进栈进栈出栈出栈栈栈s=(a1,a2,…,an)后进先出后进先出（（LIFO））2. 栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算 a2 a1 a1 a2 top       用顺序存储结构表示的栈用顺序存储结构表示的栈:              顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量一般用一维数组表示，设置一个简单变量top指示栈顶位置，指示栈顶位置，称称为为栈顶指针栈顶指针，，它始终指向待插入元素的位置。

它始终指向待插入元素的位置基本运算：基本运算：压（进）栈：压（进）栈：PUSH出栈：出栈：POP读栈顶元素：读栈顶元素：gettop例子：例子：topbaseEDCBAtopbaseCBAbasetopAbasetop空桟：空桟：top＝＝base非空桟：非空桟：top始终在桟顶元素的后一个位置始终在桟顶元素的后一个位置桟的元素个数：桟的元素个数： top-base上溢上溢下溢下溢3.  队列队列定义：一种特殊的线性结构，限定只能在表的一端进行插入，在定义：一种特殊的线性结构，限定只能在表的一端进行插入，在   表的另一端进行删除的线性表表的另一端进行删除的线性表  此种结构称为此种结构称为先进先出（先进先出（FIFO））表表    a1    ,     a2       ,     a3      ,     a4       ,   …………         an-1  ,   an           队队     列列    示示   意意   图图队队头头队队尾尾 e3 e4 (c)(c)e1,e2出队，出队，e4入队入队 队队  满满rear =3front e1 e2 e3 (b)rearfront(b)e1,e2,e3入队入队4.队列的顺序存储结构及其基本运算队列的顺序存储结构及其基本运算 3  2   1  0 (a)rear=front=-1(队空）队空）rearfront空队列空队列:非空队列非空队列:队列元素个数队列元素个数:rear=front=-1front始终指向队头元素前一个位置，而始终指向队头元素前一个位置，而rear始终始终指向队尾元素的位置指向队尾元素的位置rear-front循环队列循环队列基本思想：基本思想：把队列设想为一个循环的表，臆想把队列设想为一个循环的表，臆想elem[0]接接在在elem[maxsize-1]之后之后.……frontrearMaxsize-101 e3 e4 rear =3front0012345frontABCDEFrear上溢上溢0012345frontrear下溢下溢front=rear队满队满front=rear队空队空n栈和队列的共同特点是栈和队列的共同特点是 A)都是先进先出都是先进先出 B) 都是先进后出都是先进后出 C) 只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D) 没有共同点没有共同点n如果进栈序列为如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是，则可能的出栈序列是 A) e3,e1,e4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2D) 任意顺序任意顺序n一些重要的程序语言一些重要的程序语言(如如C语言和语言和Pascal语言语言) 允许过允许过程的递归调用。

而实现递归调用中的存储分配通常用程的递归调用而实现递归调用中的存储分配通常用 A) 栈栈B) 堆堆 C) 数组数组 D) 链表链表例题讲解例题讲解n栈底至栈顶依次存放元素栈底至栈顶依次存放元素A、、B、、C、、D，在第五个元素，在第五个元素E入栈前，入栈前，栈中元素可以出栈，则出栈序列可能是栈中元素可以出栈，则出栈序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE n栈通常采用的两种存储结构是栈通常采用的两种存储结构是 A) 线性存储结构和链表存储结构线性存储结构和链表存储结构 B) 散列方式和索引方式散列方式和索引方式 C) 链表存储结构和数组链表存储结构和数组 D) 线性存储结构和非线性存储结构线性存储结构和非线性存储结构n栈和队列通常采用的存储结构是栈和队列通常采用的存储结构是 【【1】】 n下列数据结构中，按先进后出原则组织数据的是下列数据结构中，按先进后出原则组织数据的是 A) 线性链表线性链表 B) 栈栈 C) 循环链表循环链表 D) 顺序表顺序表▽▽当循环队列非空且队尾指针等于队头指针时，说明循环队列已当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。

这种情况称为满，不能进行入队运算这种情况称为 【【2】】 链表存储结构和数组链表存储结构和数组上溢上溢n由两个栈共享一个存储空间的好处是由两个栈共享一个存储空间的好处是A) 减少存取时间，降低下溢发生的机率减少存取时间，降低下溢发生的机率 B) 节省存储空间，降低上溢发生的机率节省存储空间，降低上溢发生的机率C) 减少存取时间，降低上溢发生的机率减少存取时间，降低上溢发生的机率 D) 节省存储空间，降低下溢发生的机率节省存储空间，降低下溢发生的机率自由区lefttoprighttop0MAXNUM-1两个栈共享邻接空间两个栈共享邻接空间n下列关于栈的叙述中正确的是下列关于栈的叙述中正确的是Ａ）在栈中只能插入数据Ａ）在栈中只能插入数据 B）在栈中只能删除数据）在栈中只能删除数据C）栈是先进先出的线性表）栈是先进先出的线性表 D）栈是后进先出的线性表）栈是后进先出的线性表n下列关于队列的叙述中正确的是下列关于队列的叙述中正确的是Ａ）在队列中只能插入数据Ａ）在队列中只能插入数据 B）在队列中只能删除数据）在队列中只能删除数据C）队列是先进先出的线性表）队列是先进先出的线性表 D）队列是后进先出的线性表）队列是后进先出的线性表1.7.1 树的定义树的定义 由一个或多个结点组成的有限集合由一个或多个结点组成的有限集合。

仅有一个根结点，结仅有一个根结点，结点间有明显的层次结构关系点间有明显的层次结构关系 A C G  T2D H I  T3J M B E L KT1 F现实世界中，能用树的结构表示的例子：现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等学校的行政关系、书的层次结构、人类的家族血缘关系等1.7 树介绍几个概念：介绍几个概念：结结点点（（Node））：：树树中中的的元元素素，，包包含含数数据据项项及及若若干干指指向向其其子树的分支子树的分支结点的度结点的度（（Degree）：结点拥有的子树数结点拥有的子树数结点的层次：结点的层次：从根结点开始算起，根为第一层从根结点开始算起，根为第一层叶子叶子（（Leaf）：度为零的结点，也称端结点度为零的结点，也称端结点孩子孩子（（Child）：结点子树的根称为该结点的孩子结点结点子树的根称为该结点的孩子结点兄弟兄弟（（Sibling）：）：同一双亲的孩子同一双亲的孩子双双亲亲（（Parent））：：孩孩子子结结点点的的上上层层结结点点，，称称为为这这些些结结点点的的 双亲树的深度树的深度（（Depth)：：  树中结点的最大层次数。

树中结点的最大层次数树的度：树的度：结点所具有的最大的度结点所具有的最大的度.森林森林（（Forest）：）：M棵互不相交的树的集合棵互不相交的树的集合 A C GD H I  J M B E L KT1 F1.7.2 二叉树二叉树 （（Binary Tree））1 、二叉树的定义及其性质、二叉树的定义及其性质 (1) 二叉树的定义二叉树的定义二叉树的五种基本形态二叉树的五种基本形态       二二叉叉树树一一种种特特殊殊的的树树形形结结构构，，特特点点是是树树中中每每个个结结点点最最多多只只能能有有两两棵棵子子树树(即即二二叉叉树树中中不不存存在在度度大大于于2的的结结点点)，，且且子子树树有有左左右右之分，次序不能颠倒之分，次序不能颠倒    空二叉树空二叉树 仅有仅有根结点根结点 右子树右子树为空为空 左子树左子树为空为空左右子树左右子树均非空均非空 二叉二叉树树是是n(nn(n 0)0)个结点的有限集合它或为空数个结点的有限集合它或为空数(n=0),(n=0),或由一个根结点和两棵分别称为根的左子树和或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。

右子树的互不相交的二叉树组成特别要注意：特别要注意：二叉二叉树树不是不是一般树的特殊情况一般树的特殊情况, ,而是而是另一种树形结构另一种树形结构. .a aa ab bb b两棵不同的二叉两棵不同的二叉树树ab一一棵棵树树性质性质1:二叉树的第二叉树的第i层上至多有层上至多有2 i-1（（i  1）个结点2)  二叉树的基本性质二叉树的基本性质423167891011121314155第三层上第三层上(i=3)(i=3)，有，有2 23-13-1=4=4个节点第四层上第四层上(i=4)(i=4)，有，有2 24-14-1=8=8个节点性质性质2: 深度为深度为k的二叉树中至多含有的二叉树中至多含有2k-1个结点性质３：对任何一棵二叉树性质３：对任何一棵二叉树T，如果其终端结点数为，如果其终端结点数为n0,度度                为为2的结点数为的结点数为n2,则则n0=n2+1证明：证明：   设设n1为二叉树为二叉树T中度为中度为1的结点数；的结点数；   ∵∵二叉树中所有结点的度均小于或等于二叉树中所有结点的度均小于或等于2   ∴∴其结点总数为：其结点总数为： n=n0+n1+n2   ∵∵二叉树中除了根结点外，其余结点都有一个分支进入二叉树中除了根结点外，其余结点都有一个分支进入       设分支总数为设分支总数为B；；  则则 n=B+1;   ∵∵ 二叉树的分支是由度为二叉树的分支是由度为1或或2的结点射出的的结点射出的   ∴∴ B=n1+2*n2   ∴∴n=n1+2*n2+1=n0+n1+n2    n0=n2+1ABFCJM一般树一般树★★满二叉树满二叉树423167891011121314155特点：每一层上都含有最特点：每一层上都含有最大结点数。

大结点数★★完全二叉树完全二叉树4231678910 11125特点：特点：(1)(1)除最后一层外，每一层都取最除最后一层外，每一层都取最 大结点数，大结点数，(2)(2)最后一层结点都集中在该层最左最后一层结点都集中在该层最左边的若干位置边的若干位置性质４：具有性质４：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为112345678910121例：例：n=2    k=2         n=6   k=3         n=7   k=3         n=8   k=4         n=12  k=4性质５：如果对一棵有性质５：如果对一棵有n个结点的完全二叉树的结点按层个结点的完全二叉树的结点按层                 序编号，则对任一结点序编号，则对任一结点i(1=n,则结点则结点i无左孩子无左孩子(结点结点i为叶子结点为叶子结点);                                     否则其左孩子否则其左孩子Lchild(i)是结点是结点2i           (3)如果如果2i+1>n,则结点则结点i无右孩子无右孩子;               否则其右孩子否则其右孩子Rchild(i)是结点是结点2i+1。

1)如果如果i=1,则结点则结点i是二叉树的根是二叉树的根,无双亲无双亲;    如果如果i>1,则双亲则双亲Parent(i)是结点是结点|i/2|                例：例：112345678910121i=6  其双亲为其双亲为|i/2|= 3；其左孩子为；其左孩子为2*i=12;i=1  是树的根是树的根,无双亲无双亲;其左孩子为其左孩子为2*i=2,右孩子为右孩子为2*i+1=3 .∵∵2*i=18>12       2*i+1=19>12    ∴∴其无左、右孩子其无左、右孩子∵∵2*i+1=13>12     ∴∴其无右孩子其无右孩子i=9  其双亲为其双亲为|i/2|= 4 ；；★★树与二叉树的区别树与二叉树的区别A．树和二叉树的结点个数最少都可为．树和二叉树的结点个数最少都可为0B．树中结点的最大度数没有限制，二叉树结点最大度数为．树中结点的最大度数没有限制，二叉树结点最大度数为2C．树的．树的结点结点无左、右之分，二叉树的无左、右之分，二叉树的结点结点子树有明确的左、右之分子树有明确的左、右之分3个结点的个结点的树树3个结点的个结点的二叉二叉树树2、二叉树的存储结构、二叉树的存储结构 (2)   链式存储结构链式存储结构T[16]若父结点在数组中若父结点在数组中i下标处，其左孩子在下标处，其左孩子在2*i处，右孩子在处，右孩子在2*i+1处。

处11 A B c F E D ●●●●●●●●● 1 2 4 8 910 5 6 3 712131415(1)   顺序存储结构顺序存储结构(1)   顺序存储结构顺序存储结构2h-1= 24-1 = 15用用一一组组连连续续的的存存储储单单元元存存放放二二叉叉树树的的数数据据元元素素结结点点在在数数组组中中的的相相对对位置蕴含着结点之间的关系位置蕴含着结点之间的关系0000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费(2)、链式存储结构、链式存储结构链式存储结构链式存储结构二叉链表二叉链表三叉链表三叉链表二叉链表：二叉链表：二叉链表的结点包含三个域：数据域、左、右指针域二叉链表的结点包含三个域：数据域、左、右指针域例：例：ABCDEFG    A ^B^  C ^D^  E^  F ^^ G ^三叉链表：三叉链表：三叉链表的结点包含四个域：三叉链表的结点包含四个域：                   数据域、左、右、双亲指针域数据域、左、右、双亲指针域。

例：例：ABCDEFG    A  ^  ^B^  C       ^D^  E^  F     ^^ G     ^链式存储结构的特点：链式存储结构的特点：         （（1）操作便于实现）操作便于实现        （（2）结构复杂）结构复杂1.7.3  二叉树的遍历二叉树的遍历       查查找找某某个个结结点点，，或或对对二二叉叉树树中中全全部部结结点点进进行行某某种种处处理理，，就就需需要要遍历1）遍历定义及遍历算法）遍历定义及遍历算法    遍遍历历是是指指按按某某条条搜搜索索路路线线寻寻访访树树中中每每个个结结点点，，且且每每个个结结点点只只被被访访 问一次    按先左后右的原则，一般使用三种遍历：按先左后右的原则，一般使用三种遍历：先序遍历先序遍历(D L R):          访问根结点，按先序遍历左子树，按先序遍历右子树访问根结点，按先序遍历左子树，按先序遍历右子树中序遍历中序遍历(L D R):        按中序遍历左子树，访问根结点，按中序遍历右子树按中序遍历左子树，访问根结点，按中序遍历右子树后序遍历后序遍历(L R D):       按后序遍历左子树，按后序遍历右子树，访问根结点。

按后序遍历左子树，按后序遍历右子树，访问根结点        二叉树为空时，执行空操作，即空二叉树已遍历完二叉树为空时，执行空操作，即空二叉树已遍历完  （（2）遍历算法）遍历算法先序遍历：先序遍历：D L R中序遍历：中序遍历：L D R后序遍历：后序遍历：L R DADBCD           L            RAD    L   RD    L   R>B>>D>>CD    L   R以先序遍历以先序遍历D L RD L R为例演示遍历过程为例演示遍历过程 ABDCBDAC DBCAe-+a*b-cd/fL                       D           RL      D        R  a+ L   D   Rb*LDRc - d-LDRe / f中序遍历示图中序遍历示图n已知二叉树后序遍历序列是已知二叉树后序遍历序列是dabec，中序遍历序列是，中序遍历序列是debac，，它的前序遍历序列是它的前序遍历序列是 A) acbed B) decab C) deabc D) cedba n已知一棵二叉树前序遍历和中序遍历分别为已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和和DBGEACHF，则该二叉树的后序遍历为，则该二叉树的后序遍历为 A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHGn树是结点的集合，它的根结点数目是树是结点的集合，它的根结点数目是 A) 有且只有有且只有1B) 1或多于或多于1 C) 0或或1D) 至少至少2n下列叙述中正确的是下列叙述中正确的是 A) 线性表是线性结构线性表是线性结构B) 栈与队列是非线性结构栈与队列是非线性结构 C) 线性链表是非线性结构线性链表是非线性结构D) 二叉树是线性结构二叉树是线性结构例题讲解例题讲解n在深度为在深度为5的满二叉树中，叶子结点的个数为的满二叉树中，叶子结点的个数为 A) 32B) 31 C) 16 D) 15 n若某二叉树的前序遍历访问顺序是若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺，中序遍历访问顺序是序是dgbaechf，则其后序遍历的结点访问顺序是，则其后序遍历的结点访问顺序是 A) bdgcefha B) gdbecfha C) bdgaechf D) gdbehfcan在树结构中，树根结点没有在树结构中，树根结点没有 【【1】】 。

n具有具有3个结点的二叉树有个结点的二叉树有 A) 2种形态种形态 B) 4种形态种形态 C) 7种形态种形态 D) 5种形态种形态n设一棵二叉树中有设一棵二叉树中有3个叶子结点，有个叶子结点，有8个度为个度为1的结点，则该二的结点，则该二叉树中总的结点数为叉树中总的结点数为 A) 12 B) 13 C) 14D) 15 双亲结点双亲结点n设有下列二叉树：设有下列二叉树： 对此二叉树前序遍历的结果为对此二叉树前序遍历的结果为A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPTn设有下列二叉树：设有下列二叉树：对此二叉树的中序遍历的结果为对此二叉树的中序遍历的结果为A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCAn设树设树T的度为的度为4,其中度为其中度为1、、2、、3、、4的结点的结点个数分别为个数分别为4、、2、、1、、1则T中的叶子结点中的叶子结点数为数为A））8 B））7 C））6 D））5n设一棵完全二叉树共有设一棵完全二叉树共有700个结点，则该二个结点，则该二叉树中有（叉树中有（ ）个叶子结点。

个叶子结点 350n解法一：根据二叉树二叉树的性质3可知：叶子结点叶子结点数n0＝n2+1，根据完全二叉树完全二叉树的概念可知，度为1的结点数要么为1，要么为0，二叉树二叉树总结点数N＝n0+n1+n2＝2n0+n1－1，得出n0＝（N+1－n1）/2＝N/2向上取整，所以本题答案是350个叶子结点叶子结点n解法二：易求出总层数和末层叶子数总层数k=log2N向上取整 =10;且前9层总结点数为2^9-1=511 (完全二叉树完全二叉树的前k-1层肯定是满的)所以末层叶子数为700-511=189个请注意叶子结点叶子结点总数≠末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数末层的189个叶子只占据了上层的95个结点（189/2 )，上层（k=9)右边的0度结点数还有2^(9-1)-95=161个所以，全部叶子数＝189(末层)＋161(k-1层)=350个n在一个容量为在一个容量为15的循环队列中，若头指针的循环队列中，若头指针front=6，尾指针，尾指针rear=9，则该循环队列中，则该循环队列中共有（共有（ ）个元素n设一棵二叉树的中序遍历结果为设一棵二叉树的中序遍历结果为DBEAFC，，前序遍历结果为前序遍历结果为ABDECF，则后序遍历结果，则后序遍历结果为（为（ ）。

3DEBFCA1.8 查找和排序n顺序查找与二分查找算法顺序查找与二分查找算法n基本排序算法（交换类排序、选择类排基本排序算法（交换类排序、选择类排序、插入类排序）序、插入类排序）1.8.1 查找查找n查找是在一个给定的数据结构中，查找是在一个给定的数据结构中，根据给定的根据给定的条件查找满足条件的结点条件查找满足条件的结点不同的数据结构采不同的数据结构采用不同的查找方法查找的效率直接影响数据用不同的查找方法查找的效率直接影响数据处理的效率处理的效率n查找的结果：查找的结果：查找成功：查找成功：找到满足条件的结点找到满足条件的结点查找失败：查找失败：找不到满足条件的结点找不到满足条件的结点1.8.1.1 顺序查找（线性查找）顺序查找（线性查找）◆◆查找过程：查找过程： 对给定的一关键字对给定的一关键字K，从线性表的一端开始，逐，从线性表的一端开始，逐个进行记录的关键字和个进行记录的关键字和K的比较，直到找到关键字等的比较，直到找到关键字等于于K的记录或到达表的另一端的记录或到达表的另一端◆◆可以采用从前向后查，也可采用从后向前查的方法可以采用从前向后查，也可采用从后向前查的方法。

◆◆在平均情况下，大约要与表中一半以上元素进行比在平均情况下，大约要与表中一半以上元素进行比较，效率较低平均查找长度较大较，效率较低平均查找长度较大 最好情况：最好情况：1 最坏情况：最坏情况：n◆◆在下面两种情况下只能采取顺序查找：在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）；线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构即使是有序线性表，但采用的是链式存储结构1.8.1.2 折半查找（二分法查找）折半查找（二分法查找）n思想：先确定待查找记录所在的范围，然后逐步缩小思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止范围，直到找到或确认找不到该记录为止 n前提：必须在前提：必须在具有顺序存储结构的具有顺序存储结构的有序表中进行有序表中进行n分三种情况：分三种情况： 1）若中间项的值等于）若中间项的值等于x,则说明已查到则说明已查到 2）若）若x小于中间项的值小于中间项的值,则性表的前半部分查找；则性表的前半部分查找； 3）若）若x大于中间项的值，则性表的后半部分查找。

大于中间项的值，则性表的后半部分查找n特点：比顺序查找方法效率高最坏的情况下，需要特点：比顺序查找方法效率高最坏的情况下，需要比较比较 log2n次次1.8.2 排序排序1.8.2.1  概述概述  1、排序的功能：、排序的功能：      将一个数据元素（或记录）的将一个数据元素（或记录）的 任意序任意序 列列，重新排成，重新排成       一个按关键字一个按关键字有序有序的序列  2、排序过程的组成步骤：、排序过程的组成步骤：•   首先首先比较比较两个关键字的大小；两个关键字的大小；•    然后将记录从一个位置然后将记录从一个位置移动移动到另一个位置到另一个位置排序方法排序方法插入类排序插入类排序选择类排序选择类排序交换类排序交换类排序归并排序归并排序简单插入排序简单插入排序希尔排序希尔排序简单选择排序简单选择排序堆排序堆排序起泡排序起泡排序快速排序快速排序1.8.2.2  交交 换换 排排 序序交换排序的特点在于交换排序的特点在于交换交换有冒泡和快速排序两种有冒泡和快速排序两种 1、冒泡排序（起泡排序）、冒泡排序（起泡排序）思想：思想：小的浮起，大的沉底小的浮起，大的沉底。

从左端开始比较从左端开始比较第一趟：第第一趟：第1个与第个与第2个比较，大则交换；第个比较，大则交换；第2个与第个与第3个比较，个比较，             大则交换，大则交换，……关键字最大的记录交换到最后一个位置上；关键字最大的记录交换到最后一个位置上；第二趟：对前第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换个记录进行同样的操作，关键字次大的记录交换                到第到第n-1个个位置上；位置上；      依次类推，则完成排序依次类推，则完成排序第第六六趟趟排排序序后后第第五五趟趟排排序序后后第第四四趟趟排排序序后后第第三三趟趟排排序序后后第第二二趟趟排排序序后后第第一一趟趟排排序序后后初初始始关关键键字字思思想想：：小小的的浮浮起起，，大大的的沉底4936416511783665364156364165413641561178363641491156492525251149495611111125252525排序排序n个记录最多个记录最多需要需要n-1趟冒泡排趟冒泡排序序正序：比较次数为正序：比较次数为O(n-1) 逆序：比较次数逆序：比较次数为为O(n(n-1)/2) 适合于数据较少的适合于数据较少的情况。

情况 2、快速排序、快速排序  (对冒泡排序的改进）对冒泡排序的改进）        思思想想：：通通过过一一趟趟排排序序将将待待排排序序列列分分成成两两部部分分，，使使其其中中一一部部分分记记录录的的关关键键字字均均比比另另一一部部分分小小，，再再分分别别对对这这两两部部分分排序，以达到整个序列有序排序，以达到整个序列有序  如，经过如，经过“一次划分一次划分” ，将关键字序列，将关键字序列               52, 49, 80, 36, 14,  58, 61, 97, 23, 75  调整为调整为:  23, 49, 14, 36, (52) 58, 61, 97, 80, 752、快速排序、快速排序  (对冒泡排序的改进）对冒泡排序的改进）时间复杂度：时间复杂度：O(nlog2n) 当当待待排排序序列列逆逆序序时时，，蜕蜕变变成成冒冒泡泡排排序序，，时时间间复复杂杂度度: O(n(n-1)/2)1.8.2.3   插入排序插入排序                      简单插入、希尔排序简单插入、希尔排序1、、简单简单插入排序插入排序:• 基本思想：基本思想：从数组的第从数组的第2号元素开始，顺序从数组中号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。

的适当位置上该该算算法法适适合合于于n 较较小小的的情情况况，，时时间间复复杂度为杂度为O(n2).待排元素序列：待排元素序列：[53]   27   36   15   69   42第一次排序：第一次排序：    [27   53]   36   15   69   42第二次排序：第二次排序：    [27   36   53]   15   69   42第三次排序：第三次排序：    [15   27   36   53]   69   42第四次排序：第四次排序：    [15   27   36    53   69]  42第五次排序：第五次排序：    [15   27   36  42   53   69]                           直接插入排序示例直接插入排序示例对于有对于有n个数个数据元素的待排据元素的待排序列，插入操序列，插入操作要进行作要进行n-1趟趟最坏情况下：最坏情况下： 需要需要n(n-1)/2次比较次比较最好：最好： n-1次比较次比较希尔排序：希尔排序：希尔排序的基本思想希尔排序的基本思想:        先将整个待排记录序列分割成为若干子序列分别进行先将整个待排记录序列分割成为若干子序列分别进行直接插入排序直接插入排序,待整个序列中的记录待整个序列中的记录“基本有序基本有序”时时,再对全再对全体记录进行一次直接插入排序体记录进行一次直接插入排序.最坏情况下：需要最坏情况下：需要O(n1.5 )次比较次比较 1、简单选择排序、简单选择排序•  思想：首先从思想：首先从1~n个元素中选出关键字个元素中选出关键字最小最小的记录的记录交换到交换到第一个第一个位置上。

然后再从第位置上然后再从第2 个到第个到第n个元素个元素中选出次小的记录交换到中选出次小的记录交换到第二个第二个位置上，依次类推位置上，依次类推1.8.2.4   选择排序选择排序                                      简单选择排序、堆排序简单选择排序、堆排序初态初态8        3        9        1        6     8        3        9        1        6     8        3        9        1        6     8        3        9        1        6     ijkijkijkijk1        3        9        8        6     互换互换ijk1        3        9        8        6     ikj1        3        9        8        6     ikj第第一一趟趟第第二二趟趟1        3        9        8        6     i kj第第三三趟趟时间复杂度为时间复杂度为O(n2)，， 适用于适用于待排序元待排序元素较少素较少的情况。

的情况比较次数：比较次数： n(n-1)/2次次 2、堆排序（、堆排序（也是一种选择排序）也是一种选择排序）       堆堆是是具具有有特特定定条条件件的的顺顺序序存存储储的的完完全全二二叉叉树树，，其其特特定定条条件件是是：：任任何何一一个个非非叶叶子子结结点点的的关关键键字字大大于于等等于于（（或或小小于于等等于于））子子女女的的关关键键字的值897624331510112536497856(a):堆顶元素取最大值堆顶元素取最大值(b):堆顶元素取最小值堆顶元素取最小值堆排序需要比较的堆排序需要比较的次数为次数为O(nlog2n) (1) 堆的示例堆的示例 1.8.2.5  内部排序方法的选择内部排序方法的选择各种排序方法各有优缺点，故在不同情况下可作不同的各种排序方法各有优缺点，故在不同情况下可作不同的选择通常需考虑的因素有选择通常需考虑的因素有：待排序的记录个数；记录：待排序的记录个数；记录本身的大小；记录的键值分布情况本身的大小；记录的键值分布情况等• 若待排序的记录个数若待排序的记录个数n较小时，可采用简单排序方法较小时，可采用简单排序方法• 若若n 较大时，应采用快速排序或堆排序。

较大时，应采用快速排序或堆排序• 若待排序的记录已基本有序，可采用简单插入和起泡若待排序的记录已基本有序，可采用简单插入和起泡   排序方法方法归并排序归并排序简单插入简单插入希尔排序希尔排序简单选择简单选择堆排序堆排序起泡排序起泡排序快速排序快速排序插插入入选选择择交交换换比较次数比较次数使用建议使用建议查找查找:方法方法顺序顺序折半折半比较次数比较次数log2n最好最好:1最坏最坏:n平均平均:(n+1)/2使用条件使用条件顺序存储结构的顺序存储结构的有序表有序表任何表任何表排序排序:n-1n(n-1)/2n1.5n(n-1)/2nlog2nn-1n(n-1)/2nlog2nn(n-1)/2正序的表、正序的表、n小的表小的表与表的初始数据无关、与表的初始数据无关、n小的表小的表正序的表、正序的表、n小的表小的表n大的表大的表,但逆序的表会蜕变为起泡排序但逆序的表会蜕变为起泡排序借助辅助空间最多的方法借助辅助空间最多的方法n大的表大的表n在长度为在长度为n的有序线性表中进行二分查找最的有序线性表中进行二分查找最坏的情况下，需要的比较次数为坏的情况下，需要的比较次数为 【【2】】 。

n长度为长度为n的顺序存储线性表中，当在任何位置的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为素所需移动元素的平均个数为 【【1】】 n假设线性表的长度为假设线性表的长度为n，则在最坏情况下，冒，则在最坏情况下，冒泡排序需要的比较次数为泡排序需要的比较次数为 A) log2n B) n2 C) O(n1..5) D) n(n-1)/2n已知数据表已知数据表A中每个元素距其最终位置不远，中每个元素距其最终位置不远，为节省时间，应采用的算法是为节省时间，应采用的算法是 A) 堆排序堆排序B) 直接插入排序直接插入排序 C) 快速排序快速排序 D) 直接选择排序直接选择排序 例题讲解例题讲解log2nn/2n 冒泡排序算法在最好的情况下的元素交换次冒泡排序算法在最好的情况下的元素交换次数为数为 【【1】】 n在最坏情况下，堆排序需要比较的次数为在最坏情况下，堆排序需要比较的次数为 【【2】】 n最简单的交换排序方法是最简单的交换排序方法是 A) 快速排序快速排序 B) 选择排序选择排序 C) 堆排序堆排序 D) 冒泡排序冒泡排序n排序是计算机程序设计中的一种重要操作，排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、常见的排序方法有插入排序、 【【1】】 和选择和选择排序等。

排序等0nlog2n交换排序交换排序n在下列几种排序方法中，要求内存量最大的在下列几种排序方法中，要求内存量最大的是是 A) 插入排序插入排序 B) 选择排序选择排序 C) 快速排序快速排序D) 归并排序归并排序n在待排序的元素序列基本有序的前提下，效在待排序的元素序列基本有序的前提下，效率最高的排序方法是率最高的排序方法是 A) 冒泡排序冒泡排序 B) 选择排序选择排序 C) 快速排序快速排序 D) 归并排序归并排序 n希尔排序属于希尔排序属于 A) 交换排序交换排序 B) 归并排序归并排序 C) 选择排序选择排序D) 插入排序插入排序n对长度为对长度为n的线性表进行顺序查找，在最坏的线性表进行顺序查找，在最坏的情况下所需要的比较次数为的情况下所需要的比较次数为ＡＡ) n+1 B) n C) (n+1)/2 D) n/2第109页冒泡排序的方法：冒泡排序的方法：1.1.扫描整个线性表，逐次对相扫描整个线性表，逐次对相邻的两个元素进行比较，若为邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的逆序，则交换；第一趟扫描的结果使最大的元素排到表的最结果使最大的元素排到表的最后后 ；；2.2.除最后一个元素，对剩余的除最后一个元素，对剩余的元素重复上述过程，将次大的元素重复上述过程，将次大的数排到表的倒数第二个位置；数排到表的倒数第二个位置；3.3.重复上述过程；重复上述过程；对于长度为对于长度为n n的线性表，冒泡排的线性表，冒泡排序需要对表扫描序需要对表扫描n-1n-1遍。

遍 例例2：：n个数排序个数排序。