计算机科学导论：速成包

公式表、每个专题的关键方法步骤和 20 道练习题，完整解答附在最后。

新题目返回课程

在打印窗口中选择“另存为 PDF”，即可在设备上保存一份副本。

1公式与方法

数制

位权
二进制 2k，八进制 8k，十六进制 16k
转为十进制
Σ dk·bk
从十进制转换
除以基数，余数从下往上读
十六进制 ↔ 二进制
一位十六进制数 = 4 位二进制
二进制补码
按位取反后加 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

方法

  1. 数一数不同变量的个数：真值表有 2ⁿ 行，从全为 1 的一行开始。
  2. 给每个子公式单独一列，由内向外逐列填写。
  3. 按各联结词的规则计算：→ 只有在 1 → 0 时为 0，↔ 在两边相同时为 1。
  4. 判断等价时，逐行比较最后一列；判断论证时，只看所有前提都为 1 的那些行。
  5. 否定带量词的命题时，把 ¬ 移到内部，交换 ∀ 和 ∃，并否定内部的公式。

数字逻辑：门电路、卡诺图与触发器

基本逻辑门
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. 对于电路，从输入到输出一个门一个门地分析，并在每根线上写出值；或者写出它的表达式并填写真值表。
  2. 化简时，把 1（以及标为 X 的无关项）填入行列按格雷码 00, 01, 11, 10 排列的卡诺图。
  3. 用尽可能少而大的圈（由 1、2、4、8 或 16 个格子组成）覆盖所有 1，可以绕过边界；每个圈对应一个乘积项，由保持不变的变量构成。求 POS 形式时圈 0。
  4. 对于触发器和计数器，在每个有效时钟边沿读取输入，写出每个边沿之后的状态，并记住 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

方法

  1. 先把每个数对 n 取模；余数在 0 到 n − 1 之间。
  2. 求最大公约数时，用欧几里得算法反复做除法；最后一个非零余数就是最大公约数。
  3. 求逆元时，运行扩展算法并保留 a 的系数；若为负数则加上 n。
  4. 解 a·x ≡ b 时，两边乘以 a⁻¹；合并两个同余式时，写成 x = r₁ + m₁k。
  5. 求幂时，把指数写成二进制并反复平方；在 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

方法

  1. 写出每个顶点的度数；所有度数之和等于边数的两倍。
  2. 对于欧拉问题，先检查图是否连通，再数一数奇度顶点的个数。
  3. 对于树，利用 n − 1 条边和握手引理。
  4. 对于迪杰斯特拉算法，保留一张暂定距离表，每一轮确定未确定顶点中距离最小的那个。
  5. 对于最小生成树，把边按权重排序，跳过每条会形成圈的边（克鲁斯卡尔算法），或者从一个起点出发扩展一棵树（普里姆算法）。

IPv4 子网划分

每个子网的主机数
2(32 − prefix) − 2 (/31: 2, /32: 1)
块大小
256 − (mask octet)
网络地址
IP AND 掩码
广播地址
IP OR (NOT 掩码)：主机位全部置 1
借用 n 位得到的子网数
2n

2练习题

1.数制中等
补码中的位权1−12816403201608141201

8 位模式 1100 0110 以补码形式存储一个有符号整数。它的十进制值 N 是多少？

1100 01108 bit
N =
2.数制困难
点击各位来设置012806403201608040201

把各位设置为 0101 0011 XOR 1001 0101 的 8 位结果。该结果的十进制值 R 是多少？

0101 0011XOR1001 0101
R =
3.命题逻辑与证明中等
¬b ∨ cb ∨ ¬c¬b ∧ c¬b → ¬c

哪个公式与 b → c 在逻辑上等价？点选它。

b → c
  1. 1¬b ∨ c
  2. 2b ∨ ¬c
  3. 3¬b ∧ c
  4. 4¬b → ¬c
4.命题逻辑与证明困难
∃y ∀x ¬R(x, y)∃x ∀y ¬R(x, y)∀x ∃y ¬R(x, y)∀x ∀y ¬R(x, y)

把否定完全移到内部之后，哪个命题与 ¬∀x ∃y R(x, y) 等价？点选它。

¬∀x ∃y R(x, y)
  1. 1∃y ∀x ¬R(x, y)
  2. 2∃x ∀y ¬R(x, y)
  3. 3∀x ∃y ¬R(x, y)
  4. 4∀x ∀y ¬R(x, y)
5.数字逻辑：门电路、卡诺图与触发器中等
ABCD00011110000111101111111111

在这个卡诺图中，恰有一个 1 没有相邻的 1，所以它在最简 SOP 形式中仍是单个格子的圈（含四个文字的完整最小项）。跨越卡诺图边界的相邻关系也要计入。点选该格子。

F = Σm(1, 5, 6, 8, 9, 10, 11, 12, 13, 15)
  1. 1AB = 00, CD = 00
  2. 2AB = 00, CD = 01
  3. 3AB = 00, CD = 11
  4. 4AB = 00, CD = 10
  5. 5AB = 01, CD = 00
  6. 6AB = 01, CD = 01
  7. 7AB = 01, CD = 11
  8. 8AB = 01, CD = 10
  9. 9AB = 11, CD = 00
  10. 10AB = 11, CD = 01
  11. 11AB = 11, CD = 11
  12. 12AB = 11, CD = 10
  13. 13AB = 10, CD = 00
  14. 14AB = 10, CD = 01
  15. 15AB = 10, CD = 11
  16. 16AB = 10, CD = 10
6.数字逻辑：门电路、卡诺图与触发器困难
CLKJK12345678

一个上升沿触发的 JK 触发器从 Q = 0 开始，在 8 个时钟上升沿接收到所示的输入。Q 改变状态的次数 N 是多少？

Q₀ = 0JK
N =
7.数论与模运算中等

求 10 模 13 的逆元：满足 0 < x < 13 且 10·x ≡ 1 (mod 13) 的数 x。

a = 10n = 13
10−1 mod 13 =
8.数论与模运算困难

解 32x ≡ 40 (mod 52)。给出最小的正解 x。

32x ≡ 40 (mod 52)
x =
9.算法与复杂度中等

朴素递归斐波那契（fib(n) = fib(n−1) + fib(n−2)）的时间复杂度是：

  1. A常数
  2. B对数级
  3. C线性
  4. D指数级
10.算法与复杂度困难

用一个只保留最后两个值的循环计算第 n 个斐波那契数，时间和空间代价各是多少？

  1. AO(log n) 时间和 O(n) 空间
  2. BO(n) 时间和 O(1) 空间
  3. CO(n) 时间和 O(n) 空间
  4. DO(2ⁿ) 时间和 O(1) 空间
11.数据结构中等

为什么在实践中遍历数组往往比遍历同样长度的链表快得多？

  1. A链表总是把元素存储在磁盘上
  2. B数组遍历总共是 O(1)，而链表遍历是 O(n)
  3. C数组元素是连续存放的，因此能很好地利用 CPU 缓存
  4. D数组比较数值所用的指令更少
12.数据结构困难

伸展树（splay tree）在每次访问之后做什么？

  1. A通过旋转把被访问的节点移到根
  2. B把被访问的节点移到叶子
  3. C对查找路径上的节点重新着色
  4. D把整棵树重建成平衡形式
13.图论中等

一个连通图有 19 个顶点和 24 条边。必须去掉多少条边 k 才能剩下一棵生成树？

|V| = 19|E| = 24
k =
14.图论困难
121671018196ABCDE

普里姆算法从顶点 A 出发构造最小生成树。点选它加入的第 4 条边。

起点：Ak = 4
  1. 1边 AB
  2. 2边 AC
  3. 3边 BC
  4. 4边 BD
  5. 5边 CE
  6. 6边 DE
  7. 7边 BE
15.数据库与 SQL中等

一个外键声明了 ON DELETE CASCADE。删除父行时会发生什么？

  1. A删除总是被拒绝
  2. B引用它的子行会被自动删除
  3. C父行被复制到归档表中
  4. D子行中的外键自动被设为 NULL
16.数据库与 SQL困难

在 (last_name, first_name) 上有一个复合索引。哪个条件能最有效地利用它？

  1. AWHERE last_name = 'Jansen'
  2. BWHERE first_name LIKE '%a'
  3. CWHERE UPPER(first_name) = 'EVA'
  4. DWHERE first_name = 'Eva'
17.计算机网络中等

IPv4 首部中的哪个字段能防止数据包在路由环路中无限循环？

  1. A服务类型
  2. B生存时间（TTL）
  3. C首部校验和
  4. D标识
18.计算机网络困难

为什么先关闭 TCP 连接的一方要在 TIME_WAIT 状态停留两倍的最大报文段寿命？

  1. A等待 DNS 缓存过期
  2. B让延迟的段消亡，并在最后的 ACK 丢失时能够重发
  3. C让沿途的路由器为下一次连接更新其路由表
  4. D保留加密密钥以便日后重用
19.IPv4 子网划分中等
/?11111111111111111111111000000000网络位主机位

某部门在一个子网内需要 421 个主机地址。足够使用的最长前缀 p（最小子网）是多少？

421 hosts
p =
20.IPv4 子网划分困难
最后一个八位组 = 220112816403211618140201网络主机

某主机地址为 10.20.207.220/29。其网络地址的第四个八位组 x 是多少？

10.20.207.220/29
x =

3溶液

1.数制

答案: N = −58

位置计数制：每个数位的值等于该数字乘以基数的某次幂。二进制各位的权为 1、2、4、8、16、……；十六进制为 1、16、256、……，A–F 代表 10–15。在 8 位补码中，最左边一位的权是 −128 而不是 +128，负数就是这样存储的。

位权相加

其余各位保持正常的正权值。

−128 + 64 + 4 + 2 = −58

答案

N = −58
2.数制

答案: R = 198

设置比特位：每一位对应 2 的一个幂（128、64、…、1）。一个十六进制数字恰好是四位，在 8 位补码中最左边的位权重为 −128。按位运算对每个位位置分别进行。

逐位计算

XOR 在两位不同时得 1。

0101 0011
XOR 1001 0101
= 1100 0110

结果的值

1100 0110₂ = 198

答案

R = 198
3.命题逻辑与证明

答案: ¬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 只有在 a = 1 且 b = 0 时才为 0，所以它与 ¬a ∨ b 相同。
b → c ≡ ¬b ∨ c

用真值表检验

b = 1, c = 1: 1 | 1 1 0 1
b = 1, c = 0: 0 | 0 1 0 1
b = 0, c = 1: 1 | 1 0 1 0
b = 0, c = 0: 1 | 1 1 0 1

答案

¬b ∨ c

竖线之后的各列是按所示顺序排列的各个选项。

4.命题逻辑与证明

答案: ∃x ∀y ¬R(x, y)

量词与论证：¬∀x P(x) ≡ ∃x ¬P(x)，¬∃x P(x) ≡ ∀x ¬P(x)。把否定向内移动，交换它经过的每个量词，并用命题逻辑的定律否定内部的公式，例如 ¬(a → b) ≡ a ∧ ¬b。当所有前提为 1 的每一行中结论也为 1 时，论证是有效的。只要有一行前提为真而结论为假，它就是反例，说明论证无效。

把否定移到内部

¬∀x ∃y R(x, y) ≡ ∃x ∀y ¬R(x, y)

答案

∃x ∀y ¬R(x, y)

其他选项要么保持某个量词不变，要么改变了量词的顺序，要么错误地否定了内部的公式。

5.数字逻辑：门电路、卡诺图与触发器

答案: AB = 01, CD = 10

卡诺图：各格按格雷码（00, 01, 11, 10）排列，所以相邻的格子（包括跨越边界的格子）恰好只有一个变量不同。把 1 圈成由 1、2、4、8 或 16 个格子组成的矩形，圈尽可能大、尽可能少，直到每个 1 都被覆盖。每个圈对应一个乘积项：圈内保持不变的变量。由 2ᵏ 个格子组成的圈会消去 k 个变量。无关项 (X) 可用来使圈变大，但不必被覆盖。改为圈 0 则得到最简 POS 形式。

每个 1 的邻格

有相邻 1 的 1 可以加入由两个或更多格子组成的圈。

m6: m7, m4, m2, m14 → 0
ABCD00011110000111101111111111

孤立的 1

m6 = A′BCD′ → AB = 01, CD = 10

答案

AB = 01, CD = 10
6.数字逻辑：门电路、卡诺图与触发器

答案: N = 3

触发器与计数器：触发器只在时钟的有效边沿改变。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 个。

每个边沿之后的 Q

JK 触发器：00 保持，01 复位 (Q = 0)，10 置位 (Q = 1)，11 翻转。

1: J = 1, K = 1 → Q = 1
2: J = 1, K = 0 → Q = 1
3: J = 1, K = 0 → Q = 1
4: J = 0, K = 0 → Q = 1
5: J = 1, K = 1 → Q = 0
6: J = 0, K = 1 → Q = 0
7: J = 0, K = 0 → Q = 0
8: J = 1, K = 0 → Q = 1

数出变化的次数

0 → 1 → 1 → 1 → 1 → 0 → 0 → 0 → 1
N = 3

答案

N = 3
7.数论与模运算

答案: 10−1 mod 13 = 4

逆元与同余式：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)。

扩展欧几里得算法

每个余数 r 都写成 r ≡ t·10 (mod 13)。

r = 13, t = 0
r = 10, q = 1, t = 1
r = 3, q = 3, t = −1
r = 1, q = 3, t = 4

逆矩阵

1 ≡ 4·10 (mod 13)
x = 4
校核: 10·4 = 40 = 3·13 + 1

答案

10−1 mod 13 = 4
8.数论与模运算

答案: x = 11

逆元与同余式：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)。

除以最大公约数

gcd(32, 52) = 4
8x ≡ 10 (mod 13)

解化简后的同余式

8−1 ≡ 5 (mod 13) → x ≡ 11 (mod 13)

模 52 下的解

x ∈ {11, 24, 37, 50}
x = 11

答案

x = 11
9.算法与复杂度

答案: D · 指数级

为什么是这个答案

调用树大约按 φⁿ（约 1.618ⁿ）增长。记忆化可将其降为 O(n)。

答案

D · 指数级
10.算法与复杂度

答案: B · O(n) 时间和 O(1) 空间

为什么是这个答案

每一步只需要前两个值，因此自底向上方法中的表格可以用两个变量代替。

答案

B · O(n) 时间和 O(1) 空间
11.数据结构

答案: C · 数组元素是连续存放的，因此能很好地利用 CPU 缓存

为什么是这个答案

连续的内存带来良好的引用局部性，而链表节点可能分散各处，导致大量缓存未命中。

答案

C · 数组元素是连续存放的，因此能很好地利用 CPU 缓存
12.数据结构

答案: A · 通过旋转把被访问的节点移到根

为什么是这个答案

伸展操作通过旋转把被访问的节点移到根；单次操作可能代价为 O(n)，但均摊代价为 O(log n)。

答案

A · 通过旋转把被访问的节点移到根
13.图论

答案: k = 6

欧拉、哈密顿与树：连通图在每个顶点度数都为偶数时有欧拉回路（每条边经过一次，回到起点），在恰有两个顶点度数为奇数时有不是回路的欧拉通路；此时通路从一个奇度顶点走到另一个奇度顶点。哈密顿回路恰好经过每个顶点一次；Kn 有 (n − 1)!/2 条。n 个顶点的树有 n − 1 条边，有 m 条边的连通图在去掉 m − n + 1 条边后保留一棵生成树。

生成树的边数

19 − 1 = 18

要去掉的边数

k = 24 − 18 = 6

答案

k = 6
14.图论

答案: 边 BD

最短路径与生成树：迪杰斯特拉算法每一轮确定一个顶点：暂定距离最小的未确定顶点。它的距离随即成为最终值，并且每个邻点 v 得到 d(v) = min(d(v), d(u) + w(u, v))。克鲁斯卡尔算法按从轻到重的顺序取边并跳过会形成圈的边，从而构造最小生成树；普里姆算法从一个起点出发扩展一棵树，每次加入离开这棵树的最轻的边。n 个顶点的生成树有 n − 1 条边。

普里姆算法

1. AB (12)
2. BE (6)
3. BC (7)
4. BD (10)

边的序号 4

BD

答案

边 BD
15.数据库与 SQL

答案: B · 引用它的子行会被自动删除

为什么是这个答案

CASCADE 把删除传播到引用它的行；其他选项有 RESTRICT/NO ACTION（拒绝）和 SET NULL。

答案

B · 引用它的子行会被自动删除
16.数据库与 SQL

答案: A · WHERE last_name = 'Jansen'

为什么是这个答案

复合 B 树索引先按 last_name、再按 first_name 排序，因此在前导列上的查找可以利用它，但仅凭 first_name 无法利用这种顺序。

答案

A · WHERE last_name = 'Jansen'
17.计算机网络

答案: B · 生存时间（TTL）

为什么是这个答案

每台路由器都把 TTL 减一；减到零时数据包被丢弃，通常还会发送一条 ICMP 超时（Time Exceeded）消息。IPv6 称之为跳数限制（hop limit）。

答案

B · 生存时间（TTL）
18.计算机网络

答案: B · 让延迟的段消亡，并在最后的 ACK 丢失时能够重发

为什么是这个答案

TIME_WAIT 确保丢失的最后 ACK 能够被重发，并让旧的重复段在同一地址和端口对被重用之前过期。

答案

B · 让延迟的段消亡，并在最后的 ACK 丢失时能够重发
19.IPv4 子网划分

答案: p = 23

IPv4 子网划分：一个地址有 32 位。前缀 /p 表示前面多少位标识网络；其余 32 − p 位为主机编号。一个子网有 2³²⁻ᵖ 个地址，但第一个（网络地址）和最后一个（广播地址）不能分配给主机，所以可容纳 2³²⁻ᵖ − 2 台主机。 例外：/31（点对点链路，RFC 3021）的 2 个地址都用于主机，/32 只有一个地址（单个主机或环回地址）。

所需主机位

28 − 2 = 254 < 421
29 − 2 = 510 ≥ 421 → h = 9

前缀长度

p = 32 − 9 = 23

答案

p = /23
20.IPv4 子网划分

答案: x = 216

IPv4 子网划分：一个地址有 32 位。前缀 /p 表示前面多少位标识网络；其余 32 − p 位为主机编号。一个子网有 2³²⁻ᵖ 个地址，但第一个（网络地址）和最后一个（广播地址）不能分配给主机，所以可容纳 2³²⁻ᵖ − 2 台主机。 例外：/31（点对点链路，RFC 3021）的 2 个地址都用于主机，/32 只有一个地址（单个主机或环回地址）。

块大小

23 = 8

该主机所在子网

网络: ⌊220/8⌋·8 = 216
广播: 216 + 8 − 1 = 223
可用主机: 217 … 222

答案

x = 216

ExamProblems · examproblems.com/courses/computer-science-fundamentals