3.常识

3.1. 图灵

图灵并没有发明实际上可用的计算机，图灵发明的是计算机的可用模型（图灵机），这个模型也就是纸带计算机的最早模型。

3.2. 计算机之父

图灵是计算机之父，冯.诺依曼是现代计算机之父。

3.3 解释执行

解释执行的程序设计语言有：Python，Javascript，即不生成目标程序，而是一句一句执行。

3.4. CCF&NOI

中国计算机学会于1984年创办全国青少年计算机程序设计竞赛。

3.5. 满k叉树

设根节点深度为 0，一棵深度为 h 的满 k（k>1）叉树的节点数(k^(h+1)- 1) / (k - 1)

3.6. 图灵奖

图灵奖是由美国计算机协会设立的（ACM）。

目前获得该奖项的华人学者只有姚期智教授一人

3.7. 互联网

• LAN 局域网
• WAN：广域网
• WLAN：无线局域网
• MAN：城域网
  以太网是一种计算机局域网技术，也是目前应用最广的局域网技术，包括物理层协议

TCP/IP 协议是应用最广的通讯协议

3.8. 栈&队列

栈最大的特点： 后进先出；队列：先进先出

3.9. 各种协议

• HTTP 协议: Hyper Text Transfer Protocol（超文本传输协议）的缩写,是用于从万维网（WWW:World Wide Web ）服务器传输超文本到本地浏览器的传送协议。
• FTP: FTP（File Transfer Protocol，文件传输协议） 是 TCP/IP 协议组中的协议之一。
• SMTP:简单邮件传输协议， SMTP是一种提供可靠且有效的电子邮件传输的协议
• POP：邮局协议，从服务器上检索邮件
• IMAP:互联网信息访问协议

3.10. 各种排序算法的性质:

稳定的排序：直接插入排序（O（n），O（n^2））、冒泡(O(n^2))、归并(O(nlogn))、基数排序(O(n+r)) 不稳定：简单选择排序(O(n^2))、希尔排序(?)、堆排序(O(nlogn))、快排(O(n) O(n^2))

3.11 按下编译键的那一刻

• 高级语言变成汇编语言的过程叫编译
• 汇编语言变成机器语言的过程叫汇编
• 高级语言的可移植性一定强于汇编语言和机器语言

3.12 数据结构中的六种基本数据结构:

1. 线性表
2. 链表
3. 栈
4. 队列
5. 树
6. 图

• 线性表（数组）:

  缺点是占用内存空间大，容易形成碎片空间

  优点是可以实现随机访问（可以不知道其他位置的数字就直接调用你想调用的位置）

• 链表：

  优点：可以充分利用碎片空间

  缺点：不能实现随机访问

3.13 完全___

• 完全二叉树：所有节点按照顺序递增的二叉树
• 完全图：每两个节点之间，恰有一条边相连 (边的数量=（n-1)×n/2 n为结点的数量)