CSPJ初赛复习

第一部分 - 正文

一.存储知识：

1.存储：

编码：
比特（bit）：编码最小的单位。
字节（byte）：存储的最小单位。

2.存储单位的转化：

1 KB = 1024 Byte
1 MB = 1024 KB
1 GB = 1024 MB
1 TB = 1024 GB

3.常见的变量类型的存储大小：

1个 int = 4个 Bytes
1个 (unsigned) long long = 8个 Bytes（unsigned long long 不存负数，存非负数是long long 的两倍）
1个 bool = 1个 Byte
1个 char = 1个 Byte
1个 float = 4个 Bytes
1个 double = 8个 Bytes

二.计算机系统的组成：

硬件系统（hardware）+软件系统（software）。

1.硬件系统：

        硬件系统包括主机（CPU、内存...）以及外接设备（输入输出设备等）。

        内存分为 RAM（可读写存储器，掉电之后数据清除） 、ROM（只可读存储器，掉电之后数据保留） 和 Cache（高速缓冲存储器，为了适应CPU的高速计算） 三种。

        register（寄存器）是CPU里的一个小区域，用来存变量。一般变量存在内存，而 register 可以将变量存到CPU里去，以达到加快运行速度的目的，但一般用于存大量重复的变量，例如循环变量：for(register int i=1;i<=n;i++)之类的。

2.软件系统：

        软件系统包括操作系统（Linux、Windows、Mac等）以及应用软件（APP）。

三.进制转化：

        十进制转 m 进制——短除法：

        m进制转十进制——逐位乘后求和：

四.位运算和位移操作：​​​​​​​

1.位运算（支持各种运算率）：

优先级：括号 >> 四则运算 >> 逻辑运算 >> 位运算

        按位取反，符号~，将一个整数在二进制下逐位取反。
        按位与，符号&，将两个整数在二进制下对齐个位逐位比较，数码同为 11 则为 11，否则为 00。
        按位或，符号|，将两个整数在二进制下对齐个位逐位比较，数码同位有 11 则为 11，否则为 00。
        按位异或，符号^/xor，将两个整数在二进制下对齐个位逐位比较，数码不同则为 11，否则为 00。

2.位移操作：
        左移： 符号<<，左移一位相当于 ×2×2 。
        右移： 符号>>，右移一位相当于 ×12×12。

五.编码：

        编码包括原码、反码、补码。

        原码：正负用符号位区分，正数第一位为 00，后接数值，负数则为 11。
eg： 55 原码为 0 1010 101。−5−5 原码为 1 1011 101。

        反码：正数的反码就是原码，负数的反码是符号位不变，数值部分取反。
eg： −5−5 反码为 1 0101 010。

        补码：正数的补码还是本身，负数的补码是反码 +1+1。

六.数据结构：

        初赛常考：线性数据结构、树形数据结构、图类数据结构。

        线性数据结构： 数组（包括静态数组和动态数组）、队列（先进先出）、栈（后进先出）、链表（一环扣一环、无法直接访问任意元素）。

        栈常考进出栈顺序及前后缀表达式。
        前缀表达式：指将四则运算的符号放在最前面，两个数值放在最后面的表达式。
        后缀表达式：指将四则运算的符号放在最后面，两个数值放在最前面的表达式。

树的概念：
        树是一种特殊的图，所有结点连通，且 𝑛n 个点 𝑛−1n−1 条边，树中一定没有环。
        在树的结点中，包含父节点、子节点（相对关系）。
        根节点是没有父节点的节点，根据是否约定根节点，分为有根树（约定了根节点或边有向的树）或无根树（没有约定根节点且边无向的树）。
        叶节点是没有子节点的节点。

特殊的树形结构：
        二叉树：对于每个节点，最多只有两个子节点的树。
        完全二叉树：除了最后一层，是一颗完美二叉树，且最后一层的节点尽量靠左分布的二叉树。
        二叉搜索树：对于任意一个节点 𝑥x，其左子树中的权值均不超过 𝑥x 的权值，其右子树中的节点权值均超过 𝑥x 的权值的二叉树。

二叉树中的一些性质：
        树的深度（高度）：描述一棵树的节点层数，需要约定根节点是 00 还是 11。

二叉树中的数量性质：
        若深度从 11 计算，则二叉树第 𝑖i 层上最多有节点 2𝑖−12i−1 个。
        若深度从 11 计算，则深度为 ℎh 的二叉树最多有 2ℎ−12h−1 个节点。
        若深度从 11 计算，那么 𝑛n 个节点的二叉树深度至多为 𝑛n，至少为 ⌈log𝑛+1⌉⌈logn+1⌉。
        所有的二叉树都可以直接用数组来存储，若节点编号为 𝑖i，则下标也为 𝑖i，且左孩子为 𝑖×2i×2，右孩子为 𝑖×2+1i×2+1。

树的遍历：
        前序遍历（根左右）：对于每个节点 𝑥x，满足先输出 𝑥x，再输出 𝑥x 的左孩子，最后输出 𝑥x 的右孩子。
        中序遍历（左根右）：对于每个节点 𝑥x，满足先输出 𝑥x 的左孩子，再输出 𝑥x，最后输出 𝑥x 的右孩子。
        后序遍历（左右根）：对于每个节点 𝑥x，满足先输出 𝑥x 的左孩子，再输出 𝑥x 的右孩子，最后输出 𝑥x。
        层序遍历：从上到下，从左到右。
        由二叉树的形态可以唯一得到遍历顺序，反之不行，但 先序+中序 或 后序+中序 可以唯一确定二叉树的形态。

图的概念：
        由点和线构成的网络。

图的分类：
       有四种方式：
       可分为有向图（边有向或有箭头）和无向图（边无向或无箭头）。
        可分为有权图（边有权重）和无权图（边没有权重）。
        可分为有环图（存在至少一个环）和无环图（不存在环）。
        可分为稀疏图（点多边少）和稠密图（边多点少、边很密集）。

图顶点的度数：
        有向图：分为入度（一个点被多少箭头指向）和出度（一个点指出的箭头数量）。

        无向图：一个点连接的边的数量（无向图不分入度出度），

图的连通性：
        若图中有点 𝑥x 能够找到一条路径到达 y，则称 x 与 y 连通。

        完全图：图中的每一个点都与其余所有点有直接连边。

        对于有 n 个点的无向完全图，其边数为 𝑛×(𝑛−1)2n×(n−1)2

        对于有 n 个点的有向完全图，其边数为 𝑛×(𝑛−1)n×(n−1)

图的存储：
        1°邻接矩阵，设二维数组 𝑔𝑖,𝑗gi,j 表示点i指向点j 的一条边。
        2°邻接链表，设动态数组vectornbr[105];
        比如 22 到 55 有一条边，那么nbr[2].push_back(5)。

七.排序算法：

        冒泡排序：时间复杂度 𝑂(𝑛2)O(n2)，稳定。
        选择排序：时间复杂度 𝑂(𝑛2)O(n2)，不稳定。
        插入排序：时间复杂度 𝑂(𝑛2)O(n2)（可以做到 𝑂(𝑛)O(n)），稳定。

八.数学相关的问题：

        加法原理：做一件事情，有 𝑛n 种做法，第 𝑖i 种做法有 𝑎𝑖ai 种方式，则完成这件事情有 ∑𝑖=1𝑛𝑎𝑖∑i=1nai 种不同的方法。

        乘法原理：做一件事情，有 𝑛n 个步骤，第 𝑖i 个步骤有 𝑎𝑖ai 种方式，则完成这件事情有 ∏𝑖=1𝑛𝑎𝑖∏i=1nai 种不同的方法。

        排列数公式：在 𝑛n 个数种选 𝑚m 个数构成 11 组有序的排列，方案数为：

=𝑛!(𝑛−𝑚)!Anm=n!(n−m)! 

        组合数公式：在 𝑛n 个数种选 𝑚m 个数构成 11 组无序的组合，方案数为：

=𝐴𝑚𝑛=𝑛!(𝑛−𝑚)! 𝑚

第二部分：附录

点击链接下载CSPJ初赛模拟卷

CSPJ初赛模拟试卷.docx-C++文档类资源-CSDN下载明天就是CSPJ初赛了，我整理了一些历年真题和一些易考题放入其中，并按照试卷顺序出了代码题5道，所有更多下载资源、学习资料请访问CSDN下载频道.https://download.csdn.net/download/weixin_46522531/86542452?spm=1001.2014.3001.5503