1. Số cách chọn 3 học sinh từ một nhóm 5 học sinh để tham gia đội văn nghệ là bao nhiêu?
A. P(5, 3) = 60
B. C(5, 3) = 10
C. 5!
D. 3!
2. Cho hàm mệnh đề P(x): `x là số nguyên tố`. Giá trị chân lý của ∀xP(x) với miền xác định là tập hợp các số nguyên dương là gì?
A. Đúng
B. Sai
C. Không xác định
D. Tùy thuộc vào x
3. Trong lý thuyết tập hợp, phép toán nào sau đây cho phép tạo ra một tập hợp mới chứa tất cả các phần tử thuộc ít nhất một trong hai tập hợp ban đầu?
A. Giao (Intersection)
B. Hợp (Union)
C. Hiệu (Difference)
D. Tích Descartes (Cartesian Product)
4. 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) ∧ p] → q
D. [(p → q) ∧ ¬q] → ¬p
5. Phát biểu nào sau đây mô tả đúng về cây (tree) trong lý thuyết đồ thị?
A. Đồ thị liên thông chứa chu trình.
B. Đồ thị không liên thông không chứa chu trình.
C. Đồ thị liên thông không chứa chu trình.
D. Đồ thị không liên thông chứa chu trình.
6. Trong logic vị từ, lượng từ nào sau đây khẳng định rằng một thuộc tính đúng cho ít nhất một phần tử trong miền xác định?
A. Lượng từ phổ quát (∀ - For all)
B. Lượng từ tồn tại (∃ - There exists)
C. Lượng từ duy nhất (∃! - There exists uniquely)
D. Không có lượng từ nào phù hợp.
7. Cho tập hợp A = {1, 2, 3} và B = {a, b}. Tích Descartes A × B là tập hợp nào?
A. {1, 2, 3, a, b}
B. {{1, a}, {1, b}, {2, a}, {2, b}, {3, a}, {3, b}}
C. {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
D. {{1, 2, 3}, {a, b}}
8. Cho đồ thị vô hướng G = (V, E). Phát biểu nào sau đây là ĐÚNG về bậc của đỉnh trong đồ thị?
A. Tổng bậc của tất cả các đỉnh luôn là một số lẻ.
B. Tổng bậc của tất cả các đỉnh bằng số cạnh.
C. Tổng bậc của tất cả các đỉnh bằng hai lần số cạnh.
D. Bậc của mỗi đỉnh luôn nhỏ hơn hoặc bằng số cạnh.
9. 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ố nguyên dương (hoặc từ một số nguyên nào đó trở đi).
C. Sự tồn tại của một đối tượng toán học.
D. Tính vô nghiệm của một phương trình.
10. Trong logic vị từ, phép kéo theo logic (logical implication) `P(x) → Q(x)′ tương đương với biểu thức nào sau đây?
A. ¬P(x) ∧ Q(x)
B. P(x) ∧ ¬Q(x)
C. ¬P(x) ∨ Q(x)
D. P(x) ∨ ¬Q(x)
11. Thuật toán Dijkstra thường đượ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 (MST).
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 Hamilton trong đồ thị.
D. Kiểm tra tính liên thông của đồ thị.
12. 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. Đường đi ngắn nhất giữa hai đỉnh bất kỳ trong đồ thị.
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 lớn nhất.
C. 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.
D. Chu trình Euler đi qua tất cả các cạnh của đồ thị.
13. Đồ thị phẳng là đồ thị có thể được vẽ trên mặt phẳng sao cho:
A. Tất cả các cạnh đều có độ dài bằng nhau.
B. Không có cạnh nào cắt nhau (ngoại trừ tại các đỉnh).
C. Mỗi đỉnh có bậc bằng nhau.
D. Có chu trình Hamilton.
14. Số cạnh tối thiểu trong một đồ thị liên thông có n đỉnh là bao nhiêu?
A. n - 2
B. n - 1
C. n
D. n + 1
15. Trong đại số Boolean, định luật De Morgan phát biểu rằng (A + B)′ tương đương với biểu thức nào?
A. A′ + B′
B. A′ × B′
C. A × B
D. A + B
16. Phát biểu nào sau đây là SAI về quan hệ thứ tự bộ phận (partial order relation)?
A. Quan hệ thứ tự bộ phận phải có tính phản xạ.
B. Quan hệ thứ tự bộ phận phải có tính bắc cầu.
C. Quan hệ thứ tự bộ phận phải có tính đối xứng.
D. Quan hệ thứ tự bộ phận phải có tính phản đối xứng.
17. Trong thuật toán sắp xếp topological, mục đích chính là gì?
A. Sắp xếp các đỉnh của đồ thị theo thứ tự tăng dần của bậc.
B. Sắp xếp các đỉnh của đồ thị có hướng không chu trình (DAG) theo thứ tự tuyến tính sao cho với mọi cạnh (u, v), đỉnh u xuất hiện trước đỉnh v trong thứ tự.
C. Tìm đường đi ngắn nhất trong đồ thị có hướng.
D. Tìm cây khung nhỏ nhất trong đồ thị có hướng.
18. Cho đồ thị đầy đủ Kn (complete graph). Số cạnh của đồ thị Kn là bao nhiêu?
A. n
B. n - 1
C. n × (n - 1) ∕ 2
D. n × (n + 1) ∕ 2
19. Trong lý thuyết đồ thị, một chu trình Euler là gì?
A. Chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần.
B. Chu trình đi qua tất cả các cạnh của đồ thị đúng một lần và quay trở lại đỉnh xuất phát.
C. Đường đi ngắn nhất giữa hai đỉnh trong đồ thị.
D. Cây khung của đồ thị.
20. Trong lý thuyết automata, DFA (Deterministic Finite Automaton) là gì?
A. Một loại ngôn ngữ hình thức.
B. Một mô hình tính toán có trạng thái hữu hạn và các chuyển trạng thái xác định.
C. Một thuật toán tìm kiếm đường đi ngắn nhất.
D. Một cấu trúc dữ liệu dạng cây.
21. Số lượng quan hệ hai ngôi khác nhau có thể xác định trên tập hợp A có n phần tử là bao nhiêu?
A. 2ⁿ
B. n²
C. 2ⁿ*ⁿ
D. n!
22. Hàm số f: Z → Z được định nghĩa bởi f(x) = 2x + 1. Hàm số này có tính chất nào sau đây?
A. Toàn ánh (Surjective) nhưng không đơn ánh (Injective).
B. Đơn ánh (Injective) nhưng không toàn ánh (Surjective).
C. Song ánh (Bijective).
D. Không đơn ánh và không toàn ánh.
23. Trong số học modulo, 7 đồng dư với số nào modulo 3?
24. Quan hệ R trên tập hợp A được gọi là quan hệ tương đương nếu nó thỏa mãn đồng thời cá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, phản đối xứng.
C. Phản xạ, đối xứng, bắc cầu.
D. Đối xứng, bắc cầu, phản đối xứng.
25. Trong thuật toán tô màu đồ thị, số màu sắc tối thiểu cần thiết để tô màu các đỉnh của một đồ thị phẳng sao cho không có hai đỉnh kề nhau nào cùng màu được gọi là:
A. Số sắc (Chromatic number)
B. Bậc của đồ thị
C. Số cạnh của đồ thị
D. Kích thước đồ thị
26. Trong tổ hợp, chỉnh hợp chập k của n phần tử (ký hiệu P(n, k) hoặc A(n, k)) đượ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! × (n-k)!)
27. Một ngôn ngữ chính quy (regular language) có thể được biểu diễn bằng cách nào sau đây?
A. Máy Turing (Turing Machine)
B. Grammar phi ngữ cảnh (Context-Free Grammar)
C. Biểu thức chính quy (Regular Expression)
D. Pushdown Automaton
28. Mệnh đề `Nếu trời mưa thì đường ướt′ tương đương logic với mệnh đề nào sau đây?
A. Nếu trời không mưa thì đường không ướt.
B. Nếu đường ướt thì trời mưa.
C. Nếu đường không ướt thì trời không mưa.
D. Trời mưa và đường ướt.
29. Trong một lớp học có 30 học sinh, có 15 học sinh thích Toán, 12 học sinh thích Văn và 5 học sinh thích cả Toán và Văn. Hỏi có bao nhiêu học sinh không thích môn nào trong hai môn này?
30. Cho quan hệ R = {(1, 1), (1, 2), (2, 2), (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à bắc cầu.
B. Phản xạ và đối xứng.
C. Phản xạ và bắc cầu.
D. Phản đối xứng và bắc cầu.
