CSP-J/S 初赛总复习

xueruo · 2023-08-12 20:18:39 · 个人记录

如果有遗漏、错误或者补充，请在评论区友好地说出来

计算机常识

以下的人名不同译版不同正常，发音差不多就彳亍了。

阿达 \cdot 洛芙莱斯发明了循环和子程序，是第一个给计算机写程序的人。
约翰 \cdot 麦卡锡是人工智能之父。
菲尔兹要求设立的国际性数学奖项（数学界的诺贝尔奖）。
冯 \cdot 诺依曼创立了存储的思想。
克劳德 \cdot 香农将热力学中的熵引入信息通信领域，是信息论的创始人。
查尔斯 \cdot 巴比奇发明了分析机。
戈登 \cdot 摩尔是英特尔公司的创始人，提出了摩尔定理。
图灵机是虚拟机器人替人们进行数学运算的一个模型。发明图灵机的英国的图灵本人在二战中破译了德军的密码系统。
计算机最早用于数据计算，第一代用于军事的计算弹道和射程。
图灵奖是计算机界最高奖项。（我国姚期智是 2000 年图灵奖的获得者）
ENIAC 是世界上第一台计算机，美国的。
计算机芯片的原材料是硅。
因特网始于 1969 年的美国阿帕网。
计算机发展特点是友善的人机交互、智能数据推理、分布式信息管理。
不同位机器觉得寻址空间不同。
总线分为数据总线、地址总线和控制总线。
寄存器（register）是 CPU 的重要组成部分。
CPU 由控制器和运算器组成。

CPU------------>储存器

BIOS 是标准输入输出，是在 ROM 上的程序。跟踪指令地址寄存器是 PC（程序计数器）。存储器的发明是为了解决价格（钱）、价值（有用）、速度（快）的矛盾。 CPU 通过总线控制到每个___器。空间换算： $1\hspace{0.1cm}\text{byte(B)}$(最基本单位)$=8\hspace{0.1cm}\text{bit}$(最小单位) $1\hspace{0.1cm}\text{KB}=1024(2^{10})\hspace{0.1cm}\text{B}

1\hspace{0.1cm}\text{MB}=1024\hspace{0.1cm}\text{KB}

1\hspace{0.1cm}\text{GB}=1024\hspace{0.1cm}\text{MB}

1\hspace{0.1cm}\text{TB}=1024\hspace{0.1cm}\text{GB}

1\hspace{0.1cm}\text{PB}=1024\hspace{0.1cm}\text{TB}

1\hspace{0.1cm}\text{EB}=1024\hspace{0.1cm}\text{PB}

1\hspace{0.1cm}\text{ZB}=1024\hspace{0.1cm}\text{EB}

1\hspace{0.1cm}\text{YB}=1024\hspace{0.1cm}\text{ZB}

1\hspace{0.1cm}\text{BB}=1024\hspace{0.1cm}\text{YB}

1\hspace{0.1cm}\text{NB}=1024\hspace{0.1cm}\text{BB}

1\hspace{0.1cm}\text{DB}=1024\hspace{0.1cm}\text{NB}

1\hspace{0.1cm}\text{CB}=1024\hspace{0.1cm}\text{DB}

1\hspace{0.1cm}\text{XB}=1024\hspace{0.1cm}\text{CB}

\cdots

2^{10}\text{ 有时候用 }1000\text{ 去计算。}

金山软件公司开发了 WPS。
Microsoft (微软)开发了 Powerpoint、Word、Excel等软件。
Adode 公司开发了 PDF 阅读程序、Photoshop(.psd)。
操作系统(Windows,Dos,Linux,IOS)的作用都是控制、管理资源，对文件进行管理。
即时通信软件有 QQ,MSN,微信(Wechat)等。
P2P 是对等的应用架构网络形式，一般用于小型贷款交易和诈骗。
复制是保留原品弄一份新的到剪贴板，剪切是不保留原品直接弄到剪贴板。
系统软件-->操作系统，系统APP等。
应用软件-->用户自己下载的。
无论怎样，没被永久删除的文件，都是被标记为删除，均可找回。
Linux 没有拓展名。
Linux 的一些命令：ls 列出目录，cd 切换目录，cp 复制文件/目录，rm 删除文件/目录，find 查找，ping 网络通不通。
CPU 同一时刻最多只能处理 1 个命令。
图像储存空间=图像分辨率（通常是两个数相乘）\times 位数 \div 8（这里的 8 是指一个字节有 8 个位）视频就每一帧的图片\times 帧率 \times 时间（秒）。
位图由像素组成，容易失真。常用格式:jpg/jpeg、gif、png、bmp、psd 格式。
矢量图用点、直线等几何图形，不失真，颜色单一。常用格式: cdr、ai、swf、svg 格式。
txt 是文本文件格式，gif 是动图，photoshop 的 psd 是有图层信息的图像格式。
ASCII 码是美国信息交换标准代码([1,127])，占 1 字节。
拓展的 ASCII 码占 2 字节。
一个汉字要用 32\times32 个位的存储空间。
声音容量=采样频率\times采样位数\times声道\times时间\div 8。
LAN(局域网，烂),MAN(城域网,慢),WAN(广域网,万)。

E-mail(电子邮件)中:

SMTP 发邮件。
POP3 收邮件。

IMAP 是邮件客户端。
WTO 是世界贸易组织。
FTP 是文件传输协议，UDP 是无连接传输层。

OSI 开放式体系结构：
应用层
表示层
会话层
传输层（TCP、UDP）
网络层（IP）
数据链路层
物理层

IPv6（8位）是IPv4（4位）的升级。
域名通过 DNS（域名服务器）可以唯一对应 IP。
html 是超文本文件，用浏览器可以打开。
ARP 是 MAC(地址、IP) 与物理层的转换。

网络类型：

在试卷上：∧ 就是与操作，∨就是或操作，￢就是非操作。（很容易记混与和或）

各个数据类型对应的字节：
bool 1B
char 1B
short 2B
int 4B(\thickapprox 10^9)
long 4B
float 4B
long long 8B(\thickapprox 10^{18})
double 8B
int/int=int
int/double=double/double=double

算法和数据结构

进制转换：
这里给一个进制转换的网址，可以自己用来练习之后对答案。https://c.runoob.com/front-end/58/

(87)_{10}=(101011)_{2}=(127)_{8}=(57)_{16}

十转二见下图。
然后二进制转其他进制。
转成八进制，3 位写一个 ,位数不够补 0，然后查表。
转成十六进制，4 位写一个 ,位数不够补 0，然后查表。
以上面的为例子，(1,010,111)_{2}=(127)_{8}，(0101,0111)_{2}=(57)_{16}。
小数的见下图。

二进制数表示方式：
原码写的时候有时不会带符号位，符号位是 0 为正，否则为负。
正的原码=反码=补码。
负的原码变成反码除了符号位区反，再变成补码 +1。

递归函数自身的技巧成为递归，递归调用过多会造成栈空间溢出。
枚举法利用了计算机速度较快，精确度高，牺牲时间。
每次选最优，找到局部最优解并合并成全局最优解的算法叫贪心。
分治把大问题分解成小问题。
二分查找时间复杂度为：\Theta(\lceil\log_2n\rceil)。

三种语言：

面向对象程序设计语言有：Java、C++、C#、Python。
面向过程程序设计语言有：C、Pascal、Basic、Fortran。
汇编语言。

编译器是一种语言（通常是高级）翻译成另一种语言（通常是低级）的东西。
算法是解决问题的操作步骤，在有限的时间内，有 0 个或多个输入，有 1 个或多个输出，有限次执行，不允许有歧义。
欧几里得算法：\gcd(a,b)=\gcd(b,a\bmod b)。
桶排序、冒泡排序、std 排序、插入排序、归并排序、基数排序（不需要关键字比较）稳定。
选择排序、快速排序（数组有序时退化成 \Theta(n^2)）、希尔排序、堆排序不稳定。
搜索有深度优先搜索、广度优先搜索等。
空间复杂度是对内存空间的限制（大小一般固定）。
顺序连续的存储结构是数组，增删慢，查找快。
顺序不连续（随机）的存储结构是链表，增删快，查找慢。
高级语言程序相对于低级语言可移植性好（可以在另一个电脑运行）
不需要编译就能显现的语言：Python。
判断闰年：year%4==0&year%100!=0 || year%400=0。
位运算
线性结构：一对一；树形结构：一对多；图形结构：多对多的层次关系。
关系数据库：一对一。
数据结构：将数据存储到计算机 \not= 算法。
栈：先进后出；队列：先进先出。（进出时都要判空/满）

后缀表达式：

(1+1)/2 &=(11+)/2 \\ &=(11+2/)\\ \end{aligned}

按照正常的运算先后顺序（可以适当增添括号），把这一步的符号移到这个整体的后面。

前缀表达式（运算）：
从后往前，遇到数字就压到栈里面，遇到运算符去出栈顶两个，然后运算后再放入。

先序遍历、中序遍历、后序遍历指的是“根”遍历的顺序。
欧拉路存在要保证图联通且有两个或者零个奇点（有奇数条边连着的点），其实他就是一笔画问题。欧拉回路要保证有 0 个奇点，那么走的时候能回到起点。（两种都是从奇点出发）

拓扑排序是对于有向无环图(`AOV`)中的一个序列，不唯一。伪代码： ```cpp while(有入度为0的节点){//一般用队列实现 //对于这个操作，可能是输出，也可能是更新答案删除与它相连的所有边；//一般的实现方法是将相连的点的入度自减1 } ``` 二分图 $G$ 可划分为两个子集 $X,Y$，分别有 $m,n$ 个节点，集合之间没有边，集合互相有边，只存在长度为偶数的环。哈夫曼编码用了贪心的思想，每次将出现频率最少的两个数相加变为一个心的数放到序列里面，直到合并到 $100\%$。左子树标上 $1$，否则标上 $0$。节点的编码长度最短为祖宗数量加上自己的 $1$。 + 排列组合 ~~数量少的时候可以直接枚举，多的时候估计范围。如果弄出来的答案与不只一个的选项相近就只能听天由命了。~~ 排列：$A_n^m=\large\frac{n!}{(n-m)!}

组合：C_n^m=\large\frac{n!}{m!(n-m)!}=\large\frac{A_n^m}{m!}
排列是 n 个里面选 m 个（考虑顺序），组合是 n 个里面选 m 个（不考虑顺序）。
加法原理：多种类问题，N=\displaystyle\sum_{i=1}^n m_i。
乘法原理：多步骤问题，N=\displaystyle\prod_{i=1}^n m_i。