提高组高中组初赛复习资料PPT课件.ppt

数据结构复习 1 一 栈1 栈的定义栈是限制在线性表的一端进行插入和删除运算的线性表 又称为后进先出的线性表 2 栈的特点 后进先出 LIFO 3 栈的基本运算入栈 push s e 出栈 pop s e 等运算 S 栈 栈和队列 2 若已知一个栈的入栈顺序是1 2 3 n 其输出序列为P1 P2 P3 Pn 若P1是n 则Pi是 C A iB n 1C n i 1D 不确定以下哪一个不是栈的基本运算 B A 删除栈顶元素B 删除栈底的元素C 判断栈是否为空D 将栈置为空栈 3 设栈S的初始状态为空 元素a b c d e f依次入栈S 出栈的序列为b d c f e a 则栈S的容量至少应该是 A 6B 5C 4D 3E 2 4 元素R1 R2 R3 R4 R5入栈的顺序为R1 R2 R3 R4 R5 如果第一个出栈的是R3 那么第五个出栈的可能是 A R1B R2C R4D R5 5 二 队列1 队列的定义队列是限制在线性表的一端进行插入运算 另一端进行删除运算的线性表 2 队列的特点队列的特点是先进先出 FIFO 3 队列的基本运算入队 出队等 6 4 循环队列的优点循环队列的优点是 1 避免产生假溢出现象 2 避免出队 删除 时元素的移动现象 5 循环队列的表示首尾相接的循环数组q m 即 q 0 可以连在q m 1 之后 7 例3 2入队顺序是123456 求出队序列 根据队列的先进先出原则 出队序列是 123456例3 3循环队列用a 10 表示 f 队首指针 r 队尾指针 画出队列的初始状态 abcdefg入队后的状态 abcd出队且hijk入队后的状态 r 0123456789 f r f f r 例3 1若入栈顺序是123 写出所有可能的出栈序列 123132213231321 注意不可排成 312 8 已知队列 13 2 11 34 41 77 5 7 18 26 15 第一个进入队列的元素是13 则第五个出队列的元素是 B A 5B 41C 77D 13E 18 记T为一队列 初始时为空 现有n个总和不超过32的正整数依次入队 如果无论这些数具体为何值 都能找到一种出队的方式 使得存在某个时刻队列T中的数之和恰好为9 那么n的最小值是 9 一 数组1 数组的顺序存储方式和地址计算方法数组的存储方式有 1 行优先存储方式 2 列优先存储方式例5 1二维数组inta 10 10 以行优先存储 第1个元素的首址是100 每个元素的长度为2 求A 4 5 的存储首址 A 4 5 的存储首址 100 4 10 5 2 100 45 2 190 数组和广义表 10 已知数组中A中 每个元素A I J 在存贮时要占3个字节 设I从1变化到8 J从1变化到10 分配内存时是从地址SA开始连续按行存贮分配的 试问 A 5 8 的起始地址为 A A SA 144B SA 180C SA 222D SA 225 11 2 特殊矩阵压缩存储存储及压缩时的下标变换 1 对称矩阵和上 或下 三角矩阵的压缩存储 例 下三角矩阵的存储 按行主序方式 k i i 1 2 j当i j时0当i j 或为0 i j 2 对角矩阵例 以三对角矩阵为例 按行主序方式存储 仅存储非零部分 将一个a 100 100 的三对角矩阵以行主序存入一维数组B 298 中 元素a 65 64 在B数组中的位置k等于 k 12 3 稀疏矩阵的存储方式 三元组法矩阵A中有非零元个数s远远小于矩阵元素的总数 则称A为稀疏矩阵 0129000000000 30000140024000 M ijv 1212 139 31 3 3614 4324 13 二 广义表1 广义表的定义广义表ls d1 d2 dn 其中每个元素可以是原子 也可以是子表 称d1为表头 d2 dn为表尾 n 表示广义表的长度 括号层数表示广义表的深度 2 广义表与线性表的区别线性表 a1 a2 an 中每个元素都具有相同的类型 有两种存储结构 顺序表和链表 广义表 d1 d2 dn 中每个元素可以是原子 也可以是子表 可以将广义表看作是线性表的推广 由于原子和子表的类型不同 所以只能用链式存储结构 14 3 广义表的链式存储结构表结点原子结点 例5 2 A e a b c d 15 双向链表中有两个指针域llink和rlink 分别指向该结点的前驱及后继 设p指向链表中的一个结点 它的左右结点均非空 现要求删除结点P 则下面语句序列中正确的是 A p rlink llink p rlink p llink rlink p llink free p B P llink rlink p rlink p rlink llnik p llink free p C p rlink llink p llink p rlink llink rlink p rlink free p D p llink rlink p rlink p llink rlink llink p llink free p 16 一 二叉树或空 或由根和由互不相交的左子树 右子树构成 1 二叉链 树和二叉树 a b c d f g e a b c e d f g 17 性质1 在二叉树的第i i 0 层上至多有2i 1个结点 性质2 深度为k的二叉树中至多有2k 1个结点 k 0 性质3 对任何一棵二叉树T 如果其终端结点数为n0 度为2的结点数为n2 则n0 n2 1 性质4 有n个结点的完全二叉树的深度为 1 2 二叉树的性质 18 性质5 如果对一棵有n个结点的完全二叉树按层序从1开始编号 则对任一结点 i1 则其双亲结点是 i 2 2 如果2i n 则结点i的左孩子是结点2i 否则结点i无左孩子 3 如果2i 1 n 则结点i的右孩子是结点2i 1 否则结点i无右孩子 19 例 32个结点的完全二叉树 从根开始 按层次从左到右用1 32编号 请回答 1 它共有多少层 2 各层最左边的结点的编号是多少 3 编号为6的结点的左孩子的编号是多少 它的右孩子呢 4 编号为16的结点的左孩子的编号是多少 它的右孩子呢 5 对于编号为8的结点 它的父结点的编号是多少 编号为13的结点呢 编号为1的结点呢 20 二叉树的遍历 按某条搜索路径访问二叉树中每一个结点 使得每个结点被访问一次且仅被访问一次 遍历方法有4种 先序遍历 中序遍历 后序遍历 层次遍历 3 二叉树的遍历 21 先序遍历二叉树 1 访问根结点 2 先序遍历左子树 3 先序遍历右子树先序遍历序列 abcdfge 1 2 3 4 5 6 7 a b c d f g e 22 中序遍历二叉树 1 中序遍历左子树 2 访问根结点 3 中序遍历右子树中序遍历序列 bafgdce a b c d f g e 1 2 3 4 5 6 7 23 后序遍历二叉树 1 后序遍历左子树 2 后序遍历右子树 3 访问根结点后序遍历序列 bgfdeca a b c d f g e 1 2 3 4 5 6 7 24 a b c d f g e 1 2 3 4 5 6 7 层次遍历二叉树 按层次 1 k层 每层从左到右依次访问二叉树中的每一个结点 层次遍历序列 abcdefg 25 例6 1已知二叉树先序遍历序列是 abcdefg 中序遍历序列是 cbdaefg 1 画出该二叉树 2 写出后序遍历序列 cdbgfea 1 2 写出后序遍历序列 cdbgfea a b c d e f g 1 2 3 4 5 6 7 26 二 树 1 树的定义树 Tree 是n n 0 个结点的有限集 在任意一棵非空树中 1 有且仅有一个根结点 2 除根结点外 其余结点可分为m m 0 个互不相交的子树 27 3 树与二叉树的转换树转换成二叉树 左孩子 右兄弟 O a c g b d e f O a c g b d e f 28 2 树的存储结构 二叉链 O a c g b d e f 左孩子 右兄弟 29 4 树的遍历 O a c g b d e f 先序遍历树 1 访问根结点 2 先序遍历每一个子树先序遍历序列 oabcdfeg 30 O a c g b d e f 后序遍历树 1 后序遍历每一个子树 2 访问根结点后序遍历序列 bafdecg0 31 3 哈夫曼码 是一种前缀编码 即任一字符的编码都不是另一编码的前缀 左支用0表示 右支用1表示 1 二叉树的带权路径长度WPL wklkk 1其中 n 叶子结点个数 wk 第k个叶子的权 lk 第k个叶子到根的路径长度 2 Huffman树的构造方法 1 将 w1 w2 wn 看成n个二叉树 2 选择2个根结点的值最小的二叉树 构造1个新的二叉树 直至剩1个树止 n 三 Huffman树 32 1 构造huffman树 以小值为左孩子 2 在哈夫曼树的所有左分支上编上号码 0 右分支上编上号码 1 3 将根结点到每个叶子结点的路径编码串起来 得到字符集的哈夫曼编码 4 25 36 50 2 8 10 14 4 2 5 5 385 例6 8设通信用8个字符abcdefgh 各字符使用的相对频率分别为25 36 2 5 8 14 10 50 设计哈夫曼编码 求该树的带树路径长度 a 2500 b 3601 c 210000 d 510001 e 81001 g 101010 f 141011 h 5011 33 在有N个叶子节点的哈夫曼树中 其节点总数为 A 不确定B 2N 1C 2N 1D 2N 完全二叉树共有2 N 1个结点 则它的叶节点数是 A N 1B 2 NC ND 2N 1E N 2 二叉树T 已知其前序遍历序列为1243576 中序遍历序列为4215736 则其后序遍历序列为 A 4257631B 4275631C 4275361D 4723561E 4526371 34 一颗二叉树的前序遍历序列是ABCDEFG 后序遍历序列是CBFEGDA 则根结点的左子树的结点个数可能是 A 0B 2C 4D 6 完全二叉树的顺序存储方案 是指将完全二叉树的结点从上至下 从左至右一次存放到一个顺序结构的数组中 假定根结点存放在数组的1号位置 则第K号结点的父结点如果存在的话 应当存放在数组的 号位置 A 2kB 2k 1C k 2下取整D k 1 2下取整 前缀表达式 3 2 512 的值是 A 23B 25C 37D 65 35 二叉树T 已知其先根遍历是1243576 数字为结点的编号 以下同 后根遍历是4275631 则该二叉树的可能的中根遍历是 A 4217536B 2417536C 4217563D 2415736 36 一 图的定义图是一个二元组 G V E 其中 V 顶点的有限集 E 关系 边 的有限集 图 二 图的存储结构 1 邻接矩阵 2 邻接表 37 图的邻接矩阵可以定义为 38 邻接表 v1v2v3v4v5v6 4 3 5 5 2 5 4 v1 v5 v4 v3 v6 v2 2 39 图的遍历 从图中某一顶点出发访遍图中其余结点 使每一个结点被访问且仅被访问一次 图的遍历通常有两种方法 深度优先搜索和广度优先搜索 它们对有向图和无向图都适用 三 图的遍历 40 类似于树的先根遍历 从图中某个顶点v出发 访问此顶点 然后依次从v的未被访问的邻接点出发深度优先遍历图 直至所有与v有通路的顶点都被访问到 若此时图中还有顶点未被访问到 则另选图中未被访问的顶点作起点 重复上述过程 直到图中所有顶点都被访问到为止 1 深度优先搜索 DepthFirstSearch 41 深度优先遍历序列 v1 v2 v4 v8 v5 v3 v6 v7 42 类似于树的层次遍历 从图中某个顶点v出发 在访问了v之后 依次访问v的各个未曾访问过的邻接点 并保证先被访问的顶点的邻接点 要先于 后被访问的顶点的邻接点被访问 直至图中所有已被访问的顶点的邻接点都被访问到 若此时图中还有未被访问的顶点 则任选其中之一作为起点 重新开始上述过程 直至图中所有顶点都被访问到 2 广度优先搜索 BreadthFirstSearch 43 广度优先遍历序列 v1 v2 v3 v4 v5 v6 v7 v8 44 四 最小生成树 定义 生成树中边的权值 代价 之和最小的树 实例 1 2 4 3 5 6 6 1 6 5 5 5 6 3 4 2 1 2 4 3 5 6 1 5 3 4 2 对应的最小 代价 生成树 方法 找n 1条不构成回路的最小边 45 1 2 4 3 5 6 6 1 6 5 5 5 6 3 4 2 图G 重复执行 找n 1条不构成回路的最小边第1条边 1 3 第2条边 4 6 第3条边 2 5 第4条边 3 6 1 4 因构成回路 放弃 3 4 因构成回路 放弃第5条边 2 3 最小代价生成树 1 2 4 3 5 6 1 5 3 4 2 5 5 Kruskal算法 46 1 2 4 3 5 6 6 1 6 5 5 5 6 3 4 2 1 2 4 3 5 6 1 5 3 4 2 对应的最小 代价 生成树 prim算法 从某一顶点开始 找n 1条 不构成回路的 最小边 顶点偶对 47 从某一顶点开始 找n 1条最小边 顶点偶对 48 五 拓扑排序 用顶点表示活动的网络 简称AOV网络 ActivityOnVertices 顶点 活动 边 顶点间的优先关系 1 什么是拓扑排序将各个顶点 代表各个活动 排列成一个线性有序的序列 这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序 49 拓扑排序方法 v1 v5 v4 v3 v6 v2 1 输出顶点v6 2 输出顶点v1 3 输出顶点v3 4 输出顶点v4 5 输出顶点v2 6 输出顶点v5 1 在AOV网络中选一个入度为0的顶点 并访问该顶点 2 从图中删去该顶点 同时删去所有它发出的边 重复 1 和 2 直全部顶点均已被访问为止 若图中还有未输出的顶点 但已跳出处理循环 说明图中存在环 50 六 关键路径 用边表示活动的网络 简称AOE网络边 一个工程中的活动 Activity 边上权值 活动持续时间 Duration 顶点 事件 Event Ve j 事件Vj的最早可能开始时间 从源点V1到顶点Vj的最长路径长度 Vl i 事件Vi的最迟允许开始时间 在保证汇点Vn在Ve n 时刻完成的前提下 事件Vi的允许的最迟开始时间 Ve 1 0Ve j max Ve i 的权 Vl n Ve n Vl i min Vl j 的权 51 1 3 2 4 a1 8 a2 6 5 6 7 8 a10 12 a9 6 a8 18 a5 26 a6 4 a7 6 a3 14 a4 10 VeVl 12345678 086222832465808122228404658 Ve 1 0Vl n Ve n Ve j max Ve i 的权 Vl i min Vl j 的权 关键路径 1 2 4 5 7 8 从源点到汇点的最长路径长度 52 七 单源最短路径问题 给定一个带权有向图D与源点v 求从v到D中其它顶点的最短路径 限定各边上的权值大于或等于0 Dijkstra提出 按路径长度的递增次序 逐步产生最短路径 首先求出长度最短的一条最短路径 再参照它求出长度次短的一条最短路径 依次类推 直到从顶点v到其它各顶点的最短路径全部求出为止 53 Dijkstra逐步求解的过程 54 关于拓扑排序 下面说法正确的是 A 所有连通的有向图都可以实现拓扑排序B 对同一个图而