算法与数据结构.ppt

计算机二级C语言 上机时间90分钟 笔试时间90分钟 考核方式 笔试 公共基础 30 C语言程序设计 70 选择题20分 填空题10分 选择题50分 填空题20分 机试 C语言程序设计 基本操作题 填空题 简单应用题 改错题 综合应用题 编程题 算法与数据结构 公共基础第一部分 本章考核内容约占13 主要包括一下几个方面 算法复杂度栈 队列 线性链表的基本概念树的结点计算和遍历排序的最坏次数计算 考点1算法的基本概念1 算法是指解题方案的准确而完整的描述 换句话说 算法是对某一特定问题而采取的方法和步骤 对于一个问题 如果可以通过一个计算机程序 在有限的存储空间内运行有限的时间而得到正确的结果 则称这个问题是可解的 算法不等于程序 也不等于计算方法 程序的编制不可能优于算法的设计 考点1算法的基本概念2 算法特征 1 可行性2 确定性3 有穷性 即算法必须能在执行有限个步骤之后终止 在有限的时间内完成4 拥有足够的情报 针对实际问题而设计的算法 执行后能够得到满意的结果 每一条指令的含义明确 无二义性 并且在任何条件下 算法只有唯一的一条执行路径 即相同的输入只能得出相同的输出 算法必须在有限的时间内完成 有两重含义 一是算法中的操作步骤为有限个 二是每个步骤都能在有限时间内完成 算法中各种运算总是要施加到各个运算对象上 而这些运算对象又可能具有某种初始状态 这就是算法执行的起点或依据 考点1算法的基本概念 2008年4月 算法的有穷性是指 A 算法程序的运行时间是有限的B 算法程序所处理的数据量是有限的C 算法程序的长度是有限的D 算法只能被有限的用户使用 答案 A 算法必须在有限的时间内完成 有两重含义 一是算法中的操作步骤为有限个 二是每个步骤都能在有限时间内完成 考点1算法的基本概念3 算法的基本元素一个算法通常由两种基本要素组成 一是对数据对象的运算和操作 二是算法的控制结构 一般的计算机系统中 基本运算和操作包括以下4类 算术运算 加 减 乘 除等运算 逻辑运算 与 或 非等运算 关系运算 等于 不等于 大于 小于等运算 数据传输 赋值 输入 输出等操作 考点1算法的基本概念3 算法的基本元素算法的控制结构算法各操作之间的执行顺序称为算法的控制结构 算法的控制结构包括 顺序 选择 分支 和循环 考点1算法的基本概念4 算法设计的基本方法计算机解题的过程实际上是在实施某种算法 这种算法称为计算机算法 列举法 例如 百钱买百鸡 归纳法 递推 递归 例如 汉诺塔 减半递推技术 回溯法 例如 求解皇后问题 考点2算法的复杂度 算法的复杂度包括算法时间复杂度和算法空间复杂度 1 算法时间复杂度算法时间复杂度是指执行算法所需要的计算工作量 在度量一个算法的工作量时 用算法在执行过程中所需基本运算的执行次数来度量算法的工作量 分析算法工作量的方法 平均性和最坏情况复杂性 考点2算法的复杂度 2 算法空间复杂度一个算法的空间复杂度 一般是指执行这个算法所需要的内存空间大小 一个算法所占用的存储空间包括算法程序所占的空间 输入的初始数据所占的空间以及算法执行过程中所需要的额外空间 考点2算法的复杂度 2005年9月 算法复杂度主要包括时间复杂度和 复杂度 2006年9月 下列叙述中正确的是 A 一个算法的空间复杂度大 则其时间复杂度也必定大B 一个算法的空间复杂度大 则其时间复杂度必定小C 一个算法的时间复杂度大 则其空间复杂度必定小D 上述三种说法都不对 答案 D 空间 考点2算法的复杂度 2007年4月 下列叙述中正确的是 A 算法的效率只与问题的规模有关 而与数据的存储结构无关B 算法的时间复杂度是指执行算法所需要的计算工作量C 数据的逻辑结构与存储结构是一一对应的D 算法的时间复杂度与空间复杂度一定相关 答案 B 考点3数据结构1 基本概念1 数据 描述客观事物的数 字符以及所有能输入到计算机中并被计算机程序加工处理的符号的集合 2 数据元素 数据的基本单位 即数据集合中的个体 有时一个数据元素由若干个数据项组成 在这种情况下 将数据元素称为记录 由记录所组成的线性表为文件 考点3数据结构1 基本概念3 数据项 具有独立意义的最小数据单位 4 数据对象 具有相同特性的数据元素的集合 是数据的子集 5 结构 指数据元素之间的前后件关系 考点3数据结构1 基本概念6 数据结构 指相互关联的数据元素的集合 数据结构包含两方面信息 一是表示数据元素的信息 二是表示各数据元素之间的前后件关系 例如 描述一年四季的季节名春 夏 秋 冬 可以作为季节的数据元素 在考虑一年4个季节的顺序关系时 则 春 是 夏 的前件 而 夏 是 春 的后件等 考点3数据结构2 数据的逻辑结构在以上所述的数据结构中 数据元素之间的前后件关系是指它们的逻辑关系 而与它们在计算机中的存储位置无关 因此 上面所述的数据结构实际上是数据的逻辑结构 1 概念 所谓数据的逻辑结构 是指反映数据元素之间逻辑关系的数据结构 考点3数据结构2 数据的逻辑结构2 表示 图形表示 集合 线性 树 图 考点3数据结构2 数据的逻辑结构2 表示 二元关系表示数据的逻辑结构有两个要素 一是数据元素的集合 通常记为D 二是D上的关系 它反映了D中各数据元素之间的前后件关系 通常记为R 即一个数据结构可以表示成 B D R 其中B表示数据结构 为了反映D中各数据元素之间的前后件关系 一般用二元组来表示 考点3数据结构2 数据的逻辑结构2 表示 二元关系表示例如 一年四季的数据结构可以表示成 B D R D 春 夏 秋 冬 R 春 夏 夏 秋 秋 冬 考点4数据的存储结构1 概念 数据的逻辑结构在计算机存储空间的存放形式称为数据的存储结构 考点4数据的存储结构2 存储形式 数据元素之间的关系在计算机中有两种不同的表示方法 顺序映像和非顺序映像 并由此得到两种不同的存储结构 顺序存储结构和链式存储结构 顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系 非顺序映像的特点是借助指示元素存储地址的指针 Pointer 表示数据元素之间的逻辑关系 数据元素之间具有的逻辑关系 结构 线性关系 线性结构 如线性表 线性链表 堆栈 队列等 具有某种逻辑结构的数据在计算机存储器中的存储方式 存储映象 顺序存储结构 链式存储结构 用一组地址连续的存储单元依次存放数据元素 数据元素之间的逻辑关系通过元素的地址直接反映 用一组地址任意的存储单元依次存放数据元素 数据元素之间的逻辑关系通过指针间接地反映 非线性关系 非线性结构 如树 二叉树 图等 考点4数据的存储结构注意 数据元素在计算机存储空间中的位置关系可能与逻辑关系不同 数据的逻辑结构可以表示成多种存储结构 采用不同的存储结构 其数据处理的效率是不同的 1 研究数据元素之间的客观联系 2 研究具有某种逻辑关系的数据在计算机存储器内的存储方式 3 研究如何在数据的各种结构 逻辑的和物理的 的基础上对数据实施一系列有效的基本操作 考点4数据的存储结构 2005年4月 数据的存储结构是指 A 存储在外存中的数据B 数据所占的存储空间量C 数据在计算机中的顺序存储方式D 数据的逻辑结构在计算机中的表示 答案 D 考点4数据的存储结构 2005年9月 下列叙述中正确的是 A 一个逻辑数据结构只能有一种存储结构B 数据的逻辑结构属于线性结构 存储结构属于非线性结构C 一个逻辑数据结构可以有多种存储结构 且各种存储结构不影响数据处理的效率D 一个逻辑数据结构可以有多种存储结构 且各种存储结构影响数据处理的效率 答案 D 考点4数据的存储结构 2007年9月 下列叙述中正确的是 A 数据的逻辑结构与存储结构必定是一一对应的B 由于计算机存储空间是向量式的存储结构 因此 数据的存储结构一定是线性结构C 程序设计语言中的数组一般是顺序存储结构 因此 利用数组只能处理线性结构D 以上三种说法都不对 答案 D 考点4数据的存储结构 2008年9月 下列叙述中正确的是 A 顺序存储结构的存储一定是连续的 链式存储结构的存储空间不一定是连续的B 顺序存储结构只针对线性结构 链式存储结构只针对非线性结构C 顺序存储结构能存储有序表 链式存储结构不能存储有序表D 链式存储结构比顺序存储结构节省存储空间 答案 A 考点5线性结构与非线性结构 根据数据结构中各数据元素之间前后件关系的复杂程度 将数据结构分为两大类型 线性结构非线性结构 逻辑结构 a1a2a3 a30 存储结构 1 顺序存储结构 线性结构 线性表 2 链式存储结构 考点5线性结构与非线性结构 如果一个非空的数据结构满足两个条件 一是有且只有一个根结点 二是每一个结点最多有一个前件 也最多有一个后件 则称该数据结构为线性结构 线性结构又称线性表 注意 在一个线性结构中插入或删除任何一个结点后还应是线性结构 如果一个数据结构不是线性结构 则称为非线性结构 考点6线性表的基本概念线性表是最简单 最常用的一种数据结构 线性表由一组数据元素构成的有限序列 如一年的四个季节 线性表中结点的个数n称为线性表的长度 n 0时 称为空表 考点6线性表的基本概念非空线性表有如下一些结构特征 有且只有一个根结点 它无前件 有且只有一个终端结点 它无后件 除根结点与终端结点外 其他所有结点有且只有一个前件 也有且只有一个后件 考点7线性表的顺序存储在计算机中存放线性表的一种最简单的方法是顺序存储 也称为顺序分配 用顺序存储结构存储的线性表称作顺序表 考点7线性表的顺序存储线性表的顺序存储结构具有以下两个基本特点 1 线性表中所有元素所占的存储空间是连续的 2 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 由此可以看出 在线性表的顺序存储结构中 其前后件两个元素在存储空间中是紧邻的 且前件元素一定存储在后件元素的前面 可以通过计算机直接确定第i个结点的存储地址 例 一维数组的存储结构inta 5 a 0 a 1 a 2 a 3 a 4 1000 1006 数组元素地址 数组起始地址 元素下标 sizeof 数组类型 a 3 的地址为 1000 3 2 1006 考点7线性表的顺序存储注意 在线性表的顺序存储结构中 其前后件两个元素在存储空间中是紧邻的 且前件元素一定存储在后件元素的前面 考点8顺序表的操作1 插入顺序表的插入运算 在一般情况下 要在第i 1 i n 个元素之前插入一个新元素时 首先要从最后一个 即第n个 元素开始 直到第i个元素之间共n i 1个元素依次向后移动一个位置 移动结束后 第i个位置就被空出 然后将新元素插入到第i项 插入结束后 线性表的长度就增加了1 该运算是在线性表的第i 1个数据元素与第i个数据元素之间插入一个由符号item表示的数据元素 使长度为n的线性表 a1 a2 ai 1 ai ai 1 an 1 an 转换成长度为n 1的线性表 a1 a2 ai 1 item ai an 1 an 考点8顺序表的操作1 插入向顺序表中插入一个新结点时 由于需要保持运算的结果仍然是顺序存储 所以可能要移动一系列结点 若顺序表中结点个数为n 在向每个位置插入的概率相等的情况下 插入一个结点平均需要移动之结点个数为n 2 算法的时间复杂度是O n 顺性表的插入运算时需要移动元素 在等概率情况下 平均需要移动n 2个元素 考点8顺序表的操作2 删除顺序表的删除运算 在一般情况下 要删除第i 1 i n 个元素时 则要从第i 1个元素开始 直到第n个元素之间共n i个元素依次向前移动一个位置 删除结束后 线性表的长度就减小了1 该运算是把线性表的第i个数据元素从线性表中去掉 使得长度为n的线性表 a1 a2 ai 1 ai ai 1 an 1 an 转换成长度为n 1的线性表 a1 a2 ai 1 ai 1 an 1 an 考点8顺序表的操作2 删除从顺序表中删除一个结点可能需要移动一系列结点 在等概率的情况下 删除一个结点平均需移动结点个数为 n 1 2 算法的时间复杂度也是O n 考点9线性表的链式存储 为了适应线性表的链式存储结构 计算机的内存空间被划分为多个小块 每个小块占若干个字节 通常称这些小块为存储结点 每个存储结点分为两部分 一部分用于存储数据元素的值 称为数据域 一部分用于存储下一个数据元素的存储序号 即存储结点的地址 称为指针域 考点9线性表的链式存储 1 线性链表 单链表 所谓线性链表就是链式存储的线性表 其结点中只含有一个指针域 用来指出其后继结点的存储位置 线性链表的最后一个结点无后继结点 它的指针域为空 记为NULL或 另外还要设置表头指针head 指向线性链表的第一个结点 考点9线性表的链式存储 1 线性链表 单链表 对线性链表可以进行插入 删除等运算 注意 做删除运算时改变的是被删结点的前一个结点中指针域的值 因此 若要查找且删除某一结点 则应在查找被删结点的同时记下它前一个结点的位置 考点9线性表的链式存储 2 双向链表线性单链表中 每个结点只有一个指针域 由此指针只能找到后件节点 为了弥补线性单链表的这个缺点 在某些应用中 对线性单链表的每个结点设置两个指针 一个称为左指针 Llink 用以指向其前件结点 另一个称为右指针 Rlink 用以指向其后件结点 这样的线性链表称为双向链表 考点9线性表的链式存储 3 循环链表所谓循环链表是指链表的最后一个结点的指针值指向第一个结点 整个链表形成一个环 线性链表 考点9线性表的链式存储 注意 在链式存储结构中 存储数据结构的存储空间可以不连续 各数据结构的存储顺序与数据元素之间的逻辑关系可以不一致 而数据元素之间的逻辑关系是由指针域来确定的 考点9线性表的链式存储 2005年4月 对于线性链表的描述中正确的是 A 存储空间不一定是连续 且各元素的存储顺序是任意的B 存储空间不一定是连续 且前件元素一定存储在后件元素的前面C 存储空间必须连续 且前件元素一定存储在后件元素的前面D 存储空间必须连续 且各元素的存储顺序是任意的 答案 A 考点10栈及其基本运算 1 栈的定义栈是一种特殊的线性表 栈是限定仅在表尾 表的一端 进行插入和删除运算的线性表 表尾称为栈顶 top 表头叫做栈底 bottom 栈中无元素时称为空栈 栈遵守 后进先出 LIFO 的操作原则 具有记忆功能 考点10栈及其基本运算 2 栈的存储栈的既可以用顺序存储结构 也可用链式存储结构 在程序设计语言中 用一维数组S 1 m 作为栈的顺序存储空间 其中m为栈的最大容量 通常 栈底指针指向栈空间的低地址一端 即数组的起始地址这一端 栈用链式存储结构 带链的栈称为可利用栈 考点10栈及其基本运算 3 栈的运算1 入栈运算 指在栈顶位置插入一个新元素 其方法是先将栈顶指针top进一 即top加1 然后将新元素插入到栈顶指针指向的位置 注意 栈 上溢 错误 栈顶指针为m 2 退栈运算 指取出栈顶元素并赋给一个指定的变量 其方法是先将栈顶元素赋给一个指定的变量 然后将栈顶指针top退一 即top减1 注意 栈 下溢 错误 栈顶指针为0 考点10栈及其基本运算 3 栈的运算3 读栈顶元素 指将栈顶元素赋给一个指定的变量 注意 此元素不删除栈顶元素 只是将其赋给一个变量 因此在这个运算中 栈顶指针不会改变 考点10栈及其基本运算 2005年4月 下列关于栈的描述中错误的是 A 栈是先进后出的线性表B 栈只能顺序存储C 栈具有记忆作用D 对栈的插入与删除操作中 不需要改变栈底指针 答案 B 考点10栈及其基本运算 2005年9月 下列关于栈的描述正确的是 A 在栈中只能插入元素而不能删除元素B 在栈中只能删除元素而不能插入元素C 栈是特殊的线性表 只能在一端插入或删除元素D 栈是特殊的线性表 只能在一端插入元素 而在另一端删除元素 答案 C 考点10栈及其基本运算 2006年4月 按照 后进先出 原则组织数据的数据结构是 A 队列B 栈C 双向链表D 二叉树 2006年9月 按 先进后出 原则组织数据的数据结构是 答案 栈 B 考点10栈及其基本运算 2008年4月 下列关于栈的叙述正确的是 A 栈按 先进先出 组织数据B 栈按 先进后出 组织数据C 只能在栈底插入数据D 不能删除数据 答案 B 考点10栈及其基本运算 2008年9月 一个栈的初始状态为空 现将元素1 2 3 4 5 A B C D E依次入栈 然后再依次出栈 则元素出栈的顺序是 A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA 答案 B 考点11队列及其基本运算 1 队列的定义队列是一种特殊的线性表 队列是限定所有的插入都在表的一端进行 所有的删除都在表的另一端进行的线性表 允许插入的一端称为队尾 通常用一个称为尾指针 rear 的指针指向队尾元素 允许删除的一端称为队头 通常用一个称为头指针 front 的指针指向排头元素的前一个位置 考点11队列及其基本运算 1 队列的定义队列遵守 先进先出 FIFO 的操作原则 队尾指针和队头指针共同反映了队列中元素的动态变化情况 2 队列的存储队列既可以用顺序存储结构 一般采用循环队列 也可用链式存储结构 3 队列的运算入队运算 退队运算 取队头元素 检查队列是否为空 清除等 考点11队列及其基本运算 4 循环队列 顺序存储结构 循环队列就是将队列存储空间的最后一个位置绕到第1个位置 形成逻辑上的环状空间 供队列循环使用 考点11队列及其基本运算 4 循环队列入队运算 入队运算是指在循环队列的队尾加入一个新元素 rear加1 当rear m 1时 则置rear 1 退队运算 退队运算是指在循环队列的排头位置退出一个元素 front加1 当front m 1时 则置front 1 考点11队列及其基本运算 4 循环队列当循环队列满时有front rear 而当循环队列为空时也有front rear 为了那个区分队列是满还是队列空 通常需要增加一个标示s s 0表示队列空 s 1表示队列非空 由此可得队列满与空的条件 队列空的条件为s 0 队列满的条件为s 1且front rear 考点11队列及其基本运算 2008年4月 设某循环队列的容量为50 头指针Front 5 指向队头元素的前一位置 尾指针rear 29 指向队尾元素 则该循环队列中共有个元素 答案 24 考点11队列及其基本运算 2008年9月 下列叙述中正确的是 A 循环队列中有队头和队尾两个指针 因此 循环队列是非线性结构B 在循环队列中 只需要队头指针就能反映队列中元素的动态变化情况C 在循环队列中 只需要队尾指针就能反映队列中元素的动态变化情况D 循环队列中元素的个数是由队头指针和队尾指针共同决定 答案 D 考点11队列及其基本运算 2005年9月 数据结构分为逻辑结构和存储结构 循环队列属于结构 2006年9月 数据结构分为线性结构和非线性结构 带链的队列属于 答案 存储 线性 考点11队列及其基本运算 2007年4月 下列对队列的叙述正确的是 A 队列属于非线性表B 队列按 先进后出 原则组织数据C 队列在队尾删除数据D 队列按 先进先出 原则组织数据 2007年9月 线性表的存储结构主要分为顺序存储结构和链式存储结构 队列是一种特殊的线性表 循环队列是队列的存储结构 答案 D 顺序 考点12树的基本概念1 树树是一种简单的非线性结构 在树这种结构中 所有数据元素之间的关系具有明显的层次特性 一般认为 直线连接起来的两端结点中 上端结点是前件 下端结点是后件 具有层次关系的数据都可以用树来表示 考点12树的基本概念2 常用术语根结点 没有前件的结点 只有一个 叶子结点 没有后件的结点 父结点 每一个结点只有一个前件 该前件结点称为父结点 考点12树的基本概念2 常用术语子结点 每一个结点可以有多个后件 它们都称为该结点的子结点 兄弟 Sibling 具有相同亲结点的结点互为兄弟 结点的度 Degree 一个结点所拥有的后件的个数 树的度 树中各结点的度的最大值 考点12树的基本概念2 常用术语结点的层数 根结点的层数为1 同一层上所有结点的所有子结点都在下一层 树的深度 树的最大层次 子树 以某结点的一个子结点为根构成的树称为该结点的一棵子树 叶子结点没有子树 考点13二叉树及其基本性质 1 二叉树定义二叉树是一种很有用的非线性结构 二叉树具有以下两个特点 1 非空二叉树只有一个根结点 2 每一个结点最多有两棵子树 且分别称为该结点的左子树与右子树 二叉树的5种基本形态 考点13二叉树及其基本性质 2 二叉树的性质 在二叉树的i层上 最多有2i 1个结点 i 1 深度为k的二叉树最多有2k 1个结点 k 1 对任何一棵二叉树T 如果叶子结点 度为0 的数为n0 度为2的结点数为n2 则n0 n2 1 具有n个结点的二叉树的深度至少为 log2n 1 1 一棵非空二叉树的第i层最多有2i 1个结点 i 1 证明 采用归纳法 1 当i 1时 结论显然正确 非空二叉树的第1层有且仅有一个结点 即树的根结点 2 假设对于第j层 1 j i 1 结论也正确 即第j层最多有2j 1个结点 3 有定义可知 二叉树中每个结点最多只能有两个孩子结点 若第i 1层的每个结点都有两棵非空子树 则第i层的结点数目达到最大 而第i 1层最多有2i 2个结点已由假设证明 于是 应有2 2i 2 2i 1 证毕 2 深度为h的非空二叉树最多有2h 1个结点 证明 由性质1可知 若深度为h的二叉树的每一层的结点数目都达到各自所在层的最大值 则二叉树的结点总数一定达到最大 即有20 21 22 2i 1 2h 1 2h 1 证毕 3 若非空二叉树有n0个叶结点 有n2个度为2的结点 则n0 n2 1 证明 设该二叉树有n1个度为1的结点 结点总数为n 有n n0 n1 n2 1 设二叉树的分支数目为B 有B n 1 2 这些分支来自度于为1的结点与度度为2结点 即B n1 2n2 3 联列关系 1 2 与 3 可得到n0 n2 1 证毕 4 具有n个结点的完全二叉树的深度h log2n 1 证明 略 考点13二叉树及其基本性质 2 二叉树的性质 2005年4月 某二叉树中度为2的结点有18个 则该二叉树中有 个叶子结点 2005年9月 一棵二叉树第六层 根结点为第一层 的结点数最多为结构 2007年4月 某二叉树中有n个度为2的结点 则该二叉树中的叶子结点数为 A n 1B n 1C 2nD n 2 答案 19 A 32 考点13二叉树及其基本性质 2 二叉树的性质 2007年9月 一棵二叉树共有70个叶子结点与80个度为1的结点 则该二叉树中的总结点数为 A 219B 221C 229D 231 答案 A 考点13二叉树及其基本性质 3 满二叉树满二叉树与完全二叉树是两种特殊形态的二叉树 所谓满二叉树是指除最后一层外 每一层上的所有结点都有两个子结点 在满二叉树中 每一层上的结点数都达到最大值 考点13二叉树及其基本性质 3 满二叉树 2006年4月 在深度为7的满二叉树中 叶子结点的个数为 A 32B 31C 64D 63 2007年4月 在深度为7的满二叉树中 度为2的结点个数为 2008年4月 深度为5的满二叉树有个叶子结点 答案 16 C 63 考点13二叉树及其基本性质 4 完全二叉树1 定义 所谓完全二叉树是指除最后一层外 每一层上的结点数均达到最大值 在最后一层上只缺少右边的若干结点 考点13二叉树及其基本性质 4 完全二叉树2 性质 具有n个结点的完全二叉树的深度为 设完全二叉树共有n个结点 如果从根结点开始 按层序 每一层从左到右 用自然1 2 n给结点进行编号 则对于编号为k k 1 2 n 的结点有以下结论 考点13二叉树及其基本性质 4 完全二叉树若是k 1 则该结点为根结点 它没有父结点 若k 1 则该结点的父结点编号为INT k 2 若2k n 则编号为k的结点的左子结点编号为2k 否则该结点无左子结点 若2k 1 n 则编号为k的结点的右子结点编号为2k 1 否则该结点无右子结点 考点14二叉树的存储结构二叉树的存储通常采用链接方式 每个结点除存储结点自身的信息外再设置两个指针域llink和rlink 分别指向结点的左子女和右子女 当结点的某个指针为空时 则相应的指针值为空 NULL 考点15二叉树的遍历 遍历 或称周游 是树形结构的一种重要运算 不重复访问二叉树中的所有结点 可以按多种不同的次序遍历树形结构 二叉树的基本组成部分是 根 N 左子树 L 右子树 R 因此可有NLR LNR LRN NRL RNL RLN六种遍历次序 以下着重介绍前序遍历 中序遍历 后序遍历 考点15二叉树的遍历 遍历规则 前序遍历 先访问根结点 然后遍历左子树 最后遍历右子树 中序遍历 先访问左子树 然后遍历根结点 最后遍历右子树 后序遍历 先访问左子树 然后遍右子树 最后遍历根结点 考点15二叉树的遍历 2007年4月 对下列二叉树进行前序遍历的结果为 A DYBEAFCZXB YDEBFZXCAC ABDYECFXZD ABCDEFXYZ 答案 C 考点15二叉树的遍历 2006年9月 对下列二叉树进行中序遍历的结果是 A ACBDFEGB ACBDFGEC ABDCGEFD FCADBEG 答案 A 考点15二叉树的遍历 2008年9月 对下列二叉树进行中序遍历的结果是 答案 DBXEAYFZC 考点15二叉树的遍历 2006年4月 对如下二叉树进行后序遍历的结果为 A ABCDEFB DBEAFCC ABDECFD DEBFCA 答案 D 考点16顺序查找 顺序查找 顺序搜索 是指在线性表中查找指定的元素 查找方法 从第一个元素开始 逐个比较 若相等则查找成功 若找遍所有结点都不相等 则查找失败 优点 对线性表的结点逻辑次序没有要求 不必排序 对线性表的存储结构也没有要求 顺序存储 链式存储皆可 缺点 平均检索长度大 对于长度为n的有序线性表 在最坏的情况下 顺序查找需要比较n次 平均查找次数为n 2 考点16顺序查找 2005年4月 对长度为n的线性表进行顺序查找 在最坏情况下所需要的比较次数为 A log2nB n 2C nD n 1 2006年9月 在长度为64的有序线性表中进行顺序查找 最坏情况下需要比较的次数为 A 63B 64C 6D 7