本文从大纲要求出发，系统梳理入门阶段必须掌握的线性结构（栈、队列、链表）及基础树形结构，结合典型应用场景与代码实现技巧，帮助考生建立清晰的数据结构认知体系，为后续深入学习高阶内容奠定坚实基础。
猜你喜欢：各省市2026年NOI省队名单汇总
福利资料：为协助信息学竞赛生高效备考，特整理《2014-2025年信息学竞赛试题及答案》pdf资料
2026年NOI大纲解读九：数据结构入门
一、 知识点概览
根据《全国青少年信息学奥林匹克系列竞赛大纲(2025年修订版)》，2.1.3 数据结构是入门级中承上启下的核心章节。数据结构决定了数据如何在内存中“摆放”，直接影响算法的效率。
1. 线性结构 (Linear Structures)
链表：掌握单链表、双向链表及循环链表的概念(指针连接，非连续存储)。
栈 (Stack)：后进先出 (LIFO) 的特性，就像洗盘子，最后放上去的先拿下来。
队列 (Queue)：先进先出 (FIFO) 的特性，就像排队买饭，先来的先买。
2. 树形结构 (Tree Structures)
基础概念：根节点、叶节点、父子关系、深度、度。
二叉树 (Binary Tree)：
性质：第 层最多 个节点;深度为 最多 个节点;(叶子数 = 度为2的节点数 + 1)。
遍历：前序(根左右)、中序(左根右)、后序(左右根)。
特殊树：
完全二叉树：适合用数组存储(节点 的左孩子是 ，右孩子是 )。
哈夫曼树 (Huffman Tree)：最优二叉树，用于构造哈夫曼编码(前缀编码)。
二叉搜索树 (BST)：左子树 < 根 < 右子树。
3. 图形结构 (Graph Structures)
概念：顶点 (Vertex)、边 (Edge)、度 (Degree)、有向/无向图。
存储：
邻接矩阵：二维数组 G[u][v]，适合稠密图，空间复杂度 。
邻接表：链表或 vector 数组，适合稀疏图，空间复杂度 。
二、 常见考点与易错点分析
数据结构的考题通常结合数学性质与代码实现：
1. 二叉树遍历的“倒推”
考点：给出一棵二叉树的前序和中序遍历序列，求后序遍历序列。
技巧：前序确定根，中序分左右。单纯靠前序和后序无法唯一确定一棵二叉树。
2. 栈与队列的模拟
易错点：手动模拟出栈/入栈序列时，注意操作的合法性。例如，入栈序列为 1,2,3，不可能得到出栈序列 3,1,2(3出栈后，栈顶是2，必须2先出)。
3. 完全二叉树的数组下标
陷阱：在使用数组存储完全二叉树时，下标通常从 1 开始。如果从 0 开始，左孩子公式变为 ，容易记混。建议统一从 1 开始，父节点为 。
4. 图的存储空间爆炸
分析：邻接矩阵虽然简单，但如果是 个顶点的图，定义 int G 会导致内存超限(MLE)。此时必须使用邻接表(vector)。
三、 C++ 示例代码：二叉树的构建与遍历
以下代码演示了如何使用结构体定义二叉树，并实现前序遍历(Pre-order Traversal)。
四、 典型真题解析
例题 1：二叉树性质(模拟初赛真题)
例题 2：线性结构特征
【解答】栈（Stack）是先进后出（LIFO）；队列（Queue）是先进先出（FIFO）。答案：B
五、 结构化梳理：知识思维导图
推荐阅读：
