1. Giá trị của biểu thức logic (P ∧ Q) ∨ ¬P khi P đúng và Q sai là gì?
A. Đúng
B. Sai
C. Không xác định
D. Vừa đúng vừa sai
2. Cho đồ thị vô hướng G = (V, E) với V = {a, b, c, d} và E = {{a, b}, {b, c}, {c, d}}. Đồ thị này có phải là đồ thị liên thông không?
A. Đúng
B. Sai
C. Không xác định
D. Cần thêm thông tin
3. Cho quan hệ R = {(1, 2), (2, 3), (1, 3)} trên tập hợp A = {1, 2, 3}. Quan hệ R có tính chất bắc cầu (transitive) không?
A. Đúng
B. Sai
C. Không xác định
D. Cần thêm thông tin
4. Một cây nhị phân đầy đủ (full binary tree) có chiều cao h thì có tối đa bao nhiêu lá (leaves)?
5. Cho đồ thị G có ma trận kề (adjacency matrix) 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ố lượng đường đi từ đỉnh i đến đỉnh j
C. Có cạnh nối giữa đỉnh i và đỉnh j hay không
D. Bậc của đỉnh i
6. Trong lý thuyết tập hợp, luật phân phối (distributive law) phát biểu rằng A ∩ (B ∪ C) tương đương với biểu thức nào?
A. (A ∩ B) ∪ (A ∩ C)
B. (A ∪ B) ∩ (A ∪ C)
C. (A ∪ B) ∪ (A ∩ C)
D. (A ∩ B) ∩ (A ∪ C)
7. Cho tập hợp A = {a, b, c}. Số lượng hoán vị của các phần tử trong tập hợp A là bao nhiêu?
8. 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 phản xạ không?
A. Đúng
B. Sai
C. Không xác định
D. Cần thêm thông tin
9. 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 (AND)
B. Phép tuyển (OR)
C. Phép kéo theo (Implication)
D. Phép tương đương (Biconditional)
10. Trong combinatorics, hệ số nhị thức (n chập k) ký hiệu là C(n, k) hoặc (nk) được tính bằng công thức nào?
A. n! / (k! * (n - k)!)
B. n! / k!
C. n! / (n - k)!
D. k! / (n! * (n - k)!)
11. Trong đại số Boolean, định luật De Morgan thứ nhất 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
12. Trong thuật toán sắp xếp, độ phức tạp thời gian trung bình của thuật toán Merge Sort là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(log n)
D. O(n)
13. Cho hàm f(x) = x^2 và g(x) = 2x + 1. Hàm hợp (g ∘ f)(x) là gì?
A. x^4
B. 4x^2 + 4x + 1
C. 2x^2 + 1
D. (2x + 1)x^2
14. Quan hệ R trên tập hợp A 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ạ, đối xứng, bắc cầu
B. Phản xạ, phản đối xứng, bắc cầu
C. Đối xứng, phản đối xứng, bắc cầu
D. Phản xạ, đối xứng, phản bắc cầu
15. Cho tập hợp A = {1, 2, 3, 4, 5}. Có bao nhiêu tập con có thể tạo ra từ tập hợp A?
16. Trong số học, ước số chung lớn nhất (ƯCLN) của hai số nguyên a và b ký hiệu là gcd(a, b). Giá trị của gcd(12, 18) là bao nhiêu?
17. 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à đơn ánh (injective) không?
A. Đúng
B. Sai
C. Không xác định
D. Cần thêm thông tin
18. Trong tổ hợp, chỉnh hợp chập k của n phần tử khác với tổ hợp chập k của n phần tử ở điểm nào?
A. Chỉnh hợp có thứ tự, tổ hợp không có thứ tự
B. Tổ hợp có thứ tự, chỉnh hợp không có thứ tự
C. Chỉnh hợp chọn có lặp, tổ hợp chọn không lặp
D. Tổ hợp chọn có lặp, chỉnh hợp chọn không lặp
19. Trong lý thuyết đồ thị, chu trình Hamilton là gì?
A. Chu trình đ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 đỉnh của đồ thị mỗi đỉnh đúng một lần (trừ đỉnh đầu và đỉnh cuối trùng nhau)
C. Đường đi ngắn nhất giữa hai đỉnh
D. Cây khung nhỏ nhất của đồ thị
20. Trong lý thuyết automata, DFA là viết tắt của cụm từ nào?
A. Deterministic Finite Automaton
B. Non-deterministic Finite Automaton
C. Digital Finite Automaton
D. Dynamic Finite Automaton
21. Trong lý thuyết đồ thị, đồ thị phẳng là gì?
A. Đồ thị có thể vẽ trên mặt phẳng sao cho không có cạnh nào cắt nhau (ngoài các đỉnh)
B. Đồ thị có tất cả các đỉnh nằm trên cùng một mặt phẳng
C. Đồ thị có thể biểu diễn bằng ma trận phẳng
D. Đồ thị có tất cả các cạnh có độ dài bằng nhau
22. 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 Z. 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
23. Số cạnh tối thiểu trong một đồ thị liên thông có n đỉnh là bao nhiêu?
A. n - 1
B. n
C. n + 1
D. n * (n - 1) / 2
24. Trong logic vị từ, lượng từ tồn tại (existential quantifier) ký hiệu là?
25. Cho tập hợp A = {1, 2, 3} và B = {3, 4, 5}. Tập hợp giao (intersection) của A và B, ký hiệu A ∩ B, là tập hợp nào?
A. {1, 2, 3, 4, 5}
B. {1, 2}
C. {3}
D. {4, 5}
26. Trong số học, số nguyên tố là gì?
A. Số nguyên dương chia hết cho 1 và chính nó
B. Số nguyên dương lớn hơn 1 chỉ có hai ước số dương là 1 và chính nó
C. Số nguyên dương chỉ chia hết cho 2
D. Số nguyên dương có nhiều hơn hai ước số dương
27. Thuật toán Dijkstra đượ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
B. Tìm đường đi ngắn nhất giữa hai đỉnh
C. Tìm chu trình Euler
D. Tìm chu trình Hamilton
28. Trong lý thuyết đồ thị, bậc của một đỉnh là gì?
A. Số cạnh liên thuộc với đỉnh đó
B. Số đỉnh kề với đỉnh đó
C. Tổng trọng số của các cạnh liên thuộc với đỉnh đó
D. Số đường đi ngắn nhất từ đỉnh đó đến tất cả các đỉnh khác
29. Trong logic mệnh đề, quy tắc Modus Ponens có dạng lập luận nào?
A. Từ P → Q và ¬Q suy ra ¬P
B. Từ P → Q và P suy ra Q
C. Từ P → Q và Q suy ra P
D. Từ ¬P → Q và ¬Q suy ra P
30. Trong logic mệnh đề, luật hấp thụ (absorption law) phát biểu rằng P ∨ (P ∧ Q) tương đương với biểu thức nào?
A. P
B. Q
C. P ∧ Q
D. P ∨ Q
