CSP初赛复习

计算机的基础知识

计算机的发展

第一台电子计算机：ENIAC。

第一台具有存储功能的计算机：EDVAC。

计算机发展史上的杰出人物

• 冯·诺伊曼：存储结构、冯·诺伊曼架构
• 艾伦·图灵：图灵测试、图灵机。
• 克劳德·香农：信息论。
• 马文·明斯基、约翰·麦卡锡：对人工智能的杰出贡献。
• 阿达·洛芙莱斯：计算机程序的创始人。

计算机相关奖项

图灵奖

计算机界的最高奖项。

由美国计算机协会 ACM 于 1966 年设立。

唯一一位华人获奖者：姚期智院士。

其他奖项

计算机先驱奖、高德纳奖、冯·诺依曼奖、CCF 终身成就奖、王选奖。

计算机基本架构

采用二进制处理。冯·诺伊曼架构：

• 控制器：进行进行系统的调度、控制和协调；

• 运算器：对数据进行运算、加工、处理；

• 存储器：存储数据和信号

  • 寄存器：CPU 内部的存储器，空间很小，断电后内容会消失。

  • Cache：高速缓存，分为 $\rm L_1,L_2,L_3,L_4$，断电后内容会消失。

  • 内存储器（内存）：

    • $\rm ROM$：只读存储器，断电后内容不会消失；
    • $\rm RAM$：随机读取存储器，断电后内容会消失。

  • 外存储器（外存）：光盘、U 盘、显存等。

• 输入设备：从外部将数据输入到计算机内。

• 输出设备：将计算机内的数据输出到外部。

占用存储空间大小的计算题

$1\,\rm Tib=2^{10}\,\rm Gib=2^{20}\,\rm MiB=2^{30}\,\rm KiB=2^{40}\,\rm Byte=2^{43}\,\rm Bit$。

$1\,\rm Mbps=10^3\,\rm Kbps=10^6\,\rm bps$。

• 计算图片存储空间：分辨率 $\times$ 位深度（单位：比特）。
• 计算视频存储空间
  • 给定分辨率、帧率和时长：单张图大小 $\times$ 帧率 $\times$ 时长（单位：$\rm Bit$）
  • 给定视频的码率：$($视频码率 $+$ 音频码率$)\times$ 时长（单位根据码率单位而定）

编程语言

编程语言的发展历史

高级语言的分类

面向过程/面向对象

• 面向过程：以函数为基本程序结构。如 $\text{C, Pascal, Fortran}$。
• 面向对象：以类为基本程序结构。如 $\text{C++, Java, Python}$。

编译型语言/解释型语言

• 编译型语言：执行程序前用链接器生成可执行文件，运行效率较高。如 $\rm C++, Delphi$。
• 解释型语言：一边由翻译器翻译，一边运行代码，运行效率较低，但是跨平台性好。如 $\rm Python, Java, Ruby$。

信息学竞赛的发展

第一届 $\rm NOI$（全国青少年信息学奥林匹克竞赛）：1984 年。

主办方：中国计算机学会（CCF）。

第一届 $\rm IOI$：1989 年。

2000 年，我国举办了第 $12$ 届 $\rm IOI$。

第一届 $\rm NOIP$（全国青少年信息学奥林匹克联赛）：1995 年。

2019 年暂停一届。

第一届 $\rm CSP-J/S$：2019 年。

是参加 $\rm NOIP$ 的先决条件。

计算机网络知识

OSI 七层模型:

• HTTP：超文本传输协议

• FTP：文件传输协议

• SMTP：收、发电子邮件

• POP3：接受电子邮件

IPv4 地址的点分十进制表示：四个 $[0,255]$ 之间的正整数，中间 用 . 相连，如 $114.51.4.19$。

分类方式：

• A 类地址：$1.0.0.1\sim127.255.255.254$
• B 类地址：$128.0.0.1\sim191.255.255.254$
• C 类地址：$192.0.0.1\sim223.255.255.254$

IPv6 的地址的冒分十六进制表示：八个 $[0000, \rm FFFF]$ 的正整数， 中间用冒号相连。如 $\rm ABCD:EF01:2345:6789:ABCD:EF01:2345:6789$

基础算法

线性数据结构

链表

特点：插入与删除十分方便，但是寻找与读取的表现欠佳。

与数组的区别：链表是链状结构，而数组将所有元素按次序依次存储。

• 链表
  • 删除、插入数据的时间复杂度为 $O(1)$。
  • 寻找、读取数据的时间复杂度为 $O(n)$。
• 数组
  • 删除、插入数据的时间复杂度为 $O(n)$。
  • 寻找、读取数据的时间复杂度为 $O(1)$。

其空间复杂度为 $O(n)$。

可以动态扩展。

队列、栈

如何用栈实现队列？

这种方法使用两个栈 $F,S$ 模拟一个队列。其中 $F$ 是队尾的栈，$S$ 是队首的栈。

• push（在队尾插入）：插入到栈 $F$ 中。
• pop（在队首弹出）：
  • $S$ 非空：让 $S$ 弹栈；
  • $S$ 为空：把 $F$ 的元素倒过来压到 $S$ 中（一个一个从 $F$ 弹出后插入到 $S$ 中，做完后守卫颠倒），然后让 $S$ 弹栈。

容易证明，每个元素只会 进入/转移/弹出 一次，均摊时间复杂度为 $O(1)$。

递推、递归

递归，是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。

递归的基本思想是某个函数直接或间接地调用自身。

在程序执行中，递归是利用系统栈实现的。

递推算法通常是计算前面的一些项得到序列中指定项的值。

从已知的规律一步步推向未知的信息。

需要找到递推式。

简单图论

图的基本概念

图是由若干点以及链接点与点的边构成的。

点集 $V$ 与边集 $E$ 构成图 $G=(V,E)$。

• 无向边、有向边：边 $e=(u,v)\in E$ 是否区分先后顺序（$u\to v$）。

• 无向图/有向图/混合图：仅含无向边/有向边的图叫做无向图/有向图，二者均有的图叫做混合图。

• 带权图/正（负）权图：图中每条边 $e$ 都有一个权值 $w$，$e=(u,v,w)$。如果所有边的权值 $w$ 都是正（负）实数，称图为正（负）权图。

• 度

  • 度数（无向图）：与一个顶点 $u$ 直接连接的边的条数佳作顶点的度数 $d(u)$。
  • 入度/出度（有向图）：以一个顶点 $u$ 为起点/终点的边的条数称为该点的出度 $d^{+}(u)$/入度 $d^{-}(u)$。

• 自环：对于边 $e=(u,v)\in E$，若 $u=v$，称 $e$ 为一个自环。

• 重边：若 $e_1,e_2\in E$ 且 $e_1=e_2$，则称它们为一组重边。

• 简单图：没有重边和自环的图。

• 连通：

  • 无向图中，任意两点间村子啊一条路径，则称图是连通的；
  • 有向图中，任意两点 $u,v\in V$ 间存在两条路径使得 $u,v$ 可以互相到达，则称为强连通。将有向边换成无向边可以连通称为弱连通。
  • 无向连通图至少有 $n-1$ 条边，有向强连通图至少有 $n$ 条边（$n$ 为点数）。

• 稠密图/稀疏图：一张图的边数节点点数的平方，称为稠密图；一张图的边数远小于点数的平方，称为稀疏图。二者没有严格的定义。

• 完全图：

  • 无向图中，任意不同两点之间均有无向边；
  • 有向图中，任意不同两点间均有两条方向不同的边。

图的存储

需要掌握两类图存储方式：邻接矩阵、邻接表。

• 邻接矩阵

  使用二维数组 e 存边，e[u][v]=1 代表 $u,v$ 之间有连边，e[u][v]=0 代表没有。如果是带边权的图，$1$ 可以替换为边权。优势是可以 $O(1)$ 查询某条边是否存在；劣势是在稀疏图上效率很低，所以一般只会在稠密图上使用邻接矩阵。对于 $n$ 个顶点 $m$ 条边的图，空间复杂度为 $O(n^2)$。

• 邻接表

简单树

树的定义与表示

一个没有固定根节点的树成为无根树。无根树指定一个节点为根，即为有根树。

• 性质：
  • 边数 = 点数 - 1；
  • 无向无环的连通图，在任意不同两点间添加一条边后所得图有且仅有一个环；
  • 任意两个节点之间有且仅有唯一一条简单路径。
• 父亲：除

链

满足与任一节点相连的边不超过

菊花

满足存在结点 $u$ 使所有除 $u$ 外的结点均与 $u$ 相连的树。

二叉树：

定义：每个结点最多只有两个儿子的有根树。

完全二叉树

只有最下面两层节点度数可以小于 $2$，且最下面一层节点都集中在该层最左边的连续位置上。

• 除最后一层以外第 $i$ 层节点数量：$2^{i-1}$；
• 具有 $n$ 个节点的完全二叉树的深度：$k=\lfloor\log_2 n\rfloor+1$；
• 最后一层节点数 $n-2^{k-1}+1$。
• 数组表示：根节点为 $1$，接下来每层从左至右依次标号。
• 标号特征：对于某标号为 $u$ 的节点。
  • 左子节点：$u\times2$；
  • 右子节点：$u\times2+1$；
  • 父节点：$\Big\lfloor\dfrac{u}{2}\Big\rfloor$；
  • 兄弟节点：$\begin{cases}i-1&i\,|\,2\\i+1&\operatorname{otherwise}\end{cases}$ 。

满二叉树

每个节点的子节点树均为 $0$ 或 $2$。

完美二叉树

所有叶结点的深度都相同的二叉树。

属于完全二叉树。

遍历

• 前序遍历：根左右；
• 中序遍历：左根右；
• 后序遍历：左右根。

序列反推

已知中序遍历序列和另外一个序列可以求第三个序列。

Huffman 树

Huffman 算法

1. 初始化：

二叉搜索树

搜索

进制与位运算