初赛知识点梳理
计算机基础知识
发展阶段
- 1946 - 1958 真空电子管 军事,科学(1946 年,世界上第一台电子计算机 ENIAC 在美国宾夕法尼亚大学诞生。
- 1959 - 1964 晶体管 数据,食物。
- 1965 - 1970 集成电路 工业控制。
- 1971 - 至今 大规模,超大规模集成电路 各个领域。
- 现代 智能计算机系统 人工智能。
计算机界重要人物
- 冯·诺伊曼(美):“计算机之父”。提出计算机体系结构,计算机硬件设备由存储器,运算器,控制器,输入设备和输出设备,并且由总线连接。总线按照传输数据类型包括数据总线,数据总线,控制总线。冯诺依曼的存储程序思想:把计算过程描述为由许多命令按一定顺序组成的程序,然后把程序和数据一起输入计算机,计算对已存入的程序和数据处理后,输出结果。
- 图灵(英):”人工智能之父”。提出图灵实验,一种判定机器是否具有智能的实验方法。提出图灵机模型为现代计算机奠定基础。
- 克劳德·香农(美):创造信息论,提出了某种信息从一处传送到另一处所需的全部设备所构成的系统。
分类
- 按规模:巨型,大型,中型,小型,微型计算机(学校,家庭使用的都是微型计算机,简称微机,个人计算机胡哦 PC 机)。
- 按用途:专业,通用计算机。
- 按原理:模拟(发送端通过调制将数字信号转化为模拟信号,而且接收端通过解调将模拟信号转化为数字信号),数字计算机。
- 按功能:单媒体(只能处理数字和文字),多媒体(还可以处理图像,文本,音频,视频等)。
特征
- 运算能力快。
- 计算精度高。
- 存储能力强。
- 逻辑运算能力强。
- 自动控制能力强。
计算机语言
- 机器语言/机器码:最早的语言,计算机能识别的语言,有二进制 0/1 组成,速度快,人类编码难度高,一般由计算机自动转换。
- 汇编语言:用符号代替二进制,计算机不能直接识别,需要用编译器进行编译,编码难度依然很大,目前除了对性能要求极高的需求以外不被使用。
- 高级语言:如今流行编程语言(C++,JAVA 等),需要编译器小,难度小,分为编译方式和解释方式两种方式:
- 编译方式(C++):先对整个程序进行编译(会进行多次分析),再执行程序,速度快(进行多次编译堆程序进行优化)。
- 解释方式(Python/PHP):扫描一行解释一行,速度慢(无法进行优化)。
空间运算
1 B(Byte/字节) = 8 bit(比特)
1 TiB = 1024 GiB, 1 GiB = 1024 MiB, 1 MiB = 1024 KiB, 1KiB = 1024 B
1 TB = 1000 GB, 1 GB = 1000 MB, 1 MB = 1000 KB, 1 KB = 1000 B
iB 结尾的是 1024 单位换算,B 结尾是 1000 单位换算。(例如买 512 GB 硬盘用的时候不到 500 GiB 的原因(单位不同))
ASCII 码是有 8 bit 组成的二进制编码(1 B),一个汉字在计算机中占 2 B。
在不压缩情况下,非黑即白的二值图像,一个像素 1 bit;256 种状态的灰度图像,一个像素 8 bit(1 B);256 种状态,屏幕采用 RGB 三基色,一个像素 24 bit(3 B),也就是常说的 24 位真彩色。还有各种其他的储存方式:15 bit,16 bit,32 bit等。如果考虑压缩,区别是有损压缩还是无损压缩,具体采用那种压缩算法,会影响到一个像素占用的储存空间。
机器数和真值
- 原码:将一个整数表示成符号位 + 真值。$0$ 有两种:$+0$ 或 $-0$,$+0 = [0000\,0000]_{原}, -0= [1000\,0000]_{原}$。
- 反码:对于一个正数,反码就是其原码;对于一个负数,除符号位外,原码的各位全部取反。$0$ 仍然有两种表示:$+0 = [0000\,0000]_{反}, -0 = [1111\,1111]_{反}$。
- 补码:对于一个正数,补码就是其原码;对于一个负数,补码等于原码 $+1$,这样 $0$ 用 $[0000\,0000]_{补}$ 表示,$-0$ 不存在。实际上是,$-0$ 的补码用来表示 $-128$,这样负数又可以多表示出来一位,$[1000\,0000]_{补} = -128$,但是原码和反码不存在 $-128$,将其转换成原码或补码是不正确的。机器使用补码。
上面讨论时 8 位整数(1 bit),使用原码或反码表示范围 $[-127,+127]$,而使用补码表示范围 $[-128, +127]$。对于编程常用的 32 位 int 类型整数(4 bit),使用原码或反码表示范围 $[-(2^{31} - 1),2 ^ {31} - 1]$,而使用补码表示范围 $[-2^{31}, 2 ^ {31} - 1]$。
信息编码表示
- ASCII 码:每个字符占七位的二进制位(单位 bit),能表示 $2^{7} = 128$ 种西文字符,包括大小,字母,0-9,控制符(如回车,空格),通用符(如 +,=)等字符。基本的 ASCII 码:存储时占 1 个字节,最高位为 0,其范围是 0-127;扩展的 ASCII 码:存储时占 1 个字节,最高位为 1,其范围是 128-255;外码:计算机与人进行交换的字形符号,如字符 ”A“ 的外码 ”A“;内码:计算机内部存储和使用的数字代码,如字符 ”A“ 的内码 65。
- GB 码:即国标码,是汉字交换码,采用两个字节对每个汉字进行编码,每个字节各取 7 位,可对 $2^7 \times 2^{7} = 16384$ 个字符进行编码。常见的 GB2312-80 按使用频度将汉字分为一级汉字和二级汉字,其中一级汉字按拼音排序,二级汉字按部首排序。国标码先把汉字排列在一个 $94 \times 94$ 的方阵,由此引进两种编码方式,一种为区位码,一种国标码。区位码是十进制数表示,国标码是十六进制数表示。其换方式:区码和位码分别加上十进制数 32。如 “国” 字在表中 25 行 90 列,区位码 2590,国标码 3970AH。
- 字形码:提供计算机输出汉字(显示或打印)用的二进制信息,也称子模。通常采用数字化点阵字模。一个 $16 \times 16$ 点阵的汉字共需要 32 个字节。
- Unicode(统一码,万国码,通用码)为每种语言中的每个字符设定了统一并且唯一的二进制编码,UTF-8 和 UTF-16 是两种当前比较流行的 Unicode 编码方式,UTF-8 是目前互联网上使用最广泛的一种 Unicode 编码方式。
- 半角字符占一个字节,全角字符占两个字节。
网络体系结构
ISO 制定了一个国际标准 OSI(开放式通信系统互联参考模型),并作为一种理论下的模型。TCP/IP 被广泛使用,成为网络互联事实上的标准。
程序设计基础知识
排序基本算法:冒泡排序,插入排序,归并排序,桶排序,基数排序是稳定排序;选择排序,快速排序,堆排序,锦标赛排序是不稳定排序。
其他还包括基础算法,字符数组字符串,链表,栈、队列,树,图还请根据刷题复习。
数学问题
数学问题包含:简单数论,排列组合,特殊数列,容斥原理,抽屉原理,概率与期望,离散数学,博弈论入门。还请根据刷题复习。