文档内容
2023下 粉笔教资
《 信 息技术》
数 据 结 构与算法 3 / 5
▹ 讲师：阿彬
更多干货关注 粉笔教师教育 粉笔教师❀
复习一下（三）双链表 P272
1.双链表的定义
➢在单链表的结点中增加了一个指向其前驱的prior 指针（三）双链表 P272
2.插入操作
核心操作如下（①和②一定要在④前完成）
①s→next = p→next ②p→next→prior=s
③s→prior=p ④p→next=s（三）双链表 P273
3.删除操作
核心操作如下：
①p→next = q→next
②q→next→prior = p（四）循环链表 P273
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.一个栈的进栈顺序是A、B、C、D、E，则出栈的序列不可能是（ ）。
A.E、D、C、B、A B.D、E、C、B、A
C.D、C、E、A、B D.A、B、C、D、E（二）队列 P275
1.队列的定义：允许一端进行插入，另一端进行删除的线性表。
特点1：允许删除的一端称为队头（front）
特点2：允许插入的一端称为队尾（rear）
特点3：先进先出（后进后出）
特点4：队头和队尾指针的具体位置不唯一。（二）队列 P275
2.队列的顺序存储
（1）顺序队列
➢假设队头指针front 指向队头元素，队尾指针rear指向队尾元素的下一个位置。
进队：rear＋1
出队：front＋1（二）队列 P276
（2）循环队列 【首尾相连的环】
➢假设队头指针front 指向队头元素，队尾指针rear指向队尾元素的下一个位置。
①队空：front = rear = 0 ④队满： (rear+1)%MaxSize = front
②入队：(rear+1)%MaxSize ③出队： (front+1)%MaxSize（二）队列 P277
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）满二叉树
在同样深度的二叉树中，满二叉树的节点个数一定最多。（一）二叉树的基本概念 P280
（2）完全二叉树
对满二叉树进行编号，若编号与满二叉树的编号一一对应，则为完全二叉树
1. 去除最后一层，是满二叉树。 2. 最后一层缺少右部连续节点。书上无
下列关于二叉树的说法，错误的是（ ）。
A.在完全二叉树中，若一个节点没有左孩子，则它必为叶子节点
B.在完全二叉树中，叶子节点的双亲的左兄弟一定不是叶子节点
C.在完全二叉树中，若第i个节点为叶子节点，则编号大于i的节点一定是叶子节点
D.节点按二叉树的层序进行编号，第i个结点的右孩子编号为2i（二）二叉树的性质 P280
➢性质 1：在二叉树的第 k 层上至多有 2k–1 个节点（k≥ 1）。
➢性质 2：深度为 h 的二叉树至多有 2h –1 个节点（h ≥ 1）。（二）二叉树的性质 P281
➢性质 3：如果其叶子节点数为 n ，度为 2 的节点数为 n ，则 n =n +1。
0 2 0 2（二）二叉树的性质 P281
➢性质 4：具有 n 个节点的完全二叉树的深度为⌊log n⌋ + 1 。
2书上无
1.在深度为5的满二叉树中，叶子结点的个数是（ ）。
A.16
B.15
C.32
D.31
2.具有10个叶子节点的二叉树中有（ ）个度为2的节点。
A. 8
B. 9
C. 10
D. 11（三）二叉树的存储结构 P281
1.顺序存储结构
➢用一维数组存储二叉树中的各个节点（三）二叉树的存储结构 P282
2. 链式存储结构
➢二叉树每个节点由数据域和指针域（左孩子和右孩子）组成
【例 】将 10 个节点的完全二叉树采用链式结构进行存储。（四）二叉树的遍历 P282
遍历：是依次访问二叉树中所有节点，使得每个节点有且仅被访问一次。
1.先序遍历
➢根、左、右（四）二叉树的遍历 P283
2.中序遍历
➢左、根、右（四）二叉树的遍历 P284
3.后序遍历
➢左、右、根（四）二叉树的遍历 P284
4.层遍历
➢从上到下，从左到右书上无
（2021下·高中）某二叉树结构如图所示，后序遍历的结果是（ ）。
A.ABDFGCEH
B.FDGBAEHC
C.FGDBHECA
D.HECAGFDB书上无
二叉树的先序遍历为A B D E C F G，中序遍历为：D B E A C G F，请画出该二叉树并写出后序
遍历结果。书上无
二叉树的先序遍历为A B D E C F G，中序遍历为：D B E A C G F，请画出该二叉树并写出后序
遍历结果。
【参考答案】
二叉树如下图所示。 后序遍历结果： DEBGFCA下
节
内
容
