Nền tảng khoa học máy tính: gói ôn nước rút

Bảng công thức, các bước phương pháp chính cho từng chủ đề và 20 bài tập, kèm lời giải đầy đủ ở cuối.

Bài mớiQuay lại môn học

Trong cửa sổ in, hãy chọn “Lưu dưới dạng PDF” để giữ một bản trên thiết bị của bạn.

1Công thức và phương pháp

Hệ đếm

Giá trị vị trí
nhị phân 2k, bát phân 8k, thập lục phân 16k
Sang thập phân
Σ dk·bk
Từ thập phân
chia cho cơ số, đọc các số dư từ dưới lên
Thập lục phân ↔ nhị phân
một chữ số thập lục phân = 4 bit
Số bù hai
đảo các bit và cộng 1

Logic mệnh đề & chứng minh

Các hàng của bảng chân trị
2ⁿ
Phép kéo theo
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Phủ định của phép kéo theo
¬(p → q) ≡ p ∧ ¬q
Phép tương đương
p ↔ q ≡ (p → q) ∧ (q → p)
De Morgan
¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Luật phân phối
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Phủ định của lượng từ
¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens
p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Phương pháp

  1. Hãy đếm số biến khác nhau: bảng chân trị có 2ⁿ hàng, bắt đầu bằng hàng toàn số 1.
  2. Cho mỗi công thức con một cột riêng và điền các cột từ trong ra ngoài.
  3. Áp dụng quy tắc của từng liên kết: → chỉ bằng 0 khi 1 → 0, ↔ bằng 1 khi hai vế giống nhau.
  4. Với các tương đương, hãy so sánh các cột cuối theo từng hàng; với một suy luận, chỉ xét những hàng mà mọi tiền đề đều bằng 1.
  5. Để phủ định một mệnh đề có lượng từ, hãy đưa ¬ vào trong, đổi ∀ và ∃, rồi phủ định công thức bên trong.

Logic số: cổng, bìa K và flip-flop

Các cổng cơ bản
A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B
Các quy tắc Boole
X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X
De Morgan
(X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
Thứ tự của bìa Karnaugh
00, 01, 11, 10 (Gray code)
Nhóm 2ᵏ ô
mất k biến
Bộ ghép kênh 4-sang-1
F = A′B′I0 + A′BI1 + AB′I2 + ABI3
Flip-flop
D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
Bộ đếm
n bit: 2ⁿ trạng thái; mod-N: n nhỏ nhất thỏa 2ⁿ ≥ N; fout = fclk/N
Bộ đếm gợn sóng
fmax = 1/(n·tpd)
Bộ đếm vòng và Johnson
n và 2n trạng thái

Phương pháp

  1. Với một mạch, hãy làm từ các đầu vào đến đầu ra từng cổng một và ghi giá trị trên mọi dây, hoặc viết biểu thức của nó rồi điền bảng chân trị.
  2. Để rút gọn, hãy đặt các số 1 (và các điều kiện tùy định là X) vào một bìa Karnaugh với hàng và cột theo mã Gray: 00, 01, 11, 10.
  3. Hãy phủ các số 1 bằng càng ít nhóm và càng lớn càng tốt gồm 1, 2, 4, 8 hoặc 16 ô, cuộn qua mép; mỗi nhóm là một số hạng tích gồm các biến không đổi. Hãy nhóm các số 0 cho dạng POS.
  4. Với flip-flop và bộ đếm, hãy đọc các đầu vào tại mỗi sườn xung nhịp tích cực, ghi trạng thái sau mỗi sườn, và nhớ rằng bộ đếm n bit quay vòng sau 2ⁿ trạng thái.

Lý thuyết số & số học đồng dư

Phép chia có dư
a = q·n + r, 0 ≤ r < n
Euclid
gcd(a, b) = gcd(b, a mod b)
Bội chung nhỏ nhất
lcm(a, b) = a·b/gcd(a, b)
Nghịch đảo
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Đồng dư tuyến tính
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Hàm phi Euler
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Phương pháp

  1. Trước hết hãy rút gọn mọi số theo modulo n; số dư nằm trong khoảng từ 0 đến n − 1.
  2. Với ước chung lớn nhất, hãy chia liên tiếp theo thuật toán Euclid; số dư khác 0 cuối cùng chính là ước chung lớn nhất.
  3. Với số nghịch đảo, hãy chạy thuật toán Euclid mở rộng và lấy hệ số của a; cộng n nếu nó âm.
  4. Giải a·x ≡ b bằng cách nhân với a⁻¹; kết hợp hai đồng dư bằng cách viết x = r₁ + m₁k.
  5. Với lũy thừa, hãy viết số mũ ở dạng nhị phân và bình phương liên tiếp; trong RSA, d = e⁻¹ mod φ(n) với φ(n) = (p − 1)(q − 1).

Lý thuyết đồ thị

Bổ đề bắt tay
Σ deg(v) = 2|E|
Đồ thị đầy đủ
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Đồ thị đều
|E| = n·k/2
Cây và rừng
|E| = n − 1, |E| = n − c
Lá của cây
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
chu trình: mọi bậc đều chẵn; đường đi: đúng 2 bậc lẻ
Chu trình Hamilton trong Kn
(n − 1)!/2
Cập nhật Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Đường đi độ dài L
(Mᴸ)ij

Phương pháp

  1. Hãy ghi bậc của mỗi đỉnh; tổng các bậc bằng hai lần số cạnh.
  2. Với bài Euler, hãy kiểm tra đồ thị liên thông và đếm số đỉnh có bậc lẻ.
  3. Với cây, hãy dùng n − 1 cạnh và bổ đề bắt tay.
  4. Với Dijkstra, hãy lập bảng khoảng cách tạm thời và mỗi vòng chốt đỉnh chưa chốt có giá trị nhỏ nhất.
  5. Với cây khung nhỏ nhất, hãy sắp xếp các cạnh theo trọng số và bỏ qua mọi cạnh tạo thành chu trình (Kruskal), hoặc mở rộng một cây từ một đỉnh xuất phát (Prim).

Chia mạng con IPv4

Máy chủ trên mỗi mạng con
2(32 − prefix) − 2 (/31: 2, /32: 1)
Kích thước khối
256 − (mask octet)
Địa chỉ mạng
IP AND mặt nạ
Địa chỉ quảng bá
IP OR (NOT mask): tất cả bit host bằng 1
Mạng con từ n bit mượn
2n

2Bài tập

1.Hệ đếmTrung bình
giá trị vị trí trong số bù hai1−12806403211608140201

Dãy 8 bit 1001 0100 lưu một số nguyên có dấu dưới dạng số bù hai. Giá trị N của nó trong hệ thập phân là bao nhiêu?

1001 01008 bit
N =
2.Hệ đếmKhó
32 bit1 px1920 px1080 pxM = ? KiB

Một ảnh không nén có kích thước 1920 × 1080 điểm ảnh với 32 bit mỗi điểm ảnh. Nó chiếm bao nhiêu bộ nhớ M, tính theo KiB (1 KiB = 1024 byte)?

1920 × 1080 px32 bit/px1 KiB = 1024 B
M = KiB
3.Logic mệnh đề & chứng minhTrung bình
pqrr ∧ qq → p(r ∧ q) → (q → p)111?110?101?100?011?010?001?000?

Trong bao nhiêu hàng trong 8 hàng của bảng chân trị thì (r ∧ q) → (q → p) đúng? Gọi số này là N.

(r ∧ q) → (q → p)
N =
4.Logic mệnh đề & chứng minhKhó

Có bao nhiêu hàng trong 16 hàng của bảng chân trị làm ((b ∧ a) ∨ (d ∨ ¬c)) ∨ (b ∨ a) đúng? Gọi số này là N.

((b ∧ a) ∨ (d ∨ ¬c)) ∨ (b ∨ a)
N =
5.Logic số: cổng, bìa K và flip-flopTrung bình
MUX1I0​0I1​1I2​1I3​ABS1​S0​F

Một bộ ghép kênh 4-sang-1 có các đầu vào chọn S₁ = A và S₀ = B, và các đầu vào dữ liệu nối với I₀ = 1, I₁ = 0, I₂ = 1, I₃ = 1. Với bao nhiêu trong 8 tổ hợp của A, B và C thì đầu ra F = 1? Hãy tìm N.

I₀ = 1I₁ = 0I₂ = 1I₃ = 1
N =
6.Logic số: cổng, bìa K và flip-flopKhó
TQ0​Q0​TQ1​Q1​TQ2​Q2​TQ3​Q3​CLKMOD-10

Một bộ đếm thập phân (mod-10) đồng bộ đếm 0, 1, …, 9 rồi trở về 0. Nó bắt đầu ở 2. Sau 21 xung nhịp nó hiển thị giá trị đếm Q (theo hệ thập phân) nào?

Q0 = 221N = 10
Q =
7.Lý thuyết số & số học đồng dưTrung bình

Hãy tìm số nguyên dương nhỏ nhất x thỏa x ≡ 3 (mod 6) và x ≡ 5 (mod 11).

x ≡ 3 (mod 6)x ≡ 5 (mod 11)
x =
8.Lý thuyết số & số học đồng dưKhó
72c = me​ mod n?m = cd​ mod nm(n, e) = (589, 19)d

Hãy mã hóa thông điệp m = 72 bằng khóa công khai RSA (n, e) = (589, 19). Hãy tìm bản mã c.

n = 589e = 19m = 72
c =
9.Thuật toán và độ phức tạpTrung bình

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

  1. AO(n)
  2. BO(n²)
  3. CO(1)
  4. DO(log n)
10.Thuật toán và độ phức tạpKhó

Dùng định lý chủ, T(n) = 8T(n/2) + O(n²) có nghiệm là:

  1. AΘ(n³)
  2. BΘ(n log n)
  3. CΘ(n² log n)
  4. DΘ(n²)
11.Cấu trúc dữ liệuTrung bình

Cây AVL duy trì điều kiện cân bằng nào tại mọi nút?

  1. AMỗi nút được tô đỏ hoặc đen
  2. BChiều cao của cây con trái và phải chênh lệch tối đa 1
  3. CMọi lá ở cùng một độ sâu chính xác
  4. DCả hai cây con của mọi nút chứa đúng cùng số nút
12.Cấu trúc dữ liệuKhó

Mảng động nhân đôi khi đầy. Vì sao nhiều cách cài đặt chỉ thu nhỏ nó khi đầy một phần tư, không phải một nửa?

  1. AĐể giữ mảng được sắp xếp
  2. BVì chia đôi ở một nửa sẽ làm mất phần tử
  3. CĐể tránh đổi kích thước liên tục khi push và pop xen kẽ gần ranh giới
  4. DVì bộ cấp phát bộ nhớ chỉ có thể giải phóng bộ nhớ theo phần tư của một khối
13.Lý thuyết đồ thịTrung bình
ABCDEChu trình EulerĐường đi Euler, không có chu trìnhkhông phải cả hai

Đồ thị liên thông có chu trình Euler, đường đi Euler không phải chu trình, hay không có cái nào? Hãy nhấp vào đáp án của bạn.

|V| = 5|E| = 6
  1. 1Chu trình Euler
  2. 2Đường đi Euler, không có chu trình
  3. 3không phải cả hai
14.Lý thuyết đồ thịKhó
611599126119ABCDEFG

Thuật toán Dijkstra chạy từ A. Hãy nhấp vào đỉnh được chốt (trở thành cố định) ở vòng 3; bản thân A là vòng 1.

bắt đầu: Avòng 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
15.Cơ sở dữ liệu và SQLTrung bình

Khi nào WHERE EXISTS (subquery) đúng với một hàng?

  1. AKhi truy vấn con trả về ít nhất một hàng
  2. BKhi truy vấn con trả về một số lớn hơn không
  3. CKhi truy vấn con không trả về giá trị NULL nào
  4. DKhi truy vấn con trả về đúng một hàng
16.Cơ sở dữ liệu và SQLKhó

Bảng b chứa các giá trị 1, 2 và NULL trong cột y. SELECT * FROM a WHERE x NOT IN (SELECT y FROM b) trả về gì?

  1. AChỉ các hàng của a mà x là NULL
  2. BCác hàng của a mà x không phải 1 hoặc 2
  3. CMọi hàng của a
  4. DHoàn toàn không có hàng nào
17.Mạng máy tínhTrung bình

Dải nào sau đây là dải địa chỉ IPv4 riêng?

  1. A8.8.8.0/24
  2. B200.1.1.0/24
  3. C192.168.0.0/16
  4. D100.0.0.0/8
18.Mạng máy tínhKhó

Hiện tượng nghẽn đầu hàng (head-of-line blocking) trong HTTP/2 qua TCP xảy ra vì:

  1. AHTTP/2 dùng UDP
  2. BMột đoạn TCP bị mất làm chậm mọi luồng ghép kênh cho đến khi nó được truyền lại
  3. CMỗi yêu cầu cần một kết nối TCP mới riêng, nên các yêu cầu sau phải xếp hàng chờ
  4. DMáy chủ không xử lý được các yêu cầu song song
19.Chia mạng con IPv4Trung bình
/?11111111111111111111100000000000bit mạngbit máy chủ

Một phòng ban cần 1237 địa chỉ máy chủ trong một mạng con. Độ dài tiền tố dài nhất p (mạng con nhỏ nhất) đủ lớn là bao nhiêu?

1237 hosts
p =
20.Chia mạng con IPv4Khó
octet cuối = 129112806403201608040211mạngmáy chủ

Một máy chủ có địa chỉ 10.20.74.129/29. Octet thứ tư x của địa chỉ mạng của nó là bao nhiêu?

10.20.74.129/29
x =

3Dung dịch

1.Hệ đếm

Đáp số: N = −108

Hệ đếm theo vị trí: mỗi chữ số có giá trị bằng giá trị của nó nhân với một lũy thừa của cơ số. Trong hệ nhị phân, các vị trí có giá trị 1, 2, 4, 8, 16, …; trong hệ thập lục phân 1, 16, 256, …, với A–F biểu diễn 10–15. Trong số bù hai 8 bit, bit ngoài cùng bên trái có giá trị −128 thay vì +128, đó là cách lưu số âm.

Cộng các giá trị vị trí

Các bit còn lại giữ giá trị dương thông thường.

−128 + 16 + 4 = −108

Đáp số

N = −108
2.Hệ đếm

Đáp số: M = 8100 KiB

Hệ đếm theo vị trí: mỗi chữ số có giá trị bằng giá trị của nó nhân với một lũy thừa của cơ số. Trong hệ nhị phân, các vị trí có giá trị 1, 2, 4, 8, 16, …; trong hệ thập lục phân 1, 16, 256, …, với A–F biểu diễn 10–15. Trong số bù hai 8 bit, bit ngoài cùng bên trái có giá trị −128 thay vì +128, đó là cách lưu số âm.

Bit và byte

1920·1080·32 = 66355200 bit = 8294400 B

Đổi sang KiB

8294400/1024 = 8100 KiB

Đáp số

M = 8100 KiB
3.Logic mệnh đề & chứng minh

Đáp số: N = 7

Bảng chân trị: một công thức có n biến khác nhau có 2ⁿ hàng, mỗi hàng ứng với một tổ hợp giá trị chân trị (1 = đúng, 0 = sai). Hãy làm từ trong ra ngoài và cho mỗi công thức con một cột riêng. ¬a đảo giá trị; a ∧ b bằng 1 chỉ khi cả hai đều bằng 1; a ∨ b bằng 0 chỉ khi cả hai đều bằng 0; a → b bằng 0 chỉ khi a = 1 và b = 0; a ↔ b bằng 1 khi hai vế bằng nhau.

Bảng chân trị từng hàng

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

Đếm các hàng có giá trị 1

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

Đáp số

N = 7
4.Logic mệnh đề & chứng minh

Đáp số: N = 15

Bảng chân trị: một công thức có n biến khác nhau có 2ⁿ hàng, mỗi hàng ứng với một tổ hợp giá trị chân trị (1 = đúng, 0 = sai). Hãy làm từ trong ra ngoài và cho mỗi công thức con một cột riêng. ¬a đảo giá trị; a ∧ b bằng 1 chỉ khi cả hai đều bằng 1; a ∨ b bằng 0 chỉ khi cả hai đều bằng 0; a → b bằng 0 chỉ khi a = 1 và b = 0; a ↔ b bằng 1 khi hai vế bằng nhau.

Các cột

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

Chia theo a

a = 1: 8
a = 0: 7
N = 8 + 7 = 15

Đáp số

N = 15
5.Logic số: cổng, bìa K và flip-flop

Đáp số: N = 6

Bộ ghép kênh: một bộ ghép kênh 2ⁿ-sang-1 chuyển một trong các đầu vào dữ liệu của nó ra đầu ra; các đường chọn, đọc như một số nhị phân, quyết định đầu vào nào. Với MUX 4-sang-1 có các đường chọn S₁S₀ = AB, F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. Nối các đầu vào dữ liệu với 0, 1, C hoặc C′ làm MUX tạo ra bất kỳ hàm nào của A, B và C, đó là cách phổ biến để xây dựng logic bằng một chip.

Biểu thức đầu ra

F = A′B′ + AB′ + AB

Các hàng có F = 1

ABC = 000, 001, 100, 101, 110, 111
N = 6

Đáp số

N = 6
6.Logic số: cổng, bìa K và flip-flop

Đáp số: Q = 3

Flip-flop và bộ đếm: một flip-flop chỉ thay đổi ở sườn tích cực của xung nhịp. D sao chép đầu vào của nó (Q⁺ = D); T đảo khi T = 1; JK giữ nguyên với 00, đặt về 0 với 01, đặt lên 1 với 10 và đảo với 11. Một bộ đếm nhị phân n bit có 2ⁿ trạng thái và đếm theo modulo 2ⁿ; một bộ đếm mod-N đếm 0, 1, …, N − 1 rồi về lại 0, và cần số flip-flop n nhỏ nhất thỏa 2ⁿ ≥ N. Mỗi tầng của bộ đếm gợn sóng chia đôi tần số, nên đầu ra cuối của bộ đếm mod-N chạy ở fclk/N. Một bộ đếm Johnson gồm n flip-flop có 2n trạng thái, bộ đếm vòng có n.

Các chu kỳ đầy đủ

Cứ 10 xung thì bộ đếm trở về cùng một trạng thái.

21 = 2·10 + 1

Giá trị đếm sau các xung còn lại

Q = (2 + 1) mod 10 = 3
Q = 0011₂

Đáp số

Q = 3
7.Lý thuyết số & số học đồng dư

Đáp số: x = 27

Nghịch đảo và đồng dư: a có nghịch đảo theo modulo n đúng khi gcd(a, n) = 1. Thuật toán Euclid mở rộng viết 1 = s·n + t·a, và khi đó a⁻¹ ≡ t (mod n). Một đồng dư a·x ≡ b (mod n) với gcd(a, n) = 1 có nghiệm x ≡ a⁻¹·b. Hai đồng dư x ≡ r₁ (mod m₁) và x ≡ r₂ (mod m₂) với các modulo nguyên tố cùng nhau có một nghiệm theo modulo m₁·m₂ (định lý số dư Trung Hoa). φ(n) của Euler đếm các số từ 1 đến n nguyên tố cùng nhau với n: φ(n) = n·∏(1 − 1/p).

Đồng dư thứ nhất

x = 3 + 6k

Đồng dư thứ hai

3 + 6k ≡ 5 (mod 11) → 6k ≡ 2 (mod 11)
k ≡ 2·2 ≡ 4 (mod 11)

Kết quả

x = 3 + 6·4 = 27
x = 27
kiểm tra: 27 mod 6 = 3, 27 mod 11 = 5

Đáp số

x = 27
8.Lý thuyết số & số học đồng dư

Đáp số: c = 452

Lũy thừa modulo và RSA: tính aᵏ mod n bằng bình phương lặp: viết k ở dạng nhị phân, bình phương, rút gọn sau mỗi bước và nhân các lũy thừa có bit bằng 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) với số nguyên tố p không chia hết a, nên số mũ có thể được rút gọn theo modulo p − 1. RSA: chọn các số nguyên tố p và q, n = p·q và φ(n) = (p − 1)(q − 1); số mũ công khai e nguyên tố cùng nhau với φ(n), và số mũ bí mật là d = e⁻¹ mod φ(n). Mã hóa bằng c = mᵉ mod n và giải mã bằng m = cᵈ mod n.

Bình phương lặp

19 = 16 + 2 + 1
721 ≡ 72 (mod 589)
722 ≡ 472 (mod 589)
724 ≡ 142 (mod 589)
728 ≡ 138 (mod 589)
7216 ≡ 196 (mod 589)
7219 ≡ 72·472·196 ≡ 452 (mod 589)

Bản mã

c = 452

Đáp số

c = 452
9.Thuật toán và độ phức tạp

Đáp số: A · O(n)

Vì sao đây là đáp án

Đệ quy sâu n lời gọi trước khi có lời gọi nào trả về, và mỗi lời gọi cần một khung ngăn xếp, nên nó dùng không gian O(n).

Đáp số

A · O(n)
10.Thuật toán và độ phức tạp

Đáp số: A · Θ(n³)

Vì sao đây là đáp án

log₂ 8 = 3, và n² tăng chậm hơn n³, nên các lá chiếm ưu thế: Θ(n³).

Đáp số

A · Θ(n³)
11.Cấu trúc dữ liệu

Đáp số: B · Chiều cao của cây con trái và phải chênh lệch tối đa 1

Vì sao đây là đáp án

Hệ số cân bằng (chiều cao trái − chiều cao phải) phải là −1, 0 hoặc 1; các phép xoay khôi phục nó sau khi chèn và xóa.

Đáp số

B · Chiều cao của cây con trái và phải chênh lệch tối đa 1
12.Cấu trúc dữ liệu

Đáp số: C · Để tránh đổi kích thước liên tục khi push và pop xen kẽ gần ranh giới

Vì sao đây là đáp án

Thu nhỏ ở một nửa có thể gây đổi kích thước ở mọi thao tác trong chuỗi như vậy; khoảng cách giữa 1/4 và đầy giữ chi phí khấu hao ở O(1).

Đáp số

C · Để tránh đổi kích thước liên tục khi push và pop xen kẽ gần ranh giới
13.Lý thuyết đồ thị

Đáp số: không phải cả hai

Euler, Hamilton và cây: một đồ thị liên thông có chu trình Euler (đi qua mỗi cạnh một lần, trở về điểm đầu) khi mọi đỉnh có bậc chẵn, và có đường đi Euler không phải chu trình khi có đúng hai đỉnh bậc lẻ; khi đó đường đi chạy từ một đỉnh lẻ đến đỉnh lẻ kia. Một chu trình Hamilton thăm mỗi đỉnh một lần; Kn có (n − 1)!/2 chu trình như vậy. Một cây trên n đỉnh có n − 1 cạnh, và một đồ thị liên thông có m cạnh còn lại một cây khung sau khi bỏ m − n + 1 cạnh.

Các bậc

deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 1, deg(E) = 3

Các đỉnh lẻ

B, C, D, E → 4
không phải cả hai

Đáp số

không phải cả hai
14.Lý thuyết đồ thị

Đáp số: B

Đường đi ngắn nhất và cây khung: thuật toán Dijkstra chốt một đỉnh mỗi vòng: đỉnh chưa chốt có khoảng cách tạm thời nhỏ nhất. Khoảng cách của nó khi đó là cuối cùng, và mỗi đỉnh kề v được d(v) = min(d(v), d(u) + w(u, v)). Thuật toán Kruskal xây dựng cây khung nhỏ nhất bằng cách lấy các cạnh từ nhẹ đến nặng và bỏ qua mọi cạnh tạo thành chu trình; thuật toán Prim mở rộng một cây từ một đỉnh xuất phát bằng cách luôn thêm cạnh nhẹ nhất đi ra khỏi cây. Một cây khung của n đỉnh có n − 1 cạnh.

Dijkstra từng vòng

1. A (0): B: 6, C: 1
2. C (1): E: 10, G: 12
3. B (6)
4. E (10): F: 22
5. G (12): D: 21
6. D (21)
7. F (22)

vòng 3

B

Đáp số

B
15.Cơ sở dữ liệu và SQL

Đáp số: A · Khi truy vấn con trả về ít nhất một hàng

Vì sao đây là đáp án

EXISTS chỉ kiểm tra xem có hàng nào được tạo ra không; NOT EXISTS đúng khi truy vấn con không trả về hàng nào.

Đáp số

A · Khi truy vấn con trả về ít nhất một hàng
16.Cơ sở dữ liệu và SQL

Đáp số: D · Hoàn toàn không có hàng nào

Vì sao đây là đáp án

Phép so sánh với NULL là UNKNOWN, nên toàn bộ điều kiện không bao giờ là TRUE; dùng NOT EXISTS hoặc lọc bỏ NULL sẽ tránh được cái bẫy này.

Đáp số

D · Hoàn toàn không có hàng nào
17.Mạng máy tính

Đáp số: C · 192.168.0.0/16

Vì sao đây là đáp án

Các dải riêng là 10.0.0.0/8, 172.16.0.0/12 và 192.168.0.0/16; chúng không được định tuyến trên internet công cộng.

Đáp số

C · 192.168.0.0/16
18.Mạng máy tính

Đáp số: B · Một đoạn TCP bị mất làm chậm mọi luồng ghép kênh cho đến khi nó được truyền lại

Vì sao đây là đáp án

TCP chuyển các byte theo thứ tự, nên một lần mất gói làm tắc mọi luồng trên kết nối. QUIC (HTTP/3) xử lý các luồng độc lập qua UDP.

Đáp số

B · Một đoạn TCP bị mất làm chậm mọi luồng ghép kênh cho đến khi nó được truyền lại
19.Chia mạng con IPv4

Đáp số: p = 21

Chia mạng con IPv4: một địa chỉ có 32 bit. Tiền tố /p cho biết bao nhiêu bit đầu tiên xác định mạng; 32 − p bit còn lại đánh số các máy chủ. Một mạng con có 2³²⁻ᵖ địa chỉ, nhưng địa chỉ đầu (địa chỉ mạng) và địa chỉ cuối (địa chỉ quảng bá) không thể gán cho máy chủ, nên chứa được 2³²⁻ᵖ − 2 máy chủ. Ngoại lệ: /31 (liên kết điểm-điểm, RFC 3021) dùng cả 2 địa chỉ của nó cho host, còn /32 chỉ là một địa chỉ duy nhất (một host hoặc loopback).

Số bit máy chủ cần thiết

210 − 2 = 1022 < 1237
211 − 2 = 2046 ≥ 1237 → h = 11

Độ dài tiền tố

p = 32 − 11 = 21

Đáp số

p = /21
20.Chia mạng con IPv4

Đáp số: x = 128

Chia mạng con IPv4: một địa chỉ có 32 bit. Tiền tố /p cho biết bao nhiêu bit đầu tiên xác định mạng; 32 − p bit còn lại đánh số các máy chủ. Một mạng con có 2³²⁻ᵖ địa chỉ, nhưng địa chỉ đầu (địa chỉ mạng) và địa chỉ cuối (địa chỉ quảng bá) không thể gán cho máy chủ, nên chứa được 2³²⁻ᵖ − 2 máy chủ. Ngoại lệ: /31 (liên kết điểm-điểm, RFC 3021) dùng cả 2 địa chỉ của nó cho host, còn /32 chỉ là một địa chỉ duy nhất (một host hoặc loopback).

Kích thước khối

23 = 8

Mạng con của máy chủ này

mạng: ⌊129/8⌋·8 = 128
quảng bá: 128 + 8 − 1 = 135
máy chủ khả dụng: 129 … 134

Đáp số

x = 128

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