1. Trong lý thuyết đồ thị, đồ thị đầy đủ Kn là đồ thị như thế nào?
A. Đồ thị không có cạnh.
B. Đồ thị mà mỗi đỉnh đều kề với tất cả các đỉnh còn lại.
C. Đồ thị có chu trình Hamilton.
D. Đồ thị phẳng.
2. Trong đại số Boole, luật De Morgan phát biểu rằng:
A. (x + y)′ = x′ + y′
B. (x + y)′ = x′y′
C. (xy)′ = x′y′
D. (xy)′ = xy
3. Phát biểu nào sau đây là đúng về tập hợp?
A. Thứ tự các phần tử trong tập hợp là quan trọng.
B. Tập hợp có thể chứa các phần tử trùng lặp.
C. Tập hợp là một sưu tập vô thứ tự các đối tượng phân biệt.
D. Tập hợp chỉ có thể chứa các số.
4. Phép toán nào sau đây không phải là phép toán cơ bản trên tập hợp?
A. Hợp (∪)
B. Giao (∩)
C. Bù (`)
D. Tích Cartesian (×)
5. Số hoán vị của n phần tử phân biệt là bao nhiêu?
6. Một đồ thị được gọi là đồ thị hai phía (bipartite graph) nếu:
A. Các đỉnh của nó có thể được chia thành hai tập hợp rời nhau sao cho mọi cạnh đều nối một đỉnh từ tập hợp này sang tập hợp kia.
B. Các đỉnh của nó có thể được chia thành hai tập hợp không rời nhau sao cho mọi cạnh đều nối một đỉnh từ tập hợp này sang tập hợp kia.
C. Nó chứa chu trình Euler.
D. Nó chứa chu trình Hamilton.
7. Trong lý thuyết đồ thị, chu trình Hamilton là gì?
A. Đường đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.
B. Chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.
C. Đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần.
D. Chu trình đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần (trừ đỉnh đầu và đỉnh cuối trùng nhau).
8. Quan hệ R trên tập A được gọi là quan hệ tương đương nếu nó thỏa mãn các tính chất nào sau đây?
A. Phản xạ và đối xứng.
B. Phản xạ và bắc cầu.
C. Đối xứng và bắc cầu.
D. Phản xạ, đối xứng và bắc cầu.
9. Trong logic mệnh đề, phép toán nào sau đây biểu diễn cho `hoặc′?
A. ∧ (và)
B. ∨ (hoặc)
C. ¬ (phủ định)
D. → (kéo theo)
10. Cho tập hợp A = {1, 2, 3}. Số quan hệ hai ngôi có thể có trên tập A là bao nhiêu?
11. Trong lý thuyết automata, DFA (Deterministic Finite Automaton) là gì?
A. Máy trạng thái hữu hạn không xác định.
B. Máy trạng thái hữu hạn xác định.
C. Máy Turing không xác định.
D. Máy Turing xác định.
12. Trong logic mệnh đề, quy tắc suy luận Modus Ponens có dạng:
A. [(p → q) ∧ q] → p
B. [(p → q) ∧ p] → q
C. [(¬p → q) ∧ q] → ¬p
D. [(p → ¬q) ∧ p] → ¬q
13. Phép toán XOR (hoặc loại trừ) giữa hai bit A và B cho kết quả là 1 khi nào?
A. Khi cả A và B đều là 0.
B. Khi cả A và B đều là 1.
C. Khi A và B khác nhau.
D. Khi A và B giống nhau.
14. Cho đồ thị vô hướng G = (V, E). Bậc của một đỉnh v ∈ V là gì?
A. Số lượng đỉnh kề với v.
B. Số lượng cạnh trong đồ thị.
C. Tổng số đỉnh và cạnh trong đồ thị.
D. Số lượng đường đi đơn từ v đến tất cả các đỉnh khác.
15. Trong tổ hợp, chỉnh hợp chập k của n phần tử (k ≤ n) là gì?
A. Số cách chọn k phần tử từ n phần tử mà không quan tâm đến thứ tự.
B. Số cách chọn k phần tử từ n phần tử có quan tâm đến thứ tự.
C. Số cách sắp xếp n phần tử.
D. Số cách chia n phần tử thành k nhóm.
16. Định lý Euler về đồ thị phẳng liên thông phát biểu điều gì?
A. Số đỉnh trừ số cạnh cộng số miền bằng 2 (V - E + F = 2).
B. Tổng bậc của các đỉnh bằng hai lần số cạnh.
C. Một đồ thị có chu trình Euler khi và chỉ khi tất cả các đỉnh có bậc chẵn.
D. Số miền của đồ thị phẳng luôn nhỏ hơn số cạnh.
17. Trong logic vị từ, lượng từ ∀ (với mọi) được gọi là:
A. Lượng từ tồn tại.
B. Lượng từ phổ quát.
C. Lượng từ duy nhất.
D. Lượng từ phủ định.
18. Trong hệ đếm cơ số 2 (hệ nhị phân), số 1011₂ tương đương với số nào trong hệ đếm cơ số 10 (hệ thập phân)?
19. Hàm số f(x) = x² + 1 có phải là toàn ánh (surjective) từ tập số nguyên Z sang tập số nguyên Z không?
A. Đúng
B. Sai
C. Không xác định
D. Tùy thuộc vào x
20. Số cạnh của đồ thị đầy đủ Kn là bao nhiêu?
A. n
B. n-1
C. n(n-1)∕2
D. n²
21. Phát biểu nào sau đây là đúng về đồ thị cây?
A. Đồ thị cây có chứa chu trình.
B. Đồ thị cây là đồ thị liên thông và không có chu trình.
C. Đồ thị cây là đồ thị không liên thông và không có chu trình.
D. Đồ thị cây là đồ thị liên thông và có thể có chu trình.
22. Số cách chọn ra 2 học sinh từ 5 học sinh để tham gia đội văn nghệ là bao nhiêu?
23. Cho hàm mệnh đề P(x): `x là số nguyên tố`. Miền xác định là tập hợp số nguyên dương. Mệnh đề ∀x P(x) có giá trị chân lý là gì?
A. Đúng
B. Sai
C. Không xác định
D. Tùy thuộc vào x
24. Hàm số f: A → B được gọi là đơn ánh (injective) khi nào?
A. Với mọi x, y ∈ A, nếu f(x) = f(y) thì x = y.
B. Với mọi y ∈ B, tồn tại x ∈ A sao cho f(x) = y.
C. Với mọi x, y ∈ A, nếu x = y thì f(x) = f(y).
D. Với mọi y ∈ B, có nhiều nhất một x ∈ A sao cho f(x) = y.
25. Trong số học, ước chung lớn nhất (ƯCLN) của hai số nguyên a và b, ký hiệu gcd(a, b), là gì?
A. Số lớn nhất chia hết cho cả a và b.
B. Số nhỏ nhất chia hết cho cả a và b.
C. Số lớn nhất mà cả a và b đều chia hết cho.
D. Số nhỏ nhất mà cả a và b đều chia hết cho.
26. 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 xạ.
C. Bắc cầu.
D. Phản xạ và bắc cầu.
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 bao gồm 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 bao gồm tất cả các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất.
C. Cây bao gồm một số đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất.
D. Cây bao gồm một số đỉnh của đồ thị và có tổng trọng số cạnh lớn nhất.
28. Cho tập A = {a, b, c, d}. Phân hoạch của tập A là gì?
A. Một tập con của A.
B. Một tập hợp các tập con của A sao cho hợp của chúng bằng A và chúng đôi một rời nhau.
C. Một tập hợp các tập con của A sao cho giao của chúng bằng A.
D. Một tập hợp các phần tử của A.
29. Thuật toán Dijkstra được sử dụng để giải quyết bài toán nào?
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. Kiểm tra tính liên thông của đồ thị.
30. Phát biểu nào sau đây về phép chứng minh bằng quy nạp toán học là đúng?
A. Chứng minh mệnh đề đúng cho mọi trường hợp cụ thể.
B. Chứng minh mệnh đề đúng cho trường hợp cơ sở và bước quy nạp.
C. Chứng minh mệnh đề sai cho trường hợp cơ sở và bước quy nạp.
D. Chỉ cần chứng minh mệnh đề đúng cho trường hợp cơ sở.
