计算机科学导论：速成包

公式表、每个专题的关键方法步骤和 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 位补码存储 −76。按无符号数读取，该位模式的值 U 是多少？

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

把各位设置为 0001 1110 << 1 的 8 位结果。该结果的十进制值 R 是多少？

0001 1110<< 1
R =
3.命题逻辑与证明中等
重言式矛盾式偶然式

(a ∧ (a → b)) → b 是重言式、矛盾式还是偶然式？点选你的答案。

(a ∧ (a → b)) → b
  1. 1重言式
  2. 2矛盾式
  3. 3偶然式
4.命题逻辑与证明困难
q → r¬q → ¬rq ∧ rr → q

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

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

在这个卡诺图中，恰有一个 1 没有相邻的 1，所以它在最简 SOP 形式中仍是单个格子的圈（含四个文字的完整最小项）。跨越卡诺图边界的相邻关系也要计入。点选该格子。

F = Σm(1, 6, 7, 8, 10, 11)
  1. 1AB = 00, CD = 00
  2. 2AB = 00, CD = 01
  3. 3AB = 00, CD = 11
  4. 4AB = 00, CD = 10
  5. 5AB = 01, CD = 00
  6. 6AB = 01, CD = 01
  7. 7AB = 01, CD = 11
  8. 8AB = 01, CD = 10
  9. 9AB = 11, CD = 00
  10. 10AB = 11, CD = 01
  11. 11AB = 11, CD = 11
  12. 12AB = 11, CD = 10
  13. 13AB = 10, CD = 00
  14. 14AB = 10, CD = 01
  15. 15AB = 10, CD = 11
  16. 16AB = 10, CD = 10
6.数字逻辑：门电路、卡诺图与触发器困难
ABCD000111100001111000X113120405X706X12113X150141819011010

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

F(A, B, C, D) = Σm(2, 3, 8, 9, 13) + d(1, 7, 12, 15)
N =
7.数论与模运算中等

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

a = 47n = 74
47−1 mod 74 =
8.数论与模运算困难

用反复平方法求 40180 mod 73。

a = 40k = 180n = 73
40180 mod 73 =
9.算法与复杂度中等

关于一个没有可达基本情况的递归函数，下列哪个说法是正确的？

  1. A编译器总会把它变成能安全结束的循环
  2. B它的运行时间为 O(1)
  3. C它会自动返回 0
  4. D它会不断调用自身，直到调用栈溢出
10.算法与复杂度困难

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

  1. A不可能被解决
  2. B不属于 NP，但比所有 NP 问题都难，例如停机问题
  3. C属于 NP，且所有 NP 问题都能在多项式时间内归约到它
  4. D可以在多项式时间内解决
11.数据结构中等

在使用开放寻址法的哈希表中，可能的最大负载因子是多少？

  1. A没有最大值
  2. B2
  3. C0.5
  4. D1
12.数据结构困难

与有序链表相比，跳表（skip list）的主要优势是什么？

  1. A保证 O(1) 的查找，因为每个节点都存有指向其他所有节点的指针
  2. B利用多层前向指针，实现期望 O(log n) 的查找
  3. C它不占用额外内存
  4. D它以无序方式存储键
13.图论中等

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

4 × deg 44 × deg 5
L =
14.图论困难
18851213162014ABCDEF

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

|V| = 6|E| = 8
W =
15.数据库与 SQL中等

哪条语句删除表中的所有行、保留其结构，并且不能带 WHERE 子句？

  1. A带 WHERE 子句的 DELETE FROM
  2. BDROP TABLE
  3. CALTER TABLE
  4. DTRUNCATE TABLE
16.数据库与 SQL困难

哪个窗口函数在每个分区内为行分配 1、2、3……且不出现并列？

  1. ADENSE_RANK()
  2. BRANK()
  3. CCOUNT()
  4. DROW_NUMBER()
17.计算机网络中等

哪个 TCP 标志表示发送方已发送完数据？

  1. APSH
  2. BSYN
  3. CURG
  4. DFIN
18.计算机网络困难

在 TCP 连接中，接收窗口（rwnd）控制什么？

  1. A根据接收方缓冲区，发送方可以发送多少未确认的数据
  2. B每个 IP 数据包头部的大小
  3. C重传超时时间，根据每个报文段测得的往返时间计算
  4. D打开的端口数量
19.IPv4 子网划分中等
/24 → /2811111111111111111111111111110000网络位主机位

网络 192.168.82.0/24 被划分为若干 /28 子网，从最低地址起编号为 1、2、3、…（子网 1 从 .0 开始）。子网 10 的网络地址的第四个八位组 x 是多少？

192.168.82.0/24/28子网 10 (子网 1 从 .0 开始)
x =
20.IPv4 子网划分困难
最后一个八位组 = 252112816413211618140201网络主机

某主机地址为 10.20.155.252/26。其网络地址的第四个八位组 x 是多少？

10.20.155.252/26
x =

3溶液

1.数制

答案: U = 180

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

取反加一

76 = 0100 1100
取反后: 1011 0011
+1 → 1011 0100

按无符号数读取

1011 0100₂ = 256 − 76 = 180

答案

U = 180
2.数制

答案: R = 60

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

逐位计算

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

0001 1110 << 1
= 0011 1100

结果的值

0011 1100₂ = 60

答案

R = 60
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)。

逐行写出真值表

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

分类

(a ∧ (a → b)) → b: 1, 1, 1, 1
每一行都是 1：重言式。

答案

重言式
4.命题逻辑与证明

答案: q → r

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

所有前提都为真的行

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

结论

q → r (假言三段论)

答案

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

答案: AB = 00, CD = 01

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

每个 1 的邻格

有相邻 1 的 1 可以加入由两个或更多格子组成的圈。

m1: m0, m3, m5, m9 → 0
ABCD0001111000011110111111

孤立的 1

m1 = A′B′C′D → AB = 00, CD = 01

答案

AB = 00, CD = 01
6.数字逻辑：门电路、卡诺图与触发器

答案: N = 2

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

质蕴涵项

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

B′C′D, AC′, A′CD, A′B′D, ABD, A′B′C
ABCD000111100001111000X113120405X706X12113X150141819011010

最小覆盖

F = AC′ + A′B′C
N = 2

答案

N = 2
7.数论与模运算

答案: 47−1 mod 74 = 63

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

r = 74, t = 0
r = 47, q = 1, t = 1
r = 27, q = 1, t = −1
r = 20, q = 1, t = 2
r = 7, q = 2, t = −3
r = 6, q = 1, t = 8
r = 1, q = 6, t = −11

逆矩阵

1 ≡ −11·47 (mod 74)
x = 63
校核: 47·63 = 2961 = 40·74 + 1

答案

47−1 mod 74 = 63
8.数论与模运算

答案: 40180 mod 73 = 72

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

二进制指数

180 = 101101002 = 128 + 32 + 16 + 4

反复平方

401 ≡ 40 (mod 73)
402 ≡ 67 (mod 73)
404 ≡ 36 (mod 73)
408 ≡ 55 (mod 73)
4016 ≡ 32 (mod 73)
4032 ≡ 2 (mod 73)
4064 ≡ 4 (mod 73)
40128 ≡ 16 (mod 73)

把需要的幂相乘

40180 ≡ 36·32·2·16 ≡ 72 (mod 73)

答案

40180 mod 73 = 72
9.算法与复杂度

答案: D · 它会不断调用自身，直到调用栈溢出

为什么是这个答案

没有基本情况，递归就永远不会停止；实际上栈帧所需的内存会耗尽，程序随之崩溃。

答案

D · 它会不断调用自身，直到调用栈溢出
10.算法与复杂度

答案: C · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它

为什么是这个答案

NP 完全问题是 NP 中最难的问题；只要其中一个有多项式算法，整个 NP 就都有多项式算法。

答案

C · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它
11.数据结构

答案: D · 1

为什么是这个答案

使用开放寻址法时，所有键都存储在表本身中，因此 n 不能超过 m；拉链法的负载因子可以大于 1。

答案

D · 1
12.数据结构

答案: B · 利用多层前向指针，实现期望 O(log n) 的查找

为什么是这个答案

随机化的层级使查找能够跳过许多节点，从而使查找、插入和删除的期望时间为 O(log n)。

答案

B · 利用多层前向指针，实现期望 O(log n) 的查找
13.图论

答案: L = 22

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

树的握手引理

L + 36 = 2(L + 8) − 2
L = 22

答案

L = 22

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

14.图论

答案: W = 58

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

克鲁斯卡尔算法

BC (5): 取
AC (8): 取
BD (12): 取
CE (13): 取
BE (14): 跳过，会形成圈
DE (16): 跳过，会形成圈
AB (18): 跳过，会形成圈
DF (20): 取

总权重

W = 5 + 8 + 12 + 13 + 20 = 58

答案

W = 58
15.数据库与 SQL

答案: D · TRUNCATE TABLE

为什么是这个答案

TRUNCATE 快速清空表并保留其定义；DELETE 可以删除选定的行，DROP 则删除表本身。

答案

D · TRUNCATE TABLE
16.数据库与 SQL

答案: D · ROW_NUMBER()

为什么是这个答案

ROW_NUMBER 生成唯一的连续编号；RANK 在并列之后会留下间隔；DENSE_RANK 则不会。

答案

D · ROW_NUMBER()
17.计算机网络

答案: D · FIN

为什么是这个答案

每一方在没有更多数据时发送 FIN，另一方对其进行确认。SYN 用于建立连接；RST 用于中止连接。

答案

D · FIN
18.计算机网络

答案: A · 根据接收方缓冲区，发送方可以发送多少未确认的数据

为什么是这个答案

接收方通告其可用的缓冲区空间；发送方据此限制未确认的数据量，防止接收方过载。

答案

A · 根据接收方缓冲区，发送方可以发送多少未确认的数据
19.IPv4 子网划分

答案: x = 144

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

块大小

24 = 16

第 10 个子网

网络: (10 − 1)·16 = 144
广播: 144 + 16 − 1 = 159

答案

x = 144
20.IPv4 子网划分

答案: x = 192

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

块大小

26 = 64

该主机所在子网

网络: ⌊252/64⌋·64 = 192
广播: 192 + 64 − 1 = 255
可用主机: 193 … 254

答案

x = 192

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