数制
- 位权
- 二进制 2k，八进制 8k，十六进制 16k
- 转为十进制
- Σ dk·bk
- 从十进制转换
- 除以基数，余数从下往上读
- 十六进制 ↔ 二进制
- 一位十六进制数 = 4 位二进制
- 二进制补码
- 按位取反后加 1
计算机科学导论：速成包
公式表、每个专题的关键方法步骤和 20 道练习题，完整解答附在最后。
1公式与方法
命题逻辑与证明
- 真值表的行数
- 2ⁿ
- 蕴涵
- p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
- 蕴涵的否定
- ¬(p → q) ≡ p ∧ ¬q
- 双条件
- p ↔ q ≡ (p → q) ∧ (q → p)
- 德摩根律
- ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
- 分配律
- p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
- 量词的否定
- ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
- 肯定前件，否定后件
- p → q, p ⊢ q; p → q, ¬q ⊢ ¬p
方法
- 数一数不同变量的个数：真值表有 2ⁿ 行，从全为 1 的一行开始。
- 给每个子公式单独一列，由内向外逐列填写。
- 按各联结词的规则计算：→ 只有在 1 → 0 时为 0，↔ 在两边相同时为 1。
- 判断等价时，逐行比较最后一列；判断论证时，只看所有前提都为 1 的那些行。
- 否定带量词的命题时，把 ¬ 移到内部，交换 ∀ 和 ∃，并否定内部的公式。
数字逻辑：门电路、卡诺图与触发器
- 基本逻辑门
- A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B
- 布尔规则
- X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X
- 德摩根律
- (X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
- 卡诺图的顺序
- 00, 01, 11, 10 (Gray code)
- 由 2ᵏ 个格子组成的圈
- 消去 k 个变量
- 4 选 1 多路选择器
- F = A′B′I0 + A′BI1 + AB′I2 + ABI3
- 触发器
- D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
- 计数器
- n 位：2ⁿ 个状态； 模 N：满足 2ⁿ ≥ N 的最小 n； fout = fclk/N
- 行波计数器
- fmax = 1/(n·tpd)
- 环形计数器与约翰逊计数器
- n 个和 2n 个状态
方法
- 对于电路，从输入到输出一个门一个门地分析，并在每根线上写出值；或者写出它的表达式并填写真值表。
- 化简时，把 1（以及标为 X 的无关项）填入行列按格雷码 00, 01, 11, 10 排列的卡诺图。
- 用尽可能少而大的圈（由 1、2、4、8 或 16 个格子组成）覆盖所有 1，可以绕过边界；每个圈对应一个乘积项，由保持不变的变量构成。求 POS 形式时圈 0。
- 对于触发器和计数器，在每个有效时钟边沿读取输入，写出每个边沿之后的状态，并记住 n 位计数器在 2ⁿ 个状态之后回绕。
数论与模运算
- 带余除法
- a = q·n + r, 0 ≤ r < n
- 欧几里得
- gcd(a, b) = gcd(b, a mod b)
- 最小公倍数
- lcm(a, b) = a·b/gcd(a, b)
- 逆矩阵
- a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
- 线性同余方程
- a·x ≡ b → x ≡ a⁻¹·b (mod n)
- 欧拉函数
- φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
- 费马
- aᵖ⁻¹ ≡ 1 (mod p)
- RSA
- n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
方法
- 先把每个数对 n 取模；余数在 0 到 n − 1 之间。
- 求最大公约数时，用欧几里得算法反复做除法；最后一个非零余数就是最大公约数。
- 求逆元时，运行扩展算法并保留 a 的系数；若为负数则加上 n。
- 解 a·x ≡ b 时，两边乘以 a⁻¹；合并两个同余式时，写成 x = r₁ + m₁k。
- 求幂时，把指数写成二进制并反复平方；在 RSA 中，d = e⁻¹ mod φ(n)，其中 φ(n) = (p − 1)(q − 1)。
图论
- 握手引理
- Σ deg(v) = 2|E|
- 完全图
- |E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
- 正则图
- |E| = n·k/2
- 树与森林
- |E| = n − 1, |E| = n − c
- 树的叶子
- L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
- 欧拉
- 回路：所有顶点度数为偶数； 通路：恰有 2 个奇度顶点
- Kn 中的哈密顿回路
- (n − 1)!/2
- 迪杰斯特拉更新
- d(v) = min(d(v), d(u) + w(u, v))
- 长度为 L 的途径
- (Mᴸ)ij
方法
- 写出每个顶点的度数；所有度数之和等于边数的两倍。
- 对于欧拉问题，先检查图是否连通，再数一数奇度顶点的个数。
- 对于树，利用 n − 1 条边和握手引理。
- 对于迪杰斯特拉算法，保留一张暂定距离表，每一轮确定未确定顶点中距离最小的那个。
- 对于最小生成树，把边按权重排序，跳过每条会形成圈的边（克鲁斯卡尔算法），或者从一个起点出发扩展一棵树（普里姆算法）。
IPv4 子网划分
- 每个子网的主机数
- 2(32 − prefix) − 2 (/31: 2, /32: 1)
- 块大小
- 256 − (mask octet)
- 网络地址
- IP AND 掩码
- 广播地址
- IP OR (NOT 掩码)：主机位全部置 1
- 借用 n 位得到的子网数
- 2n
2练习题
1.数制中等
设置各位，使其以 8 位补码存储 −15。按无符号数读取，该位模式的值 U 是多少？
N = −158 bit
U =
2.数制困难
把各位设置为 1100 1110 AND 0101 0110 的 8 位结果。该结果的十进制值 R 是多少？
1100 1110AND0101 0110
R =
3.命题逻辑与证明中等
哪个公式与 b ∨ (a ∧ c) 在逻辑上等价？点选它。
b ∨ (a ∧ c)
- 1(b ∧ a) ∨ (b ∧ c)
- 2b ∧ (a ∨ c)
- 3(b ∨ a) ∧ c
- 4(b ∨ a) ∧ (b ∨ c)
4.命题逻辑与证明困难
把否定完全移到内部之后，哪个命题与 ¬∃x (F(x) ∧ G(x)) 等价？点选它。
¬∃x (F(x) ∧ G(x))
- 1∀x (F(x) ∧ ¬G(x))
- 2∃x (¬F(x) ∧ ¬G(x))
- 3∀x (F(x) → ¬G(x))
- 4∀x (¬F(x) ∧ ¬G(x))
5.数字逻辑：门电路、卡诺图与触发器中等
用卡诺图求 F(A, B, C, D) = Σm(7, 8, 9, 10, 11, 15) 的最简和之积 (POS) 形式。它有多少个和项（因子）N？
F(A, B, C, D) = Σm(7, 8, 9, 10, 11, 15)
N =
6.数字逻辑：门电路、卡诺图与触发器困难
一个 5 位行波（异步）计数器由传播延迟均为 20 ns 的触发器构成。所有输出必须在下一个时钟边沿之前稳定下来。求最高时钟频率 fmax。
n = 5tpd = 20 ns
fmax = MHz
7.数论与模运算中等
解 19x ≡ 21 (mod 23)。给出满足 0 < x < 23 的解 x。
19x ≡ 21 (mod 23)
x =
8.数论与模运算困难
某个 RSA 密钥使用素数 p = 19 和 q = 37，公钥指数 e = 23。求私钥指数 d（0 < d < φ(n)）。
p = 19q = 37e = 23
d =
9.算法与复杂度中等
贪心算法（greedy algorithm）：
- A尝试所有可能的解
- B在每一步都做出局部最优的选择
- C总能给出最优解
- D只使用递归
10.算法与复杂度困难
用自底向上的方法从 n 个无序元素构建二叉堆的时间复杂度是多少？
- AO(log n)
- BO(n log n)
- CO(n²)
- DO(n)
11.数据结构中等
为什么在实践中遍历数组往往比遍历同样长度的链表快得多？
- A数组遍历总共是 O(1)，而链表遍历是 O(n)
- B数组元素是连续存放的，因此能很好地利用 CPU 缓存
- C链表总是把元素存储在磁盘上
- D数组比较数值所用的指令更少
12.数据结构困难
一个动态数组在满时容量翻倍。为什么许多实现只在它只有四分之一满时才缩容，而不是一半满时？
- A为了使数组保持有序
- B因为在一半满时减半会丢失元素
- C为了避免在边界附近交替进行 push 和 pop 时反复调整大小
- D因为内存分配器只能以块的四分之一为单位释放内存
13.图论中等
这个连通图有欧拉回路、有不是回路的欧拉通路，还是两者都没有？点选你的答案。
|V| = 7|E| = 9
- 1欧拉回路
- 2有欧拉通路，无回路
- 3都不是
14.图论困难
用迪杰斯特拉算法求带权图中从 A 到 F 的最短路径的长度 d(F)。
起点：A终点：F
d(F) =
15.数据库与 SQL中等
一个表在每一行订单上都存储了客户地址。只修改其中一行的地址而不修改其他行，这是哪种情况的例子？
- A幻读
- B删除异常
- C更新异常
- D插入异常
16.数据库与 SQL困难
哪个窗口函数在每个分区内为行分配 1、2、3……且不出现并列？
- ARANK()
- BROW_NUMBER()
- CDENSE_RANK()
- DCOUNT()
17.计算机网络中等
以太网帧中的循环冗余校验（CRC）用于什么？
- A加密该帧
- B自动纠正每一个比特错误
- C检测传输差错
- D选择最佳路由
18.计算机网络困难
标准以太网（Ethernet）载荷的最大传输单元（MTU）是多少？
- A在所有网络中均为 9000 字节
- B65,535 字节
- C1500 字节
- D64 字节
19.IPv4 子网划分中等
一个子网使用掩码 255.255.255.224。它有多少个可用主机地址 H？
255.255.255.224
H =
20.IPv4 子网划分困难
某主机地址为 10.20.251.238/28。其子网广播地址的最后一个数（第四个八位组）x 是多少？
10.20.251.238/28
x =
3溶液
1.数制
答案: U = 241
设置比特位：每一位对应 2 的一个幂（128、64、…、1）。一个十六进制数字恰好是四位，在 8 位补码中最左边的位权重为 −128。按位运算对每个位位置分别进行。
取反加一
15 = 0000 1111
取反后: 1111 0000
+1 → 1111 0001
按无符号数读取
1111 0001₂ = 256 − 15 = 241
答案
U = 241
2.数制
答案: R = 70
设置比特位：每一位对应 2 的一个幂（128、64、…、1）。一个十六进制数字恰好是四位，在 8 位补码中最左边的位权重为 −128。按位运算对每个位位置分别进行。
逐位计算
AND 只有在两位都为 1 时才得 1。
1100 1110
AND 0101 0110
= 0100 0110
结果的值
0100 0110₂ = 70
答案
R = 70
3.命题逻辑与证明
答案: (b ∨ a) ∧ (b ∨ c)
逻辑等价：两个公式在真值表的每一行取值都相同时，它们是等价（≡）的。重言式在每一行都为 1，矛盾式在每一行都为 0，偶然式则两者都不是。常用定律：德摩根律，¬(a ∧ b) ≡ ¬a ∨ ¬b 和 ¬(a ∨ b) ≡ ¬a ∧ ¬b；a → b ≡ ¬a ∨ b ≡ ¬b → ¬a（逆否命题）；¬(a → b) ≡ a ∧ ¬b；以及分配律，a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)。
定律
∨ 对 ∧ 有分配律：a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)。
b ∨ (a ∧ c) ≡ (b ∨ a) ∧ (b ∨ c)
用真值表检验
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 0 1
a = 1, b = 0, c = 1: 1 | 0 0 1 1
a = 1, b = 0, c = 0: 0 | 0 0 0 0
a = 0, b = 1, c = 1: 1 | 1 1 1 1
a = 0, b = 1, c = 0: 1 | 0 0 0 1
a = 0, b = 0, c = 1: 0 | 0 0 0 0
a = 0, b = 0, c = 0: 0 | 0 0 0 0
答案
(b ∨ a) ∧ (b ∨ c)
竖线之后的各列是按所示顺序排列的各个选项。
4.命题逻辑与证明
答案: ∀x (F(x) → ¬G(x))
量词与论证：¬∀x P(x) ≡ ∃x ¬P(x)，¬∃x P(x) ≡ ∀x ¬P(x)。把否定向内移动，交换它经过的每个量词，并用命题逻辑的定律否定内部的公式，例如 ¬(a → b) ≡ a ∧ ¬b。当所有前提为 1 的每一行中结论也为 1 时，论证是有效的。只要有一行前提为真而结论为假，它就是反例，说明论证无效。
把否定移到内部
¬∃x (F(x) ∧ G(x)) ≡ ∀x (F(x) → ¬G(x))
答案
∀x (F(x) → ¬G(x))
其他选项要么保持某个量词不变，要么改变了量词的顺序，要么错误地否定了内部的公式。
5.数字逻辑：门电路、卡诺图与触发器
答案: N = 3
卡诺图：各格按格雷码（00, 01, 11, 10）排列，所以相邻的格子（包括跨越边界的格子）恰好只有一个变量不同。把 1 圈成由 1、2、4、8 或 16 个格子组成的矩形，圈尽可能大、尽可能少，直到每个 1 都被覆盖。每个圈对应一个乘积项：圈内保持不变的变量。由 2ᵏ 个格子组成的圈会消去 k 个变量。无关项 (X) 可用来使圈变大，但不必被覆盖。改为圈 0 则得到最简 POS 形式。
圈 0
每个圈都是由 2ᵏ 个格子组成的矩形；边上的格子与对边上的格子相邻。
(B′ + D)
(B′ + C)
(A + B)
最简 POS 形式
F = (B′ + D)(B′ + C)(A + B)
N = 3
答案
N = 3
6.数字逻辑：门电路、卡诺图与触发器
答案: fmax = 10 MHz
触发器与计数器：触发器只在时钟的有效边沿改变。D 复制其输入 (Q⁺ = D)；T 在 T = 1 时翻转；JK 在 00 时保持，01 时复位，10 时置位，11 时翻转。n 位二进制计数器有 2ⁿ 个状态，按模 2ⁿ 计数；模 N 计数器依次计 0, 1, …, N − 1 然后回到 0，需要满足 2ⁿ ≥ N 的最小 n 个触发器。行波计数器的每一级使频率减半，所以模 N 计数器的最后一级输出频率为 fclk/N。n 个触发器的约翰逊计数器有 2n 个状态，环形计数器有 n 个。
最坏情况的稳定时间
T = 5·20 ns = 100 ns
最高频率
fmax = 1/100 ns = 10 MHz
答案
fmax = 10 MHz
7.数论与模运算
答案: x = 12
逆元与同余式：a 模 n 有逆元，当且仅当 gcd(a, n) = 1。扩展欧几里得算法把 1 写成 s·n + t·a，于是 a⁻¹ ≡ t (mod n)。当 gcd(a, n) = 1 时，同余式 a·x ≡ b (mod n) 的解为 x ≡ a⁻¹·b。模数互素的两个同余式 x ≡ r₁ (mod m₁) 和 x ≡ r₂ (mod m₂) 在模 m₁·m₂ 下有唯一解（中国剩余定理）。欧拉函数 φ(n) 表示 1 到 n 中与 n 互素的数的个数：φ(n) = n·∏(1 − 1/p)。
19 的逆元
r = 23, t = 0
r = 19, q = 1, t = 1
r = 4, q = 4, t = −1
r = 3, q = 1, t = 5
r = 1, q = 3, t = −6
19−1 ≡ 17 (mod 23)
求解
x ≡ 17·21 = 357 ≡ 12 (mod 23)
校核: 19·12 = 228 ≡ 21 (mod 23)
答案
x = 12
8.数论与模运算
答案: d = 479
模幂与 RSA：用反复平方法计算 aᵏ mod n：把 k 写成二进制，平方，每一步之后取模，并把对应二进制位为 1 的幂相乘。费马：对不整除 a 的素数 p，aᵖ⁻¹ ≡ 1 (mod p)，所以指数可以对 p − 1 取模。RSA：选取素数 p 和 q，n = p·q，φ(n) = (p − 1)(q − 1)；公钥指数 e 与 φ(n) 互素，私钥指数为 d = e⁻¹ mod φ(n)。用 c = mᵉ mod n 加密，用 m = cᵈ mod n 解密。
模数与欧拉函数值
n = 19·37 = 703
φ(n) = 18·36 = 648
扩展欧几里得算法
r = 648, t = 0
r = 23, q = 28, t = 1
r = 4, q = 5, t = −28
r = 3, q = 1, t = 141
r = 1, q = 3, t = −169
私钥指数
d = 479
校核: 23·479 = 11017 = 17·648 + 1
答案
d = 479
9.算法与复杂度
答案: B · 在每一步都做出局部最优的选择
为什么是这个答案
贪心算法速度快，对某些问题是最优的（例如 Dijkstra、Huffman 编码），但一般情况下并非如此（例如某些硬币体系下的找零问题）。
答案
B · 在每一步都做出局部最优的选择
10.算法与复杂度
答案: D · O(n)
为什么是这个答案
对各层的下沉代价求和得到一个收敛级数，因此建堆（heapify）在线性时间内完成。
答案
D · O(n)
11.数据结构
答案: B · 数组元素是连续存放的，因此能很好地利用 CPU 缓存
为什么是这个答案
连续的内存带来良好的引用局部性，而链表节点可能分散各处，导致大量缓存未命中。
答案
B · 数组元素是连续存放的，因此能很好地利用 CPU 缓存
12.数据结构
答案: C · 为了避免在边界附近交替进行 push 和 pop 时反复调整大小
为什么是这个答案
在一半满时缩容，可能使这样的操作序列中每次操作都触发一次调整大小；1/4 与满之间的间隔使均摊代价保持在 O(1)。
答案
C · 为了避免在边界附近交替进行 push 和 pop 时反复调整大小
13.图论
答案: 都不是
欧拉、哈密顿与树：连通图在每个顶点度数都为偶数时有欧拉回路（每条边经过一次，回到起点），在恰有两个顶点度数为奇数时有不是回路的欧拉通路；此时通路从一个奇度顶点走到另一个奇度顶点。哈密顿回路恰好经过每个顶点一次；Kn 有 (n − 1)!/2 条。n 个顶点的树有 n − 1 条边，有 m 条边的连通图在去掉 m − n + 1 条边后保留一棵生成树。
度
deg(A) = 1, deg(B) = 4, deg(C) = 3, deg(D) = 3, deg(E) = 3, deg(F) = 2, deg(G) = 2
奇度顶点
A, C, D, E → 4
都不是
答案
都不是
14.图论
答案: d(F) = 17
最短路径与生成树：迪杰斯特拉算法每一轮确定一个顶点：暂定距离最小的未确定顶点。它的距离随即成为最终值，并且每个邻点 v 得到 d(v) = min(d(v), d(u) + w(u, v))。克鲁斯卡尔算法按从轻到重的顺序取边并跳过会形成圈的边，从而构造最小生成树；普里姆算法从一个起点出发扩展一棵树，每次加入离开这棵树的最轻的边。n 个顶点的生成树有 n − 1 条边。
迪杰斯特拉算法逐轮过程
每一行：被确定的顶点、它的最终距离，以及距离得到改进的邻点。
A (0): B: 5, C: 10
B (5): D: 20, G: 19
C (10): E: 12, G: 15
E (12): D: 13, F: 22
D (13): F: 17
G (15)
F (17)
最短路径
A → C → E → D → F
d(F) = 17
答案
d(F) = 17
15.数据库与 SQL
答案: C · 更新异常
为什么是这个答案
冗余存储意味着一次更改必须在许多行中进行；漏改一些就会使数据不一致，而规范化可以防止这种情况。
答案
C · 更新异常
16.数据库与 SQL
答案: B · ROW_NUMBER()
为什么是这个答案
ROW_NUMBER 生成唯一的连续编号；RANK 在并列之后会留下间隔；DENSE_RANK 则不会。
答案
B · ROW_NUMBER()
17.计算机网络
答案: C · 检测传输差错
为什么是这个答案
发送方对帧计算 CRC；接收方重新计算，若两者不同就丢弃该帧。CRC 能检测差错，但不能纠正差错。
答案
C · 检测传输差错
18.计算机网络
答案: C · 1500 字节
为什么是这个答案
标准以太网最多承载 1500 字节的载荷；更大的 IP 数据包必须分片或使用路径 MTU 发现（path MTU discovery）。
答案
C · 1500 字节
19.IPv4 子网划分
答案: H = 30
IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).
前缀长度
255.255.255.224 = /27
可用主机数
25 − 2 = 30
答案
H = 30
20.IPv4 子网划分
答案: x = 239
IPv4 子网划分：一个地址有 32 位。前缀 /p 表示前面多少位标识网络；其余 32 − p 位为主机编号。一个子网有 2³²⁻ᵖ 个地址，但第一个（网络地址）和最后一个（广播地址）不能分配给主机，所以可容纳 2³²⁻ᵖ − 2 台主机。 例外：/31（点对点链路，RFC 3021）的 2 个地址都用于主机，/32 只有一个地址（单个主机或环回地址）。
块大小
24 = 16
该主机所在子网
网络: ⌊238/16⌋·16 = 224
广播: 224 + 16 − 1 = 239
可用主机: 225 … 238
答案
x = 239
ExamProblems · examproblems.com/courses/computer-science-fundamentals