一、计算机组成原理

关系代数笛卡尔积+选择+投影题

一先学透所有核心知识点（零基础必看）

1. 关系代数三大核心运算符

2. 运算符优先级与运算顺序

关系代数的运算顺序严格遵循从内到外先括号后括号外：

先算括号内的 R×S（笛卡尔积）→ 再算 σ（选择，挑行）→ 最后算 π（投影，挑列）

3. 列号与列名的对应规则（解题核心）

当两个关系做笛卡尔积 R×S 时，新关系的列顺序 = R的所有列在前，S的所有列在后，列号从1开始依次编号。

• 若两个表有重名列（比如本题R和S都有CD列），必须用表名前缀区分：R.C 代表R表的C列，S.C 代表S表的C列，否则会产生歧义。

4. 本题关系RS的结构明细

关键结论：R×S 共7列，列号1-7对应：1:R.A2:R.B3:R.C4:R.D5:S.C6:S.D7:S.E

校验码知识点

什么是校验码

计算机在存储和传输数据的时候，可能因为硬件故障电磁干扰等原因导致某个二进制位从 0 变成 1，或者从 1 变成 0，这就叫做"出错"。校验码就是一种专门用来发现甚至纠正这种错误的编码方案。

常见的校验码有两种。一种叫奇偶校验码，只能发现奇数个位出错，但没办法确定是哪一位出错，所以只能检错不能纠错。另一种就是这道题考的海明码，它不仅能发现错误，还能精确定位出错的那一位，从而自动纠正。

海明码的基本原理

海明码的做法是：在原始数据位里插入若干个额外的校验位。每个校验位负责监控特定的几个数据位，它的值由被它监控的所有数据位共同决定。一旦某个数据位出错，就会有一部分校验位的值发生变化，通过观察哪些校验位出了问题，就能精确算出是第几位出错，然后把那一位翻转回来，完成纠错。

海明码需要几个校验位——核心公式

设原始数据有 $n$ 位，需要插入 $r$ 个校验位，则 $r$ 必须满足：

$$2^r \geq n + r + 1$$

这个公式怎么理解：$r$ 个校验位一共能表示 $2^r$ 种不同的状态组合。这些状态要能覆盖三种情况：第一，$n$ 个数据位各自出错，第二，$r$ 个校验位各自出错，第三，没有任何位出错。三种情况加起来一共需要 $n + r + 1$ 种状态，所以 $2^r$ 必须大于等于 $n + r + 1$。

求 $r$ 的方法就是从小到大逐个代入 $r = 1 2 3 \ldots$，找到第一个让不等式成立的 $r$，那就是最少需要的校验位数。

海明码的位置编号规则

把海明码的所有位（包括数据位和校验位）从右到左依次编号，从 $1$ 开始。

校验位只能放在编号为 $2$ 的幂次的位置上，也就是位置 $124816\ldots$，分别叫做 $P_1P_2P_3P_4\ldots$。其余位置放数据位。

某个数据位由哪些校验位负责——二进制分解

这是最核心的规则：把某个数据位的位置序号写成二进制，哪几个二进制位上是 $1$，就由对应位置上的校验位来监控这个数据位。

举个具体例子：位置序号 $14$，写成二进制是 $1110$，从右往左各位的权值是 $1248$，值为 $1$ 的位对应权值是 $248$，所以位置 $14$ 的数据由位置 $8$ 的 $P_4$位置 $4$ 的 $P_3$位置 $2$ 的 $P_2$ 共同负责校验。

再举一个：位置序号 $5$，写成二进制是 $0101$，值为 $1$ 的位对应权值是 $1$ 和 $4$，所以位置 $5$ 的数据由位置 $4$ 的 $P_3$位置 $1$ 的 $P_1$ 共同负责校验。

记住口诀：位置序号做二进制分解，分解出哪些 $2$ 的幂次，就由那些幂次位置上的校验位负责。

层次化存储体系

内存编址与存储芯片知识点

什么是十六进制

计算机里的地址通常用十六进制表示，十六进制用 $0\text{-}9$ 和 $A\text{-}F$ 共16个符号，其中 $A=10B=11C=12D=13E=14F=15$。地址末尾加 H 就表示这是一个十六进制数。

按字节编址是什么意思

按字节编址的意思是：内存里每一个字节都有一个独立的地址编号，相邻两个地址之间正好差1个字节。所以从地址 $X$ 到地址 $Y$ 一共包含的字节数就是：

$$\text{字节数} = Y - X + 1$$

加1是因为要把起始地址本身也算进去，就像从第1页到第5页一共是5页而不是4页一样。

怎么计算两个十六进制地址之间的字节数

直接用末地址减去首地址，再加1，结果就是字节数。十六进制做减法和十进制一样，只是逢16进1。

KB 和字节的换算

$1\text{KB} = 1024$ 字节 $= 2^{10}$ 字节。换算时把字节数除以 $1024$ 就得到 KB 数。

存储芯片的容量怎么看

一块芯片写成"$64\text{K} \times 8\text{bit}$"，意思是这块芯片能存 $64\text{K}$ 个存储单元，每个存储单元是 $8$ 位（即1字节）。所以这块芯片的总容量就是 $64\text{K} \times 1$ 字节 $= 64\text{KB}$。

需要几片芯片

用需要覆盖的总内存容量除以每片芯片的容量，就得到需要的芯片数量：

$$\text{芯片数} = \frac{\text{总内存容量}}{\text{单片芯片容量}}$$

I/O 数据传输控制方式知识点

什么是 I/O 数据传输

I/O 是 Input/Output 的缩写，也就是输入输出。计算机不只有 CPU 和内存，还连接着键盘鼠标硬盘网卡打印机等各种外部设备。CPU 和这些外部设备之间交换数据，就叫做 I/O 数据传输。问题在于外部设备的速度远远比 CPU 慢，CPU 需要一种机制来协调和管理这些设备，这就是 I/O 数据传输控制方式。

程序查询方式

CPU 主动不断地去问外部设备"你好了没有，数据准备好了吗"，设备没准备好就一直等，准备好了才继续。这就像你在店里等餐，每隔几秒就问服务员"好了吗好了吗"，一直等到上菜为止。这种方式 CPU 会被完全占用，什么其他事情都干不了，效率极低。

中断方式

CPU 不去主动等待，而是继续干自己的事情。外部设备准备好了之后，主动发一个信号通知 CPU，这个信号就叫做中断请求。CPU 收到中断请求后，暂停当前正在执行的程序，保存好当前的工作状态（这叫保存现场），然后跳转去处理外部设备的事情。处理完之后，恢复刚才保存的工作状态（这叫恢复现场），回到原来暂停的地方继续执行。

这就像你在专心写作业，手机突然响了（中断请求），你记下写到哪一行了（保存现场），去接电话（处理中断），接完电话回来翻到刚才那一行继续写（恢复现场）。

中断方式让 CPU 不再需要傻等，效率大幅提升，是现代计算机最核心的机制之一。

保存现场的含义

CPU 在执行程序时，各种寄存器里存着当前程序运行到哪里了中间计算结果是多少等关键信息。一旦跳去处理中断，这些信息可能被覆盖掉，回来就不知道刚才做到哪了。所以在跳转之前，必须把这些寄存器的值全部压入栈（一块临时存储区域）保存起来，处理完中断再从栈里取回来，恢复成中断前的状态，这样原程序就能无缝衔接地继续跑下去。

DMA 方式

DMA 是 Direct Memory Access（直接内存访问）的缩写。它引入了一个专门的 DMA 控制器，让外部设备可以直接和内存之间传输大批量数据，整个过程完全不需要 CPU 参与。CPU 只在开始和结束时介入一下，中间全程解放出来干别的事。这就像公司请了一个专职快递员，老板（CPU）只需要说一声"帮我把这批货从仓库搬到车间"，剩下的全交给快递员，老板可以去忙其他事。DMA 特别适合大批量数据传输，比如硬盘读写网络数据包收发。

通道方式

通道是比 DMA 更强大的方式，它相当于一个功能简化的小 CPU，能执行一套专门的通道指令，独立管理多个外部设备的数据传输，只在完成整批任务后才通知主 CPU。这种方式用在大型计算机服务器等需要同时管理大量 I/O 设备的场合。

实际应用举例

你按下键盘上的一个键，键盘控制器立刻向 CPU 发出中断请求，CPU 暂停当前任务，跳转到键盘中断处理程序，读取你按的是哪个键，然后回来继续之前的工作。整个过程发生在几微秒内，你完全感觉不到。同样，当你的程序在从硬盘加载一个大文件时，操作系统会启动 DMA 传输，CPU 在此期间可以继续响应鼠标点击播放音乐等其他任务，等 DMA 传完了再发一个中断通知 CPU。

总线系统知识点

什么是总线

总线就是计算机内部各个部件之间传递信息的公共通道，可以把它想象成一条高速公路，CPU内存硬盘显卡等所有部件都连在这条公路上，信息就沿着这条路来回传送。如果没有总线，每两个部件之间都要单独连一根线，部件一多线路就会乱成一团，根本没法管理。总线的好处就是所有部件共享同一组线路，大大简化了连接方式。

三总线结构——数据总线地址总线控制总线

计算机里的总线按照传输信息的类型不同，分成三种，合在一起就叫三总线结构。

第一种是数据总线，负责传输真正的数据内容，比如从内存里读出的数值CPU 计算好的结果等。数据总线是双向的，数据可以从 CPU 送往内存，也可以从内存送往 CPU。数据总线的宽度（有几根线）决定了每次能传多少位数据，比如32位数据总线每次能传32个二进制位。

第二种是地址总线，负责传输地址，告诉其他部件"我要访问的是哪个位置"。比如 CPU 想读内存里某个地址的数据，就先通过地址总线把那个地址发出去。地址总线是单向的，只能从 CPU 发出去，不能反过来。地址总线的宽度决定了 CPU 最多能寻址多大的内存空间，比如32位地址总线最多能访问 $2^{32} = 4\text{GB}$ 的内存。

第三种是控制总线，负责传输控制命令和状态信号，比如"我现在要读数据""我现在要写数据""操作完成了""有中断请求"等。控制总线是双向的，CPU 可以发命令给设备，设备也可以发状态信号给 CPU。

三条总线的分工可以用一个比喻来记

你去图书馆借书：你告诉管理员书架编号（地址总线），管理员把书拿给你（数据总线），你说的是"借"还是"还"（控制总线）。三条线各司其职，缺一不可。

实际应用

你双击打开一个程序，CPU 通过地址总线告诉内存控制器"去读地址 X 的数据"，控制总线发出"读"信号，内存控制器把数据通过数据总线送回 CPU。整个过程三条总线协同工作，每秒钟这样的操作要发生几十亿次。现代电脑主板上那些密密麻麻的电路线，很大一部分就是各种总线的物理实现。

指令寻址方式及其应用

知识点通俗讲解

在了解“寻址方式”之前，我们先打个通俗的比方。假设CPU（中央处理器）是一个极其忙碌的厨师，“指令”就是菜谱上的一个个步骤，而**“操作数”就是做菜需要的食材**。

所谓**“寻址方式”，其实就是厨师去哪里找食材的方法**。找食材的地方不同，花费的时间自然就不一样。

1. 立即寻址（Immediate Addressing）：
   • 什么意思：指令本身就带着要处理的数据。
   • 厨师比喻：菜谱上直接写着“把这包已经贴在菜谱上的盐倒进去”。食材就在步骤说明书上。
   • 速度：最快。厨师看菜谱的同时就已经把盐拿在手里了，不需要去任何地方找。
2. 寄存器寻址（Register Addressing）：
   • 什么意思：数据存放在CPU内部的“寄存器”中（寄存器是CPU里极其微小但速度极快的存储空间）。
   • 厨师比喻：菜谱上写着“用你围裙口袋里的盐”。寄存器就像是厨师贴身的口袋。
   • 速度：很快，排第二。虽然不如直接贴在菜谱上快（因为要伸手去口袋掏一下），但因为口袋就在厨师自己身上，拿取速度依然非常迅速。
3. 直接寻址（Direct Addressing）：
   • 什么意思：指令里只给出了数据在内存（主存）中的地址，CPU必须根据这个地址去内存里把数据取出来。
   • 厨师比喻：菜谱上写着“去厨房外面的大仓库（内存）里的第8号架子上拿盐”。
   • 速度：最慢。厨师必须停下手头的活，走出厨房，走到仓库，找到架子，拿盐，再走回来。在计算机中，CPU访问外部内存的速度远远慢于它自身内部的处理速度。

实际中的应用

1. 软件优化与底层编程：虽然我们平时用高级语言（如PythonJava）写代码时感觉不到这些，但把代码翻译给电脑听的“编译器”却在疯狂计算。为了让程序跑得更快，编译器会尽量把常用的变量放在“寄存器”里（寄存器寻址），或者直接用数字常量（立即寻址），尽量减少去内存里找数据（直接寻址）的次数。
2. 选购电脑的参考：这能帮你理解为什么电脑的CPU缓存（相当于比寄存器大一点，比内存快很多的“小仓库”）那么重要。因为去内存（直接寻址）太慢了，CPU需要离自己近的地方来存放数据，减少等待时间。

流水线技术

知识点通俗讲解
流水线技术（Pipelining）的核心思想是：把一个复杂的任务拆分成几个小步骤，并行处理，以提高效率。

想象一个“汉堡制作流水线”：

• 第 1 步：取指（取材料） —— 耗时 4 分钟
• 第 2 步：分析（处理材料） —— 耗时 2 分钟
• 第 3 步：执行（组装汉堡） —— 耗时 3 分钟

如果不使用流水线，做一个汉堡要 9 分钟，100 个汉堡就要 900 分钟。
但在流水线中，只要第一个汉堡处理完第一步，就可以马上处理第二个汉堡的第一步，不需要等第一个汉堡全部做完。

关键规则：
流水线中，每一个步骤的周期（即速度）必须由这几个步骤里“最慢的那个步骤”来决定。 就像工厂传送带的速度不能超过最慢的工位，否则材料会堆积。在本题中，最慢的步骤是“取指”（4个单位时间）。

实际应用
现代电脑手机的 CPU 都在使用流水线技术。它们之所以能每秒执行几十亿次指令，就是因为这种并行处理机制。如果 CPU 没有流水线，处理器的性能会下降到现在的几十分之一甚至更低。

可靠性：串联与并联的艺术

在计算机系统设计中，“可靠性”指的是系统在规定时间内不出故障的能力。为了让系统更稳固，工程师们主要使用两种结构：

1. 串联模型（一荣俱荣，一损俱损）

• 结构：几个部件像“糖葫芦”一样连在一起。
• 逻辑：只有所有部件都正常工作，系统才正常。如果其中任何一个坏了，整个系统就瘫痪了。
• 计算：总可靠性 = 所有部件可靠性的乘积（因为可靠性R通常小于1，乘得越多，结果越小）。

2. 并联模型（备用机制，互为备份）

• 结构：几个部件像“立交桥”一样并行排列。
• 逻辑：只要有一个部件工作，系统就能跑。只有所有部件同时坏掉，系统才会崩溃。
• 计算：
  • 先算“坏”的概率：单个部件坏的概率是 $(1-R)$。
  • 并联时所有部件同时坏的概率：$(1-R)^n$ （n是部件数量）。
  • 总可靠性 = $1 - (\text{所有部件同时坏掉的概率}) = 1 - (1-R)^n$。

3. 实际应用

• 服务器集群：为了防止网站挂掉，公司会买多台服务器（并联）。只要有一台活着，用户就能访问。
• 航天飞行器：为了防止重要零件坏掉，通常会设计 3 个备份（三模冗余）。因为串联系统极其脆弱，所以关键系统内部往往充斥着各种并联设计。

操作系统概述

嵌入式系统（比如你微波炉里的芯片汽车的行车电脑智能手表）与普通电脑不同，它通常资源有限，且针对特定任务设计。为了满足不同的需求，它有几个核心特性：

实际应用中的理解

• 可定制性：比如开发一个简单的电子体温计，它的操作系统不需要视频播放功能，那就在定制时直接去掉。这能极大地节省内存，降低硬件成本。
• 易移植性：比如工程师开发了一款智能灯泡的控制程序，如果公司换了一个更便宜的芯片供应商，他们不需要重新写一遍代码，只需要稍微修改，就能把系统“搬”到新芯片上跑，这大大缩短了产品上市的时间。

进程管理

在操作系统中，一个进程就像一个人在处理任务，它随时处于以下三种状态之一：

信号量与PV操作
 

在操作系统中，多个进程常常需要抢夺有限的资源（比如 3 台扫描仪）。为了不发生混乱，系统引入了“信号量（S）”的概念，我们可以把它想象成一个**“资源计数器”**。

• 如果 S > 0：代表有空闲资源，进程可以直接拿走使用。
• 如果 S < 0：代表资源被抢光了，绝对值 |S| 代表当前正在排队等待的进程个数。

实际应用：想象一个有 3 个座位的自习室。S 的初始值是 3。

• 每进一个人（执行 P 操作），S 变成 210。
• 当 S 为 0 时，第 4 个人再想进来，S 就会变成 -1。这表示现在有 1 个人正在排队等着有人离开。

前趋图与PV操作

在计算机系统中，为了让多个进程和谐地“排队”或“并行”执行，我们需要一套规则来管理。前趋图就是描述任务先后顺序的流程图，而 PV 操作则是实现这些顺序的“控制开关”。

• 实际应用：例如在手机安装 App 的过程。系统必须先“下载安装包”，再“解压文件”，最后“安装到系统”。这就是一个典型的前趋关系。通过 PV 操作，系统可以确保解压动作一定在下载完成之后才开始，绝不会出错。

死锁问题

在多进程操作系统中，“死锁”是一种极端的崩溃状态。你可以把它想象成一个**“谁也不让谁”**的交通堵塞。

• 实际应用：在数据库操作中，如果事务 A 锁住了表 1 想访问表 2，同时事务 B 锁住了表 2 想访问表 1，如果不做死锁检测和预防，程序就会彻底“卡死”。为了避免这种情况，操作系统通常会利用“银行家算法”来提前预测：如果你现在把资源分配给进程，会不会导致后续大家都没法完成？如果会，就拒绝分配。

进程资源图：死锁的“诊断书”

进程资源图（Resource Allocation Graph）是用来分析系统是否发生“死锁”的有力工具。

核心判断规则（化简法）：

1. 找“非阻塞节点”：如果一个进程申请的资源正好有空余，它就能运行。
2. “运行完毕释放资源”：进程运行完会归还资源，原本阻塞的进程可能因此获得资源而变成“非阻塞”。
3. 判断死锁：如果在最后，所有进程都变成了“阻塞”状态（化简不完了），那说明系统发生了死锁。如果最后所有进程都能被“化简掉”（运行完毕），则无死锁。

页式存储

页式存储管理是操作系统中将内存“化整为零”的核心技术，通过页表将逻辑地址映射到物理内存。页表中的关键标志位定义如下：

段式存储

在计算机内存管理中，如果说“页式存储”是把程序无情地切成大小相等的“豆腐块”，那么“段式存储”就是按照程序的自然逻辑（比如主程序子函数数据区）切分成大小不一的“段落”。

• 实际应用：段式存储非常重要，它能确保“数据段”不会越界跑到“代码段”里去执行，防止程序因为非法访问内存而崩溃（即经典的“段错误”）。

段页式存储

段页式存储是操作系统中一种“折中”的内存管理方案。它综合了“段式存储”逻辑结构清晰和“页式存储”内存利用率高的优点。

• 实际应用：现代计算机操作系统（如 Linux 在 x86 架构下的实现）大多采用段页式管理。它既满足了程序员从逻辑上划分程序（代码段数据段）的需求，又解决了物理内存中大段连续空间难以申请的问题，是性能与灵活性平衡的结果。

磁盘管理与调度算法

磁盘调度算法旨在通过合理的磁头移动路径，尽可能降低寻道时间，提高系统磁盘读写性能。

设备管理

在计算机系统中，设备管理负责协调操作系统与各种硬件（鼠标硬盘打印机等）之间的通信。为了简化操作，管理软件被分成了四个层次，每一层都像是一个专门处理不同任务的“翻译官”。

• 实际应用：当你编写一个程序读取文件时，你不需要知道硬盘是哪个厂家生产的（这归功于第1层）操作系统调用硬盘驱动程序来发送读扇区的指令（第2层）当数据读完，硬件会触发中断，告诉系统可以读取了（第3层），最后硬件完成动作。

文件相关概念

在操作系统中，文件管理系统负责在磁盘上组织和查找数据。为了高效管理这些数据，系统不仅存“用户内容”，还要存“管理信息”。

• 实际应用：当你删除一个文件时，操作系统通常只是把该文件在“目录”里的索引删掉了，并把对应的“空闲块”标记为可用。如果由于断电导致“目录”文件损坏，整个磁盘的布局就会错乱，这就是为什么系统奔溃时目录结构受损会导致系统无法启动的原因。

树形目录结构

一知识点

二实际应用

索引文件结构

什么是文件的存储问题

文件存在磁盘上，磁盘被切成一块一块固定大小的"数据块"来管理，这道题里每块是 1KB。一个文件的内容可能很大，需要占用很多块，这些块不一定是连续存放的，可能分散在磁盘各处。那么操作系统怎么知道一个文件的数据分别存在哪些块上呢？答案就是索引节点。

什么是索引节点（inode）

每个文件都有一个对应的索引节点，里面存的不是文件内容，而是这个文件的"地图"——记录着文件数据分别存在磁盘的哪些块上。这个地图是通过若干个地址项来实现的，每个地址项存一个磁盘块的地址（编号）。这道题里每个地址项占 4 字节，一共有 8 个地址项 iaddr[0]～iaddr[7]。

逻辑块号和地址项的对应关系

文件的数据块从用户角度按顺序编号，叫逻辑块号，从 0 开始。逻辑块号和 iaddr 地址项一一对应：逻辑块号 0 对应 iaddr[0]，逻辑块号 1 对应 iaddr[1]，以此类推。

三种寻址方式

一个 1KB 的索引块能存多少个地址：$1024 \div 4 = 256$ 个，这个数字非常关键，后面计算都要用到。

位示图法

什么是位示图

磁盘上有成千上万个物理块，操作系统需要随时知道哪些块是空闲的哪些块已经被占用。位示图就是专门用来记录这件事的一张"地图"。

它的原理非常简单：用一个二进制位（0或1）对应一个物理块，0 表示该块空闲，1 表示该块已占用。所有物理块的状态连在一起，就形成了一张位示图，存在磁盘的固定位置上。

字和位的概念

位示图里的二进制位不是一个个单独存的，而是按"字"来组织的。一个字有固定的位数，这道题里每个字是 32 位。字从 0 开始编号，每个字里的位也从 0 开始编号。

物理块号和字号位号的换算

已知物理块号，求它在位示图里第几个字的第几位：

$$\text{字号} = \left\lfloor \frac{\text{物理块号}}{\text{字长}} \right\rfloor$$

$$\text{位号} = \text{物理块号} \mod \text{字长}$$

反过来，已知字号和位号，求物理块号：

$$\text{物理块号} = \text{字号} \times \text{字长} + \text{位号}$$

实际应用

Linux 的 ext 文件系统用块位图（block bitmap）来管理磁盘空闲块，Windows 的 NTFS 也有类似的位图结构。每次新建文件需要分配磁盘空间时，操作系统就扫描位图找到值为 0 的位，把对应的物理块分配出去，并把该位改为 1。删除文件时则把对应位改回 0，表示空闲。位示图结构紧凑查找效率高，是最常用的磁盘空间管理方法之一。

编译程序与解释程序

什么是高级语言的翻译问题

我们写的 CPython 这类代码，CPU 完全看不懂，CPU 只认识二进制的机器指令。所以必须有一个"翻译官"把人写的代码翻译成机器能执行的指令。这个翻译官有两种工作模式，一种叫编译器，一种叫解释器。

编译器的工作方式

编译器的做法是：先把整个源程序完整地翻译一遍，生成一个独立的目标程序文件，然后每次运行直接执行那个目标程序，编译器本身不再参与。就像把一本中文书完整翻译成英文书，翻译完之后英文读者直接读英文书，不需要翻译官再在场。

解释器的工作方式

解释器的做法是：不提前翻译整个程序，而是每次运行时一行一行地读源代码，读一句翻译一句立刻执行，解释器全程参与。就像现场口译，翻译官必须一直在场，说一句翻一句。

两者的核心区别

共同点

两者都是高级程序语言的翻译工具，翻译过程都包含词法分析语法分析语义分析三个阶段。

实际应用

C/C++ 是典型的编译型语言，代码编译后生成 .exe 或 .out 文件，运行速度极快，常用于操作系统游戏引擎等对性能要求高的场合。PythonJavaScript 是典型的解释型语言，代码可以直接在任何装了解释器的机器上跑，不需要为每个平台单独编译，灵活性和可移植性强，常用于脚本数据分析网页开发。

常见程序设计语言的特点

程序设计语言的分类

程序设计语言按照发展历史和抽象程度，从低到高分为机器语言汇编语言和高级语言三大类。高级语言里又细分出很多种类，脚本语言是其中一种。

脚本语言是什么

脚本语言是高级语言的一个子类，专门用来编写自动化任务快速处理数据控制其他程序等轻量级工作的语言。它的核心特征有以下几点。

第一，脚本语言主要采用解释方式实现，也就是边读代码边执行，不需要提前编译成目标程序，写完直接运行，非常方便。

第二，脚本语言不是通用程序设计语言。通用语言（比如 CJava）适合开发各类软件，脚本语言更擅长特定场合，比如网页交互系统自动化数据处理等。

第三，脚本语言不适合系统级程序开发。系统级程序（比如操作系统驱动程序）需要直接操作硬件追求极致性能，这是 C/C++ 等编译型语言的领域，脚本语言执行效率低，不适合。

第四，脚本语言完全可以定义和调用函数。PythonJavaScript 里定义函数是最基本的功能，这一点不存在限制。

常见脚本语言及应用场景

实际应用举例

你在网页上点击一个按钮弹出提示框，背后执行的就是 JavaScript 脚本。运维工程师每天凌晨自动备份服务器数据，靠的是 Shell 脚本。数据科学家用几十行 Python 脚本就能完成几千行 Excel 数据的清洗和分析。这些场合都不需要编译，写完就能跑，这正是脚本语言的优势所在。

程序设计语言的基本成分

高级程序设计语言的四大成分

通用的高级程序设计语言一般都提供四类语言成分，分别是数据运算控制和数据传输。这四类成分缺一不可，共同构成一门完整的编程语言。

控制成分的三种结构

控制成分是最核心的考点，任何程序的执行流程都由且仅由以下三种基本控制结构组成，这是结构化程序设计的理论基础。

函数调用方式

什么是参数传递

调用函数时，需要把数据从调用方传给被调函数，传递方式不同，函数内部对参数的修改是否影响外部变量的结果也不同。最常见的两种方式是传值和传引用。

传值（Call by Value）

把实参的值复制一份给函数的形参。函数内部操作的是那份拷贝，不管函数里怎么修改形参，原来的实参变量完全不受影响。就像把你的文件复印一份给别人，别人在复印件上涂改，你的原件不变。

传引用（Call by Reference）

把实参变量的地址传给函数，函数内部直接操作原变量本身。函数里对形参的任何修改，都会直接反映到原来的实参变量上。就像直接把你的原件给别人，别人在上面改，你的原件就真的变了。

两种方式的对比

实际应用

swap 交换函数是最经典的例子。如果用传值，函数内部交换了两个局部变量，函数结束后调用方的两个变量根本没变，交换失败。必须用传引用，才能真正交换调用方的变量。

编译过程概述

编译器的六个阶段

编译器把源程序翻译成目标代码，整个过程按顺序经历六个阶段：

每个阶段做什么

词法分析是第一步，把源程序的字符流切分成一个个有意义的基本单词，比如关键字 int变量名 x运算符 + 等，叫做 Token。

语法分析是第二步，检查这些 Token 的排列组合是否符合语法规则，比如 if 后面必须跟条件表达式，缺了括号就报语法错误。

语义分析是第三步，在语法正确的基础上进一步检查含义是否合理，比如把一个整数赋值给字符串类型变量，语法上可能没问题，但语义上是错的。

中间代码生成是第四步，把源程序翻译成一种介于高级语言和机器语言之间的中间表示，方便后续优化和跨平台处理。

代码优化是第五步，对中间代码进行改进，让生成的目标代码运行更快占用内存更少。这一步是可选的，不是每个编译器都必须做。

目标代码生成是第六步，把中间代码（或优化后的中间代码）翻译成特定平台的机器指令，生成最终的目标程序。

哪些阶段是可选的

中间代码生成和代码优化这两个阶段不是每个编译器都必须有的。简单的编译器可以直接从语义分析跳到目标代码生成，跳过中间代码和优化步骤。而词法分析语法分析语义分析目标代码生成这四步是每个编译器都必须有的。

解释器和编译器的区别

解释器不生成目标代码，而是直接读源程序边解释边执行，整个运行过程中解释器都参与其中。编译器生成目标代码之后就退出了，后续运行不需要编译器再参与。

实际应用

GCC 是最常见的 C 语言编译器，你写的 .c 文件经过它的六个阶段最终变成可执行文件。编译时加 -O2 参数就是开启代码优化阶段，生成的程序会更快。Python 解释器运行 .py 文件时全程参与，所以 Python 程序一般比 C 程序慢很多。

正规式与正规集

知识点

正规式（也叫正则表达式）是描述正规集（字符串集合）的工具，核心是用简洁的符号表示一类有规律的字符串。

核心符号含义

实际应用

• 编程中字符串校验（如邮箱手机号格式验证）
• 文本编辑器的查找替换功能
• 编译原理中词法分析器的设计（定义标识符关键字的规则）

表达式

知识点

表达式是程序设计语言中描述计算的核心单元，常见的表示形式有中缀表达式前缀表达式（波兰式）和后缀表达式（逆波兰式）。

三种表达式对比

逆波兰式求值原理（栈的应用）

1. 从左到右扫描表达式
2. 遇到数字：压入栈中
3. 遇到运算符：弹出栈顶两个数（先弹出的是右操作数，后弹出的是左操作数），计算结果后压回栈中
4. 扫描结束后，栈中仅剩的数就是表达式的结果。

实际应用

• 编译器的表达式求值：将中缀表达式转为逆波兰式，再用栈求值，避免处理优先级和括号
• 计算器程序的底层实现：大部分计算器都基于逆波兰式和栈来完成计算。

线性表

知识点

线性表是最基础的数据结构，是元素按线性顺序排列的有限序列，主要有两种存储方式：顺序存储（数组）和链式存储（链表）。

两种存储方式对比

实际应用

• 顺序存储：程序中的数组栈队列的顺序实现，适合频繁查询的场景。
• 链式存储：链表栈/队列的链式实现，以及操作系统的内存管理文件系统的目录结构，适合频繁增删的场景。

队列和栈

知识点

核心概念辨析

特殊规则：受限双端队列（输出受限/输入受限）

题目中描述的规则属于**“输入受限的双端队列”**：

• 规则：元素从哪个端口进入，就只能从哪个端口取出（A进A出B进B出）。
• 转化：这种结构实际上等价于两个独立的栈。
  • A端口形成一个栈（ab依次入栈，只能b先出，a后出）。
  • B端口形成一个栈（cd依次入栈，只能d先出，c后出）。
• 最终结论：所有从A端进入的元素，出队顺序只能是 ...b a...所有从B端进入的元素，出队顺序只能是 ...d c...。

实际应用

• 栈：函数调用栈编辑器撤销操作表达式求值（后缀式）深度优先搜索(DFS)。
• 队列：消息队列任务调度广度优先搜索(BFS)银行叫号系统。
• 双端队列：缓存淘汰机制（如LRU）滑动窗口算法实现双端队列数据结构。

顶部 → b
        a

顶部 → d
        c

二叉树的存储和特性

知识点

1. 树的核心特性（通用树）

• 树的度：树中所有节点的度的最大值。
• 节点的度：节点拥有的子节点个数。
• 边数与节点数关系：边数 = 节点总数 - 1（树是连通无环图）。
• 总度数定理：所有节点的度之和 = 边数。

2. 二叉树的核心特性

• 二叉链表存储：每个节点有两个指针（左孩子右孩子），共 2k 个指针（k 为节点数）。
• 空指针数：k 个节点的二叉树，边数为 k-1，即有 k-1 个非空指针，因此空指针数 = 2k - (k-1) = k+1。
• 满二叉树/完全二叉树：特殊结构，常考性质如叶子节点数节点编号规则。

3. 实际应用

• 二叉链表：实现二叉树的链式存储，是所有二叉树算法（遍历查找平衡树）的基础。
• 树的度计算：用于解决节点数边数叶子数相关的计算题，是数据结构考试的高频考点。

二叉树遍历

什么是二叉树

二叉树是一种树形数据结构，每个节点最多有两个子节点，分别叫左子节点和右子节点。整棵树从最顶上的根节点开始，向下延伸。

三种遍历方式

遍历就是按照某种规则把二叉树的所有节点访问一遍。三种遍历方式的规则如下，记忆口诀是看"根"在什么位置：

从先序和中序还原二叉树的方法

先序遍历的第一个节点一定是根节点。找到根节点后，在中序遍历里定位根节点的位置，根节点左边的所有节点构成左子树，右边的所有节点构成右子树。然后对左子树和右子树各自递归重复这个过程，直到还原出完整的树结构。

实际应用

编译器在处理表达式时会构建语法树，后序遍历语法树就能得到逆波兰表达式（后缀表达式），方便计算机计算。文件系统的目录树删除操作也是用后序遍历，先删子文件夹再删父文件夹，确保不遗漏。

digraph bst_rule {
    node [shape=circle style=filled fillcolor=lightyellow]
    X [label="节点X"]
    L [label="左子树\n所有值 < X" shape=box fillcolor=lightblue]
    R [label="右子树\n所有值 > X" shape=box fillcolor=red]
    X -> L
    X -> R
}

哈夫曼树

什么是哈夫曼树

哈夫曼树（Huffman Tree）也叫最优二叉树，是一种根据字符出现频率构造的特殊二叉树。频率高的字符用短编码，频率低的字符用长编码，这样整体编码长度最短，达到压缩的目的。ZIPJPEG 等压缩格式都用到了哈夫曼编码的思想。

构造哈夫曼树的步骤

第一步，把所有字符的频率看作独立的叶子节点，放入一个集合。

第二步，每次从集合里取出频率最小的两个节点，把它们合并成一个新节点，新节点的频率等于两个子节点频率之和。规则是频率小的放左边，频率大的放右边（左小右大）。

第三步，把新节点放回集合，重复第二步，直到集合里只剩一个节点，那就是根节点。

哈夫曼编码的读取方法

从根节点出发，走左子树记 0，走右子树记 1，走到某个字符叶子节点时，路径上记录的 0 和 1 串起来就是该字符的哈夫曼编码。

哈夫曼编码的特点

哈夫曼编码是前缀码，任何一个字符的编码都不是另一个字符编码的前缀，这保证了解码时不会产生歧义。频率越高的字符编码越短，整体压缩效果最优。

实际应用

文件压缩（如 gzip）图片压缩（JPEG）网络数据传输都大量使用哈夫曼编码。比如英文文章里 e 出现频率最高，哈夫曼编码会给 e 分配最短的编码，从而大幅减少存储空间。

图的定义和存储

什么是图

图由顶点和边组成，顶点表示实体，边表示实体之间的关系。边有方向的叫有向图，没有方向的叫无向图。

邻接矩阵

用一个二维数组表示图，行和列都代表顶点，数组里的值表示两个顶点之间是否有边。有向图中，$matrix[i][j]=1$ 表示有从顶点 $i$ 到顶点 $j$ 的边。矩阵大小是顶点数 $\times$ 顶点数。

邻接链表

每个顶点对应一个链表，链表里的每个节点（表结点）代表从该顶点出发能到达的一个顶点。表结点个数等于该顶点的出度（从这个顶点出发的边的数量）。

实际应用

邻接矩阵适合稠密图（边多），查询两点间是否有边速度快。邻接链表适合稀疏图（边少），节省存储空间。导航地图社交网络好友关系都是图结构的典型应用。

拓扑排序

什么是拓扑排序

拓扑排序只能用于有向无环图（DAG，Directed Acyclic Graph），也就是有方向没有环的图。它把图中所有顶点排成一个线性序列，规则是：如果存在从顶点 v 到顶点 w 的边或路径，则 v 一定排在 w 前面。

拓扑排序的步骤

第一步，找到所有入度为 0 的顶点（没有任何边指向它的顶点），把它们作为候选起点。

第二步，从候选中选一个顶点输出，然后删除它以及从它出发的所有边。

第三步，删除后可能出现新的入度为 0 的顶点，把它们加入候选。

第四步，重复第二步和第三步，直到所有顶点都输出。

入度的概念

入度是指指向该顶点的边的数量。入度为 0 说明没有任何顶点必须排在它前面，所以它可以排在当前最前面的位置。

验证序列是否合法的技巧

从序列的第二个顶点开始，检查它是否有边指向它前面的任意顶点。如果存在这样一条边，说明它应该排在那个顶点后面，序列非法。如果所有顶点都不指向自己前面的顶点，序列合法。

实际应用

大学课程安排就是典型的拓扑排序场景，必须先修完数学才能学线性代数，先学 C 语言才能学数据结构，这种先后依赖关系就用拓扑排序来安排顺序。工程项目管理软件包依赖安装（如 npmpip）也都用到拓扑排序来确定安装顺序。

算法的效率

什么是时间复杂度

时间复杂度用来衡量一个算法随着输入规模 $n$ 增大，执行时间增长的速度。我们不关心具体跑了多少秒，只关心大致的增长趋势，用大 $O$ 符号表示。

从上到下效率越来越低，$O(1)$ 最快，$O(2^n)$ 最慢。

蛮力法的复杂度分析

蛮力法（暴力法）就是把所有可能性都试一遍。比如长度为 $n$ 的序列 X，它的子序列一共有 $2^n$ 个（每个元素选或不选），对每个子序列再去 Y 里验证是否存在需要 $O(n)$ 时间，所以总时间复杂度是 $O(n \cdot 2^n)$，写作 $O(n2^n)$。

动态规划的复杂度分析

动态规划把大问题拆成子问题，用表格记录子问题的解，避免重复计算。最长公共子序列（LCS）的动态规划算法需要填一张 $n \times n$ 的表格，每格只需要 $O(1)$ 时间计算，所以总时间复杂度是 $O(n^2)$。

最长公共子序列（LCS）的递推公式

$$C[i][j]=\begin{cases}0 & \text{若 }i=0\text{ 或 }j=0\\C[i-1,j-1]+1 & \text{若 }i,j>0\text{ 且 }X_i=Y_j\\\max(C[i-1,j],\ C[i,j-1]) & \text{其他}\end{cases}$$

含义是：如果两个序列当前末尾字符相同，公共子序列长度在 $C[i-1][j-1]$ 的基础上加 1如果不同，就取去掉其中一个字符后两种情况的最大值。

实际应用

Git 的 diff 功能（比较两个文件的差异）DNA 序列比对文本相似度计算，底层都用到了 LCS 动态规划算法。蛮力法虽然简单，但 $O(n2^n)$ 在 $n=50$ 时就已经需要计算 $50 \times 2^{50} \approx 5.6 \times 10^{16}$ 次，完全不实用。

查找算法

顺序查找

从第一个元素开始逐个比较，直到找到目标或遍历完全部。时间复杂度 $O(n)$，对有序无序表都适用。

折半查找（二分查找）

只能用于有序表。每次取当前范围的中间元素比较，目标比中间值小就去左半段，大就去右半段，每次排除一半元素。时间复杂度 $O(\log n)$。

折半查找的比较过程本质上是在一棵二叉判定树上走路径，每次比较后当前的搜索区间必须满足严格的上下界约束，后面比较到的每个值必须始终在当前合法区间内。

哈希查找（散列查找）

用散列函数 $H(key)$ 把关键码映射到表中某个位置，理想情况下直接定位，时间复杂度接近 $O(1)$。当两个不同的关键码映射到同一个位置时，发生冲突，线性探查法的解决方式是依次往后找第一个空槽存入。

实际应用

数据库的 B+ 树索引本质是多路折半查找。Python 的 dictJava 的 HashMap 都是哈希表，查找极快。DNS 域名解析也用哈希表把域名快速映射到 IP 地址。

排序算法

排序算法选择原则

选择排序方法时要根据实际情况判断：$n$ 较小时用直接插入选择或冒泡数据基本有序时用直接插入（此时近似 $O(n)$）$n$ 很大且关键字位数少时用基数排序$n$ 很大时优先用 $O(n\log_2 n)$ 的快速排序堆排序或归并排序。

各排序算法对比

堆的概念

堆是一棵完全二叉树，用数组存储，下标从 1 开始。大顶堆要求每个节点的值都大于等于其子节点，根节点是最大值。构建堆时从最后一个非叶子节点（位置 $\lfloor n/2 \rfloor$）开始，从右到左逐个做"下沉"调整。

快速排序的划分

选一个基准元素，把比它小的放左边，比它大的放右边，基准元素到达最终位置，这叫一趟划分。一趟划分需要扫描整个区间一遍，时间是 $O(n)$。

哪些排序第一趟能确定某元素的最终位置

冒泡排序第一趟结束后最大元素沉底，位置确定。简单选择排序第一趟找到最小元素放到第一位，位置确定。堆排序建堆后取出堆顶，位置确定。快速排序第一趟划分后基准元素位置确定。直接插入和归并排序第一趟后不能保证任何元素到达最终位置。

实际应用

数据库 ORDER BY 底层用归并排序（稳定且适合大数据）。Java 的 Arrays.sort() 对基本类型用快速排序，对对象用归并排序（保证稳定性）。优先队列（如任务调度）用堆实现。

digraph heap_before {
    node [shape=circle]
    1 [label="2(1)"]
    2 [label="8(2)"]
    3 [label="7(3)"]
    4 [label="1(4)"]
    5 [label="3(5)"]
    6 [label="5(6)"]
    7 [label="6(7)"]
    8 [label="4(8)"]
    1->2 1->3
    2->4 2->5
    3->6 3->7
    4->8
}

digraph heap_after {
    node [shape=circle style=filled fillcolor=lightblue]
    r [label="8"]
    n4 [label="4"]
    n7 [label="7"]
    n2 [label="2"]
    n3 [label="3"]
    n5 [label="5"]
    n6 [label="6"]
    n1 [label="1"]
    r->n4 r->n7
    n4->n2 n4->n3
    n7->n5 n7->n6
    n2->n1
}

信息安全基础知识

信息安全的三个核心属性（CIA三角）

其他重要安全属性

不可抵赖性（也叫不可否认性）：通信双方不能事后否认自己发送或接收过某条消息，通过数字签名实现。

可认证性：能够验证通信方的真实身份，通过数字证书实现。

实际应用

银行系统要保证转账金额不被篡改（完整性）医疗记录不能被无关人员查看（保密性）电商平台要保证用户下单后商家无法否认（不可抵赖性）。

加密技术与认证技术

对称加密与非对称加密

数字证书

数字证书由权威的第三方机构（CA，证书颁发机构）签发，里面包含用户的公钥和身份信息。其他人通过验证证书来确认"这个公钥确实属于这个人"，解决了公钥的真实性问题，用于身份认证。

数字签名

数字签名用发送方的私钥对消息（或其哈希值）进行加密生成签名，接收方用发送方的公钥验证。因为私钥只有发送方持有，所以签名无法伪造，发送方也无法事后否认，用于保证不可抵赖性。

digraph digital_sign {
    rankdir=LR
    node [shape=box]
    A [label="发送方A"]
    B [label="接收方B"]
    sign [label="用A的私钥\n对消息签名"]
    verify [label="用A的公钥\n验证签名"]
    A -> sign -> B -> verify
    verify -> ok [label="验证通过\n=身份确认+不可否认"]
    ok [label="不可抵赖\n✓" shape=ellipse style=filled fillcolor=lightgreen]
}

数字证书 vs 数字签名的区别

数字证书解决的是"你是谁"的问题（身份认证），数字签名解决的是"这消息确实是你发的"的问题（不可抵赖）。

实际应用

HTTPS 网站用数字证书让浏览器确认服务器身份。电子合同用数字签名保证签名方无法否认。网上银行同时用两者：证书认证身份，签名保证交易不可抵赖。