C语言计算机二课件.ppt

2003 11 全国计算机等级考试二级公共基础知识 周林涛2012年2月 基本要求 1 掌握算法的基本概念 2 掌握基本数据结构及其操作 3 掌握基本排序和查找算法 4 掌握逐步求精的结构化程序设计方法 5 掌握软件工程的基本方法 具有初步应用相关技术进行软件开发的能力 6 掌握数据库的基本知识 了解关系数据库的设计 全国计算机等级考试二级公共基础知识考试大纲 考试内容一 基本数据结构与算法 1 算法的基本概念 算法复杂度的概念和意义 时间复杂度与空间复杂度 2 数据结构的定义 数据的逻辑结构与存储结构 数据结构的图形表示 线性结构与非线性结构的概念 3 线性表的定义 线性表的顺序存储结构及其插入与删除运算 4 栈和队列的定义 栈和队列的顺序存储结构及其基本运算 5 线性单链表 双向链表与循环链表的结构及其基本运算 6 树的基本概念 二叉树的定义及其存储结构 二叉树的前序 中序和后序遍历 7 顺序查找与二分法查找算法 基本排序算法 交换类排序 选择类排序 插入类排序 二 程序设计基础 1 程序设计方法与风格 2 结构化程序设计 3 面向对象的程序设计方法 对象 方法 属性及继承与多态性 三 软件工程基础 1 软件工程基本概念 软件生命周期概念 软件工具与软件开发环境 2 结构化分析方法 数据流图 数据字典 软件需求规格说明书 3 结构化设计方法 总体设计与详细设计 4 软件测试的方法 白盒测试与黑盒测试 测试用例设计 软件测试的实施 单元测试 集成测试和系统测试 5 程序的调试 静态调试与动态调试 四 数据库设计基础 1 数据库的基本概念 数据库 数据库管理系统 数据库系统 2 数据模型 实体联系模型及E R图 从E R图导出关系数据模型 3 关系代数运算 包括集合运算及选择 投影 连接运算 数据库规范化理论 4 数据库设计方法和步骤 需求分析 概念设计 逻辑设计和物理设计的相关策略 考试方式 1 公共基础的考试方式为笔试 与C语言 VisualBASIC VisualFoxPro Java Access VisualC 的笔试部分合为一张试卷 公共基础部分占全卷的30分 2 公共基础知识有10道选择题和5道填空题 第一章数据结构与算法 1 1算法 考点1 算法的基本概念计算机解题的实际过程是在实施某种算法 这种算法称为 计算机算法 解题方案的准确而完整的描述称为算法 1 算法的基本特征 可行性 执行后能得到满意结果 确定性 算法中每个步骤必须明确定义 不允许有模棱两可的解释 也不允许有多义性 有穷性 算法必须在有限时间内做完 即必须能在执行有限个步骤之后终止 还有合理的执行时间的含义 拥有足够的情报 一个执行的结果与输入的初始数据有关 不同的输入会有不同的结果输出 确保算法有效还取决于情报是否足够 所以说算法是一组严谨地定义运算顺序的规则 并且每一个规则都是有效的 且是明确的 此顺序将在有限的次数下终止 2算法的基本要素1 对数据对象的运算和操作算术运算 主要包括加减 乘 除等运算逻辑运算 主要包括与 或 非等运算关系运算 主要包括大于 小于 等于等运算数据传输 主要包括赋值 输入 输出等操作2 算法的控制结构概念 算法中各操作之间的执行顺序描述算法的工具通常有传统流程图 N S结构化流程图 算法描述语言等一个算法的功能不仅取决于所选用册操作 还与各操作之间的执行顺序有关 而且也直接反映了算法设计是否符合结构化原则 一个算法一般可以用顺序 选择 循环三种基本机构组合而成 3 算法设计的基本方法 列举法 根据提出的问题 列举所有可能的情况 并用问题中给定的条件检验那些需要 那些不需要 是计算机算法中的一个基础算法 归纳法 通过列举少量特殊情况 经过分析 最后找出一般的关系 递推 从已知的初始条件出发 逐次推出所要求的各中间结果和最后结果 递归 将复杂的问题逐层分解成为简单的问题 解决最简单的问题后 再沿原来的分解逆过程逐步进行综合 直接递归 一个算法P显式的调用自己间接递归 一个算法P调用另一个算法Q 而算法Q有调用算法P减半递推技术 分治法 减半 是指将问题的规模减半 问题的性质不变 递推 是指重复 减半 的过程 回溯法 有些实际问题很难归纳一组简单的递推公式或直观的求解步骤 也不能进行无限列举 对此问题 一种有效的方法就是 试 通过对问题的分析 试探不成功 则换别的路线再进行试探 考点2 算法的复杂度 算法的复杂度主要包括时间复杂度和空间复杂度 1 时间复杂度指执行算法所需要的计算工作量 算法工作量 n n 问题的规模可以用基本运算的次数来度量算法的工作量 运算次数还与问题的规模有关 还与特定的输入有关 在同一问题规模下 如果算法执行所需要的基本运算次数取决于某一特定输入时 可以用以下方法来分析算法的工作量 1 平均性态指各种特定输入下的基本运算次数的加权平均值来度量的算法的工作量 X 所有可能输入中的某个特定输入 X出现的概率 算法在输入X时所执行的运算次数 当规模为n时 算法所执行的基本运算次数 2 最坏情况复杂性规模为n时 算法执行的最大次数W n 的计算要比A n 的计算方便 更具有实用价值 2 空间复杂度指执行算法所需要的内存空间包括算法程序所占空间 输入初始数据空间 算法执行过程所占空间注 包括某种数据结构所需要的附加存储空间 例 算法的时间复杂度是指 A 执行算法程序所需要的时间B 算法程序的长度C 算法执行过程中所需要的基本运算次数D 算法程序中的指令条数算法的基本特征是可行性 确定性 和拥有足够的情报 算法的空间复杂度是指 A 算法程序的长度B 算法程序中的指令条数C 算法程序所占的存储空间D 执行算法所需要的存储空间 在计算机中 算法是指 A 加工方法B 解题方案的准确而完整的描述C 排序方法D 查询方法下面叙述正确的是 A 算法的执行效率与数据的存储结构无关B 算法的空间复杂度是指算法程序中指令 或语句 的条数C 算法的有穷性是指算法必须能在执行有限个步骤之后终止D 以上三种描述都不对 算法分析的目的是A 找出数据结构的合理性B 找出算法中输入和输出之间的关系C 分析算法的易懂性和可靠性D 分析算法的效率以求改进 1 2数据结构的基本概念 考点3 数据结构的定义数据结构作为计算机的一门学科 主要研究和讨论下面三个问题 1 数据的逻辑结构 数据集合中各数据元素之间的逻辑关系 2 数据的存储结构 在对数据进行处理时 各数据元素在计算机中的存储关系 3 对各种数据结构进行的运算讨论以上问题主要目的是为了提高数据处理的效率 一是提高数据处理的速度 二是尽量节省在数据处理过程中所占用的计算机存储空间 1 数据的逻辑结构 2 数据的存储结构 3 数据的运算 检索 排序 插入 删除 修改等 A 线性结构 B 非线性结构 A顺序存储 B链式存储 线性表 栈 队列 树形结构 图形结构 数据结构的三个方面 1 2 1什么是数据结构数据处理 对数据集合中的各元素以各种方式进行运算 包括插入 删除 查找 更改等运算 也包括对数据元素进行分析 例1 3 有序表 存放的顺序从大到小或从小到大无序表 存放的顺序是没有规则的无序表的顺序查找和有序表的对分查找 无序表 有序表 对分查找 只适用于有序表 而对无序表是无法进行对分查找的 数据结构 是指相互有关联的数据元素的集合元素 在数据处理领域中 每一个需要处理的对象都可以抽象成数据元素 简称元素 是数据的基本单位 在具有相同特征的数据元素中 各个数据之间存在有某种关系 即联系 这种关系反映了数据元素所固有的一种结构 在数据处理领域中 通常把数据元素之间的这种固有关系简单地用前后件关系来描述 数据中的任何关系都可以用前后件关系来描述 数据 客观事物的符号表示 数据元素 数据的基本单位 数据对象 性质相同的数据集合 1 数据的逻辑结构数据结构是指带有结构的数据元素的集合 所谓结构实际上就是指数据元素之间的前后件关系 包括两方面的信息 1 表示数据元素的信息 2 表示各数据之间的前后件关系数据的逻辑结构 是指反映数据元素之间逻辑关系 前后件关系 的数据结构 逻辑结构两要素 一是数据元素的集合D二是D上的关系 即前后件关系R 数据结构表示 B D R 有限个数据元素的集合 有限个节点间关系的集合 2 数据的存储结构各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的 而且一般也不可能相同 数据的存储结构 指数据的逻辑结构在计算机存储空间中的存放形式 也称数据的物理结构 选择合适的存储结构有利于提高数据处理的效率 常用的存储结构有顺序 链接 索引等 考点4 数据结构的图形表示数据结构可以用二元关系表示 B D R 还可以用图形表示 在数据结构的图形表示中 对于数据集合D中的每一个数据元素用中间标有元素值的方框表示 一般称之为数据结点 简称为结点 为了进一步表示各数据元素之间的前后件关系 对于关系R中的每一个二元数组 用一条有向线段从前件指向后件结点 春 夏 秋 冬 用图形方式表示一个数据结构是很方便的 而且也很直观 在数据结构中 没有前件的结点称为根结点 没有后件的结点称为终端结点 也称为叶子结点 除了根结点与叶子结点外的其他结点称为内部结点 父亲 儿子 女儿 例 用图形表示数据结构B D R D di 1 I 7 d1 d2 d3 d4 d5 d6 d7 R d1 d3 d1 d7 d2 d4 d3 d6 d4 d5 d1 d3 d6 d7 d2 d4 d5 一个数据结构中的元素结点可能是动态变化的 各数据之间的关系也可能在动态地变化 插入与删除是对数据结构的两种基本运算 考点5 线性结构和非线性结构根据前后件关系复杂程度将数据结构分为 线性结构和非线性结构 空数据结构 一个元素都没有的数据结构 非空数据结构如果满足 有且只有一个根节点 每个节点最多有一个前件节点 也最多有一个后件节点 称为线性结构 说明 在一个线性结构中插入或删除任何一个结点后还应是线性结构 若一个数据结构不是线性结构 则为非线性结构 1 3线性表及其顺序存储结构 考点6 线性表的定义线性表是由n n 0 个元素构成的有限序列 a1 a2 an 非空线性表具有如下特征 1 有且只有一个根结点a1 它无前件 2 有且只有一个终端结点an 它无后件 3 其他所有结点有且只有一个前件 也有且只有一个后件 线性表是最简单 最常用的一种数据结构 线性表由一组数据元素构成 矩阵也是一个线性表 只不过它是一个比较复杂的线性表 一个数据元素可以是简单项或若干数据项组成 由若干数据项组成的数据元素称为记录 而由多个记录组成的线性表又称文件 提醒 数据项是数据的最小单位数据元素是数据的基本单位 考点7 线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点 1 线性表中所有元素所占的存储空间是连续 2 线性表中各数据元素在存储空间中是按逻辑顺序存放的在线性表的顺序存储结构中 其前后件两个元素在存储空间中是紧邻的 且前件元素一定存储在后件元素的前面线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号惟一确定 第i个元素存储地址 ADR ai ADR a1 i 1 k 对线性表的运算 插入 删除 查找 排序 分解 合并 复制 逆转 考点8 顺序表的插入运算例 第2位前插入87 再在第9位前插入14 长度为8的线性表 插入元素87后的线性表 87 14 插入元素14后的线性表 V 1 10 V 1 10 V 1 10 上溢 为线性表开辟的存储空间已经满了 不能再插入新的元素了 如果再要插入 则会造成称为 上溢 的错误 要在第i 1 i n 个元素之间插入一个新元素时 首先要从最后一个 即第n个 元素开始 直到第i个元素之间共n i 1个元素依次向后移动一个位置 移动结束后 第i个位置就被空出 然后将新元素插入到第i项 插入结束后 线性表的长度就增加了1 在线性表的顺序存储情况下 要插入一个新元素 其效率是很低的 特别是在线性表比较大的情况 考点9 顺序表的删除运算例 先删除第1个元素 再删除第6个元素 长度为8的线性表 删除元素29后的线性表 插入元素31后的线性表 V 1 10 V 1 10 V 1 10 要删除第i 1 i n 个元素时 则要从第i 1个元素开始 直到第n个元素之间共n i个元素依次向前移动一个位置 删除结束后 线性表的长度就减小了1 在线性表的顺序存储情况下 要删除一个元素 其效率是很低的 特别是在线性表比较大的情况 例数据结构分为逻辑结构与存储结构 线性表属于 数据结构中 与所使用的计算机无关的是数据的 A 存储结构B 物理结构C 逻辑结构D 物理和存储结构数据的逻辑结构有线性结构和两大类 顺序存储方法是把逻辑上相邻的结点存储在物理位置的存储单元中 数据处理的最小单位是 A 数据B 数据元素C 数据项D 数据结构数据结构作为计算机的一门学科 主要研究数据的逻辑结构 对各种数据结构进行的运算 以及 A 数据的存储结构B 计算方法C 数据映象D 逻辑存储 根据数据结构中各数据元素之间前后件关系的复杂程度 一般将数据结构分成 A 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构数据结构包括数据的结构 数据的逻辑结构以及对数据的操作运算 数据的基本单位是 下列叙述中 错误的是 A 数据的存储结构与数据处理的效率密切相关B 数据的存储结构与数据处理的效率无关C 数据的存储结构在计算机中所占的空间不一定是连续的D 一种数据的逻辑结构可以有多种存储结构数据的存储结构是指 A 数据所占的存储空间B 数据的逻辑结构在计算机中的表示C 数据在计算机中的顺序存储方式D 存储在外存中的数据 1 4栈和队列 考点10 栈及基本运算1 什么是栈特殊的线性表 只能在表的一端进行插入和删除运算的线性表 在栈中 允许插入与删除的一端称为栈顶元素 而不允许插入与删除的另一端称为栈底元素 假设栈s a1 a2 an 则a1称为栈底元素 an成为栈顶元素 栈按照先进后出或后进先出的原则组织数据 入栈 退栈 栈顶top 栈底bottom 往栈中插入一个元素称为入栈运算 删除一个元素为退栈运算 栈示意图 2 栈的顺序存储及其运算用一维数组S 1 m 作为栈的顺序存储空间其中m为栈的最大容量 Top 0表示栈空 top m表示栈满 栈的基本运算有三种 入栈 退栈与读栈顶元素入栈 在栈顶插入一个新元素 首先将栈顶指针进1 然后将新元素插入到栈顶指针指向的位置 当栈顶指针已经指向存储空间的最后一个位置时 说明栈空间已满 不可能再进行入栈操作 这种情况称为栈的 上溢 错误 退栈 只取出栈顶元素并赋给一个指定的变量 首先将栈顶元素赋给一个指定的变量 然后将栈顶指针退1 当栈顶指针为0时 说明栈空 不可能进行退栈操作 这种情况称为栈的 下溢 错误 读栈顶元素 将栈顶元素赋给一个指定的变量 当栈顶指针为0时 说明栈空 读不到栈顶元素 考点11 队列及基本运算1 什么是队列队列 只允许在一端 对头 删除 在另一端 队尾 插入特殊的线性表 队列是允许在一端进行插入 而在另一端进行删除的线性表 允许插入的一端称为队尾 通常用一个称为尾指针 rear 的指针指向最后被插入的元素 允许删除的一端称为排头 队头 也用一个排头指针 front 指向排头元素的前一个位置假设队列q a1 a2 an 则a1称为对头元素 an成为队尾元素 队列按照先进先出或后进后出的原则组织数据 在队列中rear与fornt共同反映了队列中元素动态变化的情况 在队列末尾插入一个元素 入队运算 只涉及队尾指针rear的变化 要删除队列中的排头元素 退队运算 只涉及排头指针front的变化 退队 入队 front rear 2 循环队列及其运算 队列的顺序存储结构一般采用循环队列的形式循环队列 将队列存储空间的最后一个位置绕到第一个位置 形成逻辑上一环状空间 供队列循环使用 在循环队列结构中 当存储空间最后一个位置被使用而再要进入队运算时 只要存储空间的第一个位置空闲 便可将元素加到第一个位置 即将存储空间的第一个位置作为队尾 front rear 初始状态 REAR FRONT M Q 1 8 Q 1 8 Q 1 8 具有6个元素的循环队列 加入XY后的循环队列 退出一个元素后的循环队列 front rear front rear rear front 每进行一次入队运算 队尾指针就进一 当队尾指针rear m 1时 则rear 1每进行一次退队运算 队头指针就进一 当队头指针front m 1时则front 1 假设循环的初始状态为空 即s 0 且front rear m 1 入队运算 在循环队尾加一个新元素 这个运算有两个基本操作 首先将队尾指针进一 即rear rear 1 并当rear m 1时置rear 1 然后将新元素插入到队尾指针指向的位置 当循环队列非空且队尾指针等于排头指针时 说明循环队列已满 不能进行入队运算 这种情况称为上溢 2 退队运算 在循环队的排头退一个元素并赋给指定的变量 首先将排头指针进一 即front front 1 并当front m 1时置front 1 然后将排头指针指向的元素赋给变量当循环队列为空时 不能进行退队运算 这种情况称为下溢 栈和队列的共同特点是A 都是先进先出B 都是先进后出C 只允许在端点处插入和删除元素D 没有共同点如果进栈序列为e1 e2 e3 e4 则可能的出栈序列是A e3 e1 e4 e2B e2 e4 e3 e1C e3 e4 e1 e2D 任意顺序 1 5线性链表 考点12 线性链表的结构及其基本运算1 什么是线性链表线性表顺序存储的缺点 插入删除时移动大量元素 有 上溢 情况 空间不便于动态分配 为了适应线性表的链式存储结构 计算机存储空间被划分为若干字节 通常称这些小块为存储结点 为了存储线性表中的每一个元素 一方面要存储数据元素的值 另一方面要存储各数据元素之间的前后件关系 将存储空间中的每一个存储结点分为两部分 一部分用于存储数据元素的值 称为数据域 另一部分用于存放下一个数据元素的存储序号 即存储结点的地址 即指向后件结点 称为指针域 数据结构中的每一个数据结点对应于一个存储单元 这种存储单元成为存储结点 简称结点 数据域指针域 V i NEXT i 存储序号i 存储序号 V i NEXT i HEAD 3 1 9 5 10 物理状态 逻辑状态 在线性表的链式存储结构中 各数据结点的存储序号是不连续的 并且各结点在存储空间中的位置关系与逻辑关系也不一致 在线性链表中 各数据之间的前后件关系是由各结点的指针域来指示 指向线性表中第一个结点的指针HEAD称为头指针 当HEAD Null 或0 时称为空表 可以从头指针开始 沿各结点的指针扫描到链表中的所有结点 在某些应用中 对线性表链表中的每个结点设置两个指针 一个称为左指针 用以指向其前件 一个称为右指针 用以指向其后件 这样的链表称为双向链表 2 带链的栈栈也是线性表 也可以采用链式存储结构在实际应用中 带链的栈可以用来收集计算机存储空间中所有的空闲结点 这种带链的栈称为可利用栈 当计算机系统或用户程序需要存储结点时 就可以从中取出栈顶结点 当计算机或用户释放一个存储结点时 则要将该结点放回到可利用栈的栈顶 计算机中的所有可利用空间都可以以结点为单位链接在可利用栈中 Top p Top Top P 带链的栈 将结点P送回可利用栈 在从可利用栈取得一个结点 可利用栈及其运算 0 p P 新结点P插入队列 在带链的队列中删除一个结点 带链队列及其运算 front rear front front rear rear 3 带链的队列队列也是线性表 也可以采用链式存储结构 考点13 线性链表的基本运算 1 在线性链表中查找指定的元素 在非空线性链表中寻找包含指定元素X的前一个结点P 从头指针指向的结点开始往后沿指针进行扫描 直到后已经没有结点或下一个结点的数据域为x为止 有两种可能 当线性链表中存在包含元素X的结点时 则找到的P为第一次遇到的包含元素X的前一个结点的序号 当线性表中不存在包含元素X的结点时 则找到的P为线性链表中的最后一个结点 2 线性链表的插入为了要在线性链表中插入一个新元素 首先要给该元素分配一个新结点 以便用于存储该元素的值 新结点可以从可利用栈中取得 然后将存放新元素值的结点链接到线性表中指定的位置 p Top q head P插入到q之后 q head 3 线性链表的删除线性链表的删除包含指定元素的结点 首先要在线性链表中找到这个结点 然后将要删除的结点放回到可利用栈 无论是线性链表的插入还是删除 不需要移动表是的数据 只需改变有关结点的前一个结点的指针域即可 Top 考点14 循环链表及其基本运算 与线性链表相比 循环链表具有 1 在循环链表中增加一个表头结点 其数据域为任意或根据需要设置 指针域指向线性表的第一个元素的结点 循环链表的头指针指向表头结点 2 循环链表中最后一个结点的指针域不是空 而是指向表头结点 即循环链表中 所有结点的指针构成一个循环状 在循环链表中 只要指出表中的任何一个结点的位置 就可以从它出发访问到表中其他所有的结点 1 6树与二叉树 考点15 树的定义树是一种简单的非线性结构 在树这种数据结构中 所有数据元素之间的关系具有明显示的层次特征 在用图形表示树这种数据结构时 很像自然界的树 只不过是一棵倒长的树 这种数据结构就用 树 来命名 树是由n n o 个节点组成的有限集合在树的图形表示中 总是认为在用直线连起来的两端结点 上端结点是前件 下端结占是后件 表示前后件关系的箭头可以省略 每一个结点只有一个前件 称为父结点 没有前件的结点只有一个 称为树的根结点 简称树的根 每一个结点可以有多个后件 它们都称为该结点的子结点 没有后件的结点称为叶子结点 度 一个结点所拥有的后件个数称为该结点的度 根结点在第一层 同一层的所有结点的所有子结点都在下一层 树的最大层次称为树的深度 在树中 叶子结点没有子树 考点16 二叉树的定义及其基本性质 1 什么是二叉树二叉树具有两个特点 1 非空二叉树只有一个根结点 2 每一个结点最多只有两棵子树 且分别称为该结点的左子树与右子树 D 只有根结点的二叉树 A T B Z X C Y P 2 二叉树的基本性质 1 在二叉树的第K层上 最多有2个结点 2 深度为m的二叉树最多有2 1个结点 3 在任意一棵二叉树中 度为0的结点 即叶子结点 总是比度为2的结点多一个 4 具有n个结点的二叉树 其深度至少为 log2n 1其中 log2n 表示 log2n 的整数部分 K 1 m 3 满二叉树与完全二叉树 满二叉树 除最后一层外 每一层上的所有结点都有两个子结点 每一层上的结点数都达到最大值 即在满二叉树的第k层上有2 k 1 个结点 且深度为m的二叉树有2 k 1个结点完全二叉树 除最后一层外 每一层上的结点数均达到最大值 在最后一层上只缺少右边的若干结点 对于完全二叉树 叶子结点只可能在层次最大的两层上出现 对于任何一个结点 若其右分支下的子孙结点的最大层次为P 则其左分支下的子孙结点的最大层次或为P 或为p 1 性质5 具有n个结点的完全二叉树的深度为 log2n 1 性质6 设完全二叉树共有n个结点 如果从根结点开始 按层序 每一层从左到右 用自然数1 2 n给结点进行编号 则对于编号为k k 1 2 n 的结点有以下结论 1 若k 1 则该结点为根结点 它没有父结点 若k 1 则该结点的父结点编号为int k 2 2 若2k n 则编号为k的结点的左子结点编号为2k 否则该结点无左子结点 显然也没右子结点 3 若2k 1 n 则编号为k的结点的右子结点编号为2k 1 否则该结点为右子结点 1 2 3 4 5 6 1 2 3 4 5 6 7 深度为3的完全二叉树 深度为3的满二叉树 1 2 5 3 6 4 7 8 深度为4的完全二叉树 满二叉树是完全二叉树 完全二叉树不是满二叉树 1 6 3二叉树的存储结构 用于存储二叉树中各元素的存储结点由两部分组成 数据域和指针域 用于二叉树的存储结点的指针域有两个 一个用于指向该结点的左子结点的存储地址 称为左指针域 另一个用于指向该结点的右子结点的存储地址 称为右指针域由于二叉树的存储结构中每一个存储结点有两个指针域 因此 二叉树的链式存储结构也称为二叉链表 i 左指针域 右指针域 数据域 考点17 二叉树的遍历 F C A D B E G H P 1 前序遍历 首先遍历根结点 再遍历左子树 最后遍历右子树FCADBEGHP2 中序遍历 首先遍历左子树 再遍历根结点 再遍历右子树 ACBDFEHGP3 后序遍历 首先遍历左子树 再右子树 最后根结点 ABDCHPGEF 例 以下数据结构中不属于线性数据结构的是 A 队列B 线性表C 二叉树D 栈在一棵二叉树上第5层的结点数最多是 A 8B 16C 32D 15 下列叙述中正确的是 A 线性表是线性结构B 栈与队列是非线性结构C 线性链表是非线性结构D 二叉树是线性结构设一棵完全二叉树共有699个结点 则在该二叉树中的叶子结点数为 A 349B 350C 255D 351 下列关于栈的叙述中正确的是 A 在栈中只能插入数据B 在栈中只能删除数据C 栈是先进先出的线性表D 栈是先进后出的线性表栈和队列的共同点是 A 都是先进后出B 都是先进先出C 只允许在端点处插入和删除元素D 没有共同点 在先左后右的原则下 根据访问根结点的次序 二叉树的遍历可以分为三种 前序遍历 遍历和后序遍历 已知二叉树后序遍历序列是dbaec 中序遍历序列是debac 它的前序遍历序列是 A cedbaB acbedC decabD deabc 1 7查找技术 查找是指的一个给定的数据结构中查找某个指定的元素 考点18 顺序查找与二分查找算法1 顺序查找从线性表的第一个元素开始 顺序扫描 依次将扫描的关键字和待寻找的k值比较 若相等 则查找成功 若扫描完毕 仍未找到 则扫描失败 以下方式只能顺序查找 1 线性表为无序表 2 有序线性表采用