第1讲 _算法与数据结构ppt课件

1、1234算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。1算法的基本特征w 可行性可行性(effectiveness)w 确定性确定性(definiteness)w 有穷性有穷性(finiteness)w 拥有足够的情报拥有足够的情报2算法的基本要素w 算法中对数据的运算和操作算法中对数据的运算和操作l算术运算算术运算:包括加、减、乘、除等）包括加、减、乘、除等）l逻辑运算逻辑运算:包括包括“与与”、“或或”、“非非”等运算）等运算）l关系运算关系运算:包括包括“大于大于”、“小于小于”、“等于等于”、“不等于不等于”等）等）l数据传输数据传输:包括赋值、输入、输出等操作包括赋

2、值、输入、输出等操作w 算法的控制结构算法的控制结构53算法设计的基本方法w 列举法列举法w 归纳法归纳法w 递推递推w 递归递归w 减半递推技术减半递推技术w 回溯法回溯法6算法复杂度：时间复杂度、空间复杂度1算法的时间复杂度w 执行算法所需要的计算工作量执行算法所需要的计算工作量w 与下列因素有关：与下列因素有关：l书写算法的程序设计语言书写算法的程序设计语言l编译产生的机器语言，代码质量编译产生的机器语言，代码质量l机器执行指令的速度机器执行指令的速度l问题的规模问题的规模7问题的规模函数算法的工作量算法的工作量=f(n)算法中基本操作重复执行的频率T(n)，是问题规模n的某个函数f(n

3、)，记作：T(n)=O(f(n)w 记号记号“O”读作读作“大大O”。表示随问题规模。表示随问题规模n的增加，算法执行时间的增长率的增加，算法执行时间的增长率和和f(n)相应增加。相应增加。常见算法复杂度：w O(1)：常数阶常数阶 O(n)：作线性阶作线性阶 O(n2)：平方阶平方阶w O(n3)：立方阶立方阶 O(logn)：对数阶对数阶 O(2n)：指数阶指数阶8nn矩阵相乘算法：时间复杂度为O(n3)。9分析算法的工作量两种方法：w 平均性态平均性态w 最坏情况复杂性最坏情况复杂性102算法的空间复杂度算法的空间复杂度w 算法执行过程中所需的最大存储空间算法执行过程中所需的最大存储空间

4、w 存储量包括以下三部分存储量包括以下三部分l算法程序所占的空间算法程序所占的空间l输入的初始数据所占的存储空间输入的初始数据所占的存储空间l算法执行过程中所要的额外空间算法执行过程中所要的额外空间w 算法空间复杂度可定义为：算法空间复杂度可定义为：S(n)=O(f(n)w 原地工作原地工作(in place)的算法：记作的算法：记作O(1)w 压缩存储技术压缩存储技术11121数据结构研究的主要内容w 数据的逻辑结构数据的逻辑结构w 数据的存储结构数据的存储结构w 对各种数据结构进行的运算对各种数据结构进行的运算2研究数据结构目的w 提高数据处理的速度提高数据处理的速度w 尽量节省在数据处理

5、过程中所占用的计算机存储空间尽量节省在数据处理过程中所占用的计算机存储空间131数据结构研究的主要内容w 数据的逻辑结构数据的逻辑结构w 数据的存储结构数据的存储结构w 对各种数据结构进行的运算对各种数据结构进行的运算2研究数据结构目的w 提高数据处理的速度提高数据处理的速度w 尽量节省在数据处理过程中所占用的计算机存储空间尽量节省在数据处理过程中所占用的计算机存储空间14 1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构A 顺序存储 B 链式存储 线性表栈队树形结构图形结构数据结构的三个方面 153数据结构的定义数据结构的定义w

6、 相互有关联的数据元素的集合相互有关联的数据元素的集合w 数据元素之间的关系可以用前后件关系来描述数据元素之间的关系可以用前后件关系来描述w 一个数据结构应包含以下两方面信息：一个数据结构应包含以下两方面信息：l表示数据元素的信息表示数据元素的信息 l表示各数据元素之间的前后件关系表示各数据元素之间的前后件关系164数据的逻辑结构w 对数据元素之间的逻辑关系的描述对数据元素之间的逻辑关系的描述w 只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关w 两个要素：两个要素：l数据元素的集合，通常记为数据元素的集合，通常记为D；l前后件关

7、系，通常记为前后件关系，通常记为Rw 一个数据结构一个数据结构B可以表示为：可以表示为：B=（D，R）175数据的存储结构w 数据的逻辑结构在计算机存储空间中的存放形式数据的逻辑结构在计算机存储空间中的存放形式w 常用的存储结构：常用的存储结构：l顺序顺序l链式链式l索引索引w 一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其数据处理的效率是不同数据处理的效率是不同18数据结点：用方框表示w 根结点、终端结点根结点、终端结点前后件关系：用有向线段表示基本运算：w 插入运算插入运算w 删除运算删除运算w 查找、分类、

8、合并、分解、复制、修改、查找、分类、合并、分解、复制、修改、19空的数据结构：一个数据元素都没有线性结构w 如果一个非空数据结构满足下列两个条件：如果一个非空数据结构满足下列两个条件：l有且只有一个根结点；有且只有一个根结点；l每一个结点最多有一个前件，也最多有一个后件。每一个结点最多有一个前件，也最多有一个后件。w 常见的线性结构有：线性表、栈与队列、线性链表常见的线性结构有：线性表、栈与队列、线性链表非线性结构w 如果一个数据结构不是线性结构如果一个数据结构不是线性结构w 常见的非线性结构有：树、二叉树、图常见的非线性结构有：树、二叉树、图20211.3.1 线性表的基本概念线性表的基本概

9、念线性表：由n(n0)个相同类型数据元素构成的有限序列：n定义为线性表的表长；n=0 时的线性表被称为空表。称i为在线性表中的位序。例如：w 英文大写字母表英文大写字母表（A，B，C，D，E，F，X，Y，Z）w 同一花色的同一花色的13张扑克牌张扑克牌 l(2,3,4,5,6,7,8,9,10,J,Q,K,A),(21niaaaa22线性表的结构特征w 数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；w 对于一个非空线性表，有且只有一个根结点对于一个非空线性表，有且只有一个根结点a1，它无前件，有且只有一个，它无前

10、件，有且只有一个终端结点终端结点an，它无后件，除根结点与终端结点外，其他所有结点有且只有，它无后件，除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。一个前件，也有且只有一个后件。线性表的存储结构w 顺序存储顺序存储w 链式存储链式存储1.3.1 线性表的基本概念线性表的基本概念231.3.2 线性表的顺序存储结构线性表的顺序存储结构两个基本特点：w 线性表中所有元素所占的存储空间是连续的。线性表中所有元素所占的存储空间是连续的。w 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。存储示意图kiaLocaLoc

11、i*) 1()()(1241.3.3 顺序表的插入运算顺序表的插入运算251.3.4 顺序表的删除运算顺序表的删除运算26顺序表的插入和删除分析顺序表的插入和删除分析插入算法的分析w 假设线性表中含有假设线性表中含有n个数据元素，在进行插入操作时，若假定在个数据元素，在进行插入操作时，若假定在n+1个位置个位置上插入元素的可能性均等，则平均移动元素的个数为：上插入元素的可能性均等，则平均移动元素的个数为：删除算法的分析w 在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：的个数为：分析结论w 顺序存储结构表

12、示的线性表，在做插入或删除操作时，平均需要移动大约顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑删除操作时，这一点需要值得考虑niidlninpnE121)(1112) 1(11niiisninpnE27281.4.1 栈及其基本运算栈及其基本运算1栈的定义w 栈（栈（stack）：一种只允许在表的一端进行插入或删除操作的特殊的线性表）：一种只允许在表的一端进行插入或删除操作的特殊的线性表w 栈顶栈顶(top) ：允许进

13、行插入与删除操作的一端：允许进行插入与删除操作的一端w 栈底栈底(bottom)：不允许插入与删除操作的另一端：不允许插入与删除操作的另一端w 先进后出（先进后出（FILO）或后进先出）或后进先出(LIFO)的线性表的线性表292栈的顺序存储及其运算栈的顺序存储及其运算w top=0：栈空：栈空 top=m：栈满栈满w 栈的基本运算栈的基本运算 l入栈运算入栈运算l退栈运算退栈运算l读栈顶元素读栈顶元素1.4.1 栈及其基本运算栈及其基本运算301.4.2 队列及其基本运算队列及其基本运算1队列的定义w 限定只能在表的一端进行插入和在另一端进行删除操作的线性表限定只能在表的一端进行插入和在另一

14、端进行删除操作的线性表w 队尾队尾(rear)：允许插入的一端：允许插入的一端w 队头队头(front)：允许删除的另一端：允许删除的另一端w 先进先出（先进先出（FIFO）表或后进后出（）表或后进后出（LILO）线性表）线性表w 基本操作基本操作l入队运算：往队列的队尾插入一个元素，队尾指针入队运算：往队列的队尾插入一个元素，队尾指针rear的变化的变化l退队运算：从队列的排头删除一个元素，队头指针退队运算：从队列的排头删除一个元素，队头指针front的变化的变化312循环队列及其运算w 队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，队列存储空间的最后一个位置绕到第一个位置

15、，形成逻辑上的环状空间，供队列循环使用供队列循环使用 w 入队运算入队运算 ：队尾指针加：队尾指针加1，并当，并当rear=m+1时置时置rear=1w 出队运算：队头指针加出队运算：队头指针加1，并当，并当front=m+1时置时置front=11.4.2 队列及其基本运算队列及其基本运算32331.5.1 线性链表的基本概念线性链表的基本概念1线性表顺序存储的缺点w 插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素。素时需要移动大量的数据元素。w 线性表的顺序存储结构下，线性表的存储空

16、间不便于扩充。线性表的顺序存储结构下，线性表的存储空间不便于扩充。w 线性表的顺序存储结构不便于对存储空间的动态分配。线性表的顺序存储结构不便于对存储空间的动态分配。342线性链表w 线性表的链式存储结构线性表的链式存储结构w 物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的链表中的指针链接来实现的w 每个结点由两部分组成：数据域和指针域每个结点由两部分组成：数据域和指针域1.5.1 线性链表的基本概念线性链表的基本概念35双向链表：每个结点设置两个指针w 左指针：指向其前件结点左指针：指向

17、其前件结点w 右指针：指向其后件结点右指针：指向其后件结点1.5.1 线性链表的基本概念线性链表的基本概念361.5.2 线性链表的基本运算线性链表的基本运算插入删除合并分解逆转复制排序查找371在线性链表中查找指定元素w 链表不是随机存取结构链表不是随机存取结构w 从链表的头指针出发，顺着链域从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第逐个结点往下搜索，直至搜索到第i个个结点为止结点为止2线性链表的插入1.5.2 线性链表的基本运算线性链表的基本运算383线性链表的删除与顺序存储相比，链表的优点有：w 插入和删除元素时，不需要移动数据元素，只需要修改指针即可插入和删除元

18、素时，不需要移动数据元素，只需要修改指针即可 1.5.2 线性链表的基本运算线性链表的基本运算391.5.3 栈和队列的链式存储结构栈和队列的链式存储结构 1栈的链式存储结构栈的链式存储结构链栈链栈402队列链式存储结构队列链式存储结构链队列链队列1.5.3 栈和队列的链式存储结构栈和队列的链式存储结构 411.5.4 循环链表及其基本运算循环链表及其基本运算循环链表特点：w 在链表中增加了一个表头结点在链表中增加了一个表头结点w 最后一个结点的指针域指向表头结点，构成了一个环状链最后一个结点的指针域指向表头结点，构成了一个环状链循环链表优点：w 从任一结点出发来访问表中其他所有结点从任一结点

19、出发来访问表中其他所有结点w 空表与非空表的运算的统一空表与非空表的运算的统一 42431.6 树与二叉树树与二叉树1树的定义树的定义w 树树(Tree)是是n(n0)个结点的有限集个结点的有限集T，T为空时称为空树，否则它满足如下为空时称为空树，否则它满足如下两个条件：两个条件：（1）有且仅有一个特定的称为根）有且仅有一个特定的称为根(Root)的结点；的结点；（2）其余的结点可分为）其余的结点可分为m(m0)个互不相交的子集个互不相交的子集T1，T2，T3，Tm，其中每个子集又是一棵树，并称其为子树。其中每个子集又是一棵树，并称其为子树。442树中的基本概念w 父结点与树的根：每个结点最多

20、只允许有一个前件，称为该结点的父结点。父结点与树的根：每个结点最多只允许有一个前件，称为该结点的父结点。没有前件的结点中有一个，称为树的根结点。没有前件的结点中有一个，称为树的根结点。w 子结点与叶子结点：在树结构中，每一个结点可以有多个后件，它们都称子结点与叶子结点：在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。为该结点的子结点。没有后件的结点称为叶子结点。w 结点的度和树的度：一个结点所拥有后件个数称为该结点的度。一棵树中结点的度和树的度：一个结点所拥有后件个数称为该结点的度。一棵树中各个结点度数的最大值叫做这棵树的度。各个结点度数的最大值叫做

21、这棵树的度。w 层和树的深度：树结构是一种层次结构，根结点为第一层，根的子结点为层和树的深度：树结构是一种层次结构，根结点为第一层，根的子结点为第二层，其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数第二层，其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度。叫做此树的深度。1.6 树与二叉树树与二叉树451.6.1 树的基本概念树的基本概念树的特点w （1）树中只有根结点没有前件；）树中只有根结点没有前件；w （2）除根外，其余结点都有且仅一个前件；）除根外，其余结点都有且仅一个前件；w （3）树的结点，可以有零个或多个后件；）树的结点，可以有零个或多个后件；w

22、（4）除根外的其他结点，都存在唯一条从根到该结点的路径；）除根外的其他结点，都存在唯一条从根到该结点的路径；w （5）树是一种分支结构（除根的结点外）每个元素都有且仅有一个直接前）树是一种分支结构（除根的结点外）每个元素都有且仅有一个直接前件，有且仅有零个或多个直接后件。件，有且仅有零个或多个直接后件。树的存储w 用多重链表来表示用多重链表来表示461.6.2 二叉树及其基本性质二叉树及其基本性质1二叉树的定义w 一个二叉树是一个二叉树是n个结点的有限集合（个结点的有限集合（n0），此集合或者是空集（），此集合或者是空集（n=0），），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树

23、的二叉或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成，并且左右子树都是二叉树。树组成，并且左右子树都是二叉树。w 特点：特点：l非空二叉树只有一个根结点；非空二叉树只有一个根结点；l每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。472二叉树的性质w 性质1 在二叉树的第在二叉树的第k层上，最多有层上，最多有 个结点。个结点。w 性质2 深度为深度为m的二叉树最多有个的二叉树最多有个 结点。结点。w 性质3 在任意一棵二叉树中，度数为在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为的结点（即

24、叶子结点）总比度为2的的结点多一个。即：结点多一个。即： 其中，其中，n0表示度数为表示度数为0的结点数，的结点数，n2表示度数为表示度数为2的结点数。的结点数。w 性质4 具有具有n个结点的二叉树的深度至少为个结点的二叉树的深度至少为 ，其中，其中 表示取表示取 的整数部分。的整数部分。)1(21kk12 m120 nn1log2nlog2nn2log1.6.2 二叉树及其基本性质二叉树及其基本性质483满二叉树和完全二叉树满二叉树和完全二叉树w 满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。w 完全二叉树：除最后一层外，

25、每一层上的结点数均达到最大值；在最后一完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。层上只缺少右边的若干结点。1.6.2 二叉树及其基本性质二叉树及其基本性质49性质5 具有n个结点的完全二叉树深度为 。性质6 设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，n给结点进行编号，则对于编号为k（k=1，2，n）的结点有以下结论：若若k=1，则该结点为根结点，它没有父结点；若，则该结点为根结点，它没有父结点；若k1，则该结点的父结点的，则该结点的父结点的编号为编号为INT(k/2)。若若2kn，则编号为，则编号为k的左

26、子结点编号为的左子结点编号为2k；否则该结点无左子结点（显然；否则该结点无左子结点（显然也没有右子结点）。也没有右子结点）。若若2k+1n，则编号为，则编号为k的右子结点编号为的右子结点编号为2k+1；否则该结点无右子结点。；否则该结点无右子结点。1log2n1.6.2 二叉树及其基本性质二叉树及其基本性质501.6.3 二叉树的存储结构二叉树的存储结构普通二叉树w 采用链式存储结构采用链式存储结构w 存储结点由两部分组成：数据域与指针域存储结点由两部分组成：数据域与指针域w 两个指针域：两个指针域：l左指针域左指针域l右指针域右指针域满二叉树与完全二叉树w 采用顺序存储结构采用顺序存储结构5

27、11.6.4 二叉树的遍历二叉树的遍历二叉树的遍历：不重复地访问二叉树中的所有结点 1前序遍历（DLR）w 首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。2中序遍历（LDR）w 首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树右子树时，仍然先遍历左子树，然后访问根

28、结点，最后遍历右子树3后序遍历（LRD）w 首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。52前序遍历：w A、B、D、G、C、E、F中序遍历：w D、G、B、A、E、C、F 后序遍历：w G、D、B、E、F、C、A 1.6.4 二叉树的遍历二叉树的遍历53541.7 查找技术查找技术查找（Searching）：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。查找结果：w 查找

29、成功：找到查找成功：找到w 查找不成功：没找到查找不成功：没找到平均查找长度：查找过程中关键字和给定值比较的平均次数551.7.1 顺序查找顺序查找基本思想：w 从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。查找不成功。平均要与表中一半以上元素进行比较，最坏情况下需要比较n次。下列两种情况下只能采用顺序查找：w 如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储

30、结构如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。还是链式存储结构，都只能用顺序查找。w 即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。561.7.2 二分法查找二分法查找思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。前提：必须在具有顺序存储结构的有序表中进行。查找过程：查找过程：1）若中间项的值等于x,则说

31、明已查到。2）若x小于中间项的值，则在线性表的前半部分查找；3）若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。最坏的情况下，需要比较特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。次。57例：查找元素22过程： 1.7.2 二分法查找二分法查找58591.8.1 交换类排序法交换类排序法基本思想w 两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。直到没有反序的记录为止。方法w 冒泡排序冒泡排序w 快速排序快速排序601.冒泡排序冒泡排序 基本思想

32、w 对存放原始数据的数组，按从后往前的方向进行多次扫描，当发现相邻两对存放原始数据的数组，按从后往前的方向进行多次扫描，当发现相邻两个数据的次序与排序要求的个数据的次序与排序要求的“递增次序递增次序”不符合时，即将这两个数据进行不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。性能分析w 假设线性表的长度假设线性表的长度n，则在最坏情况下，需要的比较次数为，则在最坏情况下，需要的比较次数为n(n-1)/2。611.冒泡排序冒泡排序 622快速排序快速排序基本思想w 任取待排序序列中的某个元

33、素作为基准（一般取第一个元素），通过一趟任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。后分别对两个子序列继续进行排序，直至整个序列有序。快速排序的平均时间复杂度为O(nlog2n)。632快速排序快速排序641.8.2 插入类排序法插入类排序法基本思想：w 每次将一个待排序的

34、记录，按其关键字大小插入到前面已经排好序的子序每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。列中的适当位置，直到全部记录插入完成为止。方法:w 简单插入排序简单插入排序w 希尔排序希尔排序651简单插入排序法简单插入排序法基本思想：w 把把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排

35、序码进行比较，将它插第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。入到有序表中的适当位置，使之成为新的有序表。在最坏的情况下，需要n(n-1)/2次比较。661简单插入排序法简单插入排序法672希尔排序希尔排序基本思想w 先将整个待排元素序列分割成若干个子序列（由相隔某个增量先将整个待排元素序列分割成若干个子序列（由相隔某个增量h的元素组成的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序

36、在元素基本时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。有序的情况下（接近最好情况），效率是很高的。w 增量序列一般取增量序列一般取 ，其中，其中n为待排序序列的长度为待排序序列的长度在最坏情况下，希尔排序的时间复杂度为 )log, 2 , 1(2/2nknhki)(5 . 1nO682希尔排序希尔排序691.8.3 选择类排序法选择类排序法基本思想：w 每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子序列的最后，直到全部记录排序完毕。序列的最后，直到全

37、部记录排序完毕。方法：w 简单选择排序简单选择排序w 堆排序堆排序701简单选择排序法简单选择排序法 基本思想：w 扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。剩下的子表采用同样的方法，直到子表空为止。最坏情况下，需要比较n(n-1)/2次。711简单选择排序法简单选择排序法 722堆排序法堆排序法堆的定义具有具有n个元素的序列，当且仅当满足个元素的序列，当且仅当满足 或或 时称之为堆。称为大根堆；称为小根堆时称之为堆。称为大根堆；称为小根堆 。122iiiihhhh1

38、22iiiihhhh732堆排序法堆排序法建堆w 在建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若在建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。这个调整过程一直做到所有子树均为堆为止。堆排序w （1）首先将一个无序序列建成堆。）首先将一个无序序列建成堆。w （2）然后将堆顶元素）然后将堆顶元素(序列中的最大项序列中的最大项)与堆中最后一个元素交换与堆中最后一个元素交换(最大项应最大项应该在序

39、列的最后该在序列的最后)。不考虑已经换到最后的那个元素，只考虑前。不考虑已经换到最后的那个元素，只考虑前n-1个元素个元素构成的子序列，将该子序列调整为堆。构成的子序列，将该子序列调整为堆。w 反复做步骤（反复做步骤（2），直到剩下的子序列空为止。），直到剩下的子序列空为止。在最坏情况下，堆排序法需要比较的次数为O(nlog2n)。74各种排序法比较各种排序法比较 7576【例1-1】问题处理方案的正确而完整的描述称为 。答案 算法历年真题历年真题 77【例1-3】算法的时间复杂度是指_。A）执行算法程序所需要的时间）执行算法程序所需要的时间B）算法程序的长度）算法程序的长度C）算法执行过程中

40、所需要的基本运算次数）算法执行过程中所需要的基本运算次数D）算法程序中的指令条数）算法程序中的指令条数答案C历年真题历年真题 78【例1-4】算法的空间复杂度是指_。A）算法程序的长度）算法程序的长度B）算法程序中的指令条数）算法程序中的指令条数C）算法程序所占的存储空间）算法程序所占的存储空间D）算法执行过程中所需要的存储空间）算法执行过程中所需要的存储空间答案D历年真题历年真题 79【例1-5】下列叙述中正确的是 。A）一个算法的空间复杂度大，则其时间复杂度也必定大）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小）一个算法的空间复杂度大，则其

41、时间复杂度必定小C）一个算法的时间复杂度大，则其空间可复杂度必定小）一个算法的时间复杂度大，则其空间可复杂度必定小D）上述三种说法都不对）上述三种说法都不对答案 D历年真题历年真题 80【例1-6】下列叙述中正确的是 。 A）一个逻辑数据结构只能有一种存储结构）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结

42、构影响数据处理）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率的效率答案 D历年真题历年真题 81【例1-7】数据结构分为逻辑结构和存储结构，循环队列属于 结构。答案 逻辑历年真题历年真题 82【例1-9】下列叙述中正确的是_。A）线性链表是线性表的链式存储结构）线性链表是线性表的链式存储结构B）栈与队列是非线性结构）栈与队列是非线性结构C）双向链表是非线性结构）双向链表是非线性结构D）只有根结点的二叉树是线性结构）只有根结点的二叉树是线性结构答案 A历年真题历年真题 83【例1-10】某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为200，则第12个元素的存储

43、地址为 。A）248B）247C）246D）244答案 D历年真题历年真题 84【例1-11】在长度为n的顺序表的第i（1in+1）个位置上插入一个元素，元素的移动次数为 。A）n-i+1B）n-iC）iD）i-1答案 A历年真题历年真题 85【例1-12】在一个长度为n的顺序表中，删除第i（1in）个元素时，需要移动的元素个数为 。A）n-i+1B）n-iC）iD）i-1答案 B历年真题历年真题 86【例1-13】以下描述的中，不是线性表的顺序存储结构的特征的是 。A）不便于插入和删除）不便于插入和删除B）需要连续的存储空间）需要连续的存储空间C）可随机访问）可随机访问D）需另外开辟空间来保

44、存元素之间的关系）需另外开辟空间来保存元素之间的关系答案 D历年真题历年真题 87【例1-14】下列关于栈的描述中错误的是_。A）栈是先进后出的线性表）栈是先进后出的线性表B）栈只能顺序存储）栈只能顺序存储C）栈具有记忆作用）栈具有记忆作用D）对栈的插入与删除操作中，不需要改变栈底指针）对栈的插入与删除操作中，不需要改变栈底指针答案 B历年真题历年真题 88【例1-15】栈和队列的共同点是_。A）都是先进先出）都是先进先出B）都是先进后出）都是先进后出C）只允许在端点处插入和删除元素）只允许在端点处插入和删除元素D）没有共同点）没有共同点答案 C历年真题历年真题 89【例1-16】栈的输入序列

45、为1，2，3，n-1，n，输出序列的第1个元素为n，则第个输出元素为_。A）n-i+1B）n-1C）iD）哪个元素无所谓）哪个元素无所谓答案 A历年真题历年真题 90【例1-17】一个队列的入队序列是1、2、3、4，则队列的输出序列是 。A）4、3、2、1B）1、2、3、4C）1、4、3、2D）3、2、4、1答案 B历年真题历年真题 91【例1-18】队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。允许插入的一端称作_。答案 队尾历年真题历年真题 92【例1-19】下列对于线性链表的描述中正确的是 。A）存储空间不一定是连续，且各元素的存储顺序是任意的）存储空间不一定是连续，且

46、各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且各前件元素一定存储在后件元素的前面）存储空间必须连续，且各前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的）存储空间必须连续，且各元素的存储顺序是任意的 答案 A历年真题历年真题 93【例1-20】下列叙述中，错误的是 。A）线性表是由）线性表是由n个数据元素组成的一个有限序列个数据元素组成的一个有限序列B）线性表是一种线性结构。）线性表是一种线性结构。C）线性表的所有结点有且只有一个前件和一

47、个后件）线性表的所有结点有且只有一个前件和一个后件D）线性表可以是空表。）线性表可以是空表。答案 C历年真题历年真题 94【例1-21】下列描述的不是链表的优点是_。A）逻辑上相邻的结点物理上不必邻接）逻辑上相邻的结点物理上不必邻接B）插入、删除运算操作方便，不必移动结点）插入、删除运算操作方便，不必移动结点C）所需存储空间比线性表节省）所需存储空间比线性表节省D）无需事先估计存储空间的大小）无需事先估计存储空间的大小答案 C历年真题历年真题 95【例1-22】某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素。删除运算是指删除表头第一个元素，那么采用 存储方式最节省运算时间。A）仅有尾指针的单向循环链表）仅有尾指针的单向循环链表B）仅有头指针的单向循环链表）仅有头指针的单向循环链表C）单向链表）单向链表D）顺序存储）顺序存储答案 A历年真题历年真题 96【例1-23】一棵二叉树第六层（根结点为第一层）的结点数最多为 个。答案 32历年真题历年真题 97【例1-24】深度为5的二叉树至多有_个结点。A）16B）32C）31D）10答案 C历年真题历年真题 98【例1-25】设树T的度为4，