CSP-J 复赛知识点详细版(ai整理）
zhang_hao_xuan · · 算法·理论
数据结构
数组：
掌握数组的定义、初始化、访问和修改等基本操 作，了解数组越界的原因和危害。例如，在一些模拟题 中，经常需要对数组进行遍历和更新操作，要注意下标的 范围。
链表：
理解链表的节点结构，掌握链表的插入、删除和遍历操 作。链表在一些需要频繁插入和删除元素的场景中比数组 更有优势。
栈和队列：
明确栈和队列的特点及应用场景，如栈在表达式求值、函 数调用栈中的应用，队列在广度优先搜索、任务调度中的 应用。
树：
熟悉树的基本概念，如节点、父节点、子节点、深度、高 度等，掌握二叉树的遍历方式（前序遍历、中序遍历、后 序遍历），以及树的层次遍历。
图：
了解图的表示方法，如邻接矩阵和邻接表，掌握图的遍历算法，如深度优先搜索和广度优先搜索。
算法设计与分析
贪心算法：
理解贪心算法的思想，能够根据问题的特点判 断是否可以使用贪心算法，如活动安排问题、背包问题 等。
分治算法：
掌握分治算法的基本步骤，如归并排序、快速排序就是分 治算法的典型应用。
动态规划(dp)算法：
学会分析问题的最优子结构和重叠子问题，能够设计状态 转移方程，如背包问题、最长公共子序列问题等。
回溯算法：
了解回溯算法的适用场景，如排列组合问题、八皇后问题 等，掌握回溯算法的递归实现和剪枝优化技巧。
图论
最短路径算法：
掌握 Dijkstra 算法和 Floyd - Warshall 算法的原理和实现，能够应用它们解决实际问题 中的最短路径问题。
最小生成树算法：
理解 Prim 算法和 Kruskal 算法的思想，能够使用这两种 算法求图的最小生成树。
拓扑排序：
掌握拓扑排序的概念和算法，能够对有向无环图进行拓扑 排序。
字符串处理
基本操作：
熟练掌握字符串的拼接、比较、查找、替换等操作，在 C++ 中，要熟悉 string 类的常用成员函数。
字符串匹配算法：
了解 KMP 算法、Boyer - Moore 算法等 的原理，能够使用这些算法在一个字符串中查找另一个字 符串的出现位置。
排序与查找
排序算法：
掌握冒泡排序、插入排序、选择排序、快速排序、归并排 序、堆排序等常见排序算法的原理、时间复杂度和空间复 杂度，能够根据数据的特点选择合适的排序算法。
查找算法：
理解二分查找的原理和适用条件，能够实现二 分查找算法，同时了解哈希表的原理和应用，掌握哈希表 的插入、查找和删除操作。
数学知识
数论基础：
了解质数、合数、最大公约数、最小公倍数、同余等概 念，掌握欧几里得算法求最大公约数等基本数论算法。
排列组合：
掌握排列和组合的计算公式，能够运用排列组 合的知识解决计数问题。
概率与统计：
了解基本的概率概念，如事件、概率、条件概率等，能够计算一些简单事件的概率。