计算机科学导论：速成包

公式表、每个专题的关键方法步骤和 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.数制中等
8 位补码0−12806403201608040201

设置各位，使其以 8 位补码存储 −106。按无符号数读取，该位模式的值 U 是多少？

N = −1068 bit
U =
2.数制困难
点击各位来设置012806403201608040201

把各位设置为 1010 0111 XOR 1010 1110 的 8 位结果。该结果的十进制值 R 是多少？

1010 0111XOR1010 1110
R =
3.命题逻辑与证明中等
b → c¬b → ¬cc ∧ ¬b¬c → ¬b

你想用逆否证明来证明 c → b。你要改为证明哪个蕴涵？点选它。

c → b
  1. 1b → c
  2. 2¬b → ¬c
  3. 3c ∧ ¬b
  4. 4¬c → ¬b
4.命题逻辑与证明困难
¬rq ∨ pr ∨ pr ∧ p

已知前提 q ∨ r; ¬q ∨ p。由它们可以推出哪个结论？点选它。

q ∨ r¬q ∨ p
  1. 1¬r
  2. 2q ∨ p
  3. 3r ∨ p
  4. 4r ∧ p
5.数字逻辑：门电路、卡诺图与触发器中等
ABC000111100101324576

把 F = AB′C + A′B′ + AC 化简为最简积之和形式。化简后的表达式包含多少个文字 L？

F = AB′C + A′B′ + AC
L =
6.数字逻辑：门电路、卡诺图与触发器困难
ABCD000111100001111000X10302141517X6X120130151140819X11010

求 F(A, B, C, D) = Σm(4, 5, 7, 9, 14) + d(1, 6, 11, 12) 的最简 SOP 形式，其中 d 表示无关项。它有多少个乘积项 N？

F(A, B, C, D) = Σm(4, 5, 7, 9, 14) + d(1, 6, 11, 12)
N =
7.数论与模运算中等

求满足 x ≡ 8 (mod 12) 和 x ≡ 9 (mod 13) 的最小正整数 x。

x ≡ 8 (mod 12)x ≡ 9 (mod 13)
x =
8.数论与模运算困难
mc = me​ mod n73m = cd​ mod n?(n, e) = (91, 23)d

某个 RSA 密钥使用 p = 7，q = 13，e = 23。解密密文 c = 73：求消息 m。

p = 7q = 13e = 23c = 73
m =
9.算法与复杂度中等

均摊分析衡量的是什么？

  1. A在随机输入上的期望代价
  2. B算法在最好输入上的代价
  3. C在最坏情况的操作序列上，每个操作的平均代价
  4. D序列中任何位置上单个最昂贵操作的代价
10.算法与复杂度困难

哪种算法通过反复加入不会形成环的最便宜的边来求最小生成树？

  1. AKruskal 算法
  2. BFloyd–Warshall
  3. CDijkstra 算法
  4. D从一个节点出发的 Prim 算法
11.数据结构中等

含 V 个顶点的图的邻接矩阵占用多少内存？

  1. AO(V²)
  2. BO(E)
  3. CO(V + E)
  4. DO(log V)
12.数据结构困难

在使用开放寻址法的哈希表中，为什么删除操作常用"墓碑"（tombstone）标记？

  1. A墓碑可以加快哈希计算
  2. B清空槽位可能会破坏其他键的探测序列
  3. C它能使表变得有序
  4. D出于安全考虑，被删除的键必须永久保留，因此槽位永远不能重用
13.图论中等

完全图 K5 有多少条不同的哈密顿回路 H？只是起点或方向不同的回路算作同一条。

K5
H =
14.图论困难
127911145216ABCDEF

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

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

哪个查询返回每个客户的订单数量？

  1. ASELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id
  2. BSELECT customer_id, COUNT(*) FROM orders ORDER BY customer_id
  3. CSELECT customer_id FROM orders WHERE COUNT(*) > 0
  4. DSELECT DISTINCT COUNT(*) FROM orders
16.数据库与 SQL困难

在 customers LEFT JOIN orders 之后，为什么要用 COUNT(o.id) 而不是 COUNT(*) 来统计每个客户的订单数？

  1. ACOUNT(o.id) 只统计不同的客户
  2. B对没有订单的客户，COUNT(*) 会把用 NULL 填充的那一行计为 1
  3. C连接之后不允许使用 COUNT(*)
  4. DCOUNT(*) 会忽略含有 NULL 值的行
17.计算机网络中等

什么能唯一标识互联网上 TCP 连接的一端？

  1. A仅域名
  2. B仅 MAC 地址
  3. C子网掩码和网关
  4. DIP 地址加端口号
18.计算机网络困难

一台 8 端口交换机（无 VLAN）的每个端口上连接一台主机。共有多少个冲突域和广播域？

  1. A1 个冲突域，8 个广播域
  2. B8 个冲突域，8 个广播域
  3. C8 个冲突域，1 个广播域
  4. D1 个冲突域，1 个广播域
19.IPv4 子网划分中等
/24 → /2711111111111111111111111111100000网络位主机位

网络 192.168.10.0/24 需要划分为至少 6 个相等的子网。若借用尽可能少的位，每个子网有多少可用主机 H？

192.168.10.0/246 subnets
H =
20.IPv4 子网划分困难
第三个八位组 = 26012806403211618041201网络主机

一台主机的地址为 172.20.26.120/23。其网络地址的第三个八位组 x 是多少？

172.20.26.120/23
x =

3溶液

1.数制

答案: U = 150

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

取反加一

106 = 0110 1010
取反后: 1001 0101
+1 → 1001 0110

按无符号数读取

1001 0110₂ = 256 − 106 = 150

答案

U = 150
2.数制

答案: R = 9

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

逐位计算

XOR 在两位不同时得 1。

1010 0111
XOR 1010 1110
= 0000 1001

结果的值

0000 1001₂ = 9

答案

R = 9
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 = c, b = b

逆否命题

¬b → ¬a = ¬b → ¬c

答案

¬b → ¬c

逆否命题与原命题等价，所以证明了它就证明了原命题。

4.命题逻辑与证明

答案: r ∨ p

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

所有前提都为真的行

p = 1, q = 1, r = 1: ¬r = 0, q ∨ p = 1, r ∨ p = 1, r ∧ p = 1
p = 1, q = 1, r = 0: ¬r = 1, q ∨ p = 1, r ∨ p = 1, r ∧ p = 0
p = 1, q = 0, r = 1: ¬r = 0, q ∨ p = 1, r ∨ p = 1, r ∧ p = 1
p = 0, q = 0, r = 1: ¬r = 0, q ∨ p = 0, r ∨ p = 1, r ∧ p = 0

结论

r ∨ p (分辨率)

答案

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

答案: L = 4

布尔代数：化简表达式的规则有 X + X′ = 1 和 X·X′ = 0、X + X = X、吸收律 X + X·Y = X、合并律 X·Y + X·Y′ = X、X + X′Y = X + Y，以及一致性定理 XY + X′Z + YZ = XY + X′Z。德摩根律把 (X·Y)′ 变成 X′ + Y′，把 (X + Y)′ 变成 X′·Y′。卡诺图以图形方式应用这些规则：每个由两个相邻格子组成的圈，就是一次使用 XY + XY′ = X。

表达式的最小项

AB′C → m(5)
A′B′ → m(0, 1)
AC → m(5, 7)
ABC00011110011011030204151706

圈组并读出结果

F = AC + A′B′

数出文字个数

L = 4

答案

L = 4
6.数字逻辑：门电路、卡诺图与触发器

答案: N = 3

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

质蕴涵项

由 1 和 X 能够构成的最大的圈。

BD′, B′C′D, A′C′D, A′B, AB′D
ABCD000111100001111000X10302141517X6X120130151140819X11010

最小覆盖

F = BD′ + B′C′D + A′B
N = 3

答案

N = 3

还存在另一种大小相同的圈法；它的项数和文字数相同。

7.数论与模运算

答案: x = 152

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

第一个同余式

x = 8 + 12k

第二个同余式

8 + 12k ≡ 9 (mod 13) → 12k ≡ 1 (mod 13)
k ≡ 12·1 ≡ 12 (mod 13)

结果

x = 8 + 12·12 = 152
x = 152
校核: 152 mod 12 = 8, 152 mod 13 = 9

答案

x = 152
8.数论与模运算

答案: m = 5

模幂与 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 = 91, φ(n) = 72
d = 23−1 mod 72 = 47

用反复平方法解密

47 = 32 + 8 + 4 + 2 + 1
731 ≡ 73 (mod 91)
732 ≡ 51 (mod 91)
734 ≡ 53 (mod 91)
738 ≡ 79 (mod 91)
7316 ≡ 53 (mod 91)
7332 ≡ 79 (mod 91)
7347 ≡ 73·51·53·79·79 ≡ 5 (mod 91)

消息

m = 5
校核: 523 mod 91 = 73

答案

m = 5
9.算法与复杂度

答案: C · 在最坏情况的操作序列上，每个操作的平均代价

为什么是这个答案

均摊分析把少数昂贵操作的代价分摊到许多廉价操作上，从而对任意操作序列给出有保证的平均值。

答案

C · 在最坏情况的操作序列上，每个操作的平均代价
10.算法与复杂度

答案: A · Kruskal 算法

为什么是这个答案

Kruskal 按权重对边排序，若一条边连接不同的连通分量就加入它；Prim 则从一个起始顶点开始扩展一棵树。

答案

A · Kruskal 算法
11.数据结构

答案: A · O(V²)

为什么是这个答案

邻接矩阵存储 V × V 个元素，适合稠密图；邻接表占用 O(V + E)，更适合稀疏图。

答案

A · O(V²)
12.数据结构

答案: B · 清空槽位可能会破坏其他键的探测序列

为什么是这个答案

如果被删除的槽位变为空，之后的查找可能会提前停止，从而漏掉探测链中更靠后的键。

答案

B · 清空槽位可能会破坏其他键的探测序列
13.图论

答案: H = 12

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

计数

H = (5 − 1)!/2 = 24/2 = 12

答案

H = 12
14.图论

答案: 边 BD

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

普里姆算法

1. BC (7)
2. BD (9)
3. DF (5)
4. EF (2)
5. AC (12)

边的序号 2

BD

答案

边 BD
15.数据库与 SQL

答案: A · SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id

为什么是这个答案

GROUP BY customer_id 为每个客户生成一个分组，COUNT(*) 统计每个分组中的行数。

答案

A · SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id
16.数据库与 SQL

答案: B · 对没有订单的客户，COUNT(*) 会把用 NULL 填充的那一行计为 1

为什么是这个答案

左连接为这类客户生成一行订单列为 NULL 的记录；COUNT(o.id) 跳过 NULL，正确地报告为 0。

答案

B · 对没有订单的客户，COUNT(*) 会把用 NULL 填充的那一行计为 1
17.计算机网络

答案: D · IP 地址加端口号

为什么是这个答案

一个 TCP 连接由源 IP 和端口以及目的 IP 和端口共同标识。端口用于区分同一主机上的众多应用程序。

答案

D · IP 地址加端口号
18.计算机网络

答案: C · 8 个冲突域，1 个广播域

为什么是这个答案

交换机的每个端口都是一个独立的冲突域，但广播会被转发到所有端口，因此整台交换机是一个广播域。若换成集线器，则冲突域和广播域各只有一个。

答案

C · 8 个冲突域，1 个广播域
19.IPv4 子网划分

答案: H = 30

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

借用的位数

23 = 8 ≥ 6 → b = 3, /27

每个子网的主机数

25 − 2 = 30

答案

H = 30
20.IPv4 子网划分

答案: x = 26

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).

第三个八位组中的块大小

21 = 2

该主机所在子网

网络: 172.20.26.0
广播: 172.20.27.255

答案

x = 26

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