CSP知识点整理大全

信息学史及基本知识

1. 信息学及计算机史
   • 计算机顶级奖项：图灵奖（ACM设立，1966年，“计算机界的诺贝尔奖”）、冯·诺依曼奖（IEEE设立）。
   • 信息科学大神：图灵、冯·诺伊曼。中国获图灵奖的是姚期智（清华姚班以其命名）。
   • 世界第一台电子计算机：埃尼阿克（ENIAC），1946年2月14日于美国宾夕法尼亚大学诞生，又称电子管计算机。
2. 编程相关
   • 编程语言分类：面向对象（如C++、Java、EIFFEL、Simula 67等）和面向过程（如C、Fortran语言）。高级语言需编译运行，常数大、速度慢但易移植；低级语言常数小、速度快，如汇编。
   • 递归编程：通过重复将问题分解为同类子问题来解决，即在函数中“自身调用自身”，可用于解决诸多计算机科学问题。
   • P类/NP类/NPC类问题
     • P类问题：能在多项式时间内找到算法解决的问题。
     • NP类问题：在多项式时间内验证解或猜出解的问题（非非P类问题）。
     • NPC类问题：是NP问题且所有NP问题可约化到它（问题A可约化为问题B，意味着A可用B的解法解决）。
3. 计算机系统
   • 硬件系统：包括运算器（对数据进行算术和逻辑运算）、控制器（计算机中枢神经，控制协调各部分工作）、存储器（存储信息，分只读存储器ROM和随机存储器RAM，外存储器如硬盘、光盘、软盘等）、输入设备（如键盘、鼠标、扫描仪等）、输出设备（如显示器、打印机等），还有主板、机箱、电源等。CPU（中央处理器） = 运算器 + 控制器 + 寄存器，运算器 = 算术逻辑运算单元（ALU）及浮点运算单元（FPU），存储器 = 内存储器 + 外存储器。BIOS是固化在主板ROM芯片上的程序，提供底层硬件设置和控制。断电后硬盘、ROM可保存数据，显存、RAM、CPU断电后不保存数据。计算机存储单位有TB、GB、MB、KB、B，进位关系为1024，1B = 8bit。
   • 软件系统：包括操作系统（如DOS、Wndows、UNIX、Linux等）、高级语言（C、C++、Fortran、Pascal等）、应用软件（如文字处理软件Microsoft Word、WPS等，表格处理软件Microsoft Excel、金山表格等，辅助设计软件AutoCAD、Mastercam等）。

进制及相关运算

1. 进制转化
   • 十进制转任意进制：除n取余，余数逆序。
   • 任意进制转十进制：按位转，第i位数字乘以进制的n - 1次幂。
   • 任意进制互相转化：用十进制做中转。
   • 小数的进制转换：十进制转任意进制小数乘法取整排列；任意进制转十进制小数乘负指数计算。
2. 二进制知识
   • 原码：十进制数直接转二进制后的编码。
   • 补码：正数补码是本身，负数补码是反码加一。
   • 反码：正数反码是本身，负数反码是除符号位外按位取反。
3. ASCII码：美国信息交换标准代码，基于拉丁字母，定义128个字符，常用转换如字符0→48、大写字母A→65、小写字母a→97、空格→32、换行→13。
4. 位运算与逻辑运算
   • 逻辑运算：有逻辑非（！或┐）、逻辑与（&&或∧）、逻辑或（||或∨）三种，优先级为非 > 与 > 或。位运算 + 逻辑运算优先级为逻辑非（！，┐） = 按位反（~）> 位移运算（<<,>>）> 不等号（>=,<=）> 等号（==,!=）> 按位与（&）> 按位异或（^）> 按位或（|）> 逻辑与（&&，∧）> 逻辑或（||，∨）。
   • 条件表达式：基本形式<表达式1>？<表达式2>：<表达式3>，等价于if - else条件语句，多个复合时从右往左判断，有右结合性。

图论理论知识

1. 完全图：任意两点都有边相连，边数为n×(n−1)/2（n为节点个数）。
2. 连通图：任意两点能直接或间接到达（区别于完全图必须直接边到达）。
3. 树：直观像树，定义为任意两点间简单路径有且只有一条，是连通无环图，边数为n - 1。二叉树遍历分为先序遍历（根—左儿子—右儿子）、中序遍历（左儿子—根—右儿子）、后序遍历（左儿子—右儿子—根），先序遍历 + 中序遍历或后序遍历 + 中序遍历可确定一棵二叉树，先序遍历 + 后序遍历无法确定。特殊二叉树有完全二叉树（只有最后一层不满且节点集中在左侧）和满二叉树（节点个数已满），完全二叉树叶节点为n时节点总数为2×n−1，满二叉树层数为k时节点总数为2^k−1，结论可逆。拓扑排序考到几率不大且理解有难度。

简单数据结构基本理论

1. 栈：后进先出，与前、中、后缀表达式有关。中缀表达式是人常用的，计算机计算中缀表达式涉及栈，后缀表达式实现需建存运算符号和数字的栈，碰到符号压入符号栈，碰到数字压入数字栈，数字栈有两个数时从符号栈弹出符号运算并将结果压回数字栈，前缀表达式实现原理类似但从后往前转，一个中缀表达式对应的后缀或前缀表达式不唯一。
2. 队列：先进先出，如排队买票。
3. 链表：可理解为离散的带链数组，用结构体数组模拟实现，结构体存元素和两个指向前后元素位置的int变量（数组下标）。包括初始化（处理开头元素，指针清 - 1保证合法）、插入操作（分插入到元素前和后，更改相关元素指针）、删除操作（更改前后元素指针）、遍历操作（从表头开始依次输出元素）。
4. 字符串：子串是字符串中任意连续字符组成的子序列，非空子串个数计算公式为n×(n+1)/2，考虑空子串时加1。

时空复杂度计算

1. 时间复杂度：用O表示渐进时间复杂度，取程序语句执行次数代数式的最高次项且忽略系数。计算非递归程序时间复杂度简单数循环，常数是忽略的最高次项系数与低次项带来的时间消耗。
2. 空间复杂度：类比时间复杂度，看开空间大小。计算空间占用量时，一个int占4B，通过乘4并按1024换算单位。比赛中256MB内存可开约6×10^7个int类型变量，大数组开全局变量，放主函数内容易爆栈。

排列组合问题

1. 定义与公式
   • 排列：从n个不同元素选m个按顺序排成一列，排列数Amn=n(n−1)(n−2)⋯(n−m+1)=n!/(n−m)!。
   • 组合：从n个不同元素选m个并成一组，组合数Cmn=Amn/m!=n!/[m!(n−m)!]。
   • 全排列：n = m时的排列情况，全排列数f(n)=n!。
2. 例题：生成1−n的全排列可用递归解决，递归出口为x == n + 1，递归过程通过标记数组和数列数组实现，先圈定一个值，遍历完一条链后回溯看其他选择，保证解不重不漏。

CSP - J/S考试内容包括计算机基础知识（单项选择题）、基础组合数学（单项选择题）、基础数据结构性质与基础算法（单项选择题、阅读程序）、算法综合运用（阅读程序、完善程序）。