1. Phương pháp chứng minh quy nạp toán học thường được sử dụng để chứng minh điều gì?
A. Tính đúng đắn của một thuật toán cụ thể.
B. Một mệnh đề đúng cho tất cả các số tự nhiên hoặc một tập con vô hạn của số tự nhiên.
C. Một mệnh đề đúng cho một số hữu hạn các trường hợp cụ thể.
D. Sự tồn tại của một đối tượng toán học nào đó.
2. Trong logic mệnh đề, phép toán nào sau đây được gọi là phép hội?
A. Phép tuyển (OR)
B. Phép kéo theo (Implication)
C. Phép hội (AND)
D. Phép phủ định (NOT)
3. Cho hàm f: Z → Z định nghĩa bởi f(x) = 2x + 1. Hàm f có phải là song ánh (bijective) không?
A. Có, vì f vừa đơn ánh vừa toàn ánh.
B. Không, vì f không đơn ánh.
C. Không, vì f không toàn ánh.
D. Không thể xác định.
4. Trong tổ hợp, chỉnh hợp chập k của n phần tử (k ≤ n) được tính bằng công thức nào?
A. n! ∕ (n-k)!
B. n! ∕ (k! × (n-k)!)
C. nᵏ
D. kⁿ
5. Trong lý thuyết đồ thị, đồ thị phẳng là đồ thị có thể vẽ được trên mặt phẳng sao cho:
A. Các cạnh không cắt nhau tại đỉnh.
B. Các cạnh không cắt nhau, ngoại trừ tại các đỉnh.
C. Các đỉnh không trùng nhau.
D. Mọi đỉnh đều có bậc chẵn.
6. Cho tập hợp S = {a, b, c}. Hỏi có bao nhiêu quan hệ thứ tự bộ phận (partial order relation) có thể định nghĩa trên S?
7. Cho tập hợp A = {1, 2, 3, 4, 5}. Hỏi có bao nhiêu tập con của A có đúng 3 phần tử?
A. 5!
B. 5³
C. C(5, 3) = 5! ∕ (3! × 2!)
D. P(5, 3) = 5! ∕ (5-3)!
8. Trong lý thuyết automata, DFA (Deterministic Finite Automaton) khác với NFA (Nondeterministic Finite Automaton) ở điểm nào?
A. DFA có thể có nhiều trạng thái hơn NFA.
B. Trong DFA, từ mỗi trạng thái và mỗi ký tự nhập, chỉ có duy nhất một trạng thái chuyển tiếp.
C. NFA luôn chấp nhận nhiều ngôn ngữ hơn DFA.
D. DFA dễ dàng xây dựng hơn NFA.
9. Trong lý thuyết đồ thị, khái niệm `bậc của đỉnh′ (degree of a vertex) trong đồ thị vô hướng được định nghĩa là gì?
A. Số lượng đỉnh kề với đỉnh đó.
B. Số lượng cạnh liên thuộc với đỉnh đó.
C. Tổng trọng số của các cạnh liên thuộc với đỉnh đó.
D. Số lượng đường đi ngắn nhất từ đỉnh đó đến tất cả các đỉnh khác.
10. Số cách chọn ra 3 học sinh từ một nhóm 10 học sinh để tham gia đội văn nghệ là bao nhiêu?
A. P(10, 3) = 10! ∕ (10-3)!
B. C(10, 3) = 10! ∕ (3! × (10-3)!)
C. 10³
D. 3¹⁰
11. Trong lý thuyết đồ thị, một đồ thị được gọi là đồ thị hai phía (bipartite graph) nếu tập đỉnh của nó có thể được chia thành hai tập con rời nhau V1 và V2 sao cho:
A. Mọi cạnh của đồ thị đều nối hai đỉnh trong cùng một tập con (V1 hoặc V2).
B. Mọi cạnh của đồ thị đều nối một đỉnh trong V1 và một đỉnh trong V2.
C. Có ít nhất một cạnh nối một đỉnh trong V1 và một đỉnh trong V2.
D. Số lượng đỉnh trong V1 và V2 phải bằng nhau.
12. Trong đại số Boolean, luật hấp thụ (absorption law) phát biểu rằng:
A. x + xy = x
B. x + x′ = 1
C. x × x′ = 0
D. x + y = y + x
13. Cho quan hệ R = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3)} trên tập hợp A = {1, 2, 3}. Quan hệ R có tính chất nào sau đây?
A. Đối xứng và phản xạ.
B. Phản xạ và bắc cầu.
C. Đối xứng và bắc cầu.
D. Đối xứng, phản xạ và bắc cầu.
14. Cây là một loại đồ thị đặc biệt. Phát biểu nào sau đây KHÔNG đúng về cây?
A. Cây là đồ thị liên thông.
B. Cây không chứa chu trình.
C. Giữa hai đỉnh bất kỳ của cây luôn có duy nhất một đường đi.
D. Mọi cây đều là đồ thị đầy đủ.
15. Xét quan hệ tương đương R trên tập hợp số nguyên Z được định nghĩa bởi aRb khi và chỉ khi a ≡ b (mod 3). Lớp tương đương của số 2 là tập hợp nào?
A. {…, -4, -1, 2, 5, 8, …}
B. {…, -3, 0, 3, 6, 9, …}
C. {…, -2, 1, 4, 7, 10, …}
D. {…, -1, 0, 1, 2, 3, …}
16. Trong lý thuyết đồ thị, khái niệm `đường đi Hamilton′ liên quan đến việc đi qua các đối tượng nào của đồ thị?
A. Đi qua tất cả các cạnh của đồ thị đúng một lần.
B. Đi qua tất cả các đỉnh của đồ thị đúng một lần.
C. Đi qua một tập hợp con các đỉnh của đồ thị.
D. Đi qua tất cả các cạnh và đỉnh của đồ thị.
17. Cho mệnh đề P: `Nếu trời mưa thì đường ướt′. Mệnh đề đảo của P là mệnh đề nào?
A. Nếu đường ướt thì trời mưa.
B. Nếu trời không mưa thì đường không ướt.
C. Nếu đường không ướt thì trời không mưa.
D. Trời mưa và đường không ướt.
18. Thuật toán Dijkstra được sử dụng để giải quyết bài toán nào trong lý thuyết đồ thị?
A. Tìm cây khung nhỏ nhất của đồ thị.
B. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm.
C. Tìm chu trình Euler trong đồ thị.
D. Tìm chu trình Hamilton trong đồ thị.
19. Trong số học, ước chung lớn nhất (ƯCLN) của hai số nguyên a và b được ký hiệu là gcd(a, b). Tính chất nào sau đây KHÔNG phải là tính chất của ƯCLN?
A. gcd(a, b) = gcd(b, a)
B. gcd(a, b) = gcd(a, b + ka) với mọi số nguyên k
C. gcd(ka, kb) = k × gcd(a, b) với mọi số nguyên dương k
D. gcd(a, b) luôn là một số nguyên tố.
20. Cho tập hợp A = {1, 2, 3} và B = {a, b}. Hỏi tích Descartes A x B là tập hợp nào?
A. {{1, a}, {1, b}, {2, a}, {2, b}, {3, a}, {3, b}}
B. {{a, 1}, {a, 2}, {a, 3}, {b, 1}, {b, 2}, {b, 3}}
C. {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
D. {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
21. Trong lý thuyết đồ thị, phát biểu nào sau đây về bậc của đỉnh trong đồ thị vô hướng là đúng?
A. Tổng bậc của tất cả các đỉnh trong đồ thị bằng số cạnh của đồ thị.
B. Tổng bậc của tất cả các đỉnh trong đồ thị bằng hai lần số cạnh của đồ thị.
C. Số đỉnh bậc lẻ trong đồ thị có thể là số lẻ hoặc số chẵn.
D. Tồn tại đồ thị mà tất cả các đỉnh đều có bậc lẻ.
22. Trong đại số Boolean, định luật De Morgan phát biểu rằng (x + y)′ = x′y′ và (xy)′ = x′ + y′. Ứng dụng định luật De Morgan, biểu thức (a + b′c)′ tương đương với biểu thức nào?
A. a′ + b′c′
B. a′ + (b′c)′
C. a′(b′c)′
D. a′(b + c′)
23. Trong logic vị từ, lượng từ ∀ được gọi là lượng từ nào?
A. Lượng từ tồn tại (Existential quantifier)
B. Lượng từ phổ quát (Universal quantifier)
C. Lượng từ duy nhất (Uniqueness quantifier)
D. Lượng từ phủ định (Negation quantifier)
24. Đồ thị vô hướng G = (V, E) được gọi là đồ thị Euler khi nào?
A. Khi đồ thị liên thông và có đúng hai đỉnh bậc lẻ.
B. Khi đồ thị liên thông và tất cả các đỉnh có bậc chẵn.
C. Khi đồ thị không liên thông và tất cả các đỉnh có bậc chẵn.
D. Khi đồ thị liên thông và có ít nhất một đỉnh bậc lẻ.
25. Trong lý thuyết tập hợp, phép toán nào sau đây được gọi là phép giao của hai tập hợp?
A. Phép hợp (Union)
B. Phép giao (Intersection)
C. Phép bù (Complement)
D. Phép hiệu (Difference)
26. Cho tập hợp A = {1, 2, 3, 4}. Quan hệ R trên A được định nghĩa bởi R = {(a, b) ∈ A x A | a chia hết cho b}. Quan hệ R có tính chất nào sau đây?
A. Đối xứng
B. Phản xạ
C. Bắc cầu
D. Phản đối xứng
27. Cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông có trọng số là gì?
A. Cây con liên thông chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh lớn nhất.
B. Cây con liên thông chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất.
C. Đường đi ngắn nhất giữa hai đỉnh bất kỳ trong đồ thị.
D. Chu trình Euler đi qua tất cả các cạnh của đồ thị.
28. Trong số học, thuật toán Euclid được sử dụng để tìm gì?
A. Bội chung nhỏ nhất (BCNN) của hai số.
B. Ước chung lớn nhất (ƯCLN) của hai số.
C. Số nguyên tố nhỏ hơn một số n cho trước.
D. Phân tích thừa số nguyên tố của một số.
29. Cho hàm mệnh đề P(x): `x là số chẵn′. Xét trên tập hợp các số nguyên Z. Giá trị chân lý của mệnh đề ∃x P(x) là gì?
A. Đúng
B. Sai
C. Không xác định
D. Tùy thuộc vào x
30. Cho hàm Boolean f(x, y, z) = x′yz + xy′z + xyz. Biểu thức tối giản của hàm f là:
A. yz + xz
B. xz + xy
C. yz + xy
D. xz + yz
