一、数据结构基础概念
核心知识点
数据结构定义：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，包含数据的逻辑结构、物理结构和数据的运算三部分。
逻辑结构：与计算机无关，描述数据元素之间的逻辑关系，分为线性结构（一对一，如线性表、栈、队列）和非线性结构（一对多如树形结构，多对多如图形结构）。
物理结构（存储结构）：数据在计算机中的存储形式，包括顺序存储（连续存储空间，如数组）、链接存储（非连续空间，通过指针关联，如链表）、索引存储、散列存储。
数据元素与数据项：数据元素是数据操作的基本单位，可由一个或多个数据项（数据最小单位）组成。
算法特性：有输入、输出、确定性、有穷性、有效性；健壮性（不因非法输入出错）。
重点考点
逻辑结构与物理结构的区别（选择题高频，如 “与计算机无关的是逻辑结构”）。
线性结构与非线性结构的分类（如树形是一对多，图形是多对多）。
算法的特性及评价（时间复杂度、空间复杂度）。
二、线性表
核心知识点
线性表定义：n 个数据元素的有限序列，可空（长度为 0），逻辑上一对一关系。
顺序表（顺序存储）：
特点：逻辑相邻则物理相邻，随机访问效率高（O (1)），插入删除需移动元素（效率低，O (n)）。
关键操作：插入（第 i 个元素前插入，移动 n-i+1 个元素）、删除（删除第 i 个元素，移动 n-i 个元素）。
链表（链接存储）：
分类：单链表、双向链表、循环链表（单向 / 双向）。
特点：无需连续空间，插入删除无需移动元素（仅改指针，O (1)），不可随机访问（需遍历，O (n)）。
关键操作：单链表表头插入、表尾插入、中间插入；双向循环链表插入 / 删除（需修改前后指针）；循环链表尾结点判断（p->next== 头指针）。
重点考点
顺序表插入 / 删除的元素移动次数计算（选择题高频）。
链表插入 / 删除的指针操作（综合题高频，如单链表 p 后插入 s：s->next=p->next; p->next=s）。
循环链表、双向链表的特性（如双向循环链表为空的条件：L->next==L）。
顺序表与链表的优缺点对比（如频繁插入删除选链表，随机访问选顺序表）。
三、栈与队列
核心知识点
栈（先进后出 LIFO）：
定义：仅允许在表一端（栈顶 top）插入（入栈）和删除（出栈）的线性表。
存储结构：顺序栈（数组实现，top=-1 表示栈空，入栈 top++，出栈 top--）、链栈（表头为栈顶，效率高）。
应用：递归调用、表达式求值（后缀表达式转换与计算）、括号匹配。
关键特性：元素进栈出栈顺序（如 a、b、c 进栈，不可能的出栈顺序为 c、a、b）。
队列（先进先出 FIFO）：
定义：允许在表一端（队尾 rear）插入，另一端（队首 front）删除的线性表。
存储结构：顺序队列（避免假溢出用循环队列，队空 front==rear，队满 (rear+1)% MaxSize==front）、链队。
应用：主机与打印机速度匹配、广度优先遍历（BFS）。
重点考点
栈的进出栈序列判断（选择题高频，如 4、6、8、10 进栈，可能的出栈序列为 10、8、6、4）。
后缀表达式转换（如 a*(b+c)-d 的后缀表达式为 abc+*d-）。
循环队列的判空、判满及入队 / 出队操作（综合题高频，如入队：sq->data [sq->rear]=x; sq->rear=(sq->rear+1)% MaxSize）。
栈与队列的应用场景（如递归用栈，BFS 用队列）。
四、串与广义表
核心知识点
串（字符串）：
定义：有限个字符的序列，空串（长度 0）与空格串（长度为空格个数）不同。
存储：顺序存储（适合短串）、链式存储。
关键操作：串比较（strcmp，按字符 ASCII 码比较，如 "ABCd">"ABCD"）、串连接（strcat）、子串查找（模式匹配）。
特性：串是特殊的线性表（元素为字符）。
广义表：
定义：线性表的扩展，元素可是原子或子表（广义表）。
关键概念：长度（顶级元素个数，如 (f,h,(a,b,d,c),d,e,((i,j),k)) 长度为 6）、深度（嵌套层数，如 (a,(d,a,b),h,(e,((i,j),k))) 深度为 4）、表头（第一个元素，可是原子或子表）、表尾（除表头外的元素构成的表，必为表）。
重点考点
串的比较与相等条件（长度相等且对应字符相同）。
广义表的长度、深度、表头、表尾计算（选择题高频，如广义表 ((a),((b),c),(((d)))) 长度 3、深度 4）。
串函数的功能（如 strcmp 是串比较，strcat 是串连接）。
五、树形结构（含二叉树、哈夫曼树）
核心知识点
树的基本概念：
定义：n≥0 个结点的非线性结构，n=0 为空树，n≥1 时有且仅有一个根结点，其余为子树。
术语：度（结点子树个数）、叶子结点（度 0）、深度（根到叶子的层数）、完全二叉树（上层满，下层左连续）、满二叉树（每层都满）。
性质：深度为 h 的二叉树最多有 2^h -1 个结点；完全二叉树结点 i 的左孩子为 2i，右孩子为 2i+1。
二叉树遍历：
先序遍历（根→左→右）、中序遍历（左→根→右）、后序遍历（左→右→根）、按层遍历（BFS，用队列）。
考点：已知两种遍历序列求第三种（如先序 abdec、中序 dbeac，后序为 debca）。
哈夫曼树（最优二叉树）：
定义：带权路径长度（WPL）最小的二叉树，仅含度 0（叶子）和度 2 的结点，无度 1 结点。
构造：选两个最小权值结点作为左右子树，根为权值和，重复至一个根结点。
应用：哈夫曼编码（前缀编码，压缩存储）。
重点考点
二叉树的性质计算（如深度为 5 的完全二叉树最少 16 个结点，最多 31 个结点）。
遍历序列转换（已知先序和中序求后序，或反之）。
哈夫曼树的 WPL 计算（如权值 1、2、6、8 的 WPL 为 29）。
完全二叉树的顺序存储与结点编号关系。
六、图形结构
核心知识点
图的基本概念：
定义：顶点集 V 和边集 E 的集合，分为无向图（边无方向）和有向图（边有方向）。
术语：度（无向图顶点边数，有向图分入度和出度）、连通图（任意两顶点可达）、连通分量（极大连通子图）、强连通图（有向图任意两顶点互达）。
性质：无向图所有顶点度之和 = 2× 边数；有向完全图边数 = n (n-1)，无向完全图边数 = n (n-1)/2。
图的存储：
邻接矩阵（n×n 矩阵，适合稠密图，无向图对称）、邻接表（链式存储，适合稀疏图，有向图分邻接表和逆邻接表）。
图的遍历：
深度优先遍历（DFS，用栈，类似树的先序遍历）、广度优先遍历（BFS，用队列，类似树的按层遍历）。
最小生成树：连通图中权值和最小的生成树（边数 n-1），适合稠密图用普里姆算法，稀疏图用克鲁斯卡尔算法。
重点考点
邻接矩阵与邻接表的特点（如邻接表是链式存储，无向图边结点数 = 2e）。
图的遍历序列（如无向图从顶点 1 出发的 BFS 序列）。
图的性质计算（如顶点数、边数、度的关系）。
最小生成树的边数（n-1）及构造思想。
七、查找
核心知识点
顺序查找：
特点：无需有序，遍历所有元素，时间复杂度 O (n)。
折半查找（二分查找）：
条件：顺序存储且有序。
过程：取中间元素比较，缩小查找范围，时间复杂度 O (log2n)。
考点：查找次数计算（如有序表 {11,22,33,44,55,66,77,88,99} 查找 55 需 3 次）。
二叉排序树（BST）：
定义：左子树所有结点值 <根结点值，右子树所有结点值> 根结点值，中序遍历为有序序列。
操作：插入、删除（保持 BST 性质）、查找（平均 O (log2n)，最坏 O (n)，单支树）。
分块查找：分块有序（块间有序，块内无序），先查索引表（折半或顺序），再查块内（顺序），时间复杂度介于顺序和折半之间。
哈希查找（散列查找）：
定义：通过哈希函数将关键字映射到存储地址，平均时间复杂度 O (1)。
冲突处理：开放定址法、链地址法。
重点考点
折半查找的适用条件及查找次数计算（选择题、综合题高频）。
二叉排序树的中序遍历特性（有序序列）及插入删除后结构。
各种查找方法的时间复杂度对比（顺序 O (n)，折半 O (log2n)，哈希 O (1)）。
八、排序
核心知识点
插入排序：
直接插入排序：将元素插入有序子表，稳定，时间复杂度 O (n²)，适合小规模数据。
希尔排序：分组插入，不稳定，时间复杂度 O (n^1.3)。
交换排序：
冒泡排序：相邻元素比较交换，稳定，时间复杂度 O (n²)，优化后可提前结束（无交换时）。
快速排序：选基准元素划分左右（左小右大），递归排序，不稳定，平均时间复杂度 O (nlog2n)，最坏 O (n²)（有序序列）。
选择排序：
直接选择排序：选最小 / 大元素交换到对应位置，不稳定，时间复杂度 O (n²)。
堆排序：构建大根堆 / 小根堆，依次取堆顶元素，不稳定，时间复杂度 O (nlog2n)，适合海量数据 TopK 问题。
归并排序：分治思想，合并两个有序子表，稳定，时间复杂度 O (nlog2n)，空间复杂度 O (n)。
排序算法对比：
稳定排序：插入、冒泡、归并；不稳定排序：快速、选择、堆排序。
时间复杂度：O (nlog2n)（快速、堆、归并）；O (n²)（直接插入、直接选择、冒泡）。
重点考点
各种排序的执行过程（如快速排序一趟划分结果、堆排序初始堆构建）。
排序算法的稳定性、时间复杂度、空间复杂度对比（选择题高频）。
特定场景排序选择（如海量数据 TopK 选堆排序，有序序列避免快速排序）。
排序算法代码填空（如快速排序递归调用、冒泡排序条件判断）。
九、高频题型与易错点
1. 选择题高频考点
逻辑结构与物理结构的区别。
线性表、栈、队列的操作特性。
二叉树的性质、遍历序列。
查找 / 排序算法的时间复杂度。
图的度、边数关系。
2. 综合题高频考点
链表的插入 / 删除代码填空。
栈 / 队列的操作结果计算（如入栈出栈后元素输出序列）。
二叉树遍历代码填空（先序、中序、后序递归算法）。
快速排序、插入排序的代码填空。
折半查找的比较次数计算。
3. 易错点
顺序表插入 / 删除的移动元素个数（注意 “第 i 个元素前” 与 “第 i 个元素” 的区别）。
循环队列的判空（front==rear）与判满（(rear+1)% MaxSize==front）。
二叉树遍历序列转换（需明确根结点位置）。
哈夫曼树无度 1 结点，完全二叉树可能有度 1 结点。
稳定排序与不稳定排序的判断（如快速排序不稳定，归并排序稳定）。
)