计算机科学导论：速成包

公式表、每个专题的关键方法步骤和 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 位模式 1011 1111 以补码形式存储一个有符号整数。它的十进制值 N 是多少？

1011 11118 bit

N =

2.数制困难

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

1010 1001XOR1011 0111

R =

3.命题逻辑与证明中等

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

a → (b ∧ c)

1¬(b ∧ c) → ¬a
2¬a → ¬(b ∧ c)
3(b ∧ c) → a
4a ∧ ¬(b ∧ c)

4.命题逻辑与证明困难

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

q → rq

1r
2¬r
3¬q
4q ∧ ¬r

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

用卡诺图求 F(A, B, C, D) = Σm(1, 2, 4, 6, 7, 11, 12, 13) 的最简和之积 (POS) 形式。它有多少个和项（因子）N？

F(A, B, C, D) = Σm(1, 2, 4, 6, 7, 11, 12, 13)

N =

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

对于 F(A, B, C, D) = Σm(0, 1, 7, 9, 13) + d(4, 11)（其中 d 表示无关项），求必要质蕴涵项的个数 N。

F(A, B, C, D) = Σm(0, 1, 7, 9, 13) + d(4, 11)

N =

7.数论与模运算中等

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

a = 27n = 32

27⁻¹ mod 32 =

8.数论与模运算困难

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

p = 7q = 41e = 7

d =

9.算法与复杂度中等

在无权图上进行广度优先搜索（BFS）可以求出：

A最小生成树
B所有图的拓扑序
C含负权重边的图中的最短路径
D从起始节点出发、按边数计的最短路径

10.算法与复杂度困难

为什么当某些边权为负时，Dijkstra 算法可能给出错误结果？

A优先队列中不能存储负数
B它只适用于无向图
C每遇到一条负权边它就会陷入无限循环
D顶点被取出时距离就被确定，但之后的负权边仍可能给它一条更短的路径

11.数据结构中等

一个道路网络有 100,000 个路口，每个路口大约与另外 4 个路口相连。哪种表示方法最合适？

A一个由边组成的二叉堆
B一个有序的顶点数组
C邻接矩阵
D邻接表

12.数据结构困难

一个动态数组在满时容量翻倍。为什么许多实现只在它只有四分之一满时才缩容，而不是一半满时？

A为了避免在边界附近交替进行 push 和 pop 时反复调整大小
B因为在一半满时减半会丢失元素
C为了使数组保持有序
D因为内存分配器只能以块的四分之一为单位释放内存

13.图论中等

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

|V| = 12|E| = 22

k =

14.图论困难

长度为 2 且起点和终点都是 B 的闭途径有多少条？途径可以重复顶点和边。把这个数记作 N。

M = 邻接矩阵L = 2

N =

15.数据库与 SQL中等

第三范式（3NF）消除了：

A建立在不属于任何键的列上的冗余索引
B复合键
C非键属性之间的传递依赖
D原子值

16.数据库与 SQL困难

EXPLAIN（或 PostgreSQL 中的 EXPLAIN ANALYZE）对一个查询显示什么？

A运行过该查询的用户列表
B仅以关系代数表示法改写的查询
C查询中每个 SQL 关键字的含义
D优化器选择的执行计划，例如扫描方式和连接方法

17.计算机网络中等

浏览器收到 HTTP 状态码 404。这是什么意思？

A请求成功
B找不到所请求的资源
C客户端必须先登录
D服务器发生内部错误

18.计算机网络困难

下列哪个地址是公网（而非 RFC 1918 私有）IPv4 地址？

A172.31.0.1
B10.255.0.1
C172.32.0.1
D192.168.255.1

19.IPv4 子网划分中等

一个子网使用掩码 255.255.255.192。它有多少个可用主机地址 H？

255.255.255.192

H =

20.IPv4 子网划分困难

一台路由器有到以下网络的路由：10.175.27.0/24, 10.175.28.0/24, 10.175.29.0/24, 10.175.30.0/24, 10.175.31.0/24, 10.175.32.0/24。能覆盖所有这些网络的单条汇总路由，其最长前缀长度 p 是多少？

10.175.27.0/24 … 10.175.32.0/24

p =

3溶液

1.数制

答案: N = −65

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

位权相加

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

−128 + 32 + 16 + 8 + 4 + 2 + 1 = −65

答案

N = −65

2.数制

答案: R = 30

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

逐位计算

XOR 在两位不同时得 1。

1010 1001

XOR 1011 0111

= 0001 1110

结果的值

0001 1110₂ = 30

答案

R = 30

3.命题逻辑与证明

答案: ¬(b ∧ c) → ¬a

逻辑等价：两个公式在真值表的每一行取值都相同时，它们是等价（≡）的。重言式在每一行都为 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 = a, b = b ∧ c

逆否命题

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

答案

¬(b ∧ c) → ¬a

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

4.命题逻辑与证明

答案: r

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

所有前提都为真的行

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

结论

r (肯定前件式)

答案

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

答案: N = 6

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

圈 0

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

(B + C + D)

(A′ + C′ + D)

(A′ + B + C)

(A′ + B′ + C′)

(A + B + C′ + D′)

(A + B′ + C + D′)

最简 POS 形式

F = (B + C + D)(A′ + C′ + D)(A′ + B + C)(A′ + B′ + C′)(A + B + C′ + D′)(A + B′ + C + D′)

N = 6

答案

N = 6

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

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

答案: N = 2

质蕴涵项

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

B′C′D, A′C′D′, AC′D, AB′D, A′B′C′, A′BCD

必要质蕴涵项

AC′D, A′BCD

N = 2

答案

N = 2

7.数论与模运算

答案: 27⁻¹ mod 32 = 19

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

r = 32, t = 0

r = 27, q = 1, t = 1

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

r = 2, q = 2, t = 6

r = 1, q = 2, t = −13

逆矩阵

1 ≡ −13·27 (mod 32)

x = 19

校核: 27·19 = 513 = 16·32 + 1

答案

27⁻¹ mod 32 = 19

8.数论与模运算

答案: d = 103

模幂与 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 = 7·41 = 287

φ(n) = 6·40 = 240

扩展欧几里得算法

r = 240, t = 0

r = 7, q = 34, t = 1

r = 2, q = 3, t = −34

r = 1, q = 2, t = 103

私钥指数

d = 103

生成树的边数

12 − 1 = 11

要去掉的边数

k = 22 − 11 = 11

答案

k = 11

14.图论

答案: N = 4

度：顶点的度是与它相连的边的条数。每条边有两个端点，所以度数之和等于边数的两倍：Σ deg(v) = 2|E|（握手引理）。因此奇度顶点的个数是偶数。K_n 有 n(n − 1)/2 条边，n 个顶点的 k-正则图有 nk/2 条边，n 个顶点的树有 n − 1 条边。

邻接矩阵

A: 0 1 1 0 0 0

B: 1 0 1 1 1 0

C: 1 1 0 0 1 0

C · 172.32.0.1

19.IPv4 子网划分

答案: H = 62

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.192 = /26

可用主机数

2⁶ − 2 = 62

答案

H = 62

20.IPv4 子网划分

答案: p = 18

路由汇总：汇总路由 a.b.c.0/p 覆盖前 p 位相同的所有网络。把第一个和最后一个网络中不同的那个八位组写成二进制；相同的前导位数加上它前面各八位组的位数，就是最长的汇总前缀。

比较各位

27 = 00011011

32 = 00100000

相同的前导位：2

前缀长度

p = 16 + 2 = 18

答案

p = /18

汇总路由：10.175.0.0/18 （它还覆盖了列表中没有的 58 个网络）。

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