交换排序——冒泡排序(每轮将最大元素"冒"到最后——稳定——O(n²))和快速排序(选取pivot将数组分为小于和大于两部分——递归排序——平均O(n log n))。快速排序的分区算法(Lomuto分区与Hoare分区)和退化到O(n²)的条件(已排序+pivot选首元素)。快速排序的优化(三数取中pivot/小数组切换到插入排序/三路分区)。

归并排序与堆排序：归并排序——分治思想——将两个有序子序列合并成一个有序序列——稳定——O(n log n)——需要O(n)辅助空间。堆排序——利用堆(优先队列)数据结构——建堆O(n)——每次取堆顶(最大)与末尾交换并调整堆——O(n log n)——不稳定——原地排序(O(1)空间)。两种排序的适用场景——归并排序外部排序基础、堆排序适合需要原地排序时。

插入排序与选择排序：插入排序——每步将当前元素插入已有序的的前缀部分——通过比较和移动来找到正确的插入位置。选择排序——每轮从未排序部分选最小元素放到已排序部分的末尾。均为O(n²)——但插入排序在部分有序数组上接近O(n)——选择排序的比较次数与输入无关——始终O(n²)。

单链表：链式存储——每个节点包含数据域和指针域(指向下一个节点)，不需要连续存储空间——插入/删除只需修改指针(O(1)已知位置)但查找需遍历(O(n))。头结点的作用(统一空表和非空表的操作)、前插和后插的不同指针操作顺序、单链表的创建(头插法/尾插法)、查找/插入/删除的算法。

线性表的定义与顺序表：线性表的概念(0个或多个数据元素的有限序列)、顺序表用数组存储(随机访问O(1)和插入删除O(n))、线性表的抽象数据类型(初始化/查找/插入/删除/取长)。顺序表的实现细节——容量自动扩容策略(旧容量×2 + 新元素入列)与插入/删除的数组移动操作。

栈的定义与实现：栈——只允许在表尾(栈顶)进行插入(push)和删除(pop)操作的线性表。后进先出原则(LIFO)。顺序栈用数组加栈顶指针实现(top=-1表示空栈、top=MAX-1表示满栈)。链栈用单链表实现——top指向栈顶结点。栈的应用：函数调用栈、括号匹配、表达式求值。

队列的定义与循环队列：队列(FIFO)——只允许在一端(队尾)插入、在另一端(队首)删除。顺序队列的"假溢出"(队尾指针到达数组末尾但队首之前还有空位)。循环队列通过取模运算将数组视为环形——rear=(rear+1)%M, front=(front+1)%M。队空条件front==rear——队满条件牺牲一个单元(rear+1)%M==front。

数据结构的基本概念：数据/数据元素/数据项/数据对象/数据结构的定义、逻辑结构(集合/线性/树/图)与物理结构(顺序/链式)的划分及其关系。抽象数据类型ADT的表示和实现概念。每一种数据元素由数据项组成——原子数据项是最小不可分割单位。

算法和算法分析：算法五个特性(有穷性/确定性/可行性/输入/输出)、时间复杂度的渐近表示法(大O/Ω/Θ)、空间复杂度概念、常见时间复杂度函数(O(1)/O(log n)/O(n)/O(n log n)/O(n²)/O(2^n)/O(n!))的增长率对比。

串(字符串)——由0个或多个字符组成的有限序列。空串(长度为0的串)和空格串(仅含空格的串)的区别。串的顺序存储(字符数组)和链式存储。串的基本操作——赋值/比较/求长/连接/取子串/定位子串。KMP算法的核心——next数组的构造——利用已匹配的部分信息跳过不必要的比较——将朴素匹配的O(m×n)降低为O(m+n)。