文档内容
~ 2 0 2 4 年 教 师 招 聘 ~
《 信 息技术( 科技) 》
数 据 结 构与算法 3 / 5
讲师：阿彬
更多干货关注 粉笔教师教育 粉笔教师❀
复习一下P272
（三）双链表
1.双链表的定义
➢在单链表的结点中增加了一个指向其前驱的prior指针P272
（三）双链表
2.插入操作
核心操作如下（①和②一定要在④前完成）
①s -> next = p -> next
②p -> next -> prior=s
③s -> prior=p
④p -> next=sP273
（三）双链表
3.删除操作
【补充】
核心步骤（引入p节点）
核心步骤（不引入p节点）
①p -> next = q -> next
①q -> prior -> next = q -> next
②q -> next -> prior = p
②q -> next -> prior = q -> priorP273
（四）循环链表
1.循环单链表【首尾相连】
2.循环双链表【首尾相连】P273
四、栈与队列
（一）栈
1.栈的定义：在表的同一端进行插入和删除运算的线性表
特点1：只有一端开口，允许插入和删除，称为栈顶（top）。插入称为入栈，删除称为出栈
特点2：另一端封闭，不能进行插入和删除，称为栈底（bottom）
特点3：先进后出（后进先出）
特点4：栈顶指针的具体位置不唯一P274
（一）栈
2.栈的顺序存储
➢假设top指向栈顶元素
①位置：进栈/出栈在栈顶；②栈顶指针：进栈top+1 出栈top-1；
③细节：一次性进/出栈的个数不限，但有顺序要求P275
（一）栈
3.栈的链式存储书上无
试题巩固
1.（2022上·高中）栈是一个操作受限的数据结构，对其进行插入和删除必须在（ ）。
A.栈底 B.栈顶 C.任意位置 D.指定位置书上无
试题巩固
2. 一个栈的进栈顺序是ABCDE，则出栈的序列不可能是（ ）。
A. EDCBA
B. DECBA
C. DCEAB
D. ABCDE补充
试题巩固
3. 一个栈的进栈顺序是A、B、C、D、E，则出栈的序列不可能是（ ）。
A. A、B、C、D、E
B. B、C、D、E、A
C. E、A、B、C、D
D. E、D、C、B、AP275
（二）队列
1.队列的定义：允许一端进行插入，另一端进行删除的线性表。
特点1：允许删除的一端称为队头（front）
特点2：允许插入的一端称为队尾（rear）
特点3：先进先出（后进后出）
特点4：队头和队尾指针的具体位置不唯一P275
（二）队列
2.队列的顺序存储
（1）顺序队列
➢假设队头指针front 指向队头元素，队尾指针rear指向队尾元素的下一个位置
①位置：进队在队尾，出队在队头；②指针：空队rear=front 进队rear＋1 出队 front＋1 ；
③细节：一次性进/出队的个数不限，但有顺序要求P276
（二）队列
（2）循环队列 【首尾相连的环】
➢假设队头指针front 指向队头元素，队尾指针rear指向队尾元素的下一个位置。
①队空：front = rear = 0 ④队满： (rear+1)%MaxSize = front
②入队：(rear+1)%MaxSize ③出队： (front+1)%MaxSizeP277
（二）队列
3.队列的链式存储书上无
试题巩固
1.一个队列的入队顺序是1，2，3，4，则出队的输出顺序是（ ）。
A. 4，3，2，1 B. 1，2，3，4
C. 1，4，3，2 D. 3，2，4，1
2.下列叙述中正确的是（ ）。
A.循环队列中元素的个数是由队头指针和队尾指针共同决定
B.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
D.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构第四节 树和二叉树P277
一、树
（一）树的定义
特点1：节点有限，可以为0。每一个分支又称为一棵树。
特点2：除根节点外，其余节点有且只有一个前驱，根节点无前驱。
特点3：树中所有节点可以有零个或多个后继。
特点4：n个节点有n-1条边。P278
（二）树的相关术语
1.祖先、子孙、双亲、孩子、兄弟
2.节点的度、树的度
3. 分支节点、叶子节点
4.节点的层次、树的深度
5.有序树、无序树
6.路径、路径长度P279
二、二叉树
（一）二叉树的基本概念
1.二叉树的定义
特点1：每个节点最多有 2 棵子树。
特点2：二叉树的子树严格区分左子树和右子树。
特点3：有5种基本形态。书上无
试题巩固
关于二叉树的描述，下列说法不正确的是（ ）。
A.二叉树就是度为2的有序树
B.每个节点至多只能有2棵子树
C.不存在度大于2的节点
D.二叉树分左右子树P279
（一）二叉树的基本概念
2.特殊二叉树
（1）满二叉树
特点1：除了叶子节点外，每个节点都有两个子节点
特点2：所有叶子节点都在同一层级上（最后一层）
特点3：在同样深度的二叉树中，满二叉树的节点个数一定最多P280
（一）二叉树的基本概念
2.特殊二叉树
（2）完全二叉树
1. 去除最后一层，是满二叉树。 2. 最后一层缺少右部连续节点。
对满二叉树进行编号，若编号与满二叉树的编号一一对应，则为完全二叉树P280
（二）二叉树的性质
➢性质 1：在二叉树的第 k 层上至多有 2k–1 个节点（k≥ 1）。
➢性质 2：深度为 h 的二叉树至多有 2h –1 个节点（h ≥ 1）。P281
（二）二叉树的性质
➢性质 3：如果其叶子节点数为 n ，度为 2 的节点数为 n ，则 n =n +1。
0 2 0 2P281
（二）二叉树的性质
➢性质 4：具有 n 个节点的完全二叉树的深度为⌊log n⌋ + 1 。
2书上无
试题巩固
1. 6层二叉树最多有（ ）个节点。
A.64
B.63
C.32
D.31
2. 一棵二叉树中有7个叶子节点和5个单分支节点，其总共有（ ）个节点。
A. 16
B. 18
C. 12
D. 31P281
（三）二叉树的存储结构
1.顺序存储结构
➢用一维数组存储二叉树中的各个节点P282
（三）二叉树的存储结构
2. 链式存储结构
➢二叉树每个节点由数据域和指针域（左孩子和右孩子）组成
【例 】将 10 个节点的完全二叉树采用链式结构进行存储。P282
（四）二叉树的遍历
遍历：是依次访问二叉树中所有节点，使得每个节点有且仅被访问一次。
1.先序遍历
➢根、左、右书上无
试题巩固
（2021上·高中）某二叉树结构如下图所示，其前序遍历的结果是（ ）。
A.ABDFGCEIH
B.ABDFGCEHI
C.ABDGFCEHI
D.ABDGFCEIHP283
（四）二叉树的遍历
2.中序遍历
➢左、根、右书上无
试题巩固
（2023上·高中）某二叉树结构如下图所示，中序遍历的结果是（ ）。
A.ABDFGCEHI
B.BFDGACHEI
C.FGDBHIECA
D.ABCDEFGHIP283
（四）二叉树的遍历
3.后序遍历
➢左、右、根书上无
试题巩固
（2021下·高中）某二叉树结构如图所示，后序遍历的结果是（ ）。
A.ABDFGCEH
B.FDGBAEHC
C.FGDBHECA
D.HECAGFDBP284
（四）二叉树的遍历
4.层遍历
➢从上到下，从左到右下
节
内
容
2024FENBI
