计算机2级C公共基础知识PPT课件

计算机等级考试公共基础知识 温俊香 第2页 计算机二级考试公共基础知识大纲 数据结构与算法程序设计基础软件工程基础数据库设计基础 这四个方面在试卷中出现的情况是 选择题10个 20分 填空题5个 10分 总分值占到了试卷卷面分的30 是一个不小的比例 第3页 计算机二级考试公共基础知识试卷分析 第4页 算法 算法的基本概念2 算法复杂度的概念和意义 一 基本数据结构与算法 数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术 对于等级考试 这个部分的考核重点主要在算法和数据结构的基本概念 二叉树 遍历 结点 还有排序和查找考试中也经常会涉及到 第5页 算法的定义对解题方案准确而完整的描述称为算法 算法是程序设计的核心 算法的基本概念 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则 通俗点说 就是计算机解题的过程 计算的方法 在这个过程中 无论是形成解题思路 推理实现的算法 还是编写程序 操作实现的算法 都是在实施某种算法 例 n个数从大到小进行排序 有多种排序方法 常用的有冒泡排序 选择排序等 算法不等于程序 也不等计算机方法 程序的编制不可能优于算法的设计 讲课说课 第6页 2 算法的基本特征一个算法应该具有以下五个重要的特征 有穷性确定性输入输出可行性 拥有足够的情报 第7页 算法与计算机程序算法 是一组逻辑步骤程序 用计算机语言描述的算法 3 算法的表示 INPUTrS 3 14 r rPTINTS 问题 输入园的半径 计算园的面积 一个算法的表示需要使用一些语言形式 传统的算法 图形法 如 流程图 和N S图目前常用的方法 使用伪码描述算法 第8页 冒泡排序的方法 1 扫描整个线性表 逐次对相邻的两个元素进行比较 若为逆序 则交换 第一趟扫描的结果使最大的元素排到表的最后 2 除最后一个元素 对剩余的元素重复上述过程 将次大的数排到表的倒数第二个位置 3 重复上述过程 对于长度为n的线性表 冒泡排序需要对表扫描n 1遍 算法举例 n个数排序 第9页 4 算法的两个基本要素 基本运算和操作算术运算关系运算逻辑运算数据传输 控制结构顺序选择循环 一是对数据对象的运算和操作 二是算法的控制结构 算法基本设计方法 列举法 归纳法 递推 递归 减斗递推技术 回溯法 第10页 5 算法的复杂度评价一个算法优劣的主要标准是算法的执行效率和存储需求 时间复杂度 执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度 执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积 一个算法在计算机存储器上所占用的存储空间 包括存储算法本身所占用的存储空间 算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分 第11页 1 在计算机中 算法是指 A 查询方法B 加工方法C 解题方案的准确而完整的描述D 排序方法 2 下列叙述中正确的是 07年4月 A 算法的效率只与问题的规模有关 而与数据的存储结构无关B 算法的时间复杂度是指执行算法所需要的计算工作量C 数据的逻辑结构与存储结构是一一对应的D 算法的时间复杂度与空间复杂度一定相关 3 算法的有穷性是指 08年4月 A 算法程序的运行时间是有限的B 算法程序所处理的数据量是有限的C 算法程序的长度是有限的D 算法只能被有限的用户使用 c B 算法习题 A 第12页 4 算法的时问复杂度是指 2010年3月 A 算法的执行时间B 算法所处理的数据量C 算法程序中的语句或指令条数D 算法在执行过程中所需要的基本运算次数 5 算法的空间复杂度是指 09年9月 A 算法在执行过程中所需要的计算机存储空间B 算法所处理的数据量C 算法程序中的语句或指令条数D 算法在执行过程中所需要的临时工作单元数 6 下列叙述中正确的是 06年9月 A 一个算法的空间复杂度大 则其时间复杂度也必定大B 一个算法的空间复杂度大 则其时间复杂度必定小C 一个算法的时间复杂度大 则其空间复杂度必定小D 上述三种说法都不对 D 计算工作量 A D 算法的时间复杂度是指A 执行算法程序所需要的时间B 算法程序的长度C 算法执行过程中所需要的基本运算次数D 算法程序中的指令条数算法的基本特征是可行性 确定性 1 和拥有足够的情报 算法的空间复杂度是指A 算法程序的长度B 算法程序中的指令条数C 算法程序所占的存储空间D 执行过程中所需要的存储空间在计算机中 算法是指A 加工方法B 解题方案的准确而完整的描述C 排序方法D 查询方法 例题讲解 有穷性 算法分析的目的是A 找出数据结构的合理性B 找出算法中输入和输出之间的关系C 分析算法的易懂性和可靠性D 分析算法的效率以求改进算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 1 时间复杂度和空间复杂度 第15页 计算机在进行数据处理时 实际需要处理的数据元素一般有很多 而这些大量的数据元素都需要存放在计算机中 因此 大量的数据元素在计算机中如何组织 以便提高数据处理的效率 并且节省计算机的存储空间 这是进行数据处理的关键问题 二 数据结构 程序 算法 数据结构 数据结构是指相互有关联的数据元素的集合 一般来说 人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素 对于具有不同特征的数据元素总是分别进行处理 一般情况下 在具有相同特征的数据元素集合中 各个数据元素之间存在有某种关系 即联系 这种关系反映了该集合中的数据元素所固有的一种结构 超市的物品如何存放才好找且节省空间呢 第16页 二 数据结构 数据结构是指相互有关联的数据元素的集合 数据结构是研究数据和数据之间关系的一门学科 它包括三个方面 1 数据集合中各数据元素之间所固有的逻辑关系 即数据的逻辑结构 2 在对数据进行处理时 各数据元素在计算机中的存储关系 即数据的存储结构 3 对各种数据结构进行的运算 第17页 1 逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构 数据的逻辑结构包含 1 表示数据元素的信息 2 表示各数据元素之间的前后件关系 例 1 一年四季的数据结构B D R D 春 夏 秋 冬 R 春 夏 夏 秋 秋 冬 2 家庭成员的数据结构B D R D 父亲 儿子 女儿 R 父亲 儿子 父亲 女儿 春 夏 秋 冬 数据结构的图形表示 第18页 常见的逻辑结构有 线性结构 树形结构和图形结构 线性结构结构中的每个元素之间存在一个对一个的关系 树形结构结构中的每个元素之间存在一个对多个的关系 图形结构或网状结构结构中的每个元素之间存在多个对多个的关系 其中 树形结构和图形结构统称为非线形结构 数据的逻辑结构可以用二元关系表示 也可以直观地用图形来表示 第19页 2 存储结构 物理结构 计算机在实际进行数据处理时 被处理的各数据元素总是被存放在计算机的存储空间中 并且 各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的 而且一般也不可能相同 如 一年四季家庭成员计算机存储空间怎样存放 存储结构指数据结构在计算机存储空间中的具体实现 常见的存储结构有 顺序存储结构链式存储结构索引存储结构 只抽象地反映数据元素之间的关系的结构 而不管其存储方式的数据结构称为逻辑结构 一种数据结构可以根据需要表示成一种或多种存储结构 第20页 3 数据的运算检索插入删除更新排序 通常 一个数据结构中的元素结点可能是动态变化的 根据需要或在处理过程中 可以在一个数据结构中增加一个新结点 插入运算 也可以删除某个结点 删除运算 除此之外 对数据结构的运算还有查找 分类 合并 分解 复制和修改 在对数据结构的处理过程中 不仅数据结构中结点的个数在动态变化 而且 各数据元素之间的关系也有可能在动态地变化 如 无序表变有序表 数据结构是研究数据和数据之间关系的一门学科 研究以下三方面内容 数据的逻辑结构数据的存储结构数据的运算 第21 92页 常见的数据结构 数据结构分类线性结构与非线性结构两大类型 线性结构 一个非空的数据结构若满足下面的两个条件 则这种数据结构即为线性结构 有且仅有一个根结点 除第一个结点外 每一个结点最多有一个前件 除最后一个结点外 每一个结点最多有一个后件 常见的线性结构有 线性表 栈 队列 线性链表等 第22 92页 常见的非线性结构有树 二叉树 图等 非线性结构 一个数据结构不是线性结构 第23页 线性表 LinearList 线性表是由n n 0 个数据元素a1 a2 ai an组成的一个有限序列 简单的线性表 复杂的线性表 记录102011001张三男 记录202011003李四女 记录3 记录4 第24页 线性表的顺序存储结构 特点 顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里 顺序存储结构只存储结点的值 不存储结点间的关系 结点间的关系由存储单元的邻接关系来体现 存储地址 2000 2004 2000 4 i 1 2000 4 n 1 占4个字节 Loa ai Loa a1 L i 1 第i个数的地址 第一个数的地址 L为该类型数所占的字节 线性表的存储结构 线性表的存储结构有两种 顺序存储结构链式存储结构 第25页 顺序表的插入运算顺序表的删除运算 顺序表的插入和删除运算 在线性表顺序存储情况下 要插入或删除一个元素 都会由于数据元素的移动而消耗大量的处理时间 所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的 线性表的顺序存储结构称为顺序表 第26页 插入运算 插入算法的分析 假设线性表中含有n个数据元素 在进行插入操作时 若假定在n 1个位置上插入元素的可能性均等 则平均移动元素的个数为 第27页 删除运算 删除算法的分析 在进行删除操作时 若假定删除每个元素的可能性均等 则平均移动元素的个数为 总结 顺序存储结构表示的线性表 在做插入或删除操作时 平均需要移动大约一半的数据元素 当线性表的数据元素量较大 并且经常要对其做插入或删除操作时 这一点需要值得考虑 第28页 线性表的链式存储结构 线性表的链式存储结构称为线性链表 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻 而且各数据元素的存储顺序也是任意的 各数据元素的先后关系是由各结点的指针域指示 链式存储结构的每一个存储结点不仅存储结点的值 而且存储结点之间的关系 链式存储结构分为单链表 双向链表 循环链表线性链表不能随机存取 第29页 设线性表为 a1 a2 a3 a4 a5 HEAD 3 线性链表的物理状态 线性表的顺序存储结构 注意 123此类编号不代表所在的地址单元的地址编码 线性表的链式存储结构及其插入与删除操作 第30页 单链表 第31页 单链表的插入运算 在P所指向的结点之后插入新的结点 单链表删除运算 要求 删除结点ai 第32页 循环链表 首尾相接的链表 将最后一个结点的空指针改为指向头结点 从任一结点出发均可找到其它结点 L 带头结点的单链表 L 循环单链表 特点 可以从任何一个结点开始访问链表的所有结点 第33页 双向链表的存储结构在每个结点中设置两个指针 一个指向后继 一个指向前驱 可直接确定一个结点的前驱和后继结点 可提高效率 提问 单向链表的缺点是什么 提示 如何寻找结点的直接前趋 双向链表可以克服单链表的单向性的缺点 在双向链表的结点中有两个指针域 其一指向直接后继 另一指向直接前趋 双向循环链表 第34页 线性表的应用 应用最广的数据结构 高级语言中的数组 计算机的文件系统 计算机的目录系统 电话号码查询系统 可采用顺序表或单链表结构 各种事务处理 可采用顺序表或单链表结构 第35页 2 栈和队列 栈和队列是两种特殊的线性表 它们是运算时要受到某些限制的线性表 故也称为限定性的数据结构 栈 Stack 及其基本运算队列 Queue 及其基本运算循环队列及其基本运算 第36页 1 栈 栈 是限定仅在表尾进行插入或删除操作的线性表 栈顶 表尾 栈底 表头 空栈 不含元素的空表 进栈 出栈 栈s a1 a2 an 后进先出或先进后出 LIFO 第37页 栈的物理存储结构可以用顺序结构 也可以用链表结构 下面讨论顺序存储结构中栈元素的插入和删除运算 顺序栈的进栈和出栈运算栈的基本运算有三种 入栈 退栈和读栈顶元素 在顺序栈中插入和删除运算不需要移动表中其他数据元素 第38页 2 栈的顺序存储结构及其基本运算 用顺序存储结构表示的栈 顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素 一般用一维数组表示 设置一个简单变量top指示栈顶位置 称为针栈顶指 它始终指向待插入元素的位置 基本运算 压 进 栈 PUSH出栈 POP读栈顶元素 gettop 第39页 例子 空桟 top base非空桟 top始终在桟顶元素的后一个位置 桟的元素个数 top base 上溢 下溢 第40页 2 队列定义 一种特殊的线性结构 限定只能在表的一端进行插入 在表的另一端进行删除的线性表 此种结构称为先进先出 FIFO 表 先进先出后进后出 LIFO 第41页 队列的顺序存储结构及其基本运算 空队列 非空队列 队列元素个数 rear front 1 front始终指向队头元素前一个位置 而rear始终指向队尾元素的位置 rear front 第42页 队列的物理存储结构可以用顺序结构 也可以用链式结构 顺序队列的运算 栈有三种操作 入栈 出栈 读栈顶元素队列有三种操作 入队 出队 读队首元素 例 有入栈元素序列 ABCD 求可能的出栈序列 如是队列又是什么情况呢 第43页 循环队列把队列的存储空间在逻辑上看作一个环 当R指向存储空间的末端后 就把它重新置于始端 循环队列的运算 进行删除的一端称做队首 front 队列中进行插入的一端称做队尾 rear 习题 数据结构分为逻辑结构和存储结构 循环队列属于 结构 2005年9月 答案 存储结构 第44页 第45页 上溢 下溢 front rear队满 front rear队空 第46页 数据存储结构方面的考题 1 数据的存储结构是指 2005年4月 A 存储在外存中的数据B 数据所占的存储空间量C 数据在计算机中的顺序存储方式D 数据的逻辑结构在计算机中的表示2 下列叙述中正确的是 2009年3月 A 栈是 先进先出 的线性表B 队列是 先进后出 的线性表C 循环队列是非线性结构D 有序线性表既可以采用顺序存储结构 也可以采用链式存储结构3 数据结构分为线性结构和非线性结构 带链的队列属于 4 下列数据结构中 属于非线性结构的是A 循环队列B 带链队列C 二叉树D 带链栈 答案 D 答案 D 答案 线性结构 答案 c 第47页 5 下列叙述中正确的是 2008年9月 A 顺序存储结构的存储一定是连续的 链式存储结构的存储空间不一定是连续的B 顺序存储结构只针对线性结构 链式存储结构只针对非线性结构C 顺序存储结构能存储有序表 链式存储结构不能存储有序表D 链式存储结构比顺序存储结构节省存储空间 答案 A 6 下列关于栈的叙述正确的是 2008年4月 A 栈按 先进先出 组织数据B 栈按 先进后出 组织数据C 只能在栈底插入数据D 不能删除数据 答案 B 7 一个队列的初始状态为空 现将元素A B C D E F 5 4 3 2 1依次入队 然后再依次退队 则元素退队的顺序为 1 2010年3月 答案 A B C D E F 5 4 3 2 1 第48页 9 设某循环队列的容量为50 如果头指针front 45 指向队头元素的前一位置 尾指针rear 10 指向队尾元素 则该循环队列中共有 2 个元素 2010年3月 8 假设用一个长度为50的数组 数组元索的下标从0到49 作为栈的存储空间 栈底指针bottom指间栈底元素 栈顶指针top指向栈顶元素 如果bottom 49 top 30 数组下标 则栈中具有 个元素 2009年3月 答案 19 答案 15 46 50 1 10 链表不具有的特点是A 不必事先估计存储空间B 可随机访问任一元素C 插入删除不需要移动元素D 所需空间与线性表长度成正比数据结构分为逻辑结构与存储结构 线性链表属于 1 数据结构中 与所使用的计算机无关的是数据的A 存储结构B 物理结构C 逻辑结构D 物理和存储结构数据的逻辑结构有线性结构和 1 两大类 数据的存储结构是指A 数据所占的存储空间B 数据的逻辑结构在计算机中的表示C 数据在计算机中的顺序存储方式D 存储在外存中的数据 例题讲解 存储结构 非线性结构 顺序存储方法是把逻辑上相邻的结点存储在物理位置 2 的存储单元中 数据处理的最小单位是A 数据B 数据元素C 数据项D 数据结构数据结构作为计算机的一门学科 主要研究数据的逻辑结构 对各种数据结构进行的运算 以及A 数据的存储结构B 计算方法C 数据映象D 逻辑存储线性表的顺序存储结构和线性表的链式存储结构分别是A 顺序存取的存储结构 顺序存取的存储结构B 随机存取的存储结构 顺序存取的存储结构C 随机存取的存储结构 随机存取的存储结构D 任意存取的存储结构 任意存取的存储结构 相邻 根据数据结构中各数据元素之间前后件关系的复杂程度 一般将数据结构分成A 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构数据结构包括数据的逻辑结构 数据的 2 以及对数据的操作运算 数据的基本单位是 5 下列叙述中 错误的是A 数据的存储结构与数据处理的效率密切相关B 数据的存储结构与数据处理的效率无关C 数据的存储结构在计算机中所占的空间不一定是连续的D 一种数据的逻辑结构可以有多种存储结构 存储结构 数据元素 链表不具有的特点是A 不必事先估计存储空间B 可随机访问任一元素C 插入删除不需要移动元素D 所需空间与线性表长度成正比顺序存储方法是把逻辑上相邻的结点存储在物理位置 2 的存储单元中 长度为n的顺序存储线性表中 当在任何位置上插入一个元素概率都相等时 插入一个元素所需移动元素的平均个数为 1 线性表若采用顺序存储结构时 要求内存中可用存储单元的地址A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续不连续都可以 例题讲解 相邻 线性表L a1 a2 a3 ai an 下列说法正确的是A 每个元素都有一个直接前件和直接后件B 线性表中至少要有一个元素C 表中诸元素的排列顺序必须是由小到大或由大到小D 除第一个元素和最后一个元素外 其余每个元素都有一个且只有一个直接前件和直接后件线性表的顺序存储结构和线性表的链式存储结构分别是A 顺序存取的存储结构 顺序存取的存储结构B 随机存取的存储结构 顺序存取的存储结构C 随机存取的存储结构 随机存取的存储结构D 任意存取的存储结构 任意存取的存储结构下列叙述中 错误的是A 数据的存储结构与数据处理的效率密切相关B 数据的存储结构与数据处理的效率无关C 数据的存储结构在计算机中所占的空间不一定是连续的D 一种数据的逻辑结构可以有多种存储结构 根据数据结构中各数据元素之间前后件关系的复杂程度 一般将数据结构分成A 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构当线性表采用顺序存储结构实现存储时 其主要特点是 1 随机存取 链表不具有的特点是A 不必事先估计存储空间B 可随机访问任一元素C 插入删除不需要移动元素D 所需空间与线性表长度成正比用链表表示线性表的优点是A 便于随机存取B 花费的存储空间较顺序存储少C 便于插入和删除操作D 数据元素的物理顺序与逻辑顺序相同长度为n的顺序存储线性表中 当在任何位置上插入一个元素概率都相等时 插入一个元素所需移动元素的平均个数为 1 在单链表中 增加头结点的目的是A 方便运算的实现B 使单链表至少有一个结点C 标识表结点中首结点的位置D 说明单链表是线性表的链式存储实现 例题讲解 非空的循环单链表head的尾结点 由p所指向 满足A p next NULLB p NULLC p next headD p head循环链表的主要优点是A 不再需要头指针了B 从表中任一结点出发都能访问到整个链表C 在进行插入 删除运算时 能更好的保证链表不断开D 已知某个结点的位置后 能够容易的找到它的直接前件当循环队列非空且队尾指针等于队头指针时 说明循环队列已满 不能进行入队运算 这种情况称为 2 用链表表示线性表的突出优点是 1 上溢 插入 删除灵活 栈和队列的共同特点是A 都是先进先出B 都是先进后出C 只允许在端点处插入和删除元素D 没有共同点如果进栈序列为e1 e2 e3 e4 则可能的出栈序列是A e3 e1 e4 e2B e2 e4 e3 e1C e3 e4 e1 e2D 任意顺序一些重要的程序语言 如C语言和Pascal语言 允许过程的递归调用 而实现递归调用中的存储分配通常用A 栈B 堆C 数组D 链表 例题讲解 栈底至栈顶依次存放元素A B C D 在第五个元素E入栈前 栈中元素可以出栈 则出栈序列可能是A ABCEDB DCBEAC DBCEAD CDABE栈通常采用的两种存储结构是A 线性存储结构和链表存储结构B 散列方式和索引方式C 链表存储结构和数组D 线性存储结构和非线性存储结构栈和队列通常采用的存储结构是 1 下列数据结构中 按先进后出原则组织数据的是A 线性链表B 栈C 循环链表D 顺序表 当循环队列非空且队尾指针等于队头指针时 说明循环队列已满 不能进行入队运算 这种情况称为 2 链表存储结构和数组 上溢 由两个栈共享一个存储空间的好处是A 减少存取时间 降低下溢发生的机率B 节省存储空间 降低上溢发生的机率C 减少存取时间 降低上溢发生的机率D 节省存储空间 降低下溢发生的机率下列关于栈的叙述中正确的是 在栈中只能插入数据B 在栈中只能删除数据C 栈是先进先出的线性表D 栈是后进先出的线性表下列关于队列的叙述中正确的是 在队列中只能插入数据B 在队列中只能删除数据C 队列是先进先出的线性表D 队列是后进先出的线性表 第60页 树型结构是一种重要的非线性结构 树的概念二叉树的概念二叉树的存储二叉树的遍历 3 树与二叉树 第61页 树的概念 树的定义 是一种简单的非线性结构 n个结点的有限集 n 0 A B D F E C G H I J K M 结点 根结点 没有前件的结点只有一个称为根结点 简称树的根 空树 无结点则称为空树 父结点 结点的前件称该结点的父结点 A 只有一个结点的树 第62页 树型结构的常用术语 A B D F E C G H I J K M 子结点 结点的后件 称为该结点的子结点 可以有多个 叶子结点没有后件的结点 Q 图中叶子结点有几个 7结点的度一个结点的子树的个数 有几个分叉 Q 结点A G的度数 3 2 Q 度数为0 1 2 3的结点分别有几个 树的度树中所有结点度的最大值 Q 右图中树的度 3 第63页 树型结构的常用术语 A B D F E C G H I J K M 结点的层次树中根结点的层次为1 根结点子树的根为第2层 以此类推 Q 图中结点F的层次 树的深度树中所有结点层次的最大值 Q 图中树的深度 有序树 无序树如果树中每棵子树从左向右的排列拥有一定的顺序 不得互换 则称为有序树 否则称为无序树 第64页 二叉树的概念 定义 二叉树是一种有序的树形结构 它与一般树形结构的区别是 每个结点最多有两棵子树 子树有左右之分 次序不能任意颠倒 称左子树和右子树 二叉树的5种基本形态 第65页 树与二叉树的区别 A 树和二叉树的结点个数最少都可为0 B 树中结点的最大度数没有限制 二叉树结点最大度数为2 C 树的结点无左 右之分 二叉树的结点子树有明确的左 右之分 3个结点的树 3个结点的二叉树 第66页 二叉树的性质 性质1 在二叉树的第i层上最多有2i 1个结点 i 1 第67页 性质2 深度为h的二叉树最多有2h 1个结点 h 1 第68页 性质3 二叉树上叶子结点数比度为2的结点数多1 度为2的结点 叶子结点 第69页 满二叉树和完全二叉树 满二叉树 除最后一层外 每一层上的所有结点都有两个子结点 最后一层的结点均为0度 完全二叉树 除最后一层外 每一层上的结点数均达到最大值 在最后一层上只缺少右边的若干结点 则称这棵二叉树为完全二叉树 完全二叉树中度数为1的结点的个数为0或1 第70页 满二叉树 完全二叉树 12 13 8 9 10 11 4 5 6 7 1 2 3 完全二叉树是满二叉树满二叉树也是完全二叉树 第71页 12 13 8 9 10 11 4 5 6 1 2 3 非完全二叉树 深度为4的完全二叉树 8 4 5 6 7 1 2 3 第72页 性质4 具有n个结点的完全二叉树的深度为 log2 n 1 其中 log2n 的结果是不大于log2n的最大整数 深度为4的满二叉树 深度为4的完全二叉树 深度为3的完全二叉树具有4 7个结点深度为4的完全二叉树具有8 15深度为5的完全二叉树具有15 31 log2 8 1 ln9 In2 4 log2 15 1 In16 In2 4 深度为6的完全二叉树具有32 63深度为7的完全二叉树具有64 127深度为8的完全二叉树具有128 255深度为9的完全二叉树具有256 511深度为10的完全二叉树具有512 1023深度为11的完全二叉树具有1024 2047 第73页 性质5 具有n个结点的完全二叉树的深度为 例 n 2k 2n 6k 3n 7k 3n 8k 4n 12k 4 第74页 性质6 如果对一棵有n个结点的完全二叉树的结点按层序编号 则对任一结点i 1 i n 有 总之 如i 1它的双亲是i 2取整 左子结点是2 i 右子结点是2 i 1 当然如果算下来超过总数民N 则为没有 第75页 例 i 1是树的根 无双亲 其左子结点为2 i 2 右子结点为2 i 1 3 2 i 18 122 i 1 19 12 其无左 右子结点 2 i 1 13 12 其无右子结点 第76页 1 在深度为7的满二叉树中 叶子结点的个数为 2006年4月 A 32B 31C 64D 632 在深度为7的满二叉树中 度为2的结点个数为 07年4月 3 一棵二叉树中共有70个叶子结点与80个度为1的结点 则该二叉树中的总结点数为 07年9月 A 219B 221C 229D 2314 某二叉树中度为2的结点有18个 则该二叉树中有 个叶子结点 2005年4月 5 一棵二叉树第六层 根结点为第一层 的结点数最多为 个 2005年9月 树型结构方面的考题 1答案 C 3答案 A 5答案 32 2答案 63 4答案 19 第77页 二叉树的存储 在计算机中 二叉树通常采用链式存储结构 对于满二叉树和完全二叉树可以按层进行顺序存储 二叉树的存储结点的结构 A B D C F G E t 第78页 2 二叉树的存储结构 2 链式存储结构 T 16 若父结点在数组中i下标处 其左孩子在2 i处 右孩子在2 i 1处 1 顺序存储结构 1 顺序存储结构 2h 1 24 1 15 用一组连续的存储单元存放二叉树的数据元素 结点在数组中的相对位置蕴含着结点之间的关系 一般二叉树必须按完全二叉树的形式存储 将造成存储的浪费 第79页 2 链式存储结构 链式存储结构 二叉链表三叉链表 二叉链表 二叉链表的结点包含三个域 数据域 左 右指针域 例 第80页 三叉链表 三叉链表的结点包含四个域 数据域 左 右 双亲指针域 例 链式存储结构的特点 1 操作便于实现 2 结构复杂 第81页 二叉树的遍历 遍历指不重复地访问二叉树中的所有结点 二叉树的遍历的次序与树型结构上的大多数运算有联系 遍历的方式有三种 1 先 前 序遍历 DLR 2 中序遍历 LDR 3 后序遍历 LRD 第82页 二叉树的遍历 遍历指不重复地访问二叉树中的所有结点 1 先 前 序遍历 DLR 根左右若二叉树为空 则结束遍历操作 否则访问根结点 先序遍历左子树 先序遍历右子树 先序遍历的结果 ABECFGHD 第83页 2 中序遍历 LDR 左根右若二叉树为空 则结束遍历操作 否则中序遍历左子树 访问根结点 中序遍历右子树 中序遍历的结果 EBAFHGCD 3 后序遍历 LRD 右根左若二叉树为空 则结束遍历操作 否则后序遍历左子树 后序遍历右子树 访问根结点 后序遍历的结果 EBHGFDCA 第84页 先序序列 ABDGCEFH中序序列 DGBAECHF后序序列 GDBEHFCA A B C F H D E G 下图所示的二叉树经过三种遍历得到的顺序分别为 练习 根据先序遍历序列 建立二叉树 第85页 1 设二叉树如下 2010年3月 对该二叉树进行后序遍历的结果为 3 树型结构方面的考题2 2 对如下二叉树 2006年4月 进行后序遍历的结果为A ABCDEFB DBEAFCC ABDECFD DEBFCA EDBGHFCA D A B C F H D G E 已知二叉树后序遍历序列是dabec 中序遍历序列是debac 它的前序遍历序列是A acbedB decabC deabcD cedba已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF 则该二叉树的后序遍历为A GEDHFBCAB DGEBHFCAC ABCDEFGHD ACBFEDHG树是结点的集合 它的根结点数目是A 有且只有1B 1或多于1C 0或1D 至少2下列叙述中正确的是A 线性表是线性结构B 栈与队列是非线性结构C 线性链表是非线性结构D 二叉树是线性结构 例题讲解 在深度为5的满二叉树中 叶子结点的个数为A 32B 31C 16D 15若某二叉树的前序遍历访问顺序是abdgcefh 中序遍历访问顺序是dgbaechf 则其后序遍历的结点访问顺序是A bdgcefhaB gdbecfhaC bdgaechfD gdbehfca在树结构中 树根结点没有 1 具有3个结点的二叉树有A 2种形态B 4种形态C 7种形态D 5种形态设一棵二叉树中有3个叶子结点 有8个度为1的结点 则该二叉树中总的结点数为A 12B 13C 14D 15 双亲结点 设有下列二叉树 对此二叉树前序遍历的结果为A ZBTTCPXAB ATBZXCTPC ZBTACTXPD ATBZXCPT设有下列二叉树 对此二叉树的中序遍历的结果为A ABCDEFB DBEAFCC ABDECFD DEBFCA 设树T的度为4 其中度为1 2 3 4的结点个数分别为4 2 1 1 则T中的叶子结点数为A 8B 7C 6D 5设一棵完全二叉树共有700个结点 则该二叉树中有 个叶子结点 在一个容量为15的循环队列中 若头指针front 6 尾指针rear 9 则该循环队列中共有 个元素 设一棵二叉树的中序遍历结果为DBEAFC 前序遍历结果为ABDECF 则后序遍历结果为 350 3 DEBFCA 第90页 查找技术 查找是数据处理的重要内容 查找指在一个给定的数据结构中查找指定的元素 该元素也称关键字 若找到了满足条件的结点 称查找成功 否则称查找失败 衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数 通常根据不同的数据结构 采用不同的查找方法 顺序查找二分查找 第91页 1 7 1 1顺序查找 线性查找 查找过程 对给定的一关键字K 从线性表的一端开始 逐个进行记录的关键字和K的比较 直到找到关键字等于K的记录或到达表的另一端 可以采用从前向后查 也可采用从后向前查的方法 在平均情况下 大约要与表中一半以上元素进行比较 效率较低 平均查找长度较大 最好情况 1最坏情况 n 在下面两种情况下只能采取顺序查找 a 线性表为无序表 元素排列是无序的 b 即使是有序线性表 但采用的是链式存储结构 第92页 1 7 1 2折半查找 二分法查找 思想 先确定待查找记录所在的范围 然后逐步缩小范围 直到找到或确认找不到该记录为止 前提 必须在具有顺序存储结构的有序表中进行 分三种情况 1 若中间项的值等于x 则说明已查到 2 若x小于中间项的值 则在线性表的前半部分查找 3 若x大于中间项的值 则在线性表的后半部分查找 特点 比顺序查找方法效率高 最坏的情况下 需要比较log2n次 第93 92页 折半查找算法举例 对给定数列 有序 3 5 11 17 21 23 28 30 32 50 按折半查找算法 查找关键字值为30的数据元素 a1a2a3a4a5a6a7a8a9a10第1次 3 5 11 17 21 23 28 30 32 50 K 30mid1 1 10 2 5k a mid1 a 5 21第2次 23 28 30 32 50 mid2 6 10 2 8K a mid2 a 8 30 low high mid low high mid 第94 92页 练习假设待查有序 升序 顺序表中数据元素的关键字序列为 8 18 27 42 47 50 56 68 95 120 用折半查找方法查找关键字值为27的数据元素 对于长度为n的有序线性表 最坏情况只需比较log2n次 第95页 1 7 2排序 1 7 2 1概述1 排序的功能 将一个数据元素 或记录 的任意序列 重新排成一个按关键字有序的序列 2 排序过程的组成步骤 首先比较两个关键字的大小 然后将记录从一个位置移动到另一个位置 第96页 排序方法 插入排序 选择排序 交换排序 归并排序 简单插入排序 希尔排序 简单选择排序 堆排序 起泡排序 快速排序 第97页 1 7 2 2插入排序简单插入 希尔排序 1 简单插入排序 基本思想 从数组的第2号元素开始 顺序从数组中取出元素 并将该元素插入到其左端已排好序的数组的适当位置上 第98页 该算法适合于n较小的情况 时间复杂度为O n2 待排元素序列 53 2736156942第一次排序 2753 36156942第二次排序 273653 156942第三次排序 15273653 6942第四次排序 1527365369 42第五次排序 152736425369 直接插入排序示例 对于有n个数据元素的待排序列 插入操作要进行n 1趟 最坏情况下 需要n n 1 2次比较最好 n 1次比较 第99页 希尔排序 希尔排序的基本思想 先将整个待排记录序列分割成为若干子序列分别进行直接插入排序 待整个序列中的记录 基本有序 时 再对全体记录进行一次直接插入排序 最坏情况下 需要O n1 5 次比较 第100页 1 简单选择排序思想 首先从1 n个元素中选出关键字最小的记录交换到第一个位置上 然后再从第2个到第n个元素中选出次小的记录交换到第二个位置上 依次类推 1 7 2 3选择排序简单选择排序 堆排序 简单选择排序法 最坏情况需要n n 1 2次比较 时间复杂度为O n2 适用于待排序元素较少的情况 第101 92页 初态 15 14 22 30 37 15 11 第一趟 11 14 22 30 37 15 15 第二趟 11 14 22 30 37 15 15 第三趟 11 14 15 30 37 22 15 第四趟 11 14 15 15 37 22 30 第五趟 11 14 15 15 22 37 30 第六趟 11 14 15 15 22 30 37 有序序列 例 设待排数据元素的关键字为 15 14 22 30 37 11 每一趟排序后的序列状态如图所示 第102页 2 堆排序 也是一种选择排序 堆是具有特定条件的顺序存储的完全二叉树 其特定条件是 任何一个非叶子结点的关键字大于等于 或小于等于 子女的关键字的值 a 堆顶元素取最大值 b 堆顶元素取最小值 堆排序需要比较的次数为O nlog2n 1 堆的示例 第103页 1 7 2 4交换排序交换排序的特点在于交换 有冒泡和快速排序两种 1 冒泡排序 起泡排序 思想 小的浮起 大的沉底 从左端开始比较 第一趟 第1个与第2个比较 大则交换 第2个与第3个比较 大则交换 关键字最大的记录交换到最后一个位置上 第二趟 对前n 1个记录进行同样的操作 关键字次大的记录交换到第n 1个位置上 依次类推 则完成排序 第104页 冒泡排序 冒泡排序的方法 扫描整个线性表 逐次对相邻的两个元素进行比较 若为逆序 则交换 第一趟扫描的结果使最大 或最小 的元素排到表的最后 或最前 除最后 或最前 一个元素 对剩余的元素重复上述过程 将次大 或次小 的数排到表的倒数 或正数 第二个位置 重复上述过程 对于长度为n的线性表 冒泡排序需要对表扫描n 1遍 第105页 冒泡排序的方法 设待排数据元素的关键字为 18 20 15 32 4 25 第一趟冒泡排序后的序列状态如图所示 182015324251820153242518152032425181520324251815204322518152042532最大数 第二趟冒泡排序 第106页 Q 第二趟冒泡排序后的结果是什么样的 达到了最终的排序目标吗 一共需要多少次能够最后成为有序序列 Q 你觉得冒泡排序的效率如何 如果是你 你会用什么方法来排序 冒泡排序比较简单 当初始序列基本有序时 冒泡排序有较高的效率 反之效率较低 冒泡排序终止条件 本趟排序未发生交换 终止排序算法 第107页 初始第一趟第二趟第三趟第四趟第五趟序列排序后排序后排序后排序后排序后2618181818918262626915323232915185447915264791532915471554 设待排数据元素的关键字为 26 18 32 54 47 9 15 冒泡排序法 需要比较的次数为n n 1 2 第108页 2 快速排序 对冒泡排序的改进 思想 通过一趟排序将待排序列分成两部分 使其中一部分记录的关键字均比另一部分小 再分别对这两部分排序 以达到整个序列有序 时间复杂度 O log2n 当待排序列逆序时 蜕变成冒泡排序 时间复杂度 O n n 1 2 第109页 1 7 2 5内部排序方法的选择各种排序方法各有优缺点 故在不同情况下可作不同的选择 通常需考虑的因素有 待排序的记录个数 记录本身的大小 记录的键值分布情况等 若待排序的记录个数n较小时 可采用简单排序方法 若n较大时 应采用快速排序或堆排序 若待排序的记录已基本有序 可采用简单插入和起泡排序 第110页 查找 排序 n 1n n 1 2 n1 5 n n 1 2 nlog2n n 1n n 1 2 log2n n n 1 2 正序的表 n小的表 与表的初始数据无关 n小的表 正序的表 n小的表 n大的表 但逆序的表会蜕变为起泡排序 借助辅助空间最多的方法 n大的表 第111 92页 排序法小结 简单选择排序法 最坏情况需要n n 1 2次比较 冒泡排序法 最坏情况需要n n 1 2次比较 希尔排序法 最坏情况需要O n1 5 次比较 堆排序法 最坏情况需要O nlog2n 次比较 第112 92页 排序查找方面的考题 1 对于长度为n的线性表 在最坏情况下 下列各排序法所对应的比较次数中正确的是 2005年4月 A 冒泡排序为n 2B 冒泡排序为nC 快速排序为nD 快速排序为n n 1 2 2 在长为64的有序线性表中进行顺序查找 最坏情况下需要比较的次数为 06年9月 A 63B 64C 6D 7 3 下列数据结构中 能用二分法进行查找的是 2005年9月 A 顺序存储的有序线性表B 线性链表C 二叉链表D 有序线性链表 4 下列排序方法中 最坏情况下比较次数最少的是 09年3月 A 冒泡排序B 简单选择排序C 直接插入排序D 堆排序 D B A D 第113页 在长度为n的有序线性表中进行二分查找 最坏的情况下 需要的比较次数为 2 长度为n的顺序存储线性表中 当在任何位置上插入一个元素概率都相等时 插入一个元素所需移动元素的平均个数为 1 假设线性表的长度为n 则在最坏情况下 冒泡排序需要的比较次数为A log2nB n2C O n1 5 D n n 1 2已知数据表A中每个元素距其最终位置不远 为节省时间 应采用的算法是A 堆排序B 直接插入排序C 快速排序D 直接选择排序 例题讲解 log2n n 2 第114页 冒泡排序算法在最好的情况下的元素交换次数为 1 在最坏情况下 堆排序需要比较的次数为 2 最简单的交换排序方法是A 快速排序B 选择排序C 堆排序D 冒泡排序排序是计算机程序设计中的一种重要操作 常见的排序方法有插入排序 1 和选择排序等 0 nlog2n 交换排序 第115页 在下列几种排序方法中 要求内存量最大的是A 插入排序B 选择排序C 快速排序D 归并排序在待排序的元素序列基本有序的前提下 效率最高的排序方法是A 冒泡排序B 选择排序C 快速排序D 归并排序希尔排序属于A 交换排序B 归并排序C 选择排序D 插入排序对长度为n的线性表进行顺序查找 在最坏的情况下所需要的比较次数为 n 1B nC n 1 2D n 2 第116页 2 程序设计基础 第117页 第二章程序设计基础 内容 1 程序设计方法与风格 2 结构化程序设计 3 面向对象的程序设计方法 对象方法 属性及继承与多态性 第118页 1 源程序的文档化符号的命名 见名知意注释 序言性和功能性注释 程序的视觉组织 空格 空行 缩进 2 数据说明数据说明的次序应该规范化变量安排有序化对复杂数据结构应注释说明3 语句的结构每条语句简单明了尽量不用或少用GOTO语句尽量只采用3种基本控制结构编程4 输入和输出对所有输入数据进行校验和合理性检查输入输出格式保持一致设计良好的输出报表 清晰第一 效率第二 2 1 2程序设计风格 第119页 第120页 2 2结构化程序设计 2 2 1基本概念 基本思想对大型的程序设计 使用一些基本的结构来设计程序 无论多复杂的程序 都可以使用这些基本结构按一定的顺序组合起来 这些基本结构的特点都是只有一个入口 一个出口 由这些基本结构组成的程序就避免了任意转移 阅读起来需要来回寻找的问题 三种基本结构顺序结构选择结构循环结构三种基本结构的特点只有一个入口只有一个出口每一个基本结构中的每一部分都有机会执行到结构内不存在 死循环 第121页 2 2 2设计原则自顶向下 先总体 后细节 逐步求精 设计子目标过渡 模块化 分解总目标 限制使用goto语句 结构化程序设计方法特点要求把程序的结构规定为顺序 选择和循环三种基本机构 并提出了自顶向下 逐步求精 模块化程序设计等原则 结构化程序设计是把模块分割方法作为对大型系统进行分析的手段 使其最终转化为三种基本结构 其目的是为了解决由许多人共同开发大型软件时 如何高效率地完成可靠系统的问题 缺点 程序和数据结构松散地耦合在一起 解决此问题的方法就是采用面向对象的程序设计方法 OOP 第122页 2 3 2基本概念对象 Object 对象是系统中用来描述客观事物的一个实体 是构成系统的一个基本单位 它既包括数据 属性 也包括作用于数据的操作 行为 一个对象把属性和行为封装为一个整体一个对象通常可由对象名 属性和操作3部分组成属性即对象所包含的信息操作描述了对象执行的功能 操作也称为方法或服务 2 3面向对象的程序设计 第123