一、数据结构

1. 线性表

①数组：可以快速随机访问元素，适用于需要频繁按索引访问元素的场景。

②链表：动态数据结构，插入和删除操作较为高效，适用于频繁进行数据增减的情况。

2. 栈与队列

①栈：具有后进先出（LIFO）的特性，常用于表达式求值、函数调用栈等。

②队列：先进先出（FIFO），可用于广度优先搜索、任务调度等。

3. 树与二叉树

①二叉树的遍历（前序、中序、后序、层序遍历）：是二叉树操作的基础，常用于树的构建、搜索等。

②二叉搜索树：左子树的节点值小于根节点，右子树的节点值大于根节点，可用于高效的查找、插入和删除操作。

③平衡二叉树（如 AVL 树、红黑树）：通过旋转等操作保持树的高度平衡，保证查找、插入和删除的时间复杂度为 。

④堆：分为大根堆和小根堆，可用于优先队列、排序等。

4. 图

①图的存储方式（邻接矩阵、邻接表）：不同的存储方式适用于不同规模的图和不同的操作需求。

②图的遍历（深度优先搜索、广度优先搜索）：用于探索图的结构、寻找路径等。

③最短路径算法（Dijkstra 算法、Floyd 算法）：求解图中两点之间的最短路径。

④最小生成树算法（Prim 算法、Kruskal 算法）：用于构建连通图的最小代价生成树。

二、算法

1. 排序算法

①冒泡排序、插入排序、选择排序：简单的排序算法，时间复杂度为 。

②快速排序、归并排序、堆排序：高效的排序算法，时间复杂度为。

2. 搜索算法

①深度优先搜索、广度优先搜索：在图和树等数据结构上进行搜索的基本算法。

②回溯法：用于解决组合、排列等问题，通过不断尝试和回溯来找到所有可能的解。

③分支限界法：一种在状态空间树上进行搜索的算法，常用于求解最优化问题。

3. 动态规划

①基本概念：将问题分解为子问题，通过求解子问题并保存结果，避免重复计算，从而解决原问题。

②常见题型：背包问题、最长公共子序列、最长递增子序列等。

4. 贪心算法

①基本思想：在每一步选择中都采取当前状态下的最优决策，希望最终得到全局最优解。

②应用场景：活动安排问题、哈夫曼编码等。

三、其他知识点

1. 位运算

①按位与、按位或、按位异或等操作：可用于快速判断奇偶性、提取特定位等。

②位运算技巧：如利用位运算实现快速乘除、判断数字是否为 2 的幂等。

2. 字符串处理

①字符串匹配算法（KMP 算法、BM 算法等）：用于在一个字符串中查找另一个字符串的出现位置。

②字符串哈希：通过将字符串映射为一个整数，快速判断两个字符串是否相等。

3. 数学知识

①数论（质数判断、最大公约数、最小公倍数等）：在算法中常用于优化和解决特定问题。

②组合数学（排列组合、容斥原理等）：用于计算方案数等问题。

③概率与期望：在一些随机算法和概率问题中会用到。

在准备 CSP-S 复赛时，你需要熟练掌握这些知识点，并通过大量的练习来提高解题能力和代码实现能力。同时，要注意代码的效率和可读性，以及对时间和空间复杂度的分析以防止可能超时或者爆空间。