计算机科学基础

计算机发展史

通常考察如下知识点：

• 对计算机的定义以及发展史有一定的了解。

图灵机

所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

对于任意一个图灵机，因为它的描述是有限的，因此我们总可以用某种方式将其编码为字符串。我们用 表示图灵机 $M$ 的编码。

我们可以构造出一个特殊的图灵机，它接受任意一个图灵机 $M$ 的编码 ，然后模拟 $M$ 的运作，这样的图灵机称为通用图灵机（Universal Turing Machine）。现代电子计算机其实就是这样一种通用图灵机的模拟，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。

冯·诺伊曼结构

数学家冯·诺依曼提出了计算机制造的三个基本原则，即采用二进制逻辑、程序存储执行以及计算机由五个部分组成（运算器、控制器、存储器、输入设备、输出设备），这套理论被称为冯·诺依曼体系结构。

世界上第一个电子计算机

世界上第一台通用计算机 “ENIAC” 于 1946 年 2 月 14 日 在美国宾夕法尼亚大学诞生。

美国国防部用它来进行弹道计算。它是一个庞然大物，用了 $18000$ 个电子管，占地 $150$ 平方米，重达 $30$ 吨，耗电功率约 $150$ 千瓦，每秒钟可进行 $5000$ 次运算。

计算机时代划分

1. 第一代：1946 到 1958 年，这个时期构成计算机的主要逻辑元件是电子管，称为电子管时代。

2. 第二代：1959 到 1964 年。第二代计算机用晶体管代替了体积庞大的电子管，人们将这一时代称为晶体管计算机时代。

3. 第三代：1965 到 1970 年，此阶段以中、小规模集成电路作为计算机的逻辑元件。这一时代称为集成电路计算机时代。

4. 第四代：从 1970 年至今，随着集成电路集成度的不断提高，采用大规模、超大规模集成电路作逻辑元件，这一时代称为大规模集成电路计算机时代。

5. 第五代：智能计算机的概念是日本政府于1982年提出的，目标是实现智能计算机。这一目标至今尚未能直接促进计算机的更新换代。

编程语言的发展

• 机器语言：第一代计算机语言称为机器语言。机器语言就是 0/1 代码。计算机只能识别 $0$ 和 $1$。在计算机内部，无论是一部电影还是一首歌曲或是一张图片，最终保存的都是 0/1 代码，因为 CPU 只能执行 0/1 代码。

• 汇编语言（低级语言）：汇编语言就是将一串很枯燥无味的机器语言转化成一个英文单词。只是将某些 0/1 代码替换成了有意义的字符串，比如 add 1,2;

• 高级语言：汇编语言之后又出现了第三代语言。第三代语言又叫“高级语言”。高级语言的发展分为两个阶段，以 1980 年为分界线，前一阶段属于结构化语言或者称为面向过程的语言，后一阶段属于面向对象的语言。

现在我们日常使用的编程语言都是高级语言，例如 C/C++/Java/Python/Pascal 等。

世界上第一个被正式推广使用的高级语言是 Fortran。

计算机界奖项

计算机界最高奖项：图灵奖，由美国计算机协会（ACM）于 1966 年设立，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵（Alan M. Turing）。

目前唯一的华人图灵奖得主为：姚期智。

计算机基本结构与使用

通常考察如下几类知识点：

• 文件的概念，文件大小的计算以及换算。

• 基础的硬件设备。

文件

文件是一段由二进制组成的数据流。一个 0 或者 1 位就就叫做一位。

文件的大小也就是这个数据流由多少个 0 或 1 位组成，比如由 $1024$ 个位组成就说有 $1024$ bits。

我们一般把 $8$ 位叫做一个字节，也就是 $8$ bit= $1$ Byte，一般字节 Byte 会大写开头的 B 以示区分。

而一般会用 $2 ^ {10} = 1024$ 作为字节的换算比例，也就是说：

• 1 Byte = 8 bits

• 1 KB（千） = 1024 B

• 1 MB（兆） = 1024 KB

• 1 GB（吉） = 1024 MB

• 1 TB（太） = 1024 GB

常见文件类型

二进制文本文件：txt

图像文件：jpg、jpeg、png、gif（动态图片）

视频文件：avi、mp4、mpeg、wmv

音频文件：mp3

计算机硬件组成

• 主板：安装了组成计算机的主要电路系统，一般有 BIOS 芯片、I/O 控制芯片、键和面板控制开关接口、指示灯插接件、扩充插槽、主板及插卡的直流电源供电接插件等元件。

• CPU：又称中央处理器，是一个集成电路模块，主要是解释计算机指令以及处理计算机软件中的数据。一条指令的功能往往是由计算机中的部件执行一系列的操作来实现的，CPU 要根据指令的功能，产生相应的操作控制信号，发给相应的部件，从而控制这些部件按指令的要求进行动作。

• 内存：内存用于临时存储数据，一般采用半导体存储单元，包括随机存储器（RAM），只读存储器（ROM），以及高速缓存（CACHE）。RAM 是其中最重要的存储器，断电时数据会丢失。ROM 则是只可以读取，不可写入，断电时数据也不会丢失。CACHE 则可读写而且速度比 RAM 更快，造价也更高。

• 硬盘（外存）：硬盘用于存放永久数据，断电数据也不会丢失。

• I/O设备：显示器、鼠标、键盘等。

计算机网络基础知识

通常考察如下几类知识点：

• 计算机网络相关知识，主要是 IP 相关。

OSI七层网络协议

由上到下依次是：

• 应用层：与其它计算机进行通讯的一个应用，它是对应应用程序的通信服务的。包括 HTTP 等面向用户的协议。

• 表示层

• 会话层

• 传输层：这层的功能包括是否选择差错恢复协议还是无差错恢复协议，及在同一主机上对不同应用的数据流的输入进行复用，还包括对收到的顺序不对的数据包的重新排序功能。主要有 TCP 和 UDP*。

• *：TCP协议有可靠性（即不丢包），而UDP没有。

• 网络层：这层对端到端的包传输进行定义，它定义了能够标识所有结点的逻辑地址，还定义了路由实现的方式和学习的方式。主要协议是 IP 协议。

• 数据链路层：它定义了在单个链路上如何传输数据。

• 物理层：OSI 的物理层规范是有关传输介质的特性。

这是由国际标准化组织 ISO 于 1981 年正式推荐的规范。

IP地址

这里只讨论 IPv4 相关的知识，IPv4 是 $32$ 位的地址，而 IPv6 是 $128$ 位的地址。

IP 地址（Internet Protocol Address）是指互联网协议地址，又译为网际协议地址。

给因特网上的每台计算机和其它设备都规定了一个唯一的地址，叫做“IP地址”。由于有这种唯一的地址，才保证了用户在连网的计算机上操作时，能够高效而且方便地从千千万万台计算机中选出自己所需的对象来。

IP地址是一个 $32$ 位的二进制数，通常被分割为 $4$ 个“ $8$ 位二进制数”（也就是 $4$ 个字节）。IP地址通常用“点分十进制”表示成（$a.b.c.d$）的形式，其中，$a,b,c,d$ 都是 $0$ ~ $255$ 之间的十进制整数。

IP地址分为 $A,B,C,D,E$ 五类，在二进制表示种它们的区分是 $A$ 类地址的第一位总是 $0$，$B$ 类地址的前两位总是 $10$，$C$ 类地址的前三位总是 $110$，$D$ 类前四位固定为 $1110$，$E$ 类前五位固定为 $11110$。

子网掩码

子网掩码不能单独存在，它必须结合IP地址一起使用。子网掩码只有一个作用，就是将某个IP地址划分成网络地址和主机地址两部分。

通过计算机的子网掩码判断两台计算机是否属于同一网段的方法是，将计算机十进制的IP地址和子网掩码转换为二进制的形式，然后进行二进制“与” (AND) 计算（全 1 则得 1，不全 1 则得 0），如果得出的结果是相同的，那么这两台计算机就属于同一网段。

域名以及 DNS

域名（英语：Domain Name），又称网域，是由一串用点分隔的名字组成的Internet上某一台计算机或计算机组的名称，用于在数据传输时对计算机的定位标识（有时也指地理位置）。

比如 jisuanke.com

域名系统（英文：Domain Name System，缩写：DNS）是互联网的一项服务。它作为将域名和IP地址相互映射的一个分布式数据库，能够使人更方便地访问互联网。

域名分级

顶级域名

顶级域名是域名中只包含一个点的后缀。

国家顶级域名：.cn（中国）， .jp（日本） 等等。 国际顶级域名：.com（工商业），.net（网络提供商），.org（非盈利组织）等等。

二级域名

顶级域名到它前面一个点。

比如 xx.xx.edu.cn 是在国家顶级域名 .cn 下的二级域名 .edu 表示教育部门。

再往前就是三级、四级域名等等。

常见协议介绍

• TCP 协议：属于传输层协议，面向连接。

• UDP 协议：属于传输层协议，面向报文。

• FTP、SFTP 协议：属于应用层协议，用于传输文件。

• POP3、SMTP、IMAP 协议：属于应用层协议，用于发送邮件。

• HTTP 协议：属于应用层协议，用于网页传输。

程序设计基础知识

通常考察如下几类知识点：

• C++ 基本语法

• 高级语言

• 编译

高级语言

高级语言是相对于机器语言的一类语言，换言之，在我们熟知的编程语言中，除了机器码、汇编语言以外，都是高级语言，包括 C、C++、Python、Scratch、Java 等。

汇编语言和机器码是一一对应的关系，可以理解为同一指令的两种不同展现形式，都不属于高级语言。

第一门高级语言是 FORTRAN，诞生于 1954 年，随后陆续诞生了 C、C++、Java、Python 等语言。

程序语言除了分为高级语言和机器语言外，还可以分为面向对象、面向过程的语言。我们学过的 C++ 语言是面向对象的语言，以及 Python、Java 也都是面向对象的语言；而 FORTRAN、C 语言则是面向过程的语言。

编译

一些编译型的高级语言在经过编译器的某些步骤后会被翻译成机器语言，这个过程之一就叫编译。我们经常会使用类似 Codeblocks、Dev-C++、VS 之类的工具来一键运行所写程序，但是这些工具都不是编译器，而叫做集成开发环境 IDE（Integrated Development Environment）。

真正的 C/C++ 编译器有 gcc、g++、clang、msvc 等。

C/C++ 从代码到机器码的过程是：预处理、编译、汇编、链接。

解释型语言

例如 Python 就是一种解释型语言，此类语言是没有编译过程的，他们直接就可以按语义解释执行。这类语言的优点是写起来比较容易上手，省去了编译运行的复杂性，它有一些缺点比如由于不能生成可运行的二进制文件它必须将源码提供给客户。

C/C++ 基础类型

C/C++ 属于静态类型语言，所有的变量必须声明它的类型。

比如：int a = 0;，变量 a 在它的作用域内就一直会是整型类型。

基础类型之间可以互相转换，一般分为显式强制类型转换和隐式强制类型转换。

比如：

int a = (int)(1.0 / 2);

那么变量 a 的值就是 $0$，因为从 double 到 int 的强制类型转换会把 double 的小数位抹掉，即 $0.5$ 向下取整。

int a = 1;
double b = 2.3;
a = b;

这种就叫做隐式强制类型转换，a 的值变为 $2$。

变量进行类型转换时，还有以下的规则：

当出现在表达式里时，有符号和无符号的 char 和 short 类型都会自动转化成 int 型。float 类型也会自动转化成 double 类型。

在包含两种数据类型的任何运算里，两个值都被转换成两种类型里面的较高级别。

类型级别从高到低的顺序是 long double、double、float、unsigned long long、long long、long、unsigned int 和 int。

在赋值语句中，计算的最后结果将被转化成要被赋值的那个变量的类型。

作为参数传递的时候，char 和 short 会被转化成 int，float 会被转化成 double。

C/C++ 基础类型占用字节数

在 C/C++ 中，每种类型都有其固定的占用空间，下面给出表格：