1. Trong lý thuyết automata, DFA (Deterministic Finite Automaton) là gì?
A. Máy trạng thái hữu hạn không đơn định.
B. Máy trạng thái hữu hạn đơn định.
C. Máy Turing đơn định.
D. Máy Turing không đơn định.
2. Trong lý thuyết tập hợp, phép toán nào sau đây trả về tập hợp chứa tất cả các phần tử thuộc cả hai tập hợp đầu vào?
A. Giao (Intersection)
B. Hợp (Union)
C. Hiệu (Difference)
D. Bù (Complement)
3. Phát biểu nào sau đây là đúng về đồ thị Euler?
A. Đồ thị có chu trình Hamilton.
B. Đồ thị có đường đi Hamilton.
C. Đồ thị liên thông mà mọi đỉnh có bậc chẵn.
D. Đồ thị liên thông mà có đúng hai đỉnh bậc lẻ.
4. Trong lý thuyết đồ thị, thuật toán Kruskal được sử dụng để làm gì?
A. Tìm cây khung nhỏ nhất (Minimum Spanning Tree).
B. Tìm đường đi ngắn nhất.
C. Kiểm tra tính liên thông của đồ thị.
D. Tìm luồng cực đại trong mạng.
5. Trong số học, thuật toán Euclid được sử dụng để tìm gì?
A. Bội chung nhỏ nhất (BCNN).
B. Ước chung lớn nhất (ƯCLN).
C. Phân tích thừa số nguyên tố.
D. Số nguyên tố.
6. Đồ thị vô hướng được gọi là cây khi nó thỏa mãn đồng thời hai điều kiện nào sau đây?
A. Liên thông và có chu trình.
B. Không liên thông và không có chu trình.
C. Liên thông và không có chu trình.
D. Không liên thông và có chu trình.
7. Mệnh đề phủ định của mệnh đề 'Mọi số tự nhiên đều lớn hơn 0' là gì?
A. 'Tồn tại một số tự nhiên không lớn hơn 0'.
B. 'Mọi số tự nhiên đều nhỏ hơn hoặc bằng 0'.
C. 'Không có số tự nhiên nào lớn hơn 0'.
D. 'Tất cả các số không phải số tự nhiên đều lớn hơn 0'.
8. Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính (linear search) trong trường hợp xấu nhất là bao nhiêu, với n là kích thước của dữ liệu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
9. Trong logic mệnh đề, quy tắc suy diễn Modus Ponens có dạng nào?
A. [(p → q) ∧ ¬q] → ¬p
B. [(p → q) ∧ p] → q
C. [(p ∨ q) ∧ ¬p] → q
D. [(p ∧ q) ∧ p] → q
10. Cho hàm mệnh đề P(x): 'x là số chẵn'. Miền xác định là tập hợp số nguyên. Giá trị chân lý của ∀x P(x) là gì?
A. Đúng.
B. Sai.
C. Không xác định.
D. Vừa đúng vừa sai.
11. Tìm số nghiệm nguyên không âm của phương trình x + y + z = 5.
12. Cho tập hợp A = {1, 2, 3}. Số lượng tập con của tập hợp A là bao nhiêu?
13. Trong đại số Boole, luật De Morgan phát biểu rằng (x + y)' bằng:
A. x' + y'
B. x' * y'
C. x * y
D. x + y
14. Một dãy số được định nghĩa bởi công thức truy hồi a_n = 2a_{n-1} - a_{n-2} với a_0 = 1, a_1 = 2. Giá trị của a_3 là bao nhiêu?
15. Trong logic vị từ, lượng từ '∃' được gọi là:
A. Lượng từ phổ dụng (Universal quantifier).
B. Lượng từ tồn tại (Existential quantifier).
C. Lượng từ duy nhất.
D. Lượng từ phủ định.
16. Hàm số f: A → B được gọi là đơn ánh (injective) khi nào?
A. Với mọi a1, a2 ∈ A, nếu f(a1) = f(a2) thì a1 = a2.
B. Với mọi b ∈ B, tồn tại ít nhất một a ∈ A sao cho f(a) = b.
C. Với mọi a ∈ A, tồn tại duy nhất một b ∈ B sao cho f(a) = b.
D. Với mọi b ∈ B, tồn tại nhiều nhất một a ∈ A sao cho f(a) = b.
17. Cho quan hệ R = {(1, 1), (1, 2), (2, 2), (3, 3)} trên tập A = {1, 2, 3}. Quan hệ R có tính chất nào sau đây?
A. Đối xứng.
B. Phản đối xứng.
C. Bắc cầu.
D. Vừa phản xạ vừa đối xứng.
18. Số cạnh tối đa trong một đồ thị đơn vô hướng đầy đủ có n đỉnh là bao nhiêu?
A. n
B. n-1
C. n(n-1)/2
D. n^2
19. Phương pháp chứng minh quy nạp (Mathematical Induction) 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. Sự tồn tại của một đối tượng toán học.
D. Tính duy nhất của một đối tượng toán học.
20. Trong bài toán đếm, nguyên lý bù trừ (Principle of Inclusion-Exclusion) được sử dụng để làm gì?
A. Tính số phần tử của giao của các tập hợp.
B. Tính số phần tử của hợp của các tập hợp.
C. Tính số phần tử của hiệu của các tập hợp.
D. Tính số phần tử của tích Descartes của các tập hợp.
21. Trong mật mã học, hàm băm (hash function) lý tưởng có tính chất nào quan trọng nhất?
A. Dễ đảo ngược (reversible).
B. Khó đảo ngược (preimage resistance).
C. Tốc độ tính toán chậm.
D. Kết quả băm luôn ngắn hơn đầu vào.
22. Trong lý thuyết đồ thị, bậc của một đỉnh là gì?
A. Số đỉnh kề với đỉnh đó.
B. Số 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ố chu trình đi qua đỉnh đó.
23. Phát biểu nào sau đây là đúng về quan hệ 'chia hết' trên tập số nguyên dương?
A. Đối xứng.
B. Phản xạ.
C. Phản đối xứng.
D. Vừa đối xứng vừa phản xạ.
24. 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!
C. n! / (k! * (n-k)!)
D. k! / (n-k)!
25. Cho tập hợp A = {a, b, c, d} và quan hệ R = {(a, a), (b, b), (c, c), (d, d), (a, b), (b, a)}. Quan hệ R này có phải là quan hệ tương đương không?
A. Đúng.
B. Sai.
C. Không xác định.
D. Chỉ đúng với tập con của A.
26. Số cạnh tối thiểu trong một đồ thị liên thông có n đỉnh (n ≥ 1) là bao nhiêu?
A. n
B. n - 1
C. n + 1
D. 2n
27. Cho đồ thị G có ma trận kề A. Phần tử (i, j) của ma trận A^2 biểu diễn điều gì?
A. Số đường đi độ dài 1 từ đỉnh i đến đỉnh j.
B. Số đường đi độ dài 2 từ đỉnh i đến đỉnh j.
C. Độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh j.
D. Số đỉnh kề chung của đỉnh i và đỉnh j.
28. Hệ đếm cơ số 16 còn được gọi là hệ đếm gì?
A. Nhị phân.
B. Thập phân.
C. Bát phân.
D. Thập lục phân (Hexadecimal).
29. Quan hệ R trên tập hợp A được gọi là quan hệ tương đương nếu nó có tính chất nào sau đây?
A. Phản xạ, đối xứng, phản đối xứng.
B. Phản xạ, bắc cầu, đối xứng.
C. Đối xứng, phản xạ, toàn phần.
D. Bắc cầu, đối xứng, phản đối xứng.
30. Phát biểu nào sau đây mô tả đúng nhất về thuật toán Dijkstra?
A. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị.
B. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh còn lại 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ị.
