1. Tìm số nghiệm nguyên dương của phương trình x + y + z = 5.
2. Cho tập hợp A = {1, 2, 3}. Quan hệ R = {(1, 1), (2, 2), (3, 3), (1, 2)} trên A 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
3. Số cách chọn k phần tử từ n phần tử phân biệt mà không quan tâm đến thứ tự được gọi là gì?
A. Hoán vị
B. Chỉnh hợp
C. Tổ hợp
D. Giai thừa
4. Cho mệnh đề P: `Nếu trời mưa thì đường ướt′. Mệnh đề nào sau đây là mệnh đề đảo của P?
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.
5. Định lý Euler về đồ thị phẳng phát biểu điều gì?
A. Trong đồ thị phẳng liên thông, số đỉnh trừ số cạnh cộng số miền bằng 2.
B. Mọi đồ thị phẳng đều có thể tô màu bằng 4 màu.
C. Tổng bậc của các đỉnh trong đồ thị luôn là số chẵn.
D. Đồ thị có chu trình Euler khi và chỉ khi mọi đỉnh có bậc chẵn.
6. Trong bài toán đếm, quy tắc cộng được áp dụng khi nào?
A. Khi các công việc cần thực hiện liên tiếp nhau.
B. Khi các trường hợp là xung khắc lẫn nhau.
C. Khi các phần tử được chọn có thể lặp lại.
D. Khi cần tìm số hoán vị của một tập hợp.
7. Trong logic mệnh đề, phép toán nào sau đây được gọi là phép 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)
8. Trong hệ đếm cơ số 16 (hệ thập lục phân), ký hiệu `A′ đại diện cho giá trị nào trong hệ thập phân?
9. Thuật toán Kruskal được sử dụng để làm gì trong lý thuyết đồ thị?
A. Tìm đường đi ngắn nhất giữa hai đỉnh.
B. Tìm cây khung nhỏ nhất (Minimum Spanning Tree).
C. Tìm chu trình Euler.
D. Tô màu đồ thị.
10. 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 là quan hệ phản xạ.
B. Quan hệ thứ tự bộ phận là quan hệ phản đối xứng.
C. Quan hệ thứ tự bộ phận là quan hệ bắc cầu.
D. Quan hệ thứ tự bộ phận là quan hệ đối xứng.
11. Trong số học đồng dư, a ≡ b (mod m) có nghĩa là gì?
A. a chia hết cho b modulo m.
B. a và b có cùng số dư khi chia cho m.
C. a nhân với b chia hết cho m.
D. a lớn hơn b modulo m.
12. Trong logic mệnh đề, luật De Morgan phát biểu về sự tương đương của phép phủ định với phép toán nào?
A. Phép kéo theo và phép tuyển
B. Phép hội và phép tuyển
C. Phép hội và phép kéo theo
D. Phép tuyển và phép tương đương
13. Giá trị của biểu thức logic (p ∧ q) → (p ∨ q) luôn là gì?
A. Luôn đúng (Tautology)
B. Luôn sai (Contradiction)
C. Có thể đúng hoặc sai tùy thuộc vào giá trị của p và q
D. Không xác định
14. Cho quan hệ R trên tập số nguyên Z được định nghĩa bởi a R b nếu a - b là số chẵn. Quan hệ R có phải là quan hệ tương đương không?
A. Không, vì nó không phản xạ.
B. Không, vì nó không đối xứng.
C. Không, vì nó không bắc cầu.
D. Có, vì nó phản xạ, đối xứng và bắc cầu.
15. Mệnh đề phủ định của mệnh đề `Mọi số nguyên đều là số thực′ là gì?
A. Mọi số nguyên đều không phải là số thực.
B. Có ít nhất một số nguyên không phải là số thực.
C. Không có số nguyên nào là số thực.
D. Mọi số thực đều là số nguyên.
16. Cho hàm số f: Z → Z, f(x) = 2x + 1. Hàm số này có phải là song ánh (bijective) không?
A. Có, vì nó vừa đơn ánh vừa toàn ánh.
B. Không, vì nó không đơn ánh.
C. Không, vì nó không toàn ánh.
D. Không thể xác định.
17. Đồ thị vô hướng G = (V, E) được gọi là đồ thị đầy đủ (complete graph) khi nào?
A. Mỗi đỉnh trong V đều có bậc bằng nhau.
B. Có một đường đi giữa mọi cặp đỉnh phân biệt trong V.
C. Mọi cặp đỉnh phân biệt trong V đều kề nhau.
D. Số cạnh |E| bằng số đỉnh |V| trừ 1.
18. Hệ thức truy hồi nào mô tả dãy Fibonacci?
A. F(n) = F(n-1) + F(n-2) với F(0) = 0, F(1) = 1
B. F(n) = 2F(n-1) - F(n-2) với F(0) = 1, F(1) = 1
C. F(n) = F(n-1) × F(n-2) với F(0) = 1, F(1) = 1
D. F(n) = F(n-1) + n với F(0) = 0
19. Cho tập hợp A = {a, b, c, d}. Số tập con có 2 phần tử của A là bao nhiêu?
20. Trong thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị có trọng số không âm, cấu trúc dữ liệu nào thường được sử dụng để quản lý các đỉnh chưa xét?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Hàng đợi ưu tiên (Priority Queue)
D. Danh sách liên kết (Linked List)
21. Cho đồ thị G có ma trận kề A. Phần tử A[i][j] của ma trận kề biểu thị điều gì?
A. Trọng số của cạnh nối đỉnh i và đỉnh j.
B. Số cạnh nối đỉnh i và đỉnh j.
C. Có cạnh nối giữa đỉnh i và đỉnh j hay không.
D. Khoảng cách ngắn nhất giữa đỉnh i và đỉnh j.
22. Trong một nhóm 10 người, có bao nhiêu cách chọn ra một nhóm trưởng và một nhóm phó?
A. P(10, 2)
B. C(10, 2)
C. 10!
D. 2¹⁰
23. Phép toán XOR (phép tuyển loại trừ) giữa hai bit 1 và 0 cho kết quả là bao nhiêu?
A. 0
B. 1
C. 2
D. Không xác định
24. Trong thuật toán tô màu đồ thị, mục tiêu chính là gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh.
B. Tìm chu trình Euler hoặc Hamilton.
C. Gán màu cho các đỉnh sao cho không có hai đỉnh kề nhau có cùng màu.
D. Tìm cây khung nhỏ nhất của đồ thị.
25. Số hoán vị của n phần tử phân biệt là bao nhiêu?
26. Cho tập hợp A = {1, 2, 3, 4, 5}. Có bao nhiêu hàm số đơn ánh (injective function) từ A vào tập hợp B = {1, 2, 3, 4, 5, 6}?
A. 6!
B. 5!
C. P(6, 5)
D. C(6, 5)
27. Chu trình Euler trong đồ thị là gì?
A. Chu trình đi qua mỗi đỉnh của đồ thị đúng một lần.
B. Chu trình đi qua mỗi cạnh của đồ thị đúng một lần.
C. Chu trình ngắn nhất giữa hai đỉnh của đồ thị.
D. Chu trình dài nhất trong đồ thị.
28. Phát biểu nào sau đây là đúng về cây (tree) trong lý thuyết đồ thị?
A. Cây là đồ thị có chu trình.
B. Cây là đồ thị liên thông và không có chu trình.
C. Cây là đồ thị không liên thông và không có chu trình.
D. Cây là đồ thị liên thông và có thể có chu trình.
29. Số cạnh tối thiểu trong một đồ thị liên thông có n đỉnh là bao nhiêu?
A. n
B. n - 1
C. n + 1
D. 2n
30. Trong logic vị từ, lượng từ ∀ được gọi là gì?
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)
