1. 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ổ dụng (Universal quantifier)
C. Lượng từ duy nhất (Uniqueness quantifier)
D. Lượng từ phủ định (Negation quantifier)
2. 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 đường ướt thì trời mưa
B. Nếu trời không mưa thì đường không ướt
C. Nếu đường không ướt thì trời không mưa
D. Trời mưa và đường ướt
3. 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
B. Một mệnh đề đúng cho tất cả các số tự nhiên (hoặc một tập con vô hạn của số tự nhiên)
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 nghiệm
4. Biểu thức chính tắc tuyển chuẩn (DNF - Disjunctive Normal Form) của hàm Boolean f(x, y, z) là gì?
A. Tổng của các minterm
B. Tích của các maxterm
C. Tổng của các maxterm
D. Tích của các minterm
5. Một hoán vị của tập hợp n phần tử là gì?
A. Một tập con của n phần tử
B. Một cách sắp xếp thứ tự của tất cả n phần tử
C. Một lựa chọn k phần tử từ n phần tử
D. Một đồ thị có n đỉnh
6. Trong lý thuyết đồ thị, 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
C. Chu trình ngắn nhất trong đồ thị
D. Chu trình dài nhất trong đồ thị
7. 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 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, không bắc cầu
8. Số Stirling loại hai S(n, k) đếm cái gì?
A. Số cách chọn k phần tử từ n phần tử
B. Số cách phân hoạch một tập hợp n phần tử thành k tập con không rỗng
C. Số hoán vị của n phần tử
D. Số cách sắp xếp k phần tử trong n vị trí
9. Trong combinatorics, hệ số nhị thức C(n, k) còn được gọi là gì?
A. Số Fibonacci
B. Số Catalan
C. Số tổ hợp
D. Số chỉnh hợp
10. Trong lý thuyết tập hợp, phép toán nào sau đây trả về một tập hợp 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)
11. 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
12. Thuật toán Dijkstra được sử dụng để giải 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 từ một đỉnh nguồn đến các đỉnh còn lại
C. Tìm chu trình Hamilton
D. Tìm luồng cực đại trong mạng
13. Cho quan hệ R = {(1, 1), (1, 2), (2, 3)} trên tập hợp A = {1, 2, 3}. Tính chất nào sau đây quan hệ R có?
A. Phản xạ
B. Đối xứng
C. Bắc cầu
D. Không có tính chất nào trong các tính chất trên
14. Trong lý thuyết số, đồng dư thức a ≡ b (mod m) có nghĩa là gì?
A. a - b chia hết cho m
B. a và b đều chia hết cho m
C. a + b chia hết cho m
D. a nhân b chia hết cho m
15. Cho hàm mệnh đề P(x): 'x là số nguyên tố'. Giá trị chân lý của ∀x P(x) trên tập hợp số nguyên dương là gì?
A. Đúng
B. Sai
C. Không xác định
D. Phụ thuộc vào x
16. Đồ thị vô hướng được gọi là liên thông khi nào?
A. Khi nó có chứa chu trình Euler
B. Khi nó có chứa chu trình Hamilton
C. Khi có một đường đi giữa mọi cặp đỉnh phân biệt
D. Khi mọi đỉnh đều có bậc chẵn
17. Cây có gốc là gì?
A. Một đồ thị liên thông không có chu trình
B. Một cây trong đó một đỉnh được chỉ định là gốc
C. Một cây mà tất cả các lá đều có cùng độ sâu
D. Một cây có chứa chu trình Euler
18. 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. Deterministic Function Automaton
D. Digital Finite Algorithm
19. 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^10
20. Trong lý thuyết số học, ước số chung lớn nhất (ƯCLN) của hai số nguyên a và b là gì?
A. Số nguyên dương lớn nhất chia hết cả a và b
B. Số nguyên dương nhỏ nhất chia hết cả a và b
C. Tích của tất cả các ước số chung của a và b
D. Tổng của tất cả các ước số chung của a và b
21. Trong lý thuyết đồ thị, bậc của một đỉnh là gì?
A. Số đỉnh kề với đỉnh đó
B. Số cạnh liên thuộc với đỉnh đó
C. Tổng trọng số của các cạnh liên thuộc với đỉnh đó
D. Độ dài đường đi ngắn nhất từ đỉnh đó đến một đỉnh khác
22. Cho mạch logic có đầu vào A, B và đầu ra F = (A AND B) OR (NOT A AND B). Biểu thức Boolean tối giản của F là gì?
A. A
B. B
C. A OR B
D. A AND B
23. Số lượng cạnh trong một đồ thị đầy đủ Kn (đồ thị có n đỉnh mà mọi cặp đỉnh đều có cạnh nối) là bao nhiêu?
A. n
B. n - 1
C. n(n-1)/2
D. n^2
24. Trong đại số quan hệ, phép toán nào kết hợp thông tin từ hai quan hệ dựa trên giá trị của các thuộc tính chung?
A. Phép chọn (selection)
B. Phép chiếu (projection)
C. Phép kết nối (join)
D. Phép đổi tên (rename)
25. Cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị có trọng số liên thông là gì?
A. Một cây con chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất
B. Một chu trình Hamilton có tổng trọng số cạnh nhỏ nhất
C. Một đường đi ngắn nhất giữa hai đỉnh cụ thể trong đồ thị
D. Một đồ thị con liên thông có số cạnh lớn nhất
26. 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 không quan tâm đến thứ tự, tổ hợp có quan tâm đến thứ tự
B. Chỉnh hợp và tổ hợp đều không quan tâm đến thứ tự
C. Chỉnh hợp có quan tâm đến thứ tự, tổ hợp không quan tâm đến thứ tự
D. Chỉnh hợp luôn có số lượng lớn hơn tổ hợp
27. Trong mô hình quan hệ dữ liệu, phép toán chọn (selection) tương ứng với phép toán nào trong đại số quan hệ?
A. Phép chiếu (projection)
B. Phép hợp (union)
C. Phép chọn (selection)
D. Phép tích Descartes (Cartesian product)
28. Thuật toán Kruskal được sử dụng để làm gì?
A. Tìm đường đi ngắn nhất giữa hai đỉnh
B. Tìm cây khung nhỏ nhất
C. Tìm chu trình Euler
D. Tìm luồng cực đại trong mạng
29. Cho hàm boolean f(x, y) = x AND (NOT y). Giá trị của f(1, 0) là bao nhiêu?
A. 0
B. 1
C. 2
D. Không xác định
30. Số Fibonacci thứ n (F_n) được định nghĩa đệ quy như thế nào với n > 1?
A. F_n = F_{n-1} + F_{n-2}
B. F_n = 2 * F_{n-1}
C. F_n = F_{n-1} - F_{n-2}
D. F_n = F_{n-1} * F_{n-2}
