1. Trong số học đồng dư, phát biểu a ≡ b (mod m) có nghĩa là gì?
A. a bằng b.
B. a chia hết cho b.
C. a và b có cùng số dư khi chia cho m.
D. a - b chia hết cho m.
2. Trong lý thuyết ngôn ngữ hình thức, DFA (Deterministic Finite Automaton) là gì?
A. Một loại ngữ pháp sinh ra ngôn ngữ chính quy.
B. Một mô hình máy tính trừu tượng để nhận dạng ngôn ngữ chính quy.
C. Một thuật toán sắp xếp chuỗi hiệu quả.
D. Một cấu trúc dữ liệu để lưu trữ đồ thị.
3. Hàm số f: Z → Z được định nghĩa bởi f(x) = 2x + 1. Hàm số này có phải là song ánh (bijective) không?
A. Đúng
B. Sai
C. Không xác định
D. Có thể đúng hoặc sai tùy thuộc vào tập Z
4. Cho hàm băm h(x) = x mod 10. Giá trị băm của số 123 là bao nhiêu?
5. Cho đồ thị vô hướng G = (V, E). Điều kiện cần và đủ để đồ thị G là đồ thị Euler (có chu trình Euler) là gì?
A. G phải là đồ thị liên thông.
B. Mọi đỉnh của G phải có bậc chẵn.
C. G phải là đồ thị liên thông và mọi đỉnh của G phải có bậc chẵn.
D. G phải là đồ thị liên thông và có ít nhất một đỉnh bậc chẵn.
6. Cho quan hệ R trên tập hợp A = {1, 2, 3} được biểu diễn bởi ma trận quan hệ sau: [[1, 0, 1], [0, 1, 0], [1, 0, 1]]. Quan hệ R có tính chất nào?
A. Chỉ có tính phản xạ.
B. Chỉ có tính đối xứng.
C. Có tính phản xạ và đối xứng.
D. Không có tính phản xạ, đối xứng hay bắc cầu.
7. Cho đồ thị đầy đủ Kn<∕sub> (complete graph with n vertices). Số cạnh của Kn<∕sub> là bao nhiêu?
A. n
B. n - 1
C. n(n - 1) ∕ 2
D. n2<∕sup>
8. Cho hàm đệ quy sau: F(n) = F(n-1) + F(n-2) với F(0) = 0, F(1) = 1. Đây là dãy số nào?
A. Dãy số cấp số cộng
B. Dãy số cấp số nhân
C. Dãy số Fibonacci
D. Dãy số Harmonic
9. Thuật toán Euclid mở rộng (Extended Euclidean Algorithm) được sử dụng để làm gì?
A. Tìm ước chung lớn nhất (GCD) của hai số nguyên.
B. Tìm bội chung nhỏ nhất (LCM) của hai số nguyên.
C. Tìm nghịch đảo modulo của một số nguyên.
D. Cả (1) và (3).
10. Tính chất nào sau đây KHÔNG phải là tính chất của quan hệ thứ tự bộ phận (partial order relation)?
A. Tính phản xạ (reflexivity)
B. Tính đối xứng (symmetry)
C. Tính phản đối xứng (antisymmetry)
D. Tính bắc cầu (transitivity)
11. Cho hai tập hợp A = {1, 2, 3} và B = {3, 4, 5}. Tập hợp giao của A và B (A ∩ B) là tập hợp nào?
A. {1, 2, 3, 4, 5}
B. {1, 2}
C. {3}
D. {4, 5}
12. Trong lý thuyết đồ thị, bậc của một đỉnh (degree of a vertex) được định nghĩa là gì?
A. Số lượng cạnh trong đồ thị
B. Số lượng đỉnh trong đồ thị
C. Số lượng cạnh liên thuộc với đỉnh đó
D. Số lượng đường đi ngắn nhất đến đỉnh đó
13. 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.
B. Tính chất đúng cho tất cả các số tự nhiên (hoặc một tập hợp vô hạn các trường hợp).
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 giải pháp.
14. 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)
15. Cho tập hợp S = {a, b, c}. Số tập con của S là bao nhiêu?
16. Số cách chọn 3 cuốn sách từ 5 cuốn sách khác nhau là bao nhiêu?
17. Trong logic mệnh đề, phép toán nào sau đây được sử dụng để biểu thị mệnh đề kéo theo (implication)?
A. Phép hội (conjunction)
B. Phép tuyển (disjunction)
C. Phép kéo theo (implication)
D. Phép phủ định (negation)
18. Biểu thức logic (p ∧ q) → p là hằng đúng (tautology), mâu thuẫn (contradiction) hay không phải cả hai?
A. Hằng đúng (tautology)
B. Mâu thuẫn (contradiction)
C. Không phải cả hai
D. Không xác định
19. Trong lý thuyết đồ thị, đường đi Hamilton (Hamiltonian path) là gì?
A. Đường đi đi qua tất cả các cạnh của đồ thị đúng một lần.
B. Đường đi đi qua tất cả các đỉnh của đồ thị đúng một lần.
C. Đường đi ngắn nhất giữa hai đỉnh cho trước.
D. Đường đi dài nhất trong đồ thị.
20. Trong lý thuyết số, định lý nhỏ Fermat (Fermat′s Little Theorem) phát biểu rằng nếu p là số nguyên tố và a là số nguyên không chia hết cho p, thì ap-1<∕sup> đồng dư với số nào modulo p?
21. Trong thuật toán Dijkstra tìm đường đi ngắn nhất, cấu trúc dữ liệu nào thường được sử dụng để quản lý tập hợp các đỉnh đã xét và chưa xét?
A. Mảng (array)
B. Danh sách liên kết (linked list)
C. Hàng đợi ưu tiên (priority queue)
D. Cây nhị phân tìm kiếm (binary search tree)
22. Số hoán vị của n phần tử phân biệt là bao nhiêu?
A. n
B. 2n<∕sup>
C. n!
D. n2<∕sup>
23. Phát biểu nào sau đây là đúng về đồ thị cây (tree)?
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 có thể có hoặc không có chu trình tùy thuộc vào số lượng đỉnh.
24. Trong đại số Boolean, luật De Morgan phát biểu rằng (x + y)′ tương đương với biểu thức nào?
A. x′ + y′
B. x′ × y′
C. x × y
D. x + y
25. Trong tổ hợp, chỉnh hợp chập k của n phần tử (permutation of n taken k at a time) được tính bằng công thức nào?
A. n! ∕ (k! × (n-k)!)
B. n! ∕ (n-k)!
C. k! ∕ (n-k)!
D. n! ∕ k!
26. Trong logic, quy tắc suy luận Modus Ponens có dạng như thế nào?
A. ((p → q) ∧ ¬q) → ¬p
B. ((p → q) ∧ p) → q
C. ((p → q) ∧ ¬p) → ¬q
D. ((p ∨ q) ∧ ¬p) → q
27. Trong lý thuyết đồ thị, đồ thị phẳng (planar graph) là gì?
A. Đồ thị có tất cả các đỉnh nằm trên cùng một mặt phẳng.
B. Đồ thị có thể được vẽ trên mặt phẳng sao cho không có cạnh nào cắt nhau (ngoài các đỉnh mút của chúng).
C. Đồ thị có số cạnh ít hơn số đỉnh.
D. Đồ thị có chu trình Euler.
28. Ứng dụng nào sau đây KHÔNG phải là ứng dụng của Toán rời rạc?
A. Thiết kế mạch điện tử số.
B. Phân tích dữ liệu tài chính liên tục.
C. Mật mã học và an ninh mạng.
D. Tối ưu hóa mạng lưới giao thông.
29. Chọn phát biểu ĐÚNG về quan hệ tương đương (equivalence relation) trên một tập hợp A.
A. Quan hệ tương đương phải có tính phản xạ và đối xứng, nhưng không nhất thiết có tính bắc cầu.
B. Quan hệ tương đương phải có tính đối xứng và bắc cầu, nhưng không nhất thiết có tính phản xạ.
C. Quan hệ tương đương phải có tính phản xạ, đối xứng và bắc cầu.
D. Quan hệ tương đương chỉ cần có tính bắc cầu.
30. Trong lý thuyết tập hợp, phép toán hiệu đối xứng (symmetric difference) của hai tập hợp A và B, ký hiệu A Δ B, được định nghĩa là gì?
A. A ∩ B
B. A ∪ B
C. (A ∪ B) - (A ∩ B)
D. (A - B) ∩ (B - A)
