计算机二级学习基础PPT课件.ppt

二级公共基础知识 第一章数据结构基础 2 内容提要 算法 算法的基本概念 算法复杂度数据结构的基本概念 什么是数据结构 数据结构的图形表示 线性结构与非线性结构线性表及其顺序存储结构 线性表的基本概念 顺序存储结构 插入运算 删除运算栈和队列 栈及其基本运算 队列及其基本运算线性链表 基本概念 基本运算 循环链表及其基本运算树与二叉树 树的基本概念 二叉树及其基本性质 二叉树的存储结构 二叉树的遍历查找技术 顺序查找 二分法查找排序技术 交换类排序法 插入类排序法 选择类排序法 1 1算法 4 1 1 1算法的基本概念 算法是解题方案的准确而完整的描述 它不等于程序 也不等计算方法 1 算法的基本特征可行性 effectiveness 确定性 definiteness 有穷性 finiteness 拥有足够的情报2 算法的基本要素算法中对数据的运算和操作算术运算 包括加 减 乘 除等 逻辑运算 包括 与 或 非 等运算 关系运算 包括 大于 小于 等于 不等于 等 数据传输 包括赋值 输入 输出等操作算法的控制结构 5 1 1 1算法的基本概念 3 算法设计的基本方法列举法归纳法递推递归减半递推技术回溯法 6 1 1 2算法复杂度 算法复杂度 时间复杂度 空间复杂度1 算法的时间复杂度执行算法所需要的计算工作量与下列因素有关 书写算法的程序设计语言编译产生的机器语言 代码质量机器执行指令的速度问题的规模 7 1 1 2算法复杂度 问题的规模函数算法的工作量 f n 算法中基本操作重复执行的频率T n 是问题规模n的某个函数f n 记作 T n O f n 记号 O 读作 大O 表示随问题规模n的增加 算法执行时间的增长率和f n 相应增加 常见算法复杂度 O 1 常数阶O n 作线性阶O n2 平方阶O n3 立方阶O logn 对数阶O 2n 指数阶 8 1 1 2算法复杂度 n n矩阵相乘算法 时间复杂度为O n3 9 1 1 2算法复杂度 分析算法的工作量两种方法 平均性态最坏情况复杂性 10 1 1 2算法复杂度 2 算法的空间复杂度算法执行过程中所需的最大存储空间存储量包括以下三部分算法程序所占的空间输入的初始数据所占的存储空间算法执行过程中所要的额外空间算法空间复杂度可定义为 S n O f n 原地工作 inplace 的算法 记作O 1 压缩存储技术 1 2数据结构的基本概念 12 1 2 1什么是数据结构 1 数据结构研究的主要内容数据的逻辑结构数据的存储结构对各种数据结构进行的运算2 研究数据结构目的提高数据处理的速度尽量节省在数据处理过程中所占用的计算机存储空间 13 1 2 1什么是数据结构 1 数据结构研究的主要内容数据的逻辑结构数据的存储结构对各种数据结构进行的运算2 研究数据结构目的提高数据处理的速度尽量节省在数据处理过程中所占用的计算机存储空间 14 1 2 1什么是数据结构 15 1 2 1什么是数据结构 3 数据结构的定义相互有关联的数据元素的集合数据元素之间的关系可以用前后件关系来描述一个数据结构应包含以下两方面信息 表示数据元素的信息表示各数据元素之间的前后件关系 16 1 2 1什么是数据结构 4 数据的逻辑结构对数据元素之间的逻辑关系的描述只抽象地反映数据元素之间的逻辑关系 与计算机中的存储无关两个要素 数据元素的集合 通常记为D 前后件关系 通常记为R一个数据结构B可以表示为 B D R 17 1 2 1什么是数据结构 5 数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式常用的存储结构 顺序链式索引一种数据结构可根据需要采用不同的存储结构 采用不同的存储结构 其数据处理的效率是不同 18 1 2 2数据结构的图形表示 数据结点 用方框表示根结点 终端结点前后件关系 用有向线段表示基本运算 插入运算删除运算查找 分类 合并 分解 复制 修改 19 1 2 3线性结构与非线性结构 空的数据结构 一个数据元素都没有线性结构如果一个非空数据结构满足下列两个条件 有且只有一个根结点 每一个结点最多有一个前件 也最多有一个后件 常见的线性结构有 线性表 栈与队列 线性链表非线性结构如果一个数据结构不是线性结构常见的非线性结构有 树 二叉树 图 1 3线性表及其顺序存储结构 21 1 3 1线性表的基本概念 线性表 由n n 0 个相同类型数据元素构成的有限序列 n定义为线性表的表长 n 0时的线性表被称为空表 称i为在线性表中的位序 例如 英文大写字母表 A B C D E F X Y Z 同一花色的13张扑克牌 2 3 4 5 6 7 8 9 10 J Q K A 22 1 3 1线性表的基本概念 线性表的结构特征数据元素在表中的位置由序号决定 数据元素之间的相对位置是线性的 对于一个非空线性表 有且只有一个根结点a1 它无前件 有且只有一个终端结点an 它无后件 除根结点与终端结点外 其他所有结点有且只有一个前件 也有且只有一个后件 线性表的存储结构顺序存储链式存储 23 1 3 2线性表的顺序存储结构 两个基本特点 线性表中所有元素所占的存储空间是连续的 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 存储示意图 24 1 3 3顺序表的插入运算 25 1 3 4顺序表的删除运算 26 顺序表的插入和删除分析 插入算法的分析假设线性表中含有n个数据元素 在进行插入操作时 若假定在n 1个位置上插入元素的可能性均等 则平均移动元素的个数为 删除算法的分析在进行删除操作时 若假定删除每个元素的可能性均等 则平均移动元素的个数为 分析结论顺序存储结构表示的线性表 在做插入或删除操作时 平均需要移动大约一半的数据元素 当线性表的数据元素量较大 并且经常要对其做插入或删除操作时 这一点需要值得考虑 1 4栈和队列 28 1 4 1栈及其基本运算 1 栈的定义栈 stack 一种只允许在表的一端进行插入或删除操作的特殊的线性表栈顶 top 允许进行插入与删除操作的一端栈底 bottom 不允许插入与删除操作的另一端先进后出 FILO 或后进先出 LIFO 的线性表 29 1 4 1栈及其基本运算 2 栈的顺序存储及其运算top 0 栈空top m 栈满栈的基本运算入栈运算退栈运算读栈顶元素 30 1 4 2队列及其基本运算 1 队列的定义限定只能在表的一端进行插入和在另一端进行删除操作的线性表队尾 rear 允许插入的一端队头 front 允许删除的另一端先进先出 FIFO 表或后进后出 LILO 线性表基本操作入队运算 往队列的队尾插入一个元素 队尾指针rear的变化退队运算 从队列的排头删除一个元素 队头指针front的变化 31 1 4 2队列及其基本运算 2 循环队列及其运算队列存储空间的最后一个位置绕到第一个位置 形成逻辑上的环状空间 供队列循环使用入队运算 队尾指针加1 并当rear m 1时置rear 1出队运算 队头指针加1 并当front m 1时置front 1 1 5线性链表 33 1 5 1线性链表的基本概念 1 线性表顺序存储的缺点插入或删除的运算效率很低 在顺序存储的线性表中 插入或删除数据元素时需要移动大量的数据元素 线性表的顺序存储结构下 线性表的存储空间不便于扩充 线性表的顺序存储结构不便于对存储空间的动态分配 34 1 5 1线性链表的基本概念 2 线性链表线性表的链式存储结构物理存储单元上非连续 非顺序的存储结构 数据元素的逻辑顺序是通过链表中的指针链接来实现的每个结点由两部分组成 数据域和指针域 35 1 5 1线性链表的基本概念 双向链表 每个结点设置两个指针左指针 指向其前件结点右指针 指向其后件结点 36 1 5 2线性链表的基本运算 插入删除合并分解逆转复制排序查找 37 1 5 2线性链表的基本运算 1 在线性链表中查找指定元素链表不是随机存取结构从链表的头指针出发 顺着链域next逐个结点往下搜索 直至搜索到第i个结点为止2 线性链表的插入 38 1 5 2线性链表的基本运算 3 线性链表的删除与顺序存储相比 链表的优点有 插入和删除元素时 不需要移动数据元素 只需要修改指针即可 39 1 5 3栈和队列的链式存储结构 1 栈的链式存储结构 链栈 40 1 5 3栈和队列的链式存储结构 2 队列链式存储结构 链队列 41 1 5 4循环链表及其基本运算 循环链表特点 在链表中增加了一个表头结点最后一个结点的指针域指向表头结点 构成了一个环状链循环链表优点 从任一结点出发来访问表中其他所有结点空表与非空表的运算的统一 42 1 6树与二叉树 1 树的定义树 Tree 是n n 0 个结点的有限集T T为空时称为空树 否则它满足如下两个条件 1 有且仅有一个特定的称为根 Root 的结点 2 其余的结点可分为m m 0 个互不相交的子集T1 T2 T3 Tm 其中每个子集又是一棵树 并称其为子树 43 1 6树与二叉树 2 树中的基本概念父结点与树的根 每个结点最多只允许有一个前件 称为该结点的父结点 没有前件的结点中有一个 称为树的根结点 子结点与叶子结点 在树结构中 每一个结点可以有多个后件 它们都称为该结点的子结点 没有后件的结点称为叶子结点 结点的度和树的度 一个结点所拥有后件个数称为该结点的度 一棵树中各个结点度数的最大值叫做这棵树的度 层和树的深度 树结构是一种层次结构 根结点为第一层 根的子结点为第二层 其余各结点的层数逐层由上而下计算 一棵树中结点的最大层数叫做此树的深度 44 1 6 1树的基本概念 树的特点 1 树中只有根结点没有前件 2 除根外 其余结点都有且仅一个前件 3 树的结点 可以有零个或多个后件 4 除根外的其他结点 都存在唯一条从根到该结点的路径 5 树是一种分支结构 除根的结点外 每个元素都有且仅有一个直接前件 有且仅有零个或多个直接后件 树的存储用多重链表来表示 45 1 6 2二叉树及其基本性质 1 二叉树的定义一个二叉树是n个结点的有限集合 n 0 此集合或者是空集 n 0 或者是由一个根结点及两棵互不相交的 分别称为左子树和右子树的二叉树组成 并且左右子树都是二叉树 特点 非空二叉树只有一个根结点 每一个结点最多有两棵子树 且分别称为该结点的左子树与右子树 46 1 6 2二叉树及其基本性质 2 二叉树的性质性质1在二叉树的第k层上 最多有个结点 性质2深度为m的二叉树最多有个结点 性质3在任意一棵二叉树中 度数为0的结点 即叶子结点 总比度为2的结点多一个 即 其中 n0表示度数为0的结点数 n2表示度数为2的结点数 性质4具有n个结点的二叉树的深度至少为 其中表示取的整数部分 47 1 6 2二叉树及其基本性质 3 满二叉树和完全二叉树满二叉树 除最后一层外 每一层上的所有结点都有两个子结点 完全二叉树 除最后一层外 每一层上的结点数均达到最大值 在最后一层上只缺少右边的若干结点 48 1 6 2二叉树及其基本性质 性质5具有n个结点的完全二叉树深度为 性质6设完全二叉树共有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 否则该结点无右子结点 49 1 6 3二叉树的存储结构 普通二叉树采用链式存储结构存储结点由两部分组成 数据域与指针域两个指针域 左指针域右指针域满二叉树与完全二叉树采用顺序存储结构 50 1 6 4二叉树的遍历 二叉树的遍历 不重复地访问二叉树中的所有结点1 前序遍历 DLR 首先访问根结点 然后遍历左子树 最后遍历右子树 并且 在遍历左右子树时 仍然先访问根结点 然后遍历左子树 最后遍历右子树 2 中序遍历 LDR 首先遍历左子树 然后访问根结点 最后遍历右子树 并且 在遍历左 右子树时 仍然先遍历左子树 然后访问根结点 最后遍历右子树3 后序遍历 LRD 首先遍历左子树 然后遍历右子树 最后访问根结点 并且 在遍历左 右子树时 仍然先遍历左子树 然后遍历右子树 最后访问根结点 51 1 6 4二叉树的遍历 前序遍历 A B D G C E F中序遍历 D G B A E C F后序遍历 G D B E F C A 1 7查找技术 53 1 7查找技术 查找 Searching 根据给定的某个值 在查找表中确定一个其关键字等于给定值的数据元素 查找结果 查找成功 找到查找不成功 没找到平均查找长度 查找过程中关键字和给定值比较的平均次数 54 1 7 1顺序查找 基本思想 从表中的第一个元素开始 将给定的值与表中逐个元素的关键字进行比较 直到两者相符 查到所要找的元素为止 否则就是表中没有要找的元素 查找不成功 平均要与表中一半以上元素进行比较 最坏情况下需要比较n次 下列两种情况下只能采用顺序查找 如果线性表是无序表 即表中的元素是无序的 则不管是顺序存储结构还是链式存储结构 都只能用顺序查找 即使是有序线性表 如果采用链式存储结构 也只能用顺序查找 55 1 7 2二分法查找 思想 先确定待查找记录所在的范围 然后逐步缩小范围 直到找到或确认找不到该记录为止 前提 必须在具有顺序存储结构的有序表中进行 查找过程 1 若中间项的值等于x 则说明已查到 2 若x小于中间项的值 则在线性表的前半部分查找 3 若x大于中间项的值 则在线性表的后半部分查找 特点 比顺序查找方法效率高 最坏的情况下 需要比较log2n次 56 1 7 2二分法查找 例 查找元素22过程 1 8排序技术 58 1 8 1交换类排序法 基本思想两两比较待排序记录的关键字 发现两个记录的次序相反时即进行交换 直到没有反序的记录为止 方法冒泡排序快速排序 59 1 冒泡排序 基本思想对存放原始数据的数组 按从后往前的方向进行多次扫描 当发现相邻两个数据的次序与排序要求的 递增次序 不符合时 即将这两个数据进行互换 这样 较小的数据就会逐单元向前移动 好象气泡向上浮起一样 性能分析假设线性表的长度n 则在最坏情况下 需要的比较次数为n n 1 2 60 1 冒泡排序 61 2 快速排序 基本思想任取待排序序列中的某个元素作为基准 一般取第一个元素 通过一趟排序 将待排元素分为左右两个子序列 左子序列元素的排序码均小于或等于基准元素的排序码 右子序列的排序码则大于基准元素的排序码 然后分别对两个子序列继续进行排序 直至整个序列有序 快速排序的平均时间复杂度为O nlog2n 62 2 快速排序 63 1 8 2插入类排序法 基本思想 每次将一个待排序的记录 按其关键字大小插入到前面已经排好序的子序列中的适当位置 直到全部记录插入完成为止 方法 简单插入排序希尔排序 64 1 简单插入排序法 基本思想 把n个待排序的元素看成为一个有序表和一个无序表 开始时有序表中只包含一个元素 无序表中包含有n 1个元素 排序过程中每次从无序表中取出第一个元素 把它的排序码依次与有序表元素的排序码进行比较 将它插入到有序表中的适当位置 使之成为新的有序表 在最坏的情况下 需要n n 1 2次比较 65 1 简单插入排序法 66 2 希尔排序 基本思想先将整个待排元素序列分割成若干个子序列 由相隔某个增量h的元素组成的 分别进行直接插入排序 待整个序列中的元素基本有序 增量足够小 时 再对全体元素进行一次直接插入排序 因为直接插入排序在元素基本有序的情况下 接近最好情况 效率是很高的 增量序列一般取 其中n为待排序序列的长度在最坏情况下 希尔排序的时间复杂度为 67 2 希尔排序 68 1 8 3选择类排序法 基本思想 每一趟从待排序的记录中选出关键字最小的记录 顺序放在已排好序的子序列的最后 直到全部记录排序完毕 方法 简单选择排序堆排序 69 1 简单选择排序法 基本思想 扫描整个线性表 从中选出最小的元素 将它交换到表的最前面 然后对剩下的子表采用同样的方法 直到子表空为止 最坏情况下 需要比较n n 1 2次 70 1 简单选择排序法 71 2 堆排序法 堆的定义具有n个元素的序列 当且仅当满足 或 时称之为堆 称为大根堆 称为小根堆 72 2 堆排序法 建堆在建堆的过程中 总是将根结点值与左 右子树的根结点值进行比较 若不满足堆的条件 则将左 右子树根结点值中的大者与根结点值进行交换 这个调整过程一直做到所有子树均为堆为止 堆排序 1 首先将一个无序序列建成堆 2 然后将堆顶元素 序列中的最大项 与堆中最后一个元素交换 最大项应该在序列的最后 不考虑已经换到最后的那个元素 只考虑前n 1个元素构成的子序列 将该子序列调整为堆 反复做步骤 2 直到剩下的子序列空为止 在最坏情况下 堆排序法需要比较的次数为O nlog2n 73 各种排序法比较 典型考题分析 75 例1 1 问题处理方案的正确而完整的描述称为 2005年4月 答案算法 76 例1 2 算法复杂度主要包括时间复杂度和复杂度 2005年9月 答案空间 77 例1 3 算法的时间复杂度是指 A 执行算法程序所需要的时间B 算法程序的长度C 算法执行过程中所需要的基本运算次数D 算法程序中的指令条数答案C 78 例1 4 算法的空间复杂度是指 A 算法程序的长度B 算法程序中的指令条数C 算法程序所占的存储空间D 算法执行过程中所需要的存储空间答案D 79 例1 5 下列叙述中正确的是 2006年9月 A 一个算法的空间复杂度大 则其时间复杂度也必定大B 一个算法的空间复杂度大 则其时间复杂度必定小C 一个算法的时间复杂度大 则其空间可复杂度必定小D 上述三种说法都不对答案D 80 例1 6 下列叙述中正确的是 2005年9月 A 一个逻辑数据结构只能有一种存储结构B 数据的逻辑结构属于线性结构 存储结构属于非线性结构C 一个逻辑数据结构可以有多种存储结构 且各种存储结构不影响数据处理的效率D 一个逻辑数据结构可以有多种存储结构 且各种存储结构影响数据处理的效率答案D 81 例1 7 数据结构分为逻辑结构和存储结构 循环队列属于结构 2005年9月 答案逻辑 82 例1 8 数据结构分为线性结构和非线性结构 带链的队列属于 2006年9月 答案线性结构 83 例1 9 下列叙述中正确的是 2006年4月 A 线性链表是线性表的链式存储结构B 栈与队列是非线性结构C 双向链表是非线性结构D 只有根结点的二叉树是线性结构答案A 84 例1 10 某线性表采用顺序存储结构 每个元素占4个存储单元 首地址为200 则第12个元素的存储地址为 A 248B 247C 246D 244答案D 85 例1 11 在长度为n的顺序表的第i 1 i n 1 个位置上插入一个元素 元素的移动次数为 A n i 1B n iC iD i 1答案A 86 例1 12 在一个长度为n的顺序表中 删除第i 1 i n 个元素时 需要移动的元素个数为 A n i 1B n iC iD i 1答案B 87 例1 13 以下描述的中 不是线性表的顺序存储结构的特征的是 A 不便于插入和删除B 需要连续的存储空间C 可随机访问D 需另外开辟空间来保存元素之间的关系答案D 88 例1 14 下列关于栈的描述中错误的是 2005年4月 A 栈是先进后出的线性表B 栈只能顺序存储C 栈具有记忆作用D 对栈的插入与删除操作中 不需要改变栈底指针答案B 89 例1 15 栈和队列的共同点是 A 都是先进先出B 都是先进后出C 只允许在端点处插入和删除元素D 没有共同点答案C 90 例1 16 栈的输入序列为1 2 3 n 1 n 输出序列的第1个元素为n 则第 个输出元素为 A n i 1B n 1C iD 哪个元素无所谓答案A 91 例1 17 一个队列的入队序列是1 2 3 4 则队列的输出序列是 A 4 3 2 1B 1 2 3 4C 1 4 3 2D 3 2 4 1答案B 92 例1 18 队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表 允许插入的一端称作 答案队尾 93 例1 19 下列对于线性链表的描述中正确的是 2005年4月 A 存储空间不一定是连续 且各元素的存储顺序是任意的B 存储空间不一定是连续 且前件元素一定存储在后件元素的前面C 存储空间必须连续 且各前件元素一定存储在后件元素的前面D 存储空间必须连续 且各元素的存储顺序是任意的答案A 94 例1 20 下列叙述中 错误的是 A 线性表是由n个数据元素组成的一个有限序列B 线性表是一种线性结构 C 线性表的所有结点有且只有一个前件和一个后件D 线性表可以是空表 答案C 95 例1 21 下列描述的不是链表的优点是 A 逻辑上相邻的结点物理上不必邻接B 插入 删除运算操作方便 不必移动结点C 所需存储空间比线性表节省D 无需事先估计存储空间的大小答案C 96 例1 22 某线性表最常用的运算是插入和删除 插入运算是指在表尾插入一个新元素 删除运算是指删除表头第一个元素 那么采用存储方式最节省运算时间 A 仅有尾指针的单向循环链表B 仅有头指针的单向循环链表C 单向链表D 顺序存储答案A 97 例1 23 一棵二叉树第六层 根结点为第一层 的结点数最多为个 2005年9月 答案32 98 例1 24 深度为5的二叉树至多有 个结点 A 16B 32C 31D 10答案C 99 例1 25 设树T的度为4 其中度为1 2 3 4的结点个数分别为4 2 1 1 则T中的叶子结点为 A 8B 7C 6D 5答案A 100 例1 26 某二叉树中度为2的结点有18个 则该二叉树中有个叶子结点 2005年4月 答案19 101 例1 27 具有88个结点的二叉树 其深度至少为 答案7 102 例1 28 在深度为7的满二叉树中 叶子结点的个数为 2006年4月 A 32B 31C 64D 63答案C 103 例1 29 设一棵完全二叉树共有700个结点 则在该二叉树中有 个叶子结点 答案350 104 例1 30 对如图1 30所示的二叉树 进行后序遍历的结果为 2006年4月 A ABCDEFB DBEAFCC ABDECFD DEBFCA答案D 105 例1 31 假设一棵二叉树的后序遍历序列为DGJHEBIFCA 中序遍历序列为DBGEHJACI