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
Số bù hai 8 bit0−12806403201608040201

Đặt các bit để lưu −47 theo bù hai 8 bit. Đọc như một số không dấu, giá trị U của mẫu là bao nhiêu?

N = −478 bit
U =
2.Hệ đếmKhó
nhấp vào các bit để đặt chúng012806403201608040201

Đặt các bit thành kết quả 8 bit của 1001 1001 OR 1001 1100. Giá trị R của kết quả theo hệ thập phân là bao nhiêu?

1001 1001OR1001 1100
R =
3.Logic mệnh đề & chứng minhTrung bình
¬c ∧ ¬¬ac ∧ ¬¬a¬c ∧ ¬a¬c → ¬¬a

Bạn muốn chứng minh c → ¬a bằng phản chứng. Lúc bắt đầu bạn giả sử phát biểu nào? Hãy nhấp vào nó.

c → ¬a
  1. 1¬c ∧ ¬¬a
  2. 2c ∧ ¬¬a
  3. 3¬c ∧ ¬a
  4. 4¬c → ¬¬a
4.Logic mệnh đề & chứng minhKhó
∃x ∃y (R(x, y) → ¬R(y, x))∀x ∀y (R(x, y) ∧ ¬R(y, x))∃x ∃y (¬R(x, y) ∧ ¬R(y, x))∃x ∃y (R(x, y) ∧ ¬R(y, x))

Phát biểu nào tương đương với ¬∀x ∀y (R(x, y) → R(y, x)), khi phép phủ định đã được đưa hoàn toàn vào trong? Hãy nhấp vào nó.

¬∀x ∀y (R(x, y) → R(y, x))
  1. 1∃x ∃y (R(x, y) → ¬R(y, x))
  2. 2∀x ∀y (R(x, y) ∧ ¬R(y, x))
  3. 3∃x ∃y (¬R(x, y) ∧ ¬R(y, x))
  4. 4∃x ∃y (R(x, y) ∧ ¬R(y, x))
5.Logic số: cổng, bìa K và flip-flopTrung bình
ABCD000111100001111011111

Trong bìa Karnaugh này, đúng một số 1 không có số 1 kề, nên nó vẫn là một nhóm một ô (một minterm đầy đủ bốn literal) trong dạng SOP tối thiểu. Các ô kề qua mép bìa cũng được tính. Hãy nhấp vào ô đó.

F = Σm(0, 4, 9, 10, 14)
  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.Logic số: cổng, bìa K và flip-flopKhó
ABCD00011110000111101001X30204X51716X120130151140819011110

Với F(A, B, C, D) = Σm(0, 6, 7, 9, 10, 14) + d(3, 5, 12), trong đó d đánh dấu các điều kiện tùy định, hãy tìm số N các implicant nguyên tố cốt yếu.

F(A, B, C, D) = Σm(0, 6, 7, 9, 10, 14) + d(3, 5, 12)
N =
7.Lý thuyết số & số học đồng dưTrung bình

Hãy tìm nghịch đảo của 32 theo modulo 47: số x với 0 < x < 47 và 32·x ≡ 1 (mod 47).

a = 32n = 47
32−1 mod 47 =
8.Lý thuyết số & số học đồng dưKhó
mc = me​ mod ncm = cd​ mod nm(n, e) = (259, 19)d = ?

Một khóa RSA dùng các số nguyên tố p = 7 và q = 37 và số mũ công khai e = 19. Hãy tìm số mũ bí mật d (0 < d < φ(n)).

p = 7q = 37e = 19
d =
9.Thuật toán và độ phức tạpTrung bình

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

  1. AĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
  2. BĐúng, nhưng chỉ khi n nhỏ hơn 100
  3. CKhông, vì n³ nhỏ hơn n² khi n lớn
  4. DKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
10.Thuật toán và độ phức tạpKhó

Vì sao tìm kiếm nhị phân không cho thời gian O(log n) trên một danh sách liên kết đơn?

  1. ACác phép so sánh trên nút danh sách liên kết chậm hơn
  2. BDanh sách liên kết không thể được sắp xếp
  3. CTìm kiếm nhị phân cần ít nhất gấp đôi bộ nhớ
  4. DĐến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp
11.Cấu trúc dữ liệuTrung bình

Trie (cây tiền tố) đặc biệt hiệu quả cho:

  1. ATìm đường đi ngắn nhất
  2. BLưu trữ ma trận
  3. CSắp xếp các số
  4. DTìm kiếm theo tiền tố như tự động hoàn thành
12.Cấu trúc dữ liệuKhó

Một đối tượng được lưu làm khóa trong bản đồ băm, rồi một trường được hàm băm của nó sử dụng bị thay đổi. Kết quả có khả năng nhất là gì?

  1. ABản đồ tự động chuyển khóa sang ngăn mới
  2. BTra cứu đối tượng có thể thất bại vì nó nằm trong ngăn ứng với giá trị băm cũ
  3. CBản đồ ném lỗi ngay lúc trường thay đổi
  4. DKhông có gì thay đổi, vì giá trị băm của khóa chỉ được tính một lần khi chương trình khởi động
13.Lý thuyết đồ thịTrung bình

Một đồ thị liên thông có 17 đỉnh và 21 cạnh. Phải bỏ bao nhiêu cạnh k để còn lại một cây khung?

|V| = 17|E| = 21
k =
14.Lý thuyết đồ thịKhó
ABCDEF

Có bao nhiêu đường đi độ dài 3 từ A đến F? Một đường đi có thể lặp lại đỉnh và cạnh. Gọi số đó là N.

M = ma trận kềL = 3
N =
15.Cơ sở dữ liệu và SQLTrung bình

SQL injection là gì?

  1. AMột cách thêm chỉ mục
  2. BMột kỹ thuật sao lưu cơ sở dữ liệu
  3. CMột kỹ thuật chèn nhanh nhiều hàng bằng một câu lệnh INSERT duy nhất
  4. DMột cuộc tấn công trong đó dữ liệu người dùng nhập làm thay đổi cấu trúc của truy vấn SQL
16.Cơ sở dữ liệu và SQLKhó

Vì sao SELECT dept, name, COUNT(*) FROM emp GROUP BY dept không hợp lệ trong SQL chuẩn?

  1. Aname không được nhóm cũng không được tổng hợp, nên nó không có một giá trị duy nhất cho mỗi nhóm
  2. BGROUP BY phải liệt kê mọi cột của bảng
  3. Cdept phải xuất hiện bên trong một hàm tổng hợp
  4. DCOUNT(*) không thể dùng cùng GROUP BY
17.Mạng máy tínhTrung bình

Địa chỉ mạng của máy 192.168.10.77/26 là gì?

  1. A192.168.10.64
  2. B192.168.10.128
  3. C192.168.10.0
  4. D192.168.10.76
18.Mạng máy tínhKhó

Đơn vị truyền tối đa (MTU) của tải trọng Ethernet chuẩn là bao nhiêu?

  1. A64 byte
  2. B9000 byte trong mọi mạng
  3. C1500 byte
  4. D65,535 byte
19.Chia mạng con IPv4Trung bình
/24 → /2611111111111111111111111111000000bit mạngbit máy chủ

Mạng 192.168.10.0/24 phải được chia thành ít nhất 3 mạng con bằng nhau. Nếu mượn ít bit nhất có thể, mỗi mạng con có bao nhiêu máy chủ khả dụng H?

192.168.10.0/243 subnets
H =
20.Chia mạng con IPv4Khó
octet cuối = 128112806403201608040201mạngmáy chủ

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

10.20.173.128/27
x =

3Dung dịch

1.Hệ đếm

Đáp số: U = 209

Đặt các bit: mỗi bit có giá trị bằng một lũy thừa của hai (128, 64, …, 1). Một chữ số hex đúng bằng bốn bit, và trong bù hai 8 bit, bit ngoài cùng bên trái có giá trị −128. Các phép toán theo bit làm việc trên từng vị trí bit riêng biệt.

Đảo bit và cộng một

47 = 0010 1111
đã đảo: 1101 0000
+1 → 1101 0001

Đọc như số không dấu

1101 0001₂ = 256 − 47 = 209

Đáp số

U = 209
2.Hệ đếm

Đáp số: R = 157

Đặt các bit: mỗi bit có giá trị bằng một lũy thừa của hai (128, 64, …, 1). Một chữ số hex đúng bằng bốn bit, và trong bù hai 8 bit, bit ngoài cùng bên trái có giá trị −128. Các phép toán theo bit làm việc trên từng vị trí bit riêng biệt.

Từng bit một

OR cho 1 ở nơi có ít nhất một bit là 1.

1001 1001
OR 1001 1100
= 1001 1101

Giá trị của kết quả

1001 1101₂ = 157

Đáp số

R = 157
3.Logic mệnh đề & chứng minh

Đáp số: c ∧ ¬¬a

Tương đương logic: hai công thức tương đương (≡) khi chúng có cùng giá trị ở mọi hàng của bảng chân trị. Hằng đúng bằng 1 ở mọi hàng, mâu thuẫn bằng 0 ở mọi hàng, còn công thức ngẫu nhiên thì không thuộc loại nào. Các luật hữu ích: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b và ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (phản đảo); ¬(a → b) ≡ a ∧ ¬b; và các luật phân phối, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Các phần của phép kéo theo

a = c, b = ¬a

Phủ định của phép kéo theo

¬(a → b) ≡ a ∧ ¬b = c ∧ ¬¬a

Đáp số

c ∧ ¬¬a

Nếu giả thiết dẫn đến mâu thuẫn thì phép kéo theo phải đúng.

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

Đáp số: ∃x ∃y (R(x, y) ∧ ¬R(y, x))

Lượng từ và suy luận: ¬∀x P(x) ≡ ∃x ¬P(x) và ¬∃x P(x) ≡ ∀x ¬P(x). Đưa phép phủ định vào trong, đổi mọi lượng từ mà nó đi qua, và phủ định công thức bên trong bằng các luật logic mệnh đề, chẳng hạn ¬(a → b) ≡ a ∧ ¬b. Một suy luận hợp lệ khi kết luận bằng 1 ở mọi hàng mà tất cả tiền đề đều bằng 1. Chỉ một hàng có tiền đề đúng mà kết luận sai là một phản ví dụ và cho thấy suy luận không hợp lệ.

Đưa phép phủ định vào trong

¬∀x ∀y (R(x, y) → R(y, x)) ≡ ∃x ∃y (R(x, y) ∧ ¬R(y, x))

Đáp số

∃x ∃y (R(x, y) ∧ ¬R(y, x))

Các phương án còn lại hoặc giữ nguyên một lượng từ, hoặc đổi thứ tự các lượng từ, hoặc phủ định sai công thức bên trong.

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

Đáp số: AB = 10, CD = 01

Bìa Karnaugh: các ô được sắp xếp theo mã Gray (00, 01, 11, 10), nên các ô kề nhau, kể cả những ô qua mép, khác nhau đúng một biến. Hãy nhóm các số 1 thành hình chữ nhật gồm 1, 2, 4, 8 hoặc 16 ô, lớn nhất có thể và ít nhóm nhất có thể, cho đến khi mọi số 1 đều được phủ. Mỗi nhóm là một số hạng tích: các biến không đổi bên trong nó. Một nhóm 2ᵏ ô mất k biến. Các điều kiện tùy định (X) có thể dùng để làm nhóm lớn hơn nhưng không bắt buộc phải được phủ. Nhóm các số 0 thay vào đó sẽ cho dạng POS tối thiểu.

Các ô kề của mỗi số 1

Một số 1 có số 1 kề có thể thuộc một nhóm hai ô hoặc lớn hơn.

m9: m8, m11, m13, m1 → 0
ABCD000111100001111011111

Số 1 cô lập

m9 = AB′C′D → AB = 10, CD = 01

Đáp số

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

Đáp số: N = 3

Bìa Karnaugh: các ô được sắp xếp theo mã Gray (00, 01, 11, 10), nên các ô kề nhau, kể cả những ô qua mép, khác nhau đúng một biến. Hãy nhóm các số 1 thành hình chữ nhật gồm 1, 2, 4, 8 hoặc 16 ô, lớn nhất có thể và ít nhóm nhất có thể, cho đến khi mọi số 1 đều được phủ. Mỗi nhóm là một số hạng tích: các biến không đổi bên trong nó. Một nhóm 2ᵏ ô mất k biến. Các điều kiện tùy định (X) có thể dùng để làm nhóm lớn hơn nhưng không bắt buộc phải được phủ. Nhóm các số 0 thay vào đó sẽ cho dạng POS tối thiểu.

Các implicant nguyên tố

Các nhóm lớn nhất có thể tạo từ các số 1 và các X.

BCD′, A′CD, ACD′, A′BD, ABD′, A′BC, A′B′C′D′, AB′C′D
ABCD00011110000111101001X30204X51716X120130151140819011110

Các implicant nguyên tố cốt yếu

ACD′, A′B′C′D′, AB′C′D
N = 3

Đáp số

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

Đáp số: 32−1 mod 47 = 25

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

Thuật toán Euclid mở rộng

Mỗi số dư r được viết là r ≡ t·32 (mod 47).

r = 47, t = 0
r = 32, q = 1, t = 1
r = 15, q = 2, t = −1
r = 2, q = 7, t = 3
r = 1, q = 2, t = −22

Nghịch đảo

1 ≡ −22·32 (mod 47)
x = 25
kiểm tra: 32·25 = 800 = 17·47 + 1

Đáp số

32−1 mod 47 = 25
8.Lý thuyết số & số học đồng dư

Đáp số: d = 91

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.

Modulo và hàm phi

n = 7·37 = 259
φ(n) = 6·36 = 216

Thuật toán Euclid mở rộng

r = 216, t = 0
r = 19, q = 11, t = 1
r = 7, q = 2, t = −11
r = 5, q = 1, t = 23
r = 2, q = 2, t = −34
r = 1, q = 2, t = 91

Số mũ bí mật

d = 91
kiểm tra: 19·91 = 1729 = 8·216 + 1

Đáp số

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

Đáp số: A · Đúng, vì Big O là cận trên và n² tăng không nhanh hơn n³

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

Big O là cận trên, nên phát biểu đúng nhưng không chặt; Θ(n²) nêu tốc độ tăng chính xác.

Đáp số

A · Đúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
10.Thuật toán và độ phức tạp

Đáp số: D · Đến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp

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

Tìm kiếm nhị phân cần truy cập O(1) vào phần tử giữa; trên danh sách liên kết, đi đến đó tốn thời gian tuyến tính, nên tổng là O(n).

Đáp số

D · Đến được phần tử giữa mất O(n) bước, vì không có truy cập chỉ số trực tiếp
11.Cấu trúc dữ liệu

Đáp số: D · Tìm kiếm theo tiền tố như tự động hoàn thành

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

Trie lưu các chuỗi theo từng ký tự dọc đường đi, nên tra cứu và truy vấn tiền tố tốn thời gian tỷ lệ với độ dài khóa.

Đáp số

D · Tìm kiếm theo tiền tố như tự động hoàn thành
12.Cấu trúc dữ liệu

Đáp số: B · Tra cứu đối tượng có thể thất bại vì nó nằm trong ngăn ứng với giá trị băm cũ

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

Vị trí của khóa được chọn từ giá trị băm cũ; với giá trị băm mới, các lần tra cứu tìm sai ngăn, nên khóa phải bất biến.

Đáp số

B · Tra cứu đối tượng có thể thất bại vì nó nằm trong ngăn ứng với giá trị băm cũ
13.Lý thuyết đồ thị

Đáp số: k = 5

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 cạnh của cây khung

17 − 1 = 16

Các cạnh cần bỏ

k = 21 − 16 = 5

Đáp số

k = 5
14.Lý thuyết đồ thị

Đáp số: N = 1

Bậc: bậc của một đỉnh là số cạnh gặp đỉnh đó. Mỗi cạnh có hai đầu, nên tổng các bậc bằng hai lần số cạnh: Σ deg(v) = 2|E| (bổ đề bắt tay). Do đó số đỉnh có bậc lẻ là số chẵn. Kn có n(n − 1)/2 cạnh, một đồ thị k-đều trên n đỉnh có nk/2 cạnh, và một cây trên n đỉnh có n − 1 cạnh.

Ma trận kề

A: 0 1 1 0 0 0
B: 1 0 1 0 1 0
C: 1 1 0 0 0 0
D: 0 0 0 0 1 1
E: 0 1 0 1 0 1
F: 0 0 0 1 1 0

Thêm một bước

(M³)AF = 2·0 + 1·0 + 1·0 + 0·1 + 1·1 + 0·0 = 1

Đáp số

N = 1
15.Cơ sở dữ liệu và SQL

Đáp số: D · Một cuộc tấn công trong đó dữ liệu người dùng nhập làm thay đổi cấu trúc của truy vấn SQL

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

Khi dữ liệu người dùng nhập được nối vào SQL, kẻ tấn công có thể chèn lệnh. Câu lệnh chuẩn bị sẵn (prepared statement) với tham số giữ dữ liệu tách biệt khỏi mã.

Đáp số

D · Một cuộc tấn công trong đó dữ liệu người dùng nhập làm thay đổi cấu trúc của truy vấn SQL
16.Cơ sở dữ liệu và SQL

Đáp số: A · name không được nhóm cũng không được tổng hợp, nên nó không có một giá trị duy nhất cho mỗi nhóm

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

Mọi cột trong danh sách SELECT phải nằm trong GROUP BY hoặc bên trong một hàm tổng hợp (hoặc phụ thuộc hàm vào các cột nhóm); nếu không giá trị sẽ mơ hồ.

Đáp số

A · name không được nhóm cũng không được tổng hợp, nên nó không có một giá trị duy nhất cho mỗi nhóm
17.Mạng máy tính

Đáp số: A · 192.168.10.64

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

Các mạng con /26 bắt đầu tại 0, 64, 128 và 192. 77 nằm trong khối 64–127, nên địa chỉ mạng là 192.168.10.64.

Đáp số

A · 192.168.10.64
18.Mạng máy tính

Đáp số: C · 1500 byte

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

Ethernet chuẩn mang tối đa 1500 byte tải trọng; các gói IP lớn hơn phải được phân mảnh hoặc dùng khám phá MTU đường truyền.

Đáp số

C · 1500 byte
19.Chia mạng con IPv4

Đáp số: H = 62

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 cần mượn

22 = 4 ≥ 3 → b = 2, /26

Máy chủ trên mỗi mạng con

26 − 2 = 62

Đáp số

H = 62
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

25 = 32

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

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

Đáp số

x = 128

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