计算机科学导论：速成包

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

1011 11018 bit

N =

2.数制困难

某系统要为 1356 个项目中的每一个分配一个长度相同的独立二进制编码。最少需要多少位 b？

1356

b = bit

3.命题逻辑与证明中等

((p ∨ q) ∧ p) → ¬q 是重言式、矛盾式还是偶然式？点选你的答案。

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

1重言式
2矛盾式
3偶然式

4.命题逻辑与证明困难

真值表的 16 行中，有多少行使 (a ∧ (c ∨ ¬d)) ∧ (¬b ∨ (b → d)) 为真？把这个数记作 N。

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

N =

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

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

F = A′B′C + AC′ + A′B′ + AB′C

L =

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

一个 4 位环形计数器 Q₃Q₂Q₁Q₀ 从 1100 开始。每个时钟边沿，各位向右移动一位（Q₃ → Q₂ → Q₁ → Q₀），Q₃ 接收 Q₀。给出 6 个时钟边沿之后的状态 Q = Q₃Q₂Q₁Q₀，用十进制数表示。

Q₃Q₂Q₁Q₀ = 11006

Q =

7.数论与模运算中等

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

x ≡ 7 (mod 11)x ≡ 8 (mod 12)

x =

8.数论与模运算困难

在 {0, 1, …, 73} 中，44x ≡ 58 (mod 74) 有多少个解 N？

44x ≡ 58 (mod 74)

N =

9.算法与复杂度中等

对长度为 m 和 n 的两个字符串求最长公共子序列，标准动态规划算法的时间复杂度是多少？

AO(mn log n)
BO(2^m+n)
CO(m + n)
DO(mn)

10.算法与复杂度困难

一个问题是 NP 完全（NP-complete）的，当且仅当它：

A属于 NP，且所有 NP 问题都能在多项式时间内归约到它
B不属于 NP，但比所有 NP 问题都难，例如停机问题
C可以在多项式时间内解决
D不可能被解决

11.数据结构中等

如何在二叉搜索树中找到最小的键？

A访问每个叶子并进行比较
B从根开始沿右子节点走，直到没有右子节点为止
C从根开始沿左子节点走，直到没有左子节点为止
D只看根

12.数据结构困难

一个对象作为键存储在哈希映射中，之后其哈希函数所用的一个字段被修改了。可能的结果是什么？

A什么都不会改变，因为键的哈希只在程序启动时计算一次
B映射会自动把该键移到新的桶中
C字段改变的那一刻映射就会抛出错误
D查找该对象可能失败，因为它位于按旧哈希值确定的桶中

13.图论中等

一棵树有 2 个度为 3 的顶点，其余所有顶点都是叶子（度为 1）。它有多少片叶子 L？

2 × deg 3

L =

14.图论困难

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

起点：Dk = 3

1边 AB
2边 AC
3边 BC
4边 CE
5边 DE
6边 DF
7边 EF
8边 BE

15.数据库与 SQL中等

第一范式（1NF）要求：

A每列都包含原子值，且没有重复组
B没有外键
C每个表恰好只有一列
D每个非键列都依赖于整个键，且只依赖于键

16.数据库与 SQL困难

为什么许多 DBMS 使用严格两阶段锁，把排他锁一直持有到提交？

A它允许事务安全地读取脏数据
B它免去了事务日志
C它使死锁不可能发生
D它能防止级联中止，因为没有人能读到未提交的写入

17.计算机网络中等

TLS 通常如何使用非对称加密和对称加密？

A非对称方法用于协商密钥和认证；对称密码用于加密数据
B全程只使用非对称加密
C只使用对称加密，配合一个固定的共享密码
D对称方法用于协商密钥和认证；非对称密码用于加密全部数据

18.计算机网络困难

哪种路由协议属于链路状态协议？

AOSPF
BARP
CBGP
DRIP

19.IPv4 子网划分中等

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

948 hosts

p =

20.IPv4 子网划分困难

某主机地址为 10.20.228.211/29。其子网广播地址的最后一个数（第四个八位组）x 是多少？

10.20.228.211/29

x =

3溶液

1.数制

答案: N = −67

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

位权相加

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

−128 + 32 + 16 + 8 + 4 + 1 = −67

答案

N = −67

2.数制

答案: b = 11 bit

2 的幂

2¹⁰ = 1024 < 1356

2¹¹ = 2048 ≥ 1356

答案

b = 11

3.命题逻辑与证明

答案: 偶然式

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

逐行写出真值表

p = 1, q = 1: p ∨ q = 1, (p ∨ q) ∧ p = 1, ¬q = 0, ((p ∨ q) ∧ p) → ¬q = 0

p = 1, q = 0: p ∨ q = 1, (p ∨ q) ∧ p = 1, ¬q = 1, ((p ∨ q) ∧ p) → ¬q = 1

p = 0, q = 1: p ∨ q = 1, (p ∨ q) ∧ p = 0, ¬q = 0, ((p ∨ q) ∧ p) → ¬q = 1

p = 0, q = 0: p ∨ q = 0, (p ∨ q) ∧ p = 0, ¬q = 1, ((p ∨ q) ∧ p) → ¬q = 1

分类

((p ∨ q) ∧ p) → ¬q: 0, 1, 1, 1

在 4 行中有 3 行为 1，其余为 0：偶然式。

答案

偶然式

4.命题逻辑与证明

答案: 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。

各列

¬d; c ∨ ¬d; a ∧ (c ∨ ¬d); ¬b; b → d; ¬b ∨ (b → d); (a ∧ (c ∨ ¬d)) ∧ (¬b ∨ (b → d))

按 a 拆分

a = 1: 4

a = 0: 0

N = 4 + 0 = 4

答案

N = 4

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

答案: L = 3

布尔代数：化简表达式的规则有 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。

表达式的最小项

A′B′C → m(1)

AC′ → m(4, 6)

A′B′ → m(0, 1)

AB′C → m(5)

圈组并读出结果

F = B′ + AC′

数出文字个数

L = 3

答案

L = 3

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

答案: Q = 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 计数器的最后一级输出频率为 f_clk/N。n 个触发器的约翰逊计数器有 2n 个状态，环形计数器有 n 个。

每个边沿之后的状态

1100 → 0110 → 0011 → 1001 → 1100 → 0110 → 0011

十进制值

0011₂ = 3

答案

Q = 3

7.数论与模运算

答案: x = 128

逆元与同余式：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 = 7 + 11k

第二个同余式

7 + 11k ≡ 8 (mod 12) → 11k ≡ 1 (mod 12)

k ≡ 11·1 ≡ 11 (mod 12)

结果

x = 7 + 11·11 = 128

x = 128

校核: 128 mod 11 = 7, 128 mod 12 = 8

答案

x = 128

8.数论与模运算

答案: N = 2

除以最大公约数

gcd(44, 74) = 2

22x ≡ 29 (mod 37)

解化简后的同余式

22⁻¹ ≡ 32 (mod 37) → x ≡ 3 (mod 37)

模 74 下的解

x ∈ {3, 40}

树的握手引理

L + 6 = 2(L + 2) − 2

L = 4

答案

L = 4

捷径：L = 2 + Σ (d − 2)，对度 d ≥ 3 的顶点求和。

14.图论

答案: 边 CE

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

普里姆算法

1. DF (10)

2. EF (3)

3. CE (1)

4. BE (5)

5. AB (8)

OSPF 路由器构建区域的完整拓扑图，并用 Dijkstra 算法计算最短路径。RIP 是距离矢量协议；BGP 是路径矢量协议。

答案

A · OSPF

19.IPv4 子网划分

答案: p = 22

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

所需主机位

2⁹ − 2 = 510 < 948

2¹⁰ − 2 = 1022 ≥ 948 → h = 10

前缀长度

p = 32 − 10 = 22

答案

p = /22

20.IPv4 子网划分

答案: x = 215

块大小

2³ = 8

该主机所在子网

网络: ⌊211/8⌋·8 = 208

广播: 208 + 8 − 1 = 215

可用主机: 209 … 214

答案

x = 215

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