计算机基础知识

计算机发展历程

第一代：电子管计算机（1946-1958）
第二代：晶体管计算机（1958-1964）
第三代：集成电路计算机（1964-1971）
第四代：大规模集成电路计算机（1971-至今）

计算机特点

运算速度快
计算精度高
存储容量大
自动化程度高
逻辑判断能力强

冯·诺依曼体系结构

运算器
控制器
存储器
输入设备
输出设备

计算机结构

CPU

中央处理器，是计算机的核心，负责执行程序指令。

内存

用于临时存储数据和程序，断电后数据丢失。

硬盘

用于长期存储数据，断电后数据不丢失。

存储单位

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

计算机网络

网络分类

局域网（LAN）：覆盖范围较小
城域网（MAN）：覆盖城市范围
广域网（WAN）：覆盖大范围区域

IP地址

互联网协议地址，用于标识网络中的设备。

OSI七层模型

物理层
数据链路层
网络层
传输层
会话层
表示层
应用层

HTTP协议

超文本传输协议，用于在Web浏览器和服务器之间传输数据。

计算机语言

机器语言

由二进制代码组成，是计算机唯一能直接执行的语言。

汇编语言

用助记符代替二进制指令，需要汇编器转换为机器语言。

高级语言

接近人类自然语言，需要编译器或解释器转换。

编译型语言 vs 解释型语言

编译型：C++, Java, Go（一次性编译成机器码）
解释型：Python, JavaScript（逐行解释执行）

进制转换

十进制转其他进制

除基取余法：不断除以基数，取余数，逆序排列。

其他进制转十进制

按权展开法：每位数字乘以基数的幂次，求和。

二进制与八进制互转

每3位二进制对应1位八进制。

二进制与十六进制互转

每4位二进制对应1位十六进制。

二进制：10101010
八进制：252
十六进制：AA
十进制：170

位运算

常见位运算符

运算符	名称	说明
&	按位与	全1为1
\|	按位或	有1为1
^	按位异或	不同为1
~	按位取反	0变1, 1变0
<<	左移	乘以2
>>	右移	除以2

位运算应用

快速乘除2
交换两个数
判断奇偶性
统计二进制中1的个数

树与二叉树

树的基本概念

节点：树中的元素
根节点：没有父节点的节点
叶子节点：没有子节点的节点
深度：从根到该节点的路径长度
高度：从该节点到叶子节点的最长路径

二叉树性质

第k层最多有2^(k-1)个节点
深度为k的二叉树最多有2^k - 1个节点
对于任意二叉树，若叶子节点数为n0，度为2的节点数为n2，则n0 = n2 + 1

完全二叉树

除最后一层外，每一层都满，最后一层从左到右依次排列。

满二叉树

每一层都满的二叉树。

二叉树遍历

前序遍历：根 -> 左 -> 右
中序遍历：左 -> 根 -> 右
后序遍历：左 -> 右 -> 根