进制
- 十进制和二进制互转
- 十进制和八进制互转
- 十进制和十六进制互转
- 二进制和八进制互转
- 二进制和十六进制互转
单位
- 1字节=8位 （英文：1byte=8bit）
- 1KB=1024B（B是byte的缩写）
- 1MB=1024KB
- 1GB=1024MB
- 1TB=1024GB
逻辑运算
- 逻辑符号：
- 逻辑与：∧（或‘·’）
- 逻辑或：∨ （或‘+’）
- 逻辑非：┐
- 优先级：
- 逻辑非>逻辑与>逻辑或
- 有括号按括号，无括号先按优先级，同级运算从左至右
二叉树的遍历
- 先序遍历（前序遍历）
- 中序遍历
- 后序遍历
二叉树性质
-
深度为的二叉树至多有个节点（假设根节点所在层为1）
-
满二叉树：深度为的二叉树有个节点（假设根节点所在层为1）
-
完全二叉树：深度为𝑘有𝑛个节点的二叉树，当且仅当其中的每一个节点，都可以和同样深度𝑘的满二叉树，序号为1到𝑛的节点一对一对应
-
对任何一棵二叉树，如果叶节点数为$n_0$，度为2的节点数为$n_2$，则$n_0=n_2+1$。
-
具有n个节点的完全二叉树的深度为$\left\lfloor log_2{n} \right\rfloor + 1$。
对于一棵具有n个节点的完全二叉树，对任何一个节点（假设编号为i），有以下性质：
- 如果i=1，则节点i为根，无父节点
- 如果i>1，则其父节点编号为$\left\lfloor\frac{i}{2}\right\rfloor$
- 如果2i>n，则节点i无左子结点；否则左子结点编号为2i
- 如果2i+1>n，则节点i无右子结点；否则右子节点编号是2i+1
这里的$\left\lfloor x\right\rfloor$表示不大于x的最大整数，也就是向下取整。
栈
- 先进后出
队列
- 先进先出
链表
- 每个元素会有一个指针指向要求的下一个元素
- 单向链表：每个元素只有一个指针指向下一个元素
- 双向链表：每个元素有两个指针，一个指向下一个元素，另一个指向指向他的元素
编程语言
- 编程语言主要分两类：
- 面向对象
- 面向过程
- 常见的面向过程高级语言：
- C语言
- Fortran语言
- 常见的低级语言：
- 汇编
- 常见的面向对象高级语言:
- 除了Pascal和上面3种，其他都是
-
常见的脚本语言：
- JavaScript
- Perl
- PHP
- Python
- Ruby
计算机历史
- 对计算机做出重要贡献的人物：
- 图灵
- 冯·诺依曼
- 中国获图灵奖的人物：姚期智
- 第一台计算机：ENIAC（属于电子管计算机）
- 第一台具有存储程序功能的计算机：EDVAC
计算机硬件原理问题
- 微型计算机的面世：超大规模集成电路。
- 存储设备：
- ROM（ 硬盘，U盘）（断电数据不会丢失）
- RAM（内存）（断电数据就会丢失）
- CPU组成：
- 运算器（计算）
- 控制器
- 寄存器（临时存数据，比内存快）
- Cache高速缓存（临时存数据，比内存快，出现原因：CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中）
- 内部总线（连接上面芯片的线路）
概念
- 中国计算机学会于1984年创办全国青少年计算机程序设计竞赛。
- 操作系统的作用是控制和管理系统资源 。
- 在计算机内部用来传送、存贮、加工处理的数据或指令都是以二进制码形式进行的。
- 当出现需要时，CPU 暂时停止当前程序的执行转而执行处理新情况的过程叫做中断。
- 计算机病毒是人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 。
- CPU、存储器、I/O 设备是通过总线连接起来的。
- 目前计算机芯片（集成电路）制造的主要原料是硅（化学符号：Si），它是一种可以在沙子中提炼出的物质。
- 1956年诺贝尔物理学奖授予肖克利、巴丁和布拉顿，以表彰他们对半导体的研究和晶体管效应的发现。
- 图灵机 (Turing machine, TM) 是由图灵在1936年提出的，它是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为。
- BIOS是计算机基本输入输出系统软件的简称，操作系统是由BIOS启动的。
- 网络：LAN（局域网）、WAN（广域网）、MAN（城域网）
- 电子邮件协议：
- SMTP（简单邮件传输协议）
- POP3（邮局协议 版本3）
- IMAP（互联网信息访问协议）
- 网络协议：
- HTTP（超文本传输协议）
- FTP（文件传输协议）
排序算法的时间复杂度和空间复杂度
| 类别 | 排序方法 | 时间复杂度(平均) | 时间复杂度(最好) | 时间复杂度(最坏) | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|---|
| 插入排序 | 直接插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(n^{1.3})$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 不稳定 | |
| 选择排序 | 直接选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 堆排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(1)$ | 不稳定 | |
| 交换排序 | 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 快速排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ | $O(n\log n)$ | 不稳定 | |
| 归并排序 | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ | 稳定 | |
| 基数排序 | $O(nk)$ | $O(nk)$ | $O(nk)$ | $O(n+k)$ | 稳定 |
排列组合
排列：从n个不同元素中，任取m个元素按照一定的顺序排成一列 例子：从10个小朋友中抽出3个，按先后顺序排好队去跑操场，有多少种情况
组合：从n个不同元素中，任取m个元素并成一组 例子：从10个小朋友中抽出3个去罚站，有多少种情况
排列公式： $\mathrm{A}_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!},\quad n,m\in \mathbb{N}^* ,\text{并且}m\leq n$
组合公式： $\mathrm{C}_n^m=\frac{\mathrm{A}_n^m}{\mathrm{A}_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m!(n-m)!},\quad n,m\in \mathbb{N}^* ,\text{并且}m\leq n$