计算机科学导论：速成包

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

N = −248 bit

U =

2.数制困难

把各位设置为 1000 1111 XOR 1110 1100 的 8 位结果。该结果的十进制值 R 是多少？

1000 1111XOR1110 1100

R =

3.命题逻辑与证明中等

哪个公式与 (q ∧ r) → p 在逻辑上等价？点选它。

(q ∧ r) → p

1q ∧ (r → p)
2q → (r → p)
3(q → p) ∧ (r → p)
4(q → r) → p

4.命题逻辑与证明困难

前提为 p → r; q → r、结论为 p → q 的论证是无效的。点选真值表中作为反例的那一行。

p → rq → r∴ p → q

1p = 1, q = 1, r = 1
2p = 1, q = 1, r = 0
3p = 1, q = 0, r = 1
4p = 1, q = 0, r = 0
5p = 0, q = 1, r = 1
6p = 0, q = 1, r = 0
7p = 0, q = 0, r = 1
8p = 0, q = 0, r = 0

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

一个 4 选 1 多路选择器的选择输入为 S₁ = A 和 S₀ = B，数据输入分别接 I₀ = 0，I₁ = 1，I₂ = 1，I₃ = 1。在 A、B、C 的 8 种组合中，有多少种使输出 F = 1？求 N。

I₀ = 0I₁ = 1I₂ = 1I₃ = 1

N =

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

求 F(A, B, C, D) = Σm(1, 5, 7, 8, 12, 13, 14) + d(3, 9) 的最简 SOP 形式，其中 d 表示无关项。它包含多少个文字 L？

F(A, B, C, D) = Σm(1, 5, 7, 8, 12, 13, 14) + d(3, 9)

L =

7.数论与模运算中等

求满足 x ≡ 8 (mod 9) 和 x ≡ 1 (mod 10) 的最小正整数 x。

x ≡ 8 (mod 9)x ≡ 1 (mod 10)

x =

8.数论与模运算困难

某个 RSA 密钥使用 p = 7，q = 17，e = 23。解密密文 c = 27：求消息 m。

p = 7q = 17e = 23c = 27

m =

9.算法与复杂度中等

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

AO(n)
BO(2ⁿ)
CO(n log n)
DO(n²)

10.算法与复杂度困难

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

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

11.数据结构中等

AVL 树在每个节点上维持什么平衡条件？

A所有叶子都恰好位于同一深度
B每个节点的两棵子树包含完全相同数量的节点
C每个节点都被着成红色或黑色
D左右子树的高度之差至多为 1

12.数据结构困难

为什么数据库常用 B+ 树而不是普通的 B 树来建立索引？

A所有记录都在相互链接的叶子中，使范围扫描很高效
BB+ 树使用二叉内部节点，从而减少磁盘读取次数
CB+ 树只在根中存储数据
DB+ 树不需要保持平衡

13.图论中等

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

|V| = 19|E| = 25

k =

14.图论困难

克鲁斯卡尔算法构造最小生成树。点选它加入的第 5 条边；被跳过的边不计。

k = 5

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

15.数据库与 SQL中等

在关系代数中，投影运算符（π）对应于：

A选择哪些列出现在结果中
B按键组合两个表
C选择哪些行满足给定条件
D对结果排序

16.数据库与 SQL困难

对于一个查询，什么是覆盖索引？

A包含查询所需全部列的索引，因此不必读取表本身
B每晚重建一次的索引
C覆盖每个表每一列的索引
D只建在主键上的索引

17.计算机网络中等

主机上的默认网关有什么作用？

A它是主机所连接的交换机端口
B它负责分配 MAC 地址
C它是 DNS 服务器
D它是用于发往其他网络的流量的路由器

18.计算机网络困难

为什么 TCP 为每个连接选择一个不可预测的初始序列号？

A为该连接的各个报文段选择到达目的地的最佳路由
B更有效地压缩数据
C避免与旧的段混淆，并使伪造的段更难被注入
D加密每个段的净荷

19.IPv4 子网划分中等

网络 172.31.0.0/16 被划分为前缀为 /19 的等大子网。共有多少个子网 N？

172.31.0.0/16/19

N =

20.IPv4 子网划分困难

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

A: 27B: 10C: 30D: 3E: 4

x =

3溶液

1.数制

答案: U = 232

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

取反加一

24 = 0001 1000

取反后: 1110 0111

+1 → 1110 1000

按无符号数读取

1110 1000₂ = 256 − 24 = 232

答案

U = 232

2.数制

答案: R = 99

逐位计算

XOR 在两位不同时得 1。

1000 1111

XOR 1110 1100

= 0110 0011

结果的值

0110 0011₂ = 99

答案

R = 99

3.命题逻辑与证明

答案: q → (r → p)

逻辑等价：两个公式在真值表的每一行取值都相同时，它们是等价（≡）的。重言式在每一行都为 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 ∧ b) → c ≡ a → (b → c)。两者都只有在 a = 1、b = 1 且 c = 0 时才为 0。

(q ∧ r) → p ≡ q → (r → p)

用真值表检验

p = 1, q = 1, r = 1: 1 | 1 1 1 1

p = 1, q = 1, r = 0: 1 | 1 1 1 1

p = 1, q = 0, r = 1: 1 | 0 1 1 1

p = 1, q = 0, r = 0: 1 | 0 1 1 1

p = 0, q = 1, r = 1: 0 | 0 0 0 0

p = 0, q = 1, r = 0: 1 | 1 1 0 1

p = 0, q = 0, r = 1: 1 | 0 1 0 0

p = 0, q = 0, r = 0: 1 | 0 1 1 0

答案

q → (r → p)

竖线之后的各列是按所示顺序排列的各个选项。

4.命题逻辑与证明

答案: p = 1, q = 0, r = 1

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

逐行列出前提与结论

p = 1, q = 1, r = 1: 1 1 | 1

p = 1, q = 1, r = 0: 0 0 | 1

p = 1, q = 0, r = 1: 1 1 | 0

p = 1, q = 0, r = 0: 0 1 | 0

p = 0, q = 1, r = 1: 1 1 | 1

p = 0, q = 1, r = 0: 1 0 | 1

p = 0, q = 0, r = 1: 1 1 | 1

p = 0, q = 0, r = 0: 1 1 | 1

反例

p = 1, q = 0, r = 1

答案

p = 1, q = 0, r = 1

这种形式的论证看起来像有效的规则，但只要有一行就足以说明它并不有效。

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

答案: N = 6

多路选择器：2ⁿ 选 1 多路选择器把其数据输入之一传到输出；选择线按二进制数读取，决定选哪一个。对于选择端 S₁S₀ = AB 的 4 选 1 MUX，F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃。把数据输入接到 0、1、C 或 C′，可使 MUX 产生 A、B、C 的任意函数，这是用一块芯片实现逻辑的常用方法。

输出表达式

F = A′B + AB′ + AB

F = 1 的行

ABC = 010, 011, 100, 101, 110, 111

N = 6

答案

N = 6

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

答案: L = 7

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

质蕴涵项

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

C′D, A′D, AC′, ABD′

最小覆盖

F = A′D + AC′ + ABD′

L = 7

答案

L = 7

7.数论与模运算

答案: x = 71

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

第二个同余式

8 + 9k ≡ 1 (mod 10) → 9k ≡ 3 (mod 10)

k ≡ 9·3 ≡ 7 (mod 10)

结果

x = 8 + 9·7 = 71

x = 71

校核: 71 mod 9 = 8, 71 mod 10 = 1

答案

x = 71

8.数论与模运算

答案: m = 90

模幂与 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 = 119, φ(n) = 96

d = 23⁻¹ mod 96 = 71

用反复平方法解密

71 = 64 + 4 + 2 + 1

27¹ ≡ 27 (mod 119)

27² ≡ 15 (mod 119)

27⁴ ≡ 106 (mod 119)

27⁸ ≡ 50 (mod 119)

27¹⁶ ≡ 1 (mod 119)

27³² ≡ 1 (mod 119)

27⁶⁴ ≡ 1 (mod 119)

27⁷¹ ≡ 27·15·106·1 ≡ 90 (mod 119)

消息

m = 90

生成树的边数

19 − 1 = 18

要去掉的边数

k = 25 − 18 = 7

答案

k = 7

14.图论

答案: 边 CE

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

克鲁斯卡尔算法

1. EF (3)

2. BD (4)

3. DF (6)

4. AB (16)

5. CE (19)

随机的初始序列号能防止旧连接中延迟到达的段被接受，并使不在路径上的攻击者难以伪造有效的段。

答案

C · 避免与旧的段混淆，并使伪造的段更难被注入

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

借用位

19 − 16 = 3

子网数

N = 2³ = 8

答案

N = 8

每个 /19 子网有 2¹³ − 2 = 8190 个可用主机。

20.IPv4 子网划分

答案: x = 64

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

每个局域网的块大小

C: 30 主机 → 2⁵ = 32 (/27)

A: 27 主机 → 2⁵ = 32 (/27)

B: 10 主机 → 2⁴ = 16 (/28)

E: 4 主机 → 2³ = 8 (/29)

D: 3 主机 → 2³ = 8 (/29)

分配顺序，从大到小

C: .0 – .31

A: .32 – .63

B: .64 – .79

E: .80 – .87

D: .88 – .95

答案

x = 64

局域网 B：192.168.194.64/28。

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