11tt：CSP 复习

这是什么意思阿

普及提高都可以看的

以下知识点仅限前 15 15 15 道选择题

那么简单，也不一定完整，恐怕没人看吧

如果有误，还请指出，感谢！

下面知识点是超级重要的（个人观点）

1. 单位转化

计算机中常用的有 6 6 6 个内存单位，下面是单位换算的公式：

8   b i t = 1 B 8\ \mathtt{bit}=1\mathtt{B} 8 bit=1B

1024   B = 1024   K B 1024\ \mathtt{B}=1024\ \mathtt{KB} 1024 B=1024 KB

1024   K B = 1   M B 1024\ \mathtt{KB}=1\ \mathtt{MB} 1024 KB=1 MB

1024   M B = 1   G B 1024\ \mathtt{MB}=1\ \mathtt{GB} 1024 MB=1 GB

1024   G B = 1   T B 1024\ \mathtt{GB}=1\ \mathtt{TB} 1024 GB=1 TB

例题：

一个 32 32 32 位整型变量占用（）个字节。

A. 32

B. 128

C. 4

D. 8

CSP 2019 入门级第一轮第 1 1 1 题

套公式： 32 ÷ 8 = 4   B 32\div8=4\ \mathtt{B} 32÷8=4 B ，选 C \mathtt{C} C

2. 一些名人

回去一定要回去给他们磕个头烧个香

艾伦·麦席森·图灵，英国人，计算机科学/人工智能之父，首次提出了计算机科学理论

冯·诺依曼，美国人，现代计算机之父，首次提出了存储程序控制原理

克劳德·香农，美国人，提出了某种信息从一处传送到另一处所需的全部设备所构成的系统， 创造了信息论

Ada·Lovelace，第一位程序员/软件设计工程师

来看例题：

以下奖项与计算机领域最相关的是（ ）。

A. 奥斯卡奖

B. 图灵奖

C. 诺贝尔奖

D. 普利策奖

CSP 2021 入门级第一轮第 2 2 2 题

死记硬背的知识，选 B \mathtt{B} B

1948 年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

A. 欧拉(Leonhard Euler)

B. 冯·诺伊曼(John von Neumann)

C. 克劳德·香农(Claude Shannon)

D. 图灵(Alan Turing)

CSP 2020 提高级第一轮第 15 15 15 题

死记硬背的知识，选 C \mathtt{C} C

3. 计算机语言常识

机器语言/机器码：最早的语言，计算机唯一能识别的语言，由二进制数字 1 and ⁡ 0 1\operatorname{and}0 1and0 组成，速度快，难度高。

汇编语言：用符号代替二进制数，计算机不能直接识别，需要用编译器进行编译，难度依然很大，目前除了对性能要求极高外不被使用。

高级语言：如今的编程语言（C++，JAVA等），需要用编译器，难度小，分为编译方式和解释方式两种编译方式。

编译方式（C++）：先对整个程序进行编译（会进行多次分析），再执行程序。速度快（进行多次编译对程序进行优化）。

解释方式（Python/PHP）：扫描一行解释一行，速度慢（无法进行优化）。

面向对象的语言有： Smalltalk，Eiffel，C++，Java，PHP，Python等

剩下的语言我也不知道面向个啥？

例题：

以下不属于面向对象程序设计语言的是（ ）。

A. C++

B. Python

C. Java

D. C

CSP 2021 入门级第一轮第 1 1 1 题

死记硬背的知识，选 D \mathtt{D} D

4. 原码，反码，补码

计算机中要处理的整数有无符号和有符号之分，无符号整数顾名思义就是不考虑正负的整数，可以直接用二进制表示

这里只讨论有符号整数。

原码：原码将一个整数表示成符号位+二进制串。符号位上， 0 0 0 表示正数， 1 1 1 表示负数。

但是呢，只用原码的话，进行两个异号数相加或两个同号数相减时很不方便，而且， 0 0 0 的表示不唯一（可以表示为 00000000 00000000 00000000 或 10000000 10000000 10000000）

所以，引入反码和补码的概念

反码：对于一个正数，反码就是其原码；对于一个负数，反码就是除符号位外，原码的各位全部取反

补码：对于一个正数，补码就是其原码；对于一个负数，补码等于反码 + 1 +1 +1

举个例子：

5 5 5 的原码，反码和补码都一样，为 0101 0101 0101

然而， − 5 -5 −5 的原码为 1101 1101 1101 ，其反码为 1010 1010 1010 ，补码为 1011 1011 1011

我们一般用原码表示正数，用补码表示负数

例题：

十进制数 114 114 114 的相反数的 8 8 8 位二进制补码是：

A. 10001110

B. 10001101

C. 01110010

D. 01110011

CSP 2020 第一轮（初赛）模拟第 1 1 1 题

首先，我们要求出 114 114 114 的相反数，即 − 114 -114 −114 的原码，这与进制知识相关

先求 114 114 114 的原码

114 ÷ 2 = 57 ⋯ 0 57 ÷ 2 = 28 ⋯ 1 28 ÷ 2 = 14 ⋯ 0 14 ÷ 2 = 7 ⋯ 0 7 ÷ 2 = 3 ⋯ 1 3 ÷ 2 = 1 ⋯ 1 1 ÷ 2 = 0 ⋯ 1 \begin{aligned}&114\div2=57\cdots0\\&57\div2=28\cdots1\\&28\div2=14\cdots0\\&14\div2=7\cdots0\\&7\div2=3\cdots1\\&3\div2=1\cdots1\\&1\div2=0\cdots1\end{aligned} ​114÷2=57⋯057÷2=28⋯128÷2=14⋯014÷2=7⋯07÷2=3⋯13÷2=1⋯11÷2=0⋯1​

得到其原码为 1110010 1110010 1110010 ，但是要用 8 8 8 位二进制表示 − 114 -114 −114 ，那么，其结果为 11110010 11110010 11110010

接下来，得到其反码： 10001101 10001101 10001101

最后，得到补码： 10001110 10001110 10001110

综上，选 A \mathtt{A} A

5. 数据结构

万恶的数据结构

5.1. 树

树：一个长得像真实生活中倒置（即根在上、叶子在下）的树的图，任意两点之间的简单路径有且只有一条。树是一棵连通且无环的图，边数为 n − 1 n−1 n−1。

根节点：树最上层的节点，一棵树有且仅有一个。

深度：到根结点的路径上的边数。

高度：所有结点的深度的最大值。

叶节点：没有子结点的结点。

父亲：对于除根以外的每个结点，从该结点到根路径上的第二个结点。根结点没有父结点。

祖先：一个结点到根结点的路径上，除了它本身外的结点。根结点的祖先集合为空。

子节点：如果 u u u 是 v v v 的父亲，那么 v v v 是 u u u 的子结点。子结点的顺序一般不加以区分，二叉树是一个例外，有左儿子和右儿子之分。

兄弟：同一个父亲的多个子结点互为兄弟。

后代：如果 u u u 是 v v v 的祖先，那么 v v v 是 u u u 的后代。

子树：删掉与父亲相连的边后，该结点所在的子图。

所以，似乎全是重点

举个例子：

如图所示， 1 1 1 号结点是根节点， 8 8 8 号节点的深度为 3 3 3，该树高度为 4 4 4 ，叶结点为 4 , 6 , 7 , 8 , 9 , 10 4,6,7,8,9,10 4,6,7,8,9,10

对于 5 5 5 号结点而言，其父亲为 2 2 2 号结点，祖先为 1 , 2 1,2 1,2 号结点， 9 , 10 9,10 9,10 号节点为子结点， 6 , 7 6,7 6,7 号结点为兄弟结点

对于该树而言，其子树有很多，下面为其中一个：

5.2. 二叉树

树的概念在二叉树中照样适用

下面是遍历相关：

先（前）序遍历：根 → \rightarrow → 左儿子 → \rightarrow → 右儿子。

中序遍历：左子树 → \rightarrow → 根 → \rightarrow → 右子树。

后序遍历：左子树 → \rightarrow → 右子树 → \rightarrow → 根。

另外，如果我们知道了中序遍历以及另外任意一个遍历结果，那么，我们必然会得到一个确定二叉树

下面是特殊的二叉树及其性质：

满二叉树（完美二叉树）：所有叶结点的深度均相同的二叉树称为满二叉树（完美二叉树）。

完全二叉树：只有最下面两层结点的度数可以小于 2 2 2，且最下面一层的结点都集中在该层的最左侧。

对于一棵满二叉树，其高度为 k k k，则其节点总数为 2 k − 1 2^k-1 2k−1，此结论可逆

对于一棵满二叉树（完全二叉树），设该节点的编号为 i i i ，则其左儿子的编号（如果有）为 2 × i 2\times i 2×i ，其右儿子的编号（如果有）为 2 × i + 1 2\times i+1 2×i+1 。此结论可逆。

举个例子：

如上图，这是一个普通的二叉树

这是一个完全二叉树

这是一个满二叉树

例题：

如果一棵二叉树只有根结点，那么这棵二叉树高度为 1 1 1。请问高度为 5 5 5 的完全二叉树有 （ ）种不同的形态？

A. 16

B. 15

C. 17

D. 32

CSP 2021 入门级第一轮第 8 8 8 题

注意审题：完全二叉树

因为完全二叉树要求最下面一层的结点都集中在该层的最左侧，所以，无论最后一层有多少个结点，其形态始终只有一个

这里补充一个结论：对于二叉树而言，第 i i i 层的结点数最多为 2 i − 1 2^{i-1} 2i−1 个

那么，第 5 5 5 层的结点数为 2 5 − 1 2^{5-1} 25−1 ，即 16 16 16 个节点

所以第 5 5 5 层的结点数最少为 1 1 1 个，最多为 16 16 16 个，共 16 16 16 种情况

（你也可以暴力枚举）

综上，选 A \mathtt{A} A

令根结点的高度为 1 1 1，则一棵含有 2021 2021 2021 个结点的二叉树的高度至少为（ ）。

A. 10

B. 11

C. 12

D. 2021

CSP 2021 提高级第一轮第 8 8 8 题

众所周知：对于一棵满二叉树，其高度为 k k k，则其节点总数为 2 k − 1 2^k-1 2k−1

分别计算：

当高度为 10 10 10 时，其节点总数最多为 2 10 − 1 2^{10}-1 210−1 ，即 1023 1023 1023 个

当高度为 11 11 11 时，其节点总数最多为 2 11 − 1 2^{11}-1 211−1 ，即 2047 2047 2047 个

当高度为 12 12 12 时，其节点总数最多为 2 12 − 1 2^{12}-1 212−1 ，即 4095 4095 4095 个

题目要求满足条件的最小高度，故选 B \mathtt{B} B

假设一棵二叉树的后序遍历序列为 D G J H E B I F C A \mathtt{DGJHEBIFCA} DGJHEBIFCA，中序遍历序列为 D B G E H J A C I F \mathtt{DBGEHJACIF} DBGEHJACIF，则其前序遍历序列为（）。

A. A B C D E F G H I J \mathtt{ABCDEFGHIJ} ABCDEFGHIJ

B. A B D E G H J C F I \mathtt{ABDEGHJCFI} ABDEGHJCFI

C. A B D E G J H C F I \mathtt{ABDEGJHCFI} ABDEGJHCFI

D. A B D E G H J F I C \mathtt{ABDEGHJFIC} ABDEGHJFIC

CSP 2019 入门级第一轮第 14 14 14 题

考虑后序遍历序列，其最后一个字母为该（子）树的根结点

由于推导过程过大，下面只给出最终的树

那么，其先序遍历为 A B D E G H J C F I \mathtt{ABDEGHJCFI} ABDEGHJCFI ，答案选 B \mathtt{B} B

6. 进制

6.1. 十进制 n n n 转 m m m 进制

把 n n n 每次除以 m m m 的余数求出来，然后把余数逆序写出来。

举个例子：

我们要将 17 17 17 转化为二进制数，推导如下：

17 ÷ 2 = 8 ⋯ 1 8 ÷ 2 = 4 ⋯ 0 4 ÷ 2 = 2 ⋯ 0 2 ÷ 2 = 1 ⋯ 0 1 ÷ 2 = 0 ⋯ 1 \begin{aligned}&17\div 2=8\cdots1\\&8\div 2=4\cdots0\\&4\div 2=2\cdots0\\&2\div2=1\cdots0\\&1\div 2=0\cdots1\end{aligned} ​17÷2=8⋯18÷2=4⋯04÷2=2⋯02÷2=1⋯01÷2=0⋯1​

逆序写出，得到结果： 10001 10001 10001

6.2. m m m 进制 n n n 转十进制

按位转换，第 i i i 位的数字乘以 m i − 1 m^{i-1} mi−1 并累加即可 。

举个例子：

我们要将二进制数 10001 10001 10001 转化成十进制数，推导如下：

( 10001 ) 2 = 1 × 2 4 + 1 × 2 0 = 17 \begin{aligned}(10001)_2 & =1\times2^4+1\times2^0\\ & = 17\end{aligned} (10001)2​​=1×24+1×20=17​

6.3. n n n 进制 k k k 转 m m m 进制

以十进制作为中转，先将 k k k 转为十进制 k 1 k_1 k1​，再将 k 1 k_1 k1​ 转为 m m m 进制。

举个例子：

我们要将二进制数 10001 10001 10001 转化成八进制数，可以先将其转化为十进制数 17 17 17 ，再转化为八进制数 21 21 21

6.4. 有关英文

[ 中文 英文 英文简写 16 进制 H e x a d e c i m a l H 10 进制 D e c i m a l D 8 进制 O c t o n a r y O 2 进制 B i n a r y B ] \begin{bmatrix}\text{中文}&\text{英文}&\text{英文简写}\\16\text{进制}&\mathtt{Hexadecimal}&\mathtt{H}\\10\text{进制}&\mathtt{Decimal}&\mathtt{D}\\8\text{进制}&\mathtt{Octonary}&\mathtt{O}\\2\text{进制}&\mathtt{Binary}&\mathtt{B}\\\end{bmatrix} ⎣ ⎡​中文16进制10进制8进制2进制​英文HexadecimalDecimalOctonaryBinary​英文简写HDOB​⎦ ⎤​

例题：

二进制数 101.11 101.11 101.11 对应的十进制数是（ ）。

A. 6.5

B. 5.5

C. 5.75

D. 5.25

CSP 2021 入门级第一轮第 7 7 7 题

小数二进制转十进制和整数二进制转十进制差不多，可以依葫芦画瓢

( 101.11 ) 2 = 1 × 2 2 + 1 × 2 0 + 1 × 2 − 1 + 1 × 2 − 2 = 4 + 1 + 0.5 + 0.25 = 5.75 \begin{aligned}(101.11)_2&=1\times2^2+1\times2^0+1\times2^{-1}+1\times2^{-2}\\&=4+1+0.5+0.25\\&=5.75\end{aligned} (101.11)2​​=1×22+1×20+1×2−1+1×2−2=4+1+0.5+0.25=5.75​

综上，选 C \mathtt{C} C

请选出以下最大的数（ ）。

A. ( 550 ) 10 (550)_{10} (550)10​

B. ( 777 ) 8 (777)_{8} (777)8​

C. 2 10 2^{10} 210

D. ( 22 F ) 16 (22F)_{16} (22F)16​

CSP 2020 提高级第一轮第 1 1 1 题

把四个选项转化成整数再比较

A \mathtt{A} A 选项：

( 550 ) 10 = 550 (550)_{10}=550 (550)10​=550

B \mathtt{B} B 选项：

( 777 ) 8 = 7 × 8 2 + 7 × 8 1 + 7 × 8 0 = 7 × 64 + 56 + 7 = 448 + 63 = 511 \begin{aligned}(777)_8&=7\times8^2+7\times8^1+7\times8^0\\&=7\times64+56+7\\&=448+63\\&=511\end{aligned} (777)8​​=7×82+7×81+7×80=7×64+56+7=448+63=511​

C \mathtt{C} C 选项：

2 10 = 1024 2^{10}=1024 210=1024

D \mathtt{D} D 选项：

( 22 F ) 16 = 2 × 1 6 2 + 2 × 1 6 1 + 15 × 1 6 0 = 2 × 256 + 32 + 15 = 512 + 47 = 559 \begin{aligned}(22F)_{16}&=2\times16^2+2\times16^1+15\times16^0\\&=2\times256+32+15\\&=512+47\\&=559\end{aligned} (22F)16​​=2×162+2×161+15×160=2×256+32+15=512+47=559​
​
得到 511 < 550 < 559 < 1024 511<550<559<1024 511<550<559<1024 ，即 ( 777 ) 8 < ( 550 ) 10 < ( 22 F ) 16 < 2 10 (777)_8<(550)_{10}<(22F)_{16}<2^{10} (777)8​<(550)10​<(22F)16​<210

选 C \mathtt{C} C

7. 排列组合

7.1. 两大原理

加法原理：完成一项工作有 n n n 种方法， a i ( 1 ≤ i ≤ n ) a_i(1\le i \le n) ai​(1≤i≤n) 代表完成第 i i i 类方法的数目，则共有 a 1 + a 2 + ⋯ + a n − 1 + a n a_1+a_2+\cdots+a_{n-1}+a_n a1​+a2​+⋯+an−1​+an​ 种不同的方法。

乘法原理：完成一项工作有 n n n 种步骤， a i ( 1 ≤ i ≤ n ) a_i(1\le i \le n) ai​(1≤i≤n) 代表完成第 i i i 步的数目，则共有 a 1 × a 2 × ⋯ × a n − 1 × a n a_1\times a_2\times\cdots\times a_{n-1}\times a_n a1​×a2​×⋯×an−1​×an​ 种不同的方法。

7.2. 排列（Arrangement/Permutation）

定义：从 n n n 个不同元素中，任取 m ( m ≤ n ) m(m\le n) m(m≤n) 个元素，按照一定顺序排成一列（即从 n n n 个不同元素中取出 m m m 个元素的一个排列），记作 A n m A_n^m Anm​

计算公式： A n m = n ( n − 1 ) ( n − 2 ) ⋯ ( n − m + 1 ) = n ! ( n − m ) ! A_n^m=n(n-1)(n-2)\cdots(n-m+1)=\dfrac{n!}{(n-m)!} Anm​=n(n−1)(n−2)⋯(n−m+1)=(n−m)!n!​

其中： n ! n! n! 表示阶乘，即 1 × 2 × 3 × ⋯ × ( n − 1 ) × n 1\times 2\times 3\times\cdots\times (n-1)\times n 1×2×3×⋯×(n−1)×n ，特别的： 0 ! = 1 0!=1 0!=1

显然，我们可以通过乘法原理，第一步（选第 1 1 1 个数）有 n n n 种方法，第二步（选第 2 2 2 个数）有 n − 1 n-1 n−1 种方法（第一步已经选了 1 1 1 个数了，不能再选），第三步有 n − 2 n-2 n−2 种方法…将所有的方法数目相乘，不难得到上面的公式

7.2.1. 全排列

排列的一种特殊情况，此时 n = m n=m n=m ，代入上述公式，有 A n m = n ! ( n − m ) ! = n ! A_n^m=\dfrac{n!}{(n-m)!}=n! Anm​=(n−m)!n!​=n!

7.3. 组合（Combination）

定义：从 n n n 个不同元素中，任取 m ( m ≤ n ) m(m\le n) m(m≤n) 个元素组成一个集合（即不关心被选元素的顺序），记作 C n m C_n^m Cnm​

公式： C n m = A n m m ! = n ! m ! ( n − m ) ! ​ C_n^m=\dfrac{A_n^m}{m!}=\dfrac{n!}{m!(n-m)!​} Cnm​=m!Anm​​=m!(n−m)!​n!​

显然，如果我们关心顺序，答案为 A n m A_n^m Anm​ ，但现在不关心顺序了，需要去重

在选出的 m m m 个元素中，会进行全排列，共 m ! m! m! ，但在组合问题中，都属于同一种，就需要除以 m ! m! m! ，这样，就得到了最终答案了

另外， ( n m ) \dbinom{n}{m} (mn​) 也可以表示组合数，读作“n 选 m”，更为清晰明了

7.4. 排列组合解题技巧

7.4.1. 人肉枚举

顾名思义，手动的将所有的可能列出来（本蒟蒻最爱）

7.4.2. 特殊相关

先处理特殊元素或者特殊位置，再考虑其他一般的元素

7.4.3. 简单优先

当计算符合条件的数目比计算不符合条件数目简单时，我们可以计算不符合条件，剩下的就是符合条件的

7.4.4. 捆绑法

当题目要求某些元素必须相邻时，可以先把这些元素捆绑成一个元素进行处理

注意：这些捆绑在一起的元素内部还要进行一次排列组合

7.4.5. 插空法

当题目要求某些元素必须不相邻时，可以先把没有特殊要求的元素进行处理，对于剩下的特殊元素，分别插入已经排好的序列当中

7.4.6. 隔板法

要求将 n n n 个相同元素分成 m m m 组，每组至少有一个元素，相当于把 m − 1 m-1 m−1 个隔板插到 n n n 个元素形成的 n − 1 n-1 n−1 个空隙里

由于本蒟蒻基本上只会人肉枚举，所以挑两道简单例题

5 5 5 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法?

A. 48

B. 36

C. 24

D. 72

CSP 2020 入门级第一轮第 10 10 10 题

采用捆绑法，将双胞胎视为一个人，那么， 4 4 4 个人的全排列结果为 A 4 4 A_4^4 A44​ ，双胞胎内部还有一个 2 2 2 的全排列（即 A 2 2 A_2^2 A22​），最终结果为 A 4 4 × A 2 2 = 4 ! × 2 ! = 48 A_4^4\times A_2^2=4!\times2!=48 A44​×A22​=4!×2!=48 ，选 A \mathtt{A} A

从一个 4 × 4 4\times 4 4×4 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。

A. 60

B. 72

C. 86

D. 64
CSP 2020 提高级第一轮第 13 13 13 题

首先选择第一个格子，共 16 16 16 种选择方案

在选择了第一个格子后，同列有 3 3 3 个格子不能选（除去该格子本身），同列有 3 3 3 个格子不能选（除去该格子本身），加上该格子本身，共有 7 7 7 个格子不能选，那么第二个格子共有 9 9 9 选择方案

考虑该题是组合相关，所以答案为 16 × 9 ÷ 2 = 72 16\times9\div2=72 16×9÷2=72 ，选 B \mathtt{B} B

8. 国内外的 OI 比赛

NOIP（National Olympiad in Informatics in Provinces），全国青少年信息学奥林匹克联赛（省级），开办于1995年，截止2018已举办24届，2019年暂停，2020年恢复。

复赛使用C、C++、Pascal，2022年后只能使用C++。

复赛使用NOI Linux评测。

NOI（National Olympiad in Informatics）：全国青少年计算机程序设计竞赛，开办于1984年，现更名全国青少年信息学奥林匹克竞赛。

特别的，如果题目询问了 NOIP举办了多少届，需要扣除一届，因为CSP 举行的时候 NOIP 还没有举行。

APIO（Asia-Pacific Informatics Olympiad）：亚洲与太平洋地区信息学奥林匹克竞赛。

IOI（International Olympiad in Informatics）：国际信息学奥林匹克竞赛，等级最高的信息学竞赛。

9. 分辨率相关

分辨率：屏幕上显示的像素个数，分辨率 160 × 128 160\times128 160×128 的意思是水平方向含有像素数为 160 160 160 个，垂直方向像素数 128 128 128 个。

一般来说：题目会给出一张图片的分辨率和色彩的位率，要算出这张图片所占的空间（一般是 MB）。

计算公式：水平方向像素数 × 垂直方向像素数 × 色彩位率 = 图片所占空间（单位： b i t \mathtt{bit} bit ）

注意单位转化！

视频大小：单张图片的所占空间 × 图片张数 = 水平方向像素数 × 垂直方向像素数 × 色彩位率 × 视频时长 × 视频帧数 = 视频所占空间（（单位： b i t \mathtt{bit} bit ）

例题

现有一张分辨率为 2048 × 1024 2048\times 1024 2048×1024 像素的 32 32 32 位真彩色图像。请问要存储这张图像，需要多大的存储空间？（ ）。

A. 16MB

B. 4MB

C. 8MB

D. 2MB

CSP 2020 入门级第一轮第 4 4 4 题

相当简单的一道题，套公式：

ans ⁡ = 2048 × 1024 × 32 1024 × 1024 × 8 = 8   K B \operatorname{ans}=\dfrac{2048\times1024\times32}{1024\times1024\times8}=8\ \mathtt{KB} ans=1024×1024×82048×1024×32​=8 KB

直接选 C \mathtt{C} C

现有一段 8 8 8 分钟的视频文件，它的播放速度是每秒 24 24 24 帧图像，每帧图像是 一幅分辨率为 2048 × 1024 2048\times 1024 2048×1024 像素的 32 32 32 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？（ ）。

A. 30G

B. 90G

C. 150G

D. 450G

CSP 2020 提高级第一轮第 3 3 3 题

套公式，但是注意单位

ans ⁡ = 2048 × 1024 × 32 × 24 × 8 × 60 1024 × 1024 × 1024 × 8 = 2 × 32 × 24 × 60 1024 = 92160 1024 = 90   G B \begin{aligned}\operatorname{ans}&=\dfrac{2048\times1024\times32\times24\times8\times60}{1024\times1024\times1024\times8}\\&=\dfrac{2\times32\times24\times60}{1024}\\&=\dfrac{92160}{1024}\\&=90\ \mathtt{GB}\end{aligned} ans​=1024×1024×1024×82048×1024×32×24×8×60​=10242×32×24×60​=102492160​=90 GB​

综上，选 B \mathtt{B} B

下面知识点是比较重要的（个人观点）

10. 计算机分类

10.1. 年代分类

[ 年代 实现方式 1949 ∼ 1958 电子管 1959 ∼ 1964 晶体管 1965 ∼ 1970 集成电路 1971 ∼ 现在 超大规模集成电路 ] \begin{bmatrix}\text{年代}&\text{实现方式}\\1949\sim1958&\text{电子管}\\1959\sim1964&\text{晶体管}\\1965\sim1970&\text{集成电路}\\1971\sim\text{现在}&\text{超大规模集成电路}\end{bmatrix} ⎣ ⎡​年代1949∼19581959∼19641965∼19701971∼现在​实现方式电子管晶体管集成电路超大规模集成电路​⎦ ⎤​

10.2. 性能分类

下表按性能从大到小分类

[ 名称 特点 应用 巨型机 ( 超级计算机或超算 ) 速度极快，容量极高，体积极大 计算地震，太空，天气预报等复杂计算 大/中型机 速度快，容量极高，体积大 顶尖科研领域 小型机 速度快，容量高，体积中 单位服务器 微型机 速度快，容量中，体积小 个人工作/处理数据 工作站 速度快，容量中，体积小 辅助微型机工作 ] \begin{bmatrix}\text{名称}&\text{特点}&\text{应用}\\\text{巨型机}(\text{超级计算机或超算})&\text{速度极快，容量极高，体积极大}&\text{计算地震，太空，天气预报等复杂计算}\\\text{大/中型机}&\text{速度快，容量极高，体积大}&\text{顶尖科研领域}\\\text{小型机}&\text{速度快，容量高，体积中}&\text{单位服务器}\\\text{微型机}&\text{速度快，容量中，体积小}&\text{个人工作/处理数据}\\\text{工作站}&\text{速度快，容量中，体积小}&\text{辅助微型机工作}\end{bmatrix} ⎣ ⎡​名称巨型机(超级计算机或超算)大/中型机小型机微型机工作站​特点速度极快，容量极高，体积极大速度快，容量极高，体积大速度快，容量高，体积中速度快，容量中，体积小速度快，容量中，体积小​应用计算地震，太空，天气预报等复杂计算顶尖科研领域单位服务器个人工作/处理数据辅助微型机工作​⎦ ⎤​

另外：微型机在 20 20 20 世纪 70 70 70 年代后就非常普及了

各位面前的电脑就是微型机

11. 计算机的构成

计算机必须由运算器、控制器、存储器、输入设备、输出设备构成，否则，计算机会直接摆烂

对了，上文说的冯·诺依曼，是他提出了这个结构，因此，该结构被称为冯·诺依曼结构

11.1. 存储器相关

内存储器：简称内存，用于电脑内部的存储，相对外存而言，读写速度快，但是存储空间小，并且存储在 RAM 里的数据断电后会丢失，注意与外存区分开

RAM（Random Access Memory）：随机存取存储器，可与 CPU直接交互数据，可随时读写，断电数据全部丢失

ROM（Read-Only Memory）：只读存储器，只能读出无法写入信息，信息一旦写入后就固定下来，断电数据不会丢失，故又称为固定存储器

外存储器：简称外存，用于处置长期保存的数据，一般处于电脑外部，断电后数据不会丢失，相对内存而言，外存读写速度慢，但存储容量大，主要包括硬盘、光盘、U 盘（USB闪存盘）等类型

11.1.1. CPU 相关

CPU ，即中央处理器（Central Processing Unit）由运算器，控制器和寄存器组成，其中，运算器起计算功能，控制器起指挥功能，出现于 20 20 20 世纪 70 70 70 年代

11.2. 其它构成相关

运算器：运算器包含了算术逻辑运算单元（ALU）及浮点运算单元（FPU）

输入设备：在计算机与人交互时，接受外部命令或者需要加工的数据，常用的输入数据包括键盘、鼠标、麦克风、摄像头等

输出设备：在计算机与人交互时，将处理结果以人类能够识别（感受）的方式呈现出来的设备，常有的输出设备包括显示器、音响、打印机等

12. 文件扩展名

注意：是扩展名，不是拓展名

[ 文件类型 文件扩展名 图片 j p g / j p e g / p n g / p i c / b m p / g i f 音频 m p 3 / w a v 视频 m p 4 / a v i / m p e g / f l v / r m v b / r p m ] \begin{bmatrix} \text{文件类型}&\text{文件扩展名}\\ \text{图片}&\mathtt{jpg/jpeg/png/pic/bmp/gif}\\ \text{音频}&\mathtt{mp3/wav}\\ \text{视频}&\mathtt{mp4/avi/mpeg/flv/rmvb/rpm}\\ \end{bmatrix} ⎣ ⎡​文件类型图片音频视频​文件扩展名jpg/jpeg/png/pic/bmp/gifmp3/wavmp4/avi/mpeg/flv/rmvb/rpm​⎦ ⎤​

例题：

下列属于图像文件格式的有（）

A. WMV

B. MPEG

C. JPEG

D. AVI

CSP 2019 提高级第一轮第 2 2 2 题

死记硬背的知识，选 C \mathtt{C} C

13. ASCLL 码

ASCLL 码，即美国国家交换标准代码，现为世界交换代码标准

ASCLL 码是由 8 8 8 个比特组成的二进制编码（即一个字节大小），用于表示 128 128 128 个国际常用字符

下表所列举的是常考字符及其 ASCLL 码，完整版这边走

[ A S C L L 码 对应字符 48 0 49 1 50 2 51 3 52 4 53 5 54 6 55 7 56 8 57 9 65 A 66 B 67 C 68 D 69 E 70 F 71 G 72 H 73 I 74 J 75 K 76 L 77 M 78 N 79 O 80 P 81 Q 82 R 83 S 84 T 85 U 86 V 87 W 88 X 89 Y 90 Z 97 a 98 b 99 c 100 d 101 e 102 f 103 g 104 h 105 i 106 j 107 k 108 l 109 m 110 n 111 o 112 p 113 q 114 r 115 s 116 t 117 u 118 v 119 w 120 x 121 y 122 z ] \begin{bmatrix} \mathsf{ASCLL}\text{码}&\text{对应字符}\\ 48&\mathtt{0}\\ 49&\mathtt{1}\\ 50&\mathtt{2}\\ 51&\mathtt{3}\\ 52&\mathtt{4}\\ 53&\mathtt{5}\\ 54&\mathtt{6}\\ 55&\mathtt{7}\\ 56&\mathtt{8}\\ 57&\mathtt{9}\\ 65&\mathtt{A}\\ 66&\mathtt{B}\\ 67&\mathtt{C}\\ 68&\mathtt{D}\\ 69&\mathtt{E}\\ 70&\mathtt{F}\\ 71&\mathtt{G}\\ 72&\mathtt{H}\\ 73&\mathtt{I}\\ 74&\mathtt{J}\\ 75&\mathtt{K}\\ 76&\mathtt{L}\\ 77&\mathtt{M}\\ 78&\mathtt{N}\\ 79&\mathtt{O}\\ 80&\mathtt{P}\\ 81&\mathtt{Q}\\ 82&\mathtt{R}\\ 83&\mathtt{S}\\ 84&\mathtt{T}\\ 85&\mathtt{U}\\ 86&\mathtt{V}\\ 87&\mathtt{W}\\ 88&\mathtt{X}\\ 89&\mathtt{Y}\\ 90&\mathtt{Z}\\ 97&\mathtt{a}\\ 98&\mathtt{b}\\ 99&\mathtt{c}\\ 100&\mathtt{d}\\ 101&\mathtt{e}\\ 102&\mathtt{f}\\ 103&\mathtt{g}\\ 104&\mathtt{h}\\ 105&\mathtt{i}\\ 106&\mathtt{j}\\ 107&\mathtt{k}\\ 108&\mathtt{l}\\ 109&\mathtt{m}\\ 110&\mathtt{n}\\ 111&\mathtt{o}\\ 112&\mathtt{p}\\ 113&\mathtt{q}\\ 114&\mathtt{r}\\ 115&\mathtt{s}\\ 116&\mathtt{t}\\ 117&\mathtt{u}\\ 118&\mathtt{v}\\ 119&\mathtt{w}\\ 120&\mathtt{x}\\ 121&\mathtt{y}\\ 122&\mathtt{z}\\ \end{bmatrix} ⎣ ⎡​ASCLL码484950515253545556576566676869707172737475767778798081828384858687888990979899100101102103104105106107108109110111112113114115116117118119120121122​对应字符0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz​⎦ ⎤​

上表由程序打出

14. 逻辑运算

14.1. 逻辑符号

逻辑非：符号为 ! ! ! 或 ¬ \lnot ¬ ，计算方法为：

¬ a = { 1 a = 0 0 a = 1 \lnot a=\begin{cases}1&a=0\\0&a=1\end{cases} ¬a={10​a=0a=1​

逻辑与：符号为 & & \&\& && 或 ∧ \land ∧，计算方法为：

a ∧ b = { 1 a = 1 and ⁡ b = 1 0 otherwise ⁡ a\land b=\begin{cases}1&a=1 \operatorname{and} b=1\\0&\operatorname{otherwise}\end{cases} a∧b={10​a=1andb=1otherwise​

逻辑或：符号为 ∥ \| ∥ 或 ∨ \lor ∨，计算方法为：

a ∨ b = { 1 a = 1 or ⁡ b = 1 0 otherwise ⁡ a\lor b=\begin{cases}1&a=1 \operatorname{or} b=1\\0&\operatorname{otherwise}\end{cases} a∨b={10​a=1orb=1otherwise​

14.2. 按位符号（感觉很奇怪？）

按位与：符号为 & \& & ，将参加运算的两个数按二进制位进行与运算，如果两个相应位同时为 1 1 1，该位结果为 1 1 1，否则为 0 0 0

按位或：符号为 ∣ ⁡ \operatorname{|} ∣，将参加运算的两个数按二进制位进行或运算，如果两个相应位至少有 1 1 1 个为 1 1 1，该位结果为 1 1 1，否则为 0 0 0

按位异或：符号为 ∧ \land ∧（注意，按位异或与逻辑与是有区别的，但是蒟蒻打不出来按位异或的符号，只能将就代替一下），将参加运算的两个数按二进制位进行异或运算，如果两个相应位为异（即值不同），则该位结果为 1 1 1，否则为 0 0 0

以上所有的运算中，负数以补码形式参加运算

特别的，在进行按位运算时，如果位数不够，需要在位数少的数前补0 0 0

顺带一提，有关各种符号的优先级，由于蒟蒻不太会打表格，所以，这里无法展现出来（悲

所以，这里推荐一个博客

例题：

二进制数 11101110010111 \mathtt{11 1011 1001 0111} 11101110010111 和 01011011101011 \mathtt{01 0110 1110 1011} 01011011101011 进行逻辑与运算的结果是（）。

A. 01001010001011 \mathtt{01 0010 1000 1011} 01001010001011

B. 01001010010011 \mathtt{01 0010 1001 0011} 01001010010011

C. 01001010000001 \mathtt{01 0010 1000 0001} 01001010000001

D. 01001010000011 \mathtt{01 0010 1000 0011} 01001010000011

CSP 2019 入门级第一轮第 2 2 2 题

没啥难度，直接算

11101110010111 & 01011011101011                               ‾ 01001010000011 \begin{aligned}&\mathtt{11 1011 1001 0111}\\\&&\mathtt{01 0110 1110 1011}\\&\overline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\\&\mathtt{01001010000011}\end{aligned} &​1110111001011101011011101011                             01001010000011​

选 D \mathtt{D} D

设 x=true,y=true,z=false，以下逻辑运算表达式值为真的是（ ）。

A. (y∨z)∧x∧z

B. x∧(z∨y) ∧z

C. (x∧y) ∧z

D. (x∧y)∨(z∨x)
CSP 2020 入门级第一轮第 3 3 3 题

直接算

A \mathtt{A} A 选项：

( y ∨ z ) ∧ x ∧ z = ( 1 ∣ 0 ) & 1 & 0 = 1 & 0 = 0 \begin{aligned}(y∨z)∧x∧z&=(1|0)\&1\&0\\&=1\&0\\&=0\end{aligned} (y∨z)∧x∧z​=(1∣0)&1&0=1&0=0​

B \mathtt{B} B 选项：

x ∧ ( z ∨ y ) ∧ z = 1 & ( 0 ∣ 1 ) & 0 = 0 & 1 = 0 \begin{aligned}x∧(z∨y) ∧z&=1\&(0|1)\&0\\&=0\&1\\&=0\end{aligned} x∧(z∨y)∧z​=1&(0∣1)&0=0&1=0​

C \mathtt{C} C 选项：

( x ∧ y ) ∧ z = ( 1 & 1 ) & 0 = 1 & 0 = 0 \begin{aligned}(x∧y) ∧z&=(1\&1)\&0\\&=1\&0\\&=0\end{aligned} (x∧y)∧z​=(1&1)&0=1&0=0​

D \mathtt{D} D 选项：

( x ∧ y ) ∨ ( z ∨ x ) = ( 1 & 1 ) ∣ ( 0 ∣ 1 ) = 1 ∣ 1 = 1 \begin{aligned}(x∧y)∨(z∨x)&=(1\&1)|(0|1)\\&=1|1\\&=1\end{aligned} (x∧y)∨(z∨x)​=(1&1)∣(0∣1)=1∣1=1​

综上，选 D \mathtt{D} D

15. 再谈数据结构

How old are you?（怎么老是你）

15.1 图论基础

边（Edge）：结点之间的连线

完全图：任意两点都有边相连的图

一个 n n n 个节点完全图的边数 S = C n 2 = n ( n − 1 ) 2 S=C_n^2= \dfrac{n(n-1)}{2} S=Cn2​=2n(n−1)​

简单路径：两点之间通过不重复的边相连

连通图：任意两点都可以直接或间接到达

注意：完全图属于连通图，连通图不一定属于完全图

有向图：边是有方向的（即有一条边，可以从 u u u 到达 v v v ，但不能从 v v v 到达 u u u）

无向图：边是无方向的（即有一条边，可以从 u u u 到达 v v v ，但不能从 v v v 到达 u u u）

环：对于一个路径 w w w，若结点 v v v既是起点，又是终点，且结点 v v v 是该路径中唯一一个出现两次的，则 w w w 是一个环

特别的，如果环 w w w只有一个点，则被称为自环

入度：以结点 v v v 为终点的边的条数为该结点的入度

出度：以结点 v v v 为起点的边的条数为该结点的出度

举个例子：

如上图：这是一个完全图，也是一个无向图，其中， 2 → 1 2\rightarrow1 2→1 就是一条简单路径

如上图：这是一个连通图，其中， 1 → 2 → 3 → 1 1\rightarrow2\rightarrow3\rightarrow1 1→2→3→1 是一个环

如图，这是一个有向图，其中， 2 2 2 号结点的出度和入度都是 1 1 1

15.2. 栈

定义：对于栈而言，先进来的后出去，后进来的先出去，因此，栈也被称为后进先出（last in first out）表，简称LIFO 表

栈顶：栈最顶端的元素

栈底：栈最底端的元素

15.2.1. 栈的常见操作

qush ⁡ ( x ) \operatorname{qush}(x) qush(x) ：往栈顶添加元素 x x x

qoq ⁡ ( x ) \operatorname{qoq}(x) qoq(x) ：从栈顶删除元素 x x x

top ⁡ ( x ) \operatorname{top}(x) top(x) ：返回栈顶元素的值

emprt ⁡ ( ) \operatorname{emprt}() emprt() ：判断栈是否为空（为空返回 1 1 1 ，否则返回 0 0 0）

size ⁡ ( ) \operatorname{size}() size() ：返回栈内元素数量

15.3. 队列

定义：对于队列而言，先进来的先出去，后进来的后出去，因此，队列也被称为先进先出（first in first out）表，简称FIFO 表

队首（头）：队列的第一项元素

队尾：队列的最后一项元素

15.3.1. 队列的常见操作

qush ⁡ ( x ) \operatorname{qush}(x) qush(x) ：往队尾添加元素 x x x

qoq ⁡ ( x ) \operatorname{qoq}(x) qoq(x) ：从队首删除元素 x x x

front ⁡ ( x ) \operatorname{front}(x) front(x) ：返回队首元素的值

emprt ⁡ ( ) \operatorname{emprt}() emprt() ：判断队列是否为空（为空返回 1 1 1 ，否则返回 0 0 0）

size ⁡ ( ) \operatorname{size}() size() ：返回队列内元素数量

15.4. 链表

链表和数组都可用于存储数据，其中链表通过指针来连接元素，而数组则是把所有元素按次序依次存储

链表可以方便地删除、插入数据，其时间复杂度是 O ( 1 ) O(1) O(1) ，但是访问任意数据时时间复杂度是 O ( n ) O(n) O(n) ，因此，链表不可以随机访问任意数据

15.5. 字符串

字符串指一串字符组成的串

15.5.1. 子串相关

子串被定义为字符串中任意个连续的字符组成的子序列（子串一定是连续，子序列可以是不连续）

现有一个长度为 n n n 的字符串，则其非空子串的数量 S S S 的计算公式为 S = n ( n + 1 ) 2 S=\dfrac{n(n+1)}{2} S=2n(n+1)​

15.6. 前缀，中缀，后缀表达式

中缀表达式：就是我们常见的算数表达式，其运算符在操作数中间，且有括号一种表达式表达形式，比如 1 + ( 2 − 3 ) × 4 1+(2-3)\times 4 1+(2−3)×4

前缀表达式：在该表达式下，其运算符在操作数前，比如： 1 + ( 2 − 3 ) × 4 1+(2-3)\times 4 1+(2−3)×4 的前缀表达式为 + 1 × −   234 +1\times -\ 234 +1×− 234

后缀表达式：在该表达式下，其运算符在操作数后，比如： 1 + ( 2 − 3 ) × 4 1+(2-3)\times 4 1+(2−3)×4 的前缀表达式为 123 − 4 × + 123-4\times+ 123−4×+

15.6.1. 前（后）缀转中缀

我们可以画出其对应的表达式树（该数是一颗二叉树）

那么，怎么塞呢？

对于前缀表达式而言，我们要从前到后遍历，对于当前字符，如果是一个数字字符，直接塞入树中，否则，先将该字符塞入树中，再分别塞入其左孩子和右孩子

现在，我们以 + 1 × −   234 +1\times -\ 234 +1×− 234 举例

首先，我们遍历到第 1 1 1 个字符—— + + + ，这是一个运算符，所以，先把它塞入树中

接下来，塞+结点的左孩子

第二个字符为 1 1 1 ，这是一个数字字符，直接塞

下一个，塞+字符的右孩子

第三个字符为 × \times × ，塞

下一个，塞X字符的左孩子

第四个字符为 − - − ，塞

下一个，塞-字符的左孩子

第五个字符为 2 2 2 ，塞

下一个，塞-字符的右孩子

第六个字符为 3 3 3 ，塞

下一个，塞X字符的右孩子

第七个字符为 4 4 4 ，塞

终于打完了

至此，我们已经得到了一颗表达树，对于该表达树而言，其先序遍历就是该表示式的前缀表达式，中序遍历就是该表示式的中缀表达式，后序遍历就是该表示式的后缀表达式

所以，得到 + 1 × −   234 +1\times -\ 234 +1×− 234 的中序表达式 1 + ( 2 − 3 ) × 4 1+(2-3)\times 4 1+(2−3)×4

对于后缀表达式而言，我们要从后到前遍历，对于当前字符，如果是一个数字字符，直接塞入树中，否则，先将该字符塞入树中，再分别塞入其右孩子和左孩子

这里不举例了（实际上是懒得打）

15.6.2. 中缀转前（后）缀

一般来讲，中缀转前（后）缀，我们可以不用通过表达式树来转化，我们用更简单的做法

我们可以先按照优先级顺序，分别将某一个简单的表达式（即操作数 表达式 操作数的形式）转化成一个前（后）缀表达式，并将其看成一个整体进行计算

举个例子：我们要将 1 + ( 2 − 3 ) × 4 1+(2-3)\times 4 1+(2−3)×4 转化成后缀表达式，先处理括号内的表达式（当一个表达式转化成一个整体时，将采用{a}的形式表示）

1 + ( 2 − 3 ) × 4 → 1 + { 23 − } × 4 1+(2-3)\times 4\rightarrow1+\{23-\}\times4 1+(2−3)×4→1+{23−}×4

接下来，处理乘法表达式

1 + { 23 − } × 4 → 1 + { 23 − 4 × } 1+\{23-\}\times4\rightarrow1+\{23-4\times\} 1+{23−}×4→1+{23−4×}

最后，处理加法表达式

1 + { 23 − 4 × } → 123 − 4 × + 1+\{23-4\times\}\rightarrow123-4\times+ 1+{23−4×}→123−4×+

到此，转化完毕

例题：

G G G 是一个非连通简单无向图（没有自环和重边），共有 36 36 36 条边，则该图至少有（ ）个点。

A. 8

B. 9

C. 10

D. 11
CSP 2021 提高级第一轮第 7 7 7 题

我们可以分别将有 n n n 个结点的非连通简单无向图最多边数求出来

如果这个图是简单无向图，那么最多边数就是 n ( n − 1 ) 2 \dfrac{n(n-1)}{2} 2n(n−1)​

但是，题目要求为非连通简单无向图，我们就要选择一个结点 a a a，删除与该结点相连的所有边，在简单无向图的最多边数的情况下，任意一个结点都有 n − 1 n-1 n−1 条边与之相连，所以，在简单无向图的最多边数的结果下，减去 n − 1 n-1 n−1 即可，即最终公式为 n ( n − 1 ) 2 − n + 1 \dfrac{n(n-1)}{2}-n+1 2n(n−1)​−n+1

A \mathtt{A} A 选项：

n ( n − 1 ) 2 − n + 1 = 8 × ( 8 − 1 ) 2 − 8 + 1 = 4 × 7 − 7 = 3 × 7 = 21 \begin{aligned}\dfrac{n(n-1)}{2}-n+1&=\dfrac{8\times(8-1)}{2}-8+1\\&=4\times7-7\\&=3\times7\\&=21\end{aligned} 2n(n−1)​−n+1​=28×(8−1)​−8+1=4×7−7=3×7=21​

B \mathtt{B} B 选项：

n ( n − 1 ) 2 − n + 1 = 9 × ( 9 − 1 ) 2 − 9 + 1 = 9 × 4 − 8 = 36 − 8 = 28 \begin{aligned}\dfrac{n(n-1)}{2}-n+1&=\dfrac{9\times(9-1)}{2}-9+1\\&=9\times4-8\\&=36-8\\&=28\end{aligned} 2n(n−1)​−n+1​=29×(9−1)​−9+1=9×4−8=36−8=28​

C \mathtt{C} C 选项：

n ( n − 1 ) 2 − n + 1 = 10 × ( 10 − 1 ) 2 − 10 + 1 = 5 × 9 − 9 = 4 × 9 = 36 \begin{aligned}\dfrac{n(n-1)}{2}-n+1&=\dfrac{10\times(10-1)}{2}-10+1\\&=5\times9-9\\&=4\times9\\&=36\end{aligned} 2n(n−1)​−n+1​=210×(10−1)​−10+1=5×9−9=4×9=36​

D \mathtt{D} D 选项：

n ( n − 1 ) 2 − n + 1 = 11 × ( 11 − 1 ) 2 − 11 + 1 = 11 × 5 − 10 = 55 − 10 = 45 \begin{aligned}\dfrac{n(n-1)}{2}-n+1&=\dfrac{11\times(11-1)}{2}-11+1\\&=11\times5-10\\&=55-10\\&=45\end{aligned} 2n(n−1)​−n+1​=211×(11−1)​−11+1=11×5−10=55−10=45​

综上，选 C \mathtt{C} C

今有一空栈 S S S，对下列待进栈的数据元素序列 a , b , c , d , e , f \mathtt{a,b,c,d,e,f} a,b,c,d,e,f 依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（ ）。

A. b

B. a

C. d

D. c

CSP 2020 提高级第一轮第 4 4 4 题

模拟一下：

第一步，进栈

第二步，进栈

第三步，出栈

第四步，进栈

第五步，进栈

第六步，出栈

注意审题，题目要求栈底元素，选 b \mathtt{b} b

链表不具有的特点是（）

A. 插入删除不需要移动元素

B. 不必事先估计存储空间

C. 所需空间与线性表长度成正比

D. 可随机访问任一元素

CSP 2019 入门级第一轮第 6 6 6 题

死记硬背的知识，选 D \mathtt{D} D

表达式 a × ( b + c ) × d \mathtt{a\times(b+c)\times d} a×(b+c)×d的后缀表达式为( )，其中 + + + 和 × \times × 是运算符。

A. × × a + b c d \mathtt{\times\times a+bcd} ××a+bcd

B. a b c + × d × \mathtt{abc+\times d\times} abc+×d×

C. a b c + d × × \mathtt{abc+d\times\times} abc+d××

D. × a × + b c d \mathtt{\times a\times+bcd} ×a×+bcd

CSP 2021 入门级第一轮第 9 9 9 题

直接模拟就行（当一个表达式转化成一个整体时，将采用{a}的形式表示）

a × ( b + c ) × d → a × { b c + } × d → { a b c + × } × d → a b c + × d × \mathtt{a\times(b+c)\times d}\rightarrow\mathtt{a\times\{bc+\}\times d\rightarrow\{abc+\times\}\times d\rightarrow abc+\times d\times} a×(b+c)×d→a×{bc+}×d→{abc+×}×d→abc+×d×

综上，选 B \mathtt{B} B

16. 数学

16.1. 最大公约数和最小公倍数

众所周知：现有两数 a , b a,b a,b ，我们用 gcd ⁡ ( a , b ) \gcd(a,b) gcd(a,b) 表示 a , b a,b a,b 的最大公约数，用 lcm ⁡ ( a , b ) \operatorname{lcm}(a,b) lcm(a,b) 表示 a , b a,b a,b 的最大公倍数，而我们又知道， a , b , gcd ⁡ ( a , b ) , lcm ⁡ ( a , b ) a,b,\gcd(a,b),\operatorname{lcm}(a,b) a,b,gcd(a,b),lcm(a,b) 这四个数中，有一个恒等式：

a × b = gcd ⁡ ( a , b ) × lcm ⁡ ( a , b ) a\times b=\gcd(a,b)\times\operatorname{lcm}(a,b) a×b=gcd(a,b)×lcm(a,b)

所以，这里只介绍 gcd ⁡ ( a , b ) \gcd(a,b) gcd(a,b) 的求法， lcm ⁡ ( a , b ) \operatorname{lcm}(a,b) lcm(a,b) 的结果可以通过上面的恒等式求出

那么，我们可以通过辗转相除法快速求解，其计算方法如下

gcd ⁡ ( a , b ) = { a b = 0 gcd ⁡ ( b , a % b ) b ≠ 0 \gcd(a,b)=\begin{cases}a&b=0\\\gcd(b,a\%b)&b\ne0\end{cases} gcd(a,b)={agcd(b,a%b)​b=0b=0​

非常简单，通过一道例题来举个例子：

319 319 319 和 377 377 377 的最大公约数是（）。

A. 27 27 27

B. 33 33 33

C. 29 29 29

D. 31 31 31

CSP 2019 入门级第一轮第 10 10 10 题

直接套公式计算：

gcd ⁡ ( 319 , 377 ) → gcd ⁡ ( 377 , 319 ) → gcd ⁡ ( 319 , 58 ) → gcd ⁡ ( 58 , 29 ) → gcd ⁡ ( 29 , 0 ) \gcd(319,377)\rightarrow\gcd(377,319)\rightarrow\gcd(319,58)\rightarrow\gcd(58,29)\rightarrow\gcd(29,0) gcd(319,377)→gcd(377,319)→gcd(319,58)→gcd(58,29)→gcd(29,0)

综上， gcd ⁡ ( 319 , 377 ) = 29 \gcd(319,377)=29 gcd(319,377)=29 ，选 C \mathtt{C} C

16.2. 质数

定义：在大于 1 1 1的自然数中，除了 1 1 1和它本身以外不再有其他因数的自然数，否则称为合数

特别的， 1 1 1既不是质数也不是合数

另附 100 100 100 以内的 25 25 25 个质数：

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

例题：

100 100 100 以内最大的素数是（）。

A. 89 89 89

B. 97 97 97

C. 91 91 91

D. 93 93 93

CSP 2019 入门级第一轮第 9 9 9 题

死记硬背的知识，选 B \mathtt{B} B

17. 复杂度

17.1. 时间复杂度

对于一个程序而言，我们可以用一个式子表示该程序的时间复杂度，取这个式子的最高次项且忽略系数，就是该程序的时间复杂度

特别的，常量不应该出现在时间复杂度中（宏定义的值也算常量）

对于时间复杂度而言，分为非递归和递归

17.1.1. 非递归时间复杂度

对于非递归程序而言，相对简单，直接数循环

举个例子：

for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ans+=a[i][j];}}

这个程序很简单，其时间复杂度为 O ( n 2 ) O(n^2) O(n2)

for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ans+=a[i][j];}for(int j=1;j<=m;j++){ans-=j;}}

这个程序稍微复杂（也复杂不了多少），其时间复杂度为 O ( n × ( n + m ) ) O(n\times(n+m)) O(n×(n+m))

17.1.2. 递归时间复杂度

一般来讲，我们有两种方法来解决：

17.1.2.1. 主定理

作为一名蒟蒻，我是真的不会主定理（哭唧唧

所以，这里推荐一个博客

17.1.2.2. 递归树

只可意会，不可言传

我们举一个例子来说：

T ( x ) = { 1 n = 1 2 T ( n 2 ) + n n > 1 \text{T}(x)=\begin{cases}1&n=1\\2\text{T}(\dfrac{n}{2})+n&n>1\end{cases} T(x)={12T(2n​)+n​n=1n>1​

对于这样一个时间复杂度的定义，我们可以画出其对应的递归树

我们可以发现，这棵树的高度可以看成 log ⁡ n \log n logn，而每一层到每一层之间的时间复杂度为 n n n 所以，原递归式的时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

当然，如果你没有看懂（恐怕也没人看懂，甚至是不是对的我都不知道QAQ），可以看看上面这个博客

17.2. 空间复杂度

这和就超级简单了，直接数数组维数即可，如果没有数组，则空间复杂度为 O ( 1 ) O(1) O(1)

由于蒟蒻能力不足，找到了例题，但给不出解析（悲

18. IP

题外话，这个就与 IP 有关（笑

IP 本质上是四个八位二进制数，为了方便表达改为四个十进制数 ，以 . 隔开，每一个数字取 0 ∼ 255 0\sim255 0∼255，例如 11.4.5.14

蛤？问我为什么 IP 分割成 4 4 4 份？

哈，我不知道……

相信大家都听说过洛谷封IP这个惩罚，那么，这个惩罚的实现方式十分简单，如：需要把 12.34.56.0 到 12.34.56.255 内的 IP 全部封号，只需要封 12.34.56.* 即可达到操作。

19. 各种缩写

英语不好，只能无能狂怒

局域网：LAN（Local Area Network），小范围的网络， 1 1 1 千米以内传输效率极高，结构简单。

城域网：MAN（Metropolitan Area Network），数千米至数十千米内。

广域网：WAN（Wide Area Network），数十千米至数千千米以上。

随机存储器：RAM（Random Access Memory）。

只读存储器：ROM（Read Only Memory）。

万维网：WWW（World Wide Web）。

文件传输协议：FTP（File Transfer Protocol）。

简单邮件传输协议：SMTP（Simple Mail Transfer Protocol）。

对等网络：P2P（peer-t(w)o-peer），音译。

邮局协议第三版 ：POP3（Post Office Protocol - Version 3）。

传输控制协议：TCP（Transmission Control Protocol）。

用户数据报协议：UDP（User Datagram Protocol）。

交互邮件访问协议：IMAP（Internet Message Access Protocol）。

超文本传输协议：HTTP（S）（Hyper Text Transfer Prtcl（over Securesocket ayer）），带 “S”的为增加了传输加密和身份认证。

以下都是与算法有关

20. 排序

对于排序，我们需要了解其一般时间复杂度，最坏情况时间复杂度，最好情况时间复杂度，空间复杂度和稳定性

X选择排序冒泡排序插入排序快速排序希尔排序堆排序归并排序基数排序

一般时间复杂度	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n log ⁡ n ) O(n\log n) O(nlogn)	O ( n 1.3 ) O(n^{1.3}) O(n1.3)	O ( n log ⁡ n ) O(n\log n) O(nlogn)	O ( n log ⁡ n ) O(n\log n) O(nlogn)	O ( n k ) O(nk) O(nk)
最坏情况时间复杂度	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n 2 ) O(n^2) O(n2)	O ( n 1.3 ) O(n^{1.3}) O(n1.3)	O ( n log ⁡ n ) O(n\log n) O(nlogn)	O ( n log ⁡ n ) O(n\log n) O(nlogn)	O ( n k ) O(nk) O(nk)
最好情况时间复杂度	O ( n 2 ) O(n^2) O(n2)	O ( n ) O(n) O(n)	O ( n ) O(n) O(n)	O ( n ) O(n) O(n)	O ( n 1.3 ) O(n^{1.3}) O(n1.3)	O ( n log ⁡ n ) O(n\log n) O(nlogn)	O ( n log ⁡ n ) O(n\log n) O(nlogn)	O ( n k ) O(nk) O(nk)
空间复杂度	O ( 1 ) O(1) O(1)	O ( 1 ) O(1) O(1)	O ( 1 ) O(1) O(1)	O ( n ) O(n) O(n)	O ( 1 ) O(1) O(1)	O ( 1 ) O(1) O(1)	O ( n ) O(n) O(n)	O ( n ) ? O(n)? O(n)?
稳定性	不稳定	稳定	稳定	不稳定	不稳定	不稳定	稳定	稳定

注：基数排序中的 k k k 表示所要排序的数列中最高位数

例题：

排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。

A. 冒泡排序

B. 直接插入排序

C. 快速排序

D. 归并排序

CSP 2019 提高级第一轮第 7 7 7 题

死记硬背的知识，选 C \mathtt{C} C

冒泡排序算法的伪代码如下：

输入：数组L, n ≥ k。输出：按非递减顺序排序的 L。

FLAG ← n //标记被交换的最后元素位置while FLAG > 1 do k ← FLAG -1 FLAG ← 1 for j=1 to k do if L(j) > L(j+1) then do L(j) ↔ L(j+1) FLAG ← j

对 n n n 个数用以上冒泡排序算法进行排序，最少需要比较多少次?（ ）。

A. n 2 n^2 n2

B. n − 2 n-2 n−2

C. n − 1 n-1 n−1

D. n n n

CSP 2020 入门级第一轮第 5 5 5 题

对于冒泡排序而言，在处理有序数列的时候时间复杂度最优，那么，在如上代码中，考虑代入有序数列，那么，我们在第一次完成循环for j=1 to k do时，由于不会进行交换，所以 FLAG 的值此时为 1 1 1 ，退出循环

而针对这样一个循环，我们可以将for j=1 to k do改写成for j=1 to n-1 do，所以，选 C \mathtt{C} C

21. 哈希

一般来讲，会有两种方式考察哈希：判断哈希地址和选择哈希函数

这种题直接模拟（两个小时随便嚯嚯）

例题：

现有一个地址区间为 0 ∼ 10 0\sim 10 0∼10 的哈希表，对于出现冲突情况，会往后找第一个空的地址存储 （到 10 10 10 冲突了就从 0 0 0 开始往后），现在要依次存储 ( 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 0,1,2,3,4,5,6,7 0,1,2,3,4,5,6,7)，哈希函数为 h ( x ) = x 2 m o d 11 h(x)=x^{2} \bmod {11} h(x)=x2mod11。请问 7 7 7 存储在哈希表哪个地址中（ ）。

A. 5

B. 6

C. 7

D. 8

CSP 2021 提高级第一轮第 6 6 6 题

直接模拟：

第一个数为 0 0 0 ，代入哈希函数中进行计算： h ( 0 ) = 0 2 m o d 11 = 0 h(0)=0^{2} \bmod {11}=0 h(0)=02mod11=0 ，此时 Hash [   0   ] \text{Hash}[\ 0\ ] Hash[ 0 ] 为空，存入

第二个数为 1 1 1 ，代入哈希函数中进行计算： h ( 1 ) = 1 2 m o d 11 = 1 h(1)=1^{2} \bmod {11}=1 h(1)=12mod11=1 ，此时 Hash [   1   ] \text{Hash}[\ 1\ ] Hash[ 1 ] 为空，存入

第三个数为 2 2 2 ，代入哈希函数中进行计算： h ( 0 ) = 2 2 m o d 11 = 4 h(0)=2^{2} \bmod {11}=4 h(0)=22mod11=4 ，此时 Hash [   4   ] \text{Hash}[\ 4\ ] Hash[ 4 ] 为空，存入

第四个数为 3 3 3 ，代入哈希函数中进行计算： h ( 3 ) = 3 2 m o d 11 = 9 h(3)=3^{2} \bmod {11}=9 h(3)=32mod11=9 ，此时 Hash [   9   ] \text{Hash}[\ 9\ ] Hash[ 9 ] 为空，存入

第五个数为 4 4 4 ，代入哈希函数中进行计算： h ( 4 ) = 4 2 m o d 11 = 5 h(4)=4^{2} \bmod {11}=5 h(4)=42mod11=5 ，此时 Hash [   5   ] \text{Hash}[\ 5\ ] Hash[ 5 ] 为空，存入

第六个数为 5 5 5 ，代入哈希函数中进行计算： h ( 5 ) = 5 2 m o d 11 = 3 h(5)=5^{2} \bmod {11}=3 h(5)=52mod11=3 ，此时 Hash [   3   ] \text{Hash}[\ 3\ ] Hash[ 3 ] 为空，存入

第七个数为 6 6 6 ，代入哈希函数中进行计算： h ( 6 ) = 6 2 m o d 11 = 3 h(6)=6^{2} \bmod {11}=3 h(6)=62mod11=3 ，此时 Hash [   3   ] \text{Hash}[\ 3\ ] Hash[ 3 ] 不为空，产生冲突，寻找第一个空的地址，为 6 6 6 ，存入

第八个数为 7 7 7 ，代入哈希函数中进行计算： h ( 7 ) = 7 2 m o d 11 = 5 h(7)=7^{2} \bmod {11}=5 h(7)=72mod11=5 ，此时 Hash [   5   ] \text{Hash}[\ 5\ ] Hash[ 5 ] 不为空，产生冲突，寻找第一个空的地址，为 7 7 7 ，存入

综上，元素 7 7 7 存入了 Hash [   7   ] \text{Hash}[\ 7\ ] Hash[ 7 ] 中，选 C \mathtt{C} C

将 ( 2 , 7 , 10 , 18 ) (2, 7, 10, 18) (2,7,10,18) 分别存储到某个地址区间为 0 ∼ 10 0\sim 10 0∼10 的哈希表中，如果哈希函数 h ( x ) = ( ) h(x)=() h(x)=() ，将不会产生冲突，其中 a m o d b a \bmod b amodb 表示 a a a 除以 b b b 的余数。

A. x 2 m o d 11 x^2 \bmod{11} x2mod11

B. 2 x m o d 11 2x \bmod{11} 2xmod11

C. x m o d 11 x \bmod{11} xmod11

D. ⌊ x 2 ⌋ m o d 11 \lfloor \dfrac{x}{2} \rfloor \bmod{11} ⌊2x​⌋mod11 ，其中 ⌊ x 2 ⌋ \lfloor \dfrac{x}{2} \rfloor ⌊2x​⌋ 表示 x 2 \dfrac{x}{2} 2x​ 下取整

CSP 2020 提高级第一轮第 5 5 5 题

直接模拟：

当选择 h ( x ) = x 2 m o d 11 h(x)=x^2 \bmod{11} h(x)=x2mod11

h ( 2 ) = 2 2 m o d 11 = 4   h ( 7 ) = 7 2 m o d 11 = 5   h ( 10 ) = 1 0 2 m o d 11 = 1   h ( 18 ) = 1 8 2 m o d 11 = 5 h(2)=2^2\bmod11=4\\\ \\h(7)=7^2\bmod11=5\\\ \\h(10)=10^2\bmod11=1\\\ \\h(18)=18^2\bmod11=5 h(2)=22mod11=4 h(7)=72mod11=5 h(10)=102mod11=1 h(18)=182mod11=5

产生冲突

当选择 h ( x ) = 2 x m o d 11 h(x)=2x \bmod{11} h(x)=2xmod11

h ( 2 ) = 2 × 2 m o d 11 = 4   h ( 7 ) = 7 × 2 m o d 11 = 3   h ( 10 ) = 10 × 2 m o d 11 = 9   h ( 18 ) = 18 × 2 m o d 11 = 3 h(2)=2\times2\bmod11=4\\\ \\h(7)=7\times2\bmod11=3\\\ \\h(10)=10\times2\bmod11=9\\\ \\h(18)=18\times2\bmod11=3 h(2)=2×2mod11=4 h(7)=7×2mod11=3 h(10)=10×2mod11=9 h(18)=18×2mod11=3

产生冲突

当选择 h ( x ) = x m o d 11 h(x)=x \bmod{11} h(x)=xmod11

h ( 2 ) = 2 m o d 11 = 2   h ( 7 ) = 7 m o d 11 = 7   h ( 10 ) = 10 m o d 11 = 10   h ( 18 ) = 18 m o d 11 = 7 h(2)=2\bmod11=2\\\ \\h(7)=7\bmod11=7\\\ \\h(10)=10\bmod11=10\\\ \\h(18)=18\bmod11=7 h(2)=2mod11=2 h(7)=7mod11=7 h(10)=10mod11=10 h(18)=18mod11=7

产生冲突

当选择 h ( x ) = ⌊ x 2 ⌋ m o d 11 h(x)=\lfloor \dfrac{x}{2} \rfloor \bmod{11} h(x)=⌊2x​⌋mod11

h ( 2 ) = ⌊ 2 2 ⌋ m o d 11 = 1   h ( 7 ) = ⌊ 7 2 ⌋ m o d 11 = 3   h ( 10 ) = ⌊ 10 2 ⌋ m o d 11 = 5   h ( 18 ) = ⌊ 18 2 ⌋ m o d 11 = 9 h(2)=\lfloor \dfrac{2}{2} \rfloor \bmod{11}=1\\\ \\h(7)=\lfloor \dfrac{7}{2} \rfloor \bmod{11}=3\\\ \\h(10)=\lfloor \dfrac{10}{2} \rfloor \bmod{11}=5\\\ \\h(18)=\lfloor \dfrac{18}{2} \rfloor \bmod{11}=9 h(2)=⌊22​⌋mod11=1 h(7)=⌊27​⌋mod11=3 h(10)=⌊210​⌋mod11=5 h(18)=⌊218​⌋mod11=9

未产生冲突

综上，选 D \mathtt{D} D

22. 递归

最恶心的，没有之一

有些题只能模拟，别无他法（注意使用记忆化！）

但是有些题，我们需要转化一下，以简化问题

例题：

有如下递归代码

solve(t, n):if t=1 return 1 else return 5*solve(t-1,n) mod n

则 solve ( 23 , 23 ) \text{solve}(23,23) solve(23,23)的结果为（ ）。

A. 1

B. 7

C. 12

D. 22

CSP 2021 提高级第一轮第 11 11 11 题

这道题不需要直接模拟

观察这一段伪代码：

else return 5*solve(t-1,n) mod n

当我们完成当前递归之前的所有递归时，我们需要将结果经进行 × 5   %   23 \times5\ \%\ 23 ×5 % 23 的操作（由于 n n n 是不变的，现视为常量）

而对于当前递归的上一层递归而言，当我们完成当前递归之前的所有递归时，我们还是需要将结果经进行 × 5   %   23 \times5\ \%\ 23 ×5 % 23 的操作

所以，其结果相当于若干个 5 5 5 相乘在取模 23 23 23

那么，是几个 5 5 5 呢？

考虑整个递归，在 n ≠ 1 n\ne1 n=1的情况下，都会有 × 5 \times5 ×5 的操作

所以，会有 n − 1 n-1 n−1 次乘法操作（只有最后一次没有），在这里， n = 23 n=23 n=23 ，所以有 22 22 22 次乘法操作

因此，现在只需求表达式 5 22 m o d 23 5^{22}\bmod23 522mod23 即可

5 22 m o d 23 = 2 5 11 m o d 23 = 2 11 m o d 23 = 16 × 2 × 16 × 2 × 8 ÷ 2 ÷ 2 m o d 23 = 32 × 32 × 2 m o d 23 = 9 × 9 × 2 m o d 23 = 162 m o d 23 = 1 \begin{aligned}5^{22}\bmod23&=25^{11}\bmod23\\&=2^{11}\bmod23\\&=16\times2\times16\times2\times8\div2\div2\bmod23\\&=32\times32\times2\bmod23\\&=9\times9\times2\bmod23\\&=162\bmod23\\&=1\end{aligned} 522mod23​=2511mod23=211mod23=16×2×16×2×8÷2÷2mod23=32×32×2mod23=9×9×2mod23=162mod23=1​

综上，选 A \mathtt{A} A

考虑如下递归算法

solve(n) if n<=1 return 1 else if n>=5 return n*solve(n-2) else return n*solve(n-1)

则调用 solve ( 7 ) \text{solve}(7) solve(7) 得到的返回结果为（ ）。

A. 105

B. 840

C. 210

D. 420

CSP 2021 入门级第一轮第 13 13 13 题

这个不难，照着代码模拟即可

solve ( 7 ) = 7 × solve ( 5 ) = 7 × 5 × solve ( 3 ) = 35 × 3 × solve ( 2 ) = 105 × 2 × solve ( 1 ) = 210 \begin{aligned}\text{solve}(7)&=7\times\text{solve}(5)\\&=7\times5\times\text{solve}(3)\\&=35\times3\times\text{solve}(2)\\&=105\times2\times\text{solve}(1)\\&=210\end{aligned} solve(7)​=7×solve(5)=7×5×solve(3)=35×3×solve(2)=105×2×solve(1)=210​

选 C \mathtt{C} C

设 A A A 是 n n n 个实数的数组，考虑下面的递归算法：

XYZ (A[1..n])if n=1 then return A[1]else temp ← XYZ (A[1..n-1])if temp < A[n]then return tempelse return A[n]

请问算法 XYZ 的输出是什么？（）

A. A 数组的平均值

B. A 数组的最小值

C. A 数组的中值

D. A 数组的最大值

CSP 2020 入门级第一轮第 6 6 6 题

首先，我们可以精简一下代码：

XYZ (A[1..n])if n=1 then return A[1]else temp ← XYZ (A[1..n-1])return min(temp,A[n])

考虑从简单入手，即先处理 n ≤ 3 n\le3 n≤3 的情况

当 n = 1 n=1 n=1 时，返回 A [   1   ] A[\ 1\ ] A[ 1 ]

当 n = 2 n=2 n=2 时， temp = XYZ ( A [   1   ] ) \text{temp}=\text{XYZ}(A[\ 1\ ]) temp=XYZ(A[ 1 ]) ，即 temp = A [   1   ] \text{temp}=A[\ 1\ ] temp=A[ 1 ] ，然后，返回 min ⁡ ( temp , A [   2   ] ) \min(\text{temp},A[\ 2\ ]) min(temp,A[ 2 ]) ，即 min ⁡ { A [   i   ] } ( i ∈ { 1 , 2 } ) \min\{A[\ i\ ]\}(i\in\{1,2\}) min{A[ i ]}(i∈{1,2})

当 n = 3 n=3 n=3 时， temp = XYZ ( A [   2   ] ) \text{temp}=\text{XYZ}(A[\ 2\ ]) temp=XYZ(A[ 2 ]) ，即 temp = min ⁡ { A [   i   ] } ( i ∈ { 1 , 2 } ) \text{temp}=\min\{A[\ i\ ]\}(i\in\{1,2\}) temp=min{A[ i ]}(i∈{1,2}) ，然后，返回 min ⁡ ( temp , A [   3   ] ) \min(\text{temp},A[\ 3\ ]) min(temp,A[ 3 ]) ，即 min ⁡ { A [   i   ] } ( i ∈ { 1 , 2 , 3 } ) \min\{A[\ i\ ]\}(i\in\{1,2,3\}) min{A[ i ]}(i∈{1,2,3})

综上可得， XYZ \text{XYZ} XYZ 所求为 A \text{A} A 数组的最小值，选 B \mathtt{B} B

23. 贪心

说到贪心，就不得不提及一个算法：霍夫曼编码

虽然我不知道啥是霍夫曼编码，但是只需要知道霍夫曼编码的本质是贪心即可

例题：

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。

A. 枚举

B. 贪心

C. 递归

D. 动态规划

CSP 2021 入门级第一轮第 11 11 11 题

死记硬背的知识，选 B \mathtt{B} B

以下哪些算法不属于贪心算法？（）

A. Dijkstra 算法

B. Floyd 算法

C. Prim 算法

D. Kruskal 算法

CSP 2019 提高级第一轮第 13 13 13 题

选项 A \mathtt{A} A ：每一次选取当前已知的点中最短路最短的点进行松弛，是贪心

选项 B \mathtt{B} B ：通过对某一点的经过与否的讨论进行松弛，是DP

选项 C \mathtt{C} C ：与 Dijkstra 算法类似，是贪心

选项 D \mathtt{D} D ：每一次选取不会形成环的最短边，是贪心

选 C \mathtt{C} C

下列哪些问题不能用贪心法精确求解？（ ）

A. 霍夫曼编码问题

B. 0-1 背包问题

C. 最小生成树问题

D. 单源最短路径问题

CSP 2020 提高级第一轮第 6 6 6 题

选项 A \mathtt{A} A ：死记硬背的知识，可用贪心

选项 B \mathtt{B} B ：通过对某一物品的选与不选的讨论进行求解，不可用贪心

选项 C \mathtt{C} C ：可用贪心（Kruskal）

选项 D \mathtt{D} D ：可用贪心（Dijkstra）

选 B \mathtt{B} B

24. 图论

图论基本上已经讲完，剩下的知识一点简单东西

直接看例题：

有如下的有向图，节点为 A , B , ⋯ , J A ,B , \cdots , J A,B,⋯,J 其中每条边的长度都标在图中。则节点 A A A 到节点 J J J 的最短路径长度为（ ）。

A. 16

B. 19

C. 20

D. 22

CSP 2021 提高级第一轮第 15 15 15 题

直接模拟最短算法即可（下图中结点数值表示该点到 A A A 点的最短路）

第一次松弛后：

第二次松弛后：

第三次松弛后，图没有改变

第四次松弛后：

第五次松弛后：

第六次松弛后：

第七次松弛后：

第八次松弛后：

第九次和第十次松弛后，图没有改变

综上，选 B \mathtt{B} B

对一个 n n n 个顶点， m m m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。

A. O ( ( m + n 2 ) log ⁡ n ) O((m + n^2) \log n) O((m+n2)logn)

B. O ( m n + n 3 ) O(mn + n^3) O(mn+n3)

C. O ( ( m + n ) log ⁡ n ) O((m + n) \log n) O((m+n)logn)

D. O ( n 2 ) O(n^2) O(n2)

CSP 2020 提高级第一轮第 14 14 14 题

众所周知，没有优化的 Dijkstra 算法最外层有一个 O ( n ) O(n) O(n) 的循环，表示至少进行 n n n 次操作，在循环里面，还有两个 O ( n ) O(n) O(n) 的循环，分别用来寻找当前已知的点中最短路最短的点以及松弛操作，怼一起，时间复杂度为 O ( n 2 ) O(n^2) O(n2) ，选 D \mathtt{D} D

以下哪个结构可以用来存储图（）

A. 栈

B. 二叉树

C. 队列

D. 邻接矩阵

CSP 2019 提高级第一轮第 12 12 12 题

死记硬背的知识，选 D \mathtt{D} D

以 a a a 为起点，对下边的无向图进行深度优先遍历，则 b , c , d , e b,c,d,e b,c,d,e 四个点中有可能作为最后一个遍历到的点的个数为（ ）。

A. 1

B. 2

C. 3

D. 4

CSP 2021 入门级第一轮第 14 14 14 题

以 a a a 为起点，接下来，可以去 b b b ，也可以去 c c c

如果去 b b b ，那么只要一种遍历情况

如果去 c c c ，那么到达 c c c 时，可以去 d d d ，也可以去 e e e

分别将两种情况讨论一下

综上，只有 b , e b,e b,e 两点可能为最后一个遍历到的点，故选 B \mathtt{B} B

写到这里就差不多了，有机会（指可以尽快完成暑假作业）看再写点什么