【数据结构】2021年真题-平芜编程栈

考查单循环链表删除操作逻辑，需注意尾指针指向及内存释放顺序区分普通链表与循环链表的差异

考查双端队列操作规则，通过入队序列推导合法出队顺序，区分队列与栈的操作特性

考查数组按行优先存储的地址计算公式，需推导数组行列数及偏移量

查森林与二叉树转换关系，森林的棵数等于二叉树中根节点的最左子树分支数

考查哈夫曼树构造过程，需按权值构建最优二叉树并计算 WPL

考查平衡二叉树插入操作中的旋转调整，需判断插入后的平衡化处理结果

考查拓扑排序算法逻辑，需枚举所有可能的拓扑序列并计数

考查 Dikstra 算法执行过程，重点关注每轮选代中最短路径的更新顺序

考查B树结构特性，需根据关键字数目推导各层结点数的最大值

考查基数排序按低位优先的处理流程，重点关注第一趟按个位数分配的结果

考查大根堆的插入和调整过程，需验证堆顶无素及子树的堆性质

欧拉路径判断算法

给定排序算法，进行分析

数据结构基础操作(链表删除、队列操作、数组地址计算)树与图算法(森林与二叉树转换、哈夫曼树、平衡树、拓扑排序、最短路径)、查找与排序(B树、基数排序、堆排序)及图论算法设计(EL路径存在性判断)

考查单循环链表删除操作逻辑，需注意尾指针指向及内存释放顺序区分普通链表与循环链表的差异
已知带头结点非空单循环链表，删除第一个无素的正确语句序列

考查双端队列操作规则，通过入队序列推导合法出队顺序，区分队列与栈的操作特性
一端仅入队、另一端可入队出队的队列，判断不可行的出队序列

考查数组按行优先存储的地址计算公式，需推导数组行列数及偏移量
已知 A [0][0] 和 A [3][3]地址，求 A [5][5] 的存储地址

查森林与二叉树转换关系，森林的棵数等于二叉树中根节点的最左子树分支数
已知二叉树先序和中序遍历，求对应森林的树的棵数

考查哈夫曼树构造过程，需按权值构建最优二叉树并计算 WPL
5 个叶子节点权值求最小带权路径长度 WPL

考查平衡二叉树插入操作中的旋转调整，需判断插入后的平衡化处理结果
插入关键字 23 后平衡二叉树的根关键字

考查拓扑排序算法逻辑，需枚举所有可能的拓扑序列并计数
给定有向图，求其拓扑有序序列的个数

考查 Dikstra 算法执行过程，重点关注每轮选代中最短路径的更新顺序
求从顶点1出发，找到第二条最短路径后的 dist 数组

考查B树结构特性，需根据关键字数目推导各层结点数的最大值
高度为3的B树，第2层有4个关键字，求最多结点数

考查基数排序按低位优先的处理流程，重点关注第一趟按个位数分配的结果
LSD 基数排序第1趟后，元素 372 的前后紧邻元素

考查大根堆的插入和调整过程，需验证堆顶无素及子树的堆性质
关键字依次插入后得到的大根堆序列

欧拉路径判断算法
欧拉路径与欧拉回路：EL路径本质为欧拉路径，其存在条件是图连通且奇数度顶点数为0(欧拉回路)或2(欧拉路径)
邻接矩阵度数计算：无向图中顶点i的度数等于其邻接矩阵第i行或列)的元素和。
图连通性判断：可通过深度优先搜索(DFS)或广度优先搜索BFS)遍历图判断是否所有顶点可=达
算法基本设计思想
步骤 1:计算每个顶点的度数，统计奇数度顶点的个数cnt。
步骤 2:若cnt为0或2，进一步判断图的连通性。
步骤 3:>若图连通且cnt满足条件，返回1;否则返回 0。