计算机科学导论：速成包

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

新题目返回课程

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

1公式与方法

数制

位权: 二进制 2^k，八进制 8^k，十六进制 16^k
转为十进制: Σ d_k·b^k
从十进制转换: 除以基数，余数从下往上读
十六进制 ↔ 二进制: 一位十六进制数 = 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

方法

数一数不同变量的个数：真值表有 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′I₀ + A′BI₁ + AB′I₂ + ABI₃
触发器: D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
计数器: n 位：2ⁿ 个状态；模 N：满足 2ⁿ ≥ N 的最小 n； f_out = f_clk/N
行波计数器: f_max = 1/(n·t_pd)
环形计数器与约翰逊计数器: 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(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
正则图: |E| = n·k/2
树与森林: |E| = n − 1, |E| = n − c
树的叶子: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
欧拉: 回路：所有顶点度数为偶数；通路：恰有 2 个奇度顶点
K_n 中的哈密顿回路: (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 位得到的子网数: 2ⁿ

2练习题

1.数制中等

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

N = −828 bit

U =

2.数制困难

把各位设置为 0111 1000 >> 2 的 8 位结果。该结果的十进制值 R 是多少？

0111 1000>> 2

R =

3.命题逻辑与证明中等

在其真值表的 8 行中，(a → ¬b) ∧ (c → b) 在多少行为真？把这个数记作 N。

(a → ¬b) ∧ (c → b)

N =

4.命题逻辑与证明困难

真值表的 16 行中，有多少行使 ¬((¬s ∨ ¬q) ∨ (p ∨ r)) ∧ (s ∧ (p → q)) 为真？把这个数记作 N。

¬((¬s ∨ ¬q) ∨ (p ∨ r)) ∧ (s ∧ (p → q))

N =

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

用卡诺图求 F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 10, 11, 14) 的最简积之和 (SOP) 形式。它有多少个乘积项 N？

F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 10, 11, 14)

N =

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

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

Q₀ = 0T

N =

7.数论与模运算中等

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

a = 6n = 41

6⁻¹ mod 41 =

8.数论与模运算困难

某个 RSA 密钥使用素数 p = 5 和 q = 23，公钥指数 e = 13。求私钥指数 d（0 < d < φ(n)）。

p = 5q = 23e = 13

d =

9.算法与复杂度中等

在包含 1,000,000 个元素的有序数组上，二分查找在最坏情况下大约需要多少次比较？

A约 500,000 次
B约 1,000 次
C约 100 次
D约 20 次

10.算法与复杂度困难

在有 V 个顶点、E 条边的图上，使用二叉堆的 Dijkstra 算法运行时间是多少？

AO((V + E) log V)
BO(V + E)
CO(V³)
DO(V × E)

11.数据结构中等

为什么二叉堆可以不用任何指针而存储在数组中？

A数组会自动使键保持有序，因此不需要指针
B堆中所有的键都相等
C它是完全二叉树，因此位置遵循简单的下标公式
D堆中的元素从不超过 100 个

12.数据结构困难

原地反转一个单链表的时间和额外空间代价各是多少？

AO(1) 时间和 O(1) 额外空间
BO(n) 时间和 O(n) 额外空间
CO(n) 时间和 O(1) 额外空间
DO(n log n) 时间和 O(1) 额外空间

13.图论中等

这个连通图有欧拉回路、有不是回路的欧拉通路，还是两者都没有？点选你的答案。

|V| = 7|E| = 9

1欧拉回路
2有欧拉通路，无回路
3都不是

14.图论困难

求带权图的最小生成树的总权重 W。

|V| = 6|E| = 8

W =

15.数据库与 SQL中等

一个表在每一行订单上都存储了客户地址。只修改其中一行的地址而不修改其他行，这是哪种情况的例子？

A幻读
B更新异常
C删除异常
D插入异常

16.数据库与 SQL困难

一个应用执行 UPDATE item SET qty = 4, version = 8 WHERE id = 1 AND version = 7，如果没有行被更新就报告冲突。这是哪种技术？

A数据库分片
B乐观并发控制
C带行锁的严格两阶段锁
D预写日志

17.计算机网络中等

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

AIP 地址加端口号
B仅域名
C仅 MAC 地址
D子网掩码和网关

18.计算机网络困难

为什么要引入 TCP 窗口扩大选项？

A没有它，TCP 就无法检测长距离链路上丢失的段
B32 位的窗口字段太大，浪费了每个已发送 TCP 报文段中的首部空间
C16 位的窗口字段把窗口限制在 65,535 字节，对于高速长距离路径来说太小
DUDP 需要一种在拥塞路径上控制发送速率的方法

19.IPv4 子网划分中等

网络 10.62.84.0/22 被划分为前缀为 /25 的等大子网。共有多少个子网 N？

10.62.84.0/22/25

N =

20.IPv4 子网划分困难

某主机地址为 10.20.32.200/25。其子网中最后一个可用主机地址的第四个八位组 x 是多少？

10.20.32.200/25

x =

3溶液

1.数制

答案: U = 174

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

取反加一

82 = 0101 0010

取反后: 1010 1101

+1 → 1010 1110

按无符号数读取

1010 1110₂ = 256 − 82 = 174

答案

U = 174

2.数制

答案: R = 30

逐位计算

右移 2 位，把每一位向右移动 2 个位置；从右端移出的位丢失，左侧补入 0。

0111 1000 >> 2

= 0001 1110

结果的值

0001 1110₂ = 30

答案

R = 30

3.命题逻辑与证明

答案: N = 4

真值表：含 n 个不同变量的公式有 2ⁿ 行，每一行对应真值的一种组合（1 = 真，0 = 假）。由内向外进行，给每个子公式单独一列。¬a 把值取反；a ∧ b 只有在两者都为 1 时才为 1；a ∨ b 只有在两者都为 0 时才为 0；a → b 只有在 a = 1 且 b = 0 时才为 0；a ↔ b 在两边相等时为 1。

逐行写出真值表

a = 1, b = 1, c = 1: ¬b = 0, a → ¬b = 0, c → b = 1, (a → ¬b) ∧ (c → b) = 0

a = 1, b = 1, c = 0: ¬b = 0, a → ¬b = 0, c → b = 1, (a → ¬b) ∧ (c → b) = 0

a = 1, b = 0, c = 1: ¬b = 1, a → ¬b = 1, c → b = 0, (a → ¬b) ∧ (c → b) = 0

a = 1, b = 0, c = 0: ¬b = 1, a → ¬b = 1, c → b = 1, (a → ¬b) ∧ (c → b) = 1

a = 0, b = 1, c = 1: ¬b = 0, a → ¬b = 1, c → b = 1, (a → ¬b) ∧ (c → b) = 1

a = 0, b = 1, c = 0: ¬b = 0, a → ¬b = 1, c → b = 1, (a → ¬b) ∧ (c → b) = 1

a = 0, b = 0, c = 1: ¬b = 1, a → ¬b = 1, c → b = 0, (a → ¬b) ∧ (c → b) = 0

a = 0, b = 0, c = 0: ¬b = 1, a → ¬b = 1, c → b = 1, (a → ¬b) ∧ (c → b) = 1

数出值为 1 的行数

(a → ¬b) ∧ (c → b): 0, 0, 0, 1, 1, 1, 0, 1

N = 4

答案

N = 4

4.命题逻辑与证明

答案: N = 1

各列

¬s; ¬q; ¬s ∨ ¬q; p ∨ r; (¬s ∨ ¬q) ∨ (p ∨ r); ¬((¬s ∨ ¬q) ∨ (p ∨ r)); p → q; s ∧ (p → q); ¬((¬s ∨ ¬q) ∨ (p ∨ r)) ∧ (s ∧ (p → q))

按 p 拆分

p = 1: 0

p = 0: 1

N = 0 + 1 = 1

答案

N = 1

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

答案: N = 4

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

圈 1

每个圈都是由 2ᵏ 个格子组成的矩形；边上的格子与对边上的格子相邻。

B′D

B′C′

A′CD

ACD′

最简 SOP 形式

F = B′D + B′C′ + A′CD + ACD′

N = 4

答案

N = 4

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

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

答案: N = 2

触发器与计数器：触发器只在时钟的有效边沿改变。D 复制其输入 (Q⁺ = D)；T 在 T = 1 时翻转；JK 在 00 时保持，01 时复位，10 时置位，11 时翻转。n 位二进制计数器有 2ⁿ 个状态，按模 2ⁿ 计数；模 N 计数器依次计 0, 1, …, N − 1 然后回到 0，需要满足 2ⁿ ≥ N 的最小 n 个触发器。行波计数器的每一级使频率减半，所以模 N 计数器的最后一级输出频率为 f_clk/N。n 个触发器的约翰逊计数器有 2n 个状态，环形计数器有 n 个。

每个边沿之后的 Q

T 触发器在 T = 1 时每个上升沿翻转，在 T = 0 时保持。

1: T = 1 → Q = 1

2: T = 0 → Q = 1

3: T = 0 → Q = 1

4: T = 0 → Q = 1

5: T = 0 → Q = 1

6: T = 1 → Q = 0

7: T = 0 → Q = 0

数出变化的次数

0 → 1 → 1 → 1 → 1 → 1 → 0 → 0

N = 2

答案

N = 2

7.数论与模运算

答案: 6⁻¹ mod 41 = 7

逆元与同余式：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·6 (mod 41)。

r = 41, t = 0

r = 6, q = 6, t = 1

r = 5, q = 1, t = −6

r = 1, q = 5, t = 7

逆矩阵

1 ≡ 7·6 (mod 41)

x = 7

校核: 6·7 = 42 = 1·41 + 1

答案

6⁻¹ mod 41 = 7

8.数论与模运算

答案: d = 61

模幂与 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 = 5·23 = 115

φ(n) = 4·22 = 88

扩展欧几里得算法

r = 88, t = 0

r = 13, q = 6, t = 1

r = 10, q = 1, t = −6

r = 3, q = 3, t = 7

r = 1, q = 3, t = −27

私钥指数

d = 61

度

deg(A) = 1, deg(B) = 3, deg(C) = 3, deg(D) = 3, deg(E) = 3, deg(F) = 2, deg(G) = 3

奇度顶点

A, B, C, D, E, G → 6

都不是

答案

都不是

14.图论

答案: W = 33

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

克鲁斯卡尔算法

BE (1): 取

BC (3): 取

DF (4): 取

BD (7): 取

C · 16 位的窗口字段把窗口限制在 65,535 字节，对于高速长距离路径来说太小

19.IPv4 子网划分

答案: N = 8

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

借用位

25 − 22 = 3

子网数

N = 2³ = 8

答案

N = 8

每个 /25 子网有 2⁷ − 2 = 126 个可用主机。

20.IPv4 子网划分

答案: x = 254

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

块大小

2⁷ = 128

该主机所在子网

网络: ⌊200/128⌋·128 = 128

广播: 128 + 128 − 1 = 255

可用主机: 129 … 254

答案

x = 254

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