计算机科学导论：速成包

公式表、每个专题的关键方法步骤和 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−12816403201608041201

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

1100 00108 bit
N =
2.数制困难
16 bit1 px640 px480 pxM = ? KiB

一幅未压缩图像为 640 × 480 像素，每像素 16 位。它占用多少内存 M（以 KiB 计，1 KiB = 1024 字节）？

640 × 480 px16 bit/px1 KiB = 1024 B
M = KiB
3.命题逻辑与证明中等
pqr(q ∨ p) → rp ∧ q((q ∨ p) → r) ∧ (p ∧ q)111?110?101?100?011?010?001?000?

在其真值表的 8 行中，((q ∨ p) → r) ∧ (p ∧ q) 在多少行为真？把这个数记作 N。

((q ∨ p) → r) ∧ (p ∧ q)
N =
4.命题逻辑与证明困难
∀x (¬A(x) → ¬B(x))∃x (A(x) ∧ ¬B(x))∀x (A(x) → ¬B(x))∀x (A(x) ∧ ¬B(x))

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

¬∃x (A(x) → B(x))
  1. 1∀x (¬A(x) → ¬B(x))
  2. 2∃x (A(x) ∧ ¬B(x))
  3. 3∀x (A(x) → ¬B(x))
  4. 4∀x (A(x) ∧ ¬B(x))
5.数字逻辑：门电路、卡诺图与触发器中等
ABC000111100101324576

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

F = B′C′ + AB′C′ + A′BC′
L =
6.数字逻辑：门电路、卡诺图与触发器困难
DQ0​Q0​DQ1​Q1​DQ2​Q2​DQ3​Q3​DQ4​Q4​CLKRING

一个环形计数器由 5 个 D 触发器构成，最后一个输出反馈到第一个输入，并从单个 1 开始。它经历多少种不同的状态 N？

n = 5
N =
7.数论与模运算中等

解 15x ≡ 18 (mod 19)。给出满足 0 < x < 19 的解 x。

15x ≡ 18 (mod 19)
x =
8.数论与模运算困难
59c = me​ mod n?m = cd​ mod nm(n, e) = (629, 11)d

用 RSA 公钥 (n, e) = (629, 11) 加密消息 m = 59。求密文 c。

n = 629e = 11m = 59
c =
9.算法与复杂度中等

递推式 T(n) = 2T(n/2) + O(1) 的解是什么？

  1. AO(n log n)
  2. BO(n)
  3. CO(n²)
  4. DO(log n)
10.算法与复杂度困难

停机问题（halting problem）表明：

  1. A不存在一种算法能对所有程序和输入判定其是否会停机
  2. B应当避免使用循环
  3. C有些程序在更快的计算机上运行得更快，所以是否停机取决于硬件
  4. D每个程序最终都会停机
11.数据结构中等

一棵二叉树的根为 1，左子节点为 2，右子节点为 3；节点 2 的子节点为 4（左）和 5（右）。后序遍历的结果是什么？

  1. A5 4 3 2 1
  2. B4 5 2 3 1
  3. C4 2 5 1 3
  4. D1 2 4 5 3
12.数据结构困难

在 Kruskal 最小生成树算法中，并查集结构用来做什么？

  1. A选择起始顶点
  2. B按权重对边排序
  3. C检查一条边的两个端点是否已经连通
  4. D在搜索过程中存储每个顶点到源点的当前距离
13.图论中等

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

K6
H =
14.图论困难
11131112231329ABCDEFG

用迪杰斯特拉算法求带权图中从 A 到 F 的最短路径的长度 d(F)。

起点：A终点：F
d(F) =
15.数据库与 SQL中等

对于一行，WHERE EXISTS (subquery) 在什么情况下为真？

  1. A子查询不返回 NULL 值时
  2. B子查询至少返回一行时
  3. C子查询恰好返回一行时
  4. D子查询返回一个大于零的数时
16.数据库与 SQL困难

并发事务的调度在什么情况下被称为可串行化的？

  1. A每个事务都被分配一个序列号
  2. B其效果等价于这些事务的某种串行执行
  3. C任何事务都从不读取数据
  4. D事务只在一个 CPU 上运行
17.计算机网络中等

分布式拒绝服务（DDoS）攻击的特征是什么？

  1. A大量被攻陷的机器用流量淹没一个目标
  2. B一种病毒删除一台 PC 上的文件
  3. C攻击者从附近的汽车里读取未加密的 Wi-Fi 流量
  4. D一个攻击者猜测用户的密码
18.计算机网络困难

BGP 在互联网中的主要作用是什么？

  1. A加密路由器之间的数据
  2. B将名称解析为地址
  3. C在自治系统之间交换路由信息
  4. D通过互联网服务提供商为家庭用户分配 IP 地址
19.IPv4 子网划分中等
255.255.255.24011111111111111111111111111110000网络位主机位

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

255.255.255.240
H =
20.IPv4 子网划分困难

网络 192.168.105.0/24 用 VLSM 划分给以下局域网：A: 44 主机, B: 9 主机, C: 98 主机, D: 27 主机。子网从 .0 开始向上分配，主机最多的局域网先分配，每个局域网分配能容纳它的最小子网。局域网 D 的网络地址第四个八位组 x 是多少？

A: 44B: 9C: 98D: 27
x =

3溶液

1.数制

答案: N = −62

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

位权相加

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

−128 + 64 + 2 = −62

答案

N = −62
2.数制

答案: M = 600 KiB

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

位和字节

640·480·16 = 4915200 bit = 614400 B

换算为 KiB

614400/1024 = 600 KiB

答案

M = 600 KiB
3.命题逻辑与证明

答案: N = 1

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

逐行写出真值表

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

数出值为 1 的行数

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

答案

N = 1
4.命题逻辑与证明

答案: ∀x (A(x) ∧ ¬B(x))

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

把否定移到内部

¬∃x (A(x) → B(x)) ≡ ∀x (A(x) ∧ ¬B(x))

答案

∀x (A(x) ∧ ¬B(x))

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

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。

表达式的最小项

B′C′ → m(0, 4)
AB′C′ → m(4)
A′BC′ → m(2)
ABC00011110011001031214050706

圈组并读出结果

F = B′C′ + A′C′

数出文字个数

L = 4

答案

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

答案: N = 5

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

5 个触发器的序列

10000 → 01000 → 00100 → 00010 → 00001

状态数

N = 5

答案

N = 5
7.数论与模运算

答案: x = 5

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

15 的逆元

r = 19, t = 0
r = 15, q = 1, t = 1
r = 4, q = 3, t = −1
r = 3, q = 1, t = 4
r = 1, q = 3, t = −5
15−1 ≡ 14 (mod 19)

求解

x ≡ 14·18 = 252 ≡ 5 (mod 19)
校核: 15·5 = 75 ≡ 18 (mod 19)

答案

x = 5
8.数论与模运算

答案: c = 240

模幂与 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 解密。

反复平方

11 = 8 + 2 + 1
591 ≡ 59 (mod 629)
592 ≡ 336 (mod 629)
594 ≡ 305 (mod 629)
598 ≡ 562 (mod 629)
5911 ≡ 59·336·562 ≡ 240 (mod 629)

密文

c = 240

答案

c = 240
9.算法与复杂度

答案: B · O(n)

为什么是这个答案

根据主定理，nlog₂ 2 = n 压过常数工作量，因此 T(n) = Θ(n)，例如通过对半分割来求最大值。

答案

B · O(n)
10.算法与复杂度

答案: A · 不存在一种算法能对所有程序和输入判定其是否会停机

为什么是这个答案

Turing 证明了停机问题是不可判定的（undecidable）：假设存在判定器，就会与一个做相反行为的程序产生矛盾。

答案

A · 不存在一种算法能对所有程序和输入判定其是否会停机
11.数据结构

答案: B · 4 5 2 3 1

为什么是这个答案

后序遍历先处理 4 和 5，再处理 2，然后是 3，最后是根 1。

答案

B · 4 5 2 3 1
12.数据结构

答案: C · 检查一条边的两个端点是否已经连通

为什么是这个答案

Find 判断两个端点是否在同一个连通分量中；如果不在，就加入这条边，并用 union 合并两个分量。

答案

C · 检查一条边的两个端点是否已经连通
13.图论

答案: H = 60

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

计数

H = (6 − 1)!/2 = 120/2 = 60

答案

H = 60
14.图论

答案: d(F) = 36

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

迪杰斯特拉算法逐轮过程

每一行：被确定的顶点、它的最终距离，以及距离得到改进的邻点。

A (0): B: 11
B (11): C: 24, G: 24
C (24): E: 35
G (24): E: 33
E (33): D: 45, F: 36
F (36): D: 38
D (38)

最短路径

A → B → G → E → F
d(F) = 36

答案

d(F) = 36
15.数据库与 SQL

答案: B · 子查询至少返回一行时

为什么是这个答案

EXISTS 只检查是否产生了任何行；子查询不返回任何行时，NOT EXISTS 为真。

答案

B · 子查询至少返回一行时
16.数据库与 SQL

答案: B · 其效果等价于这些事务的某种串行执行

为什么是这个答案

可串行化是并发控制的主要正确性标准：交错执行的结果必须等于某种逐个执行顺序的结果。

答案

B · 其效果等价于这些事务的某种串行执行
17.计算机网络

答案: A · 大量被攻陷的机器用流量淹没一个目标

为什么是这个答案

在 DDoS 攻击中，许多来源压垮服务器或链路，使合法用户无法得到服务。来源众多使简单的封堵很难奏效。

答案

A · 大量被攻陷的机器用流量淹没一个目标
18.计算机网络

答案: C · 在自治系统之间交换路由信息

为什么是这个答案

BGP 是域间路由协议；自治系统（AS）通告可达前缀，并根据策略选择路径。

答案

C · 在自治系统之间交换路由信息
19.IPv4 子网划分

答案: H = 14

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.240 = /28

可用主机数

24 − 2 = 14

答案

H = 14
20.IPv4 子网划分

答案: x = 192

VLSM：每个局域网分配满足 2ʰ − 2 ≥ 其主机数的最小子网，即前缀 32 − h。先分配最大的子网，可使每个块都对齐在其自身大小的倍数上，因此网络地址就是各块大小依次相加的结果。

每个局域网的块大小

C: 98 主机 → 27 = 128 (/25)
A: 44 主机 → 26 = 64 (/26)
D: 27 主机 → 25 = 32 (/27)
B: 9 主机 → 24 = 16 (/28)

分配顺序，从大到小

C: .0 – .127
A: .128 – .191
D: .192 – .223
B: .224 – .239

答案

x = 192

局域网 D：192.168.105.192/27。

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