1. Trong lý thuyết đồ thị, một chu trình Hamilton là:
A. Chu trình đi qua tất cả các cạnh của đồ thị đúng một lần.
B. Chu trình đ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 trong đồ thị.
D. Cây bao trùm đồ thị với tổng trọng số cạnh nhỏ nhất.
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ạ
B. Đối xứng
C. Phản đối xứng
D. Bắc cầu
3. Cấu trúc dữ liệu nào sau đây thường được sử dụng để biểu diễn đồ thị trong máy tính?
A. Mảng
B. Danh sách liên kết
C. Ma trận kề và danh sách kề
D. Cây nhị phân
4. Trong logic vị từ, lượng từ ∀ được gọi là:
A. Lượng từ tồn tại
B. Lượng từ phổ quát
C. Lượng từ duy nhất
D. Lượng từ phủ định
5. Cho hàm mệnh đề P(x): `x là số nguyên tố`. Giá trị chân lý của ∀x P(x) với miền xác định là tập hợp số nguyên dương là:
A. Đúng
B. Sai
C. Không xác định
D. Tùy thuộc vào x
6. Phương pháp chứng minh quy nạp thường được sử dụng để chứng minh các mệnh đề liên quan đến:
A. Tập hợp hữu hạn
B. Số nguyên dương
C. Số thực
D. Số phức
7. Đồ thị vô hướng G = (V, E) được gọi là đồ thị Euler nếu:
A. Mọi đỉnh trong đồ thị đều có bậc chẵn.
B. Có đúng hai đỉnh có bậc lẻ.
C. Có ít nhất một đỉnh có bậc lẻ.
D. Mọi đỉnh trong đồ thị đều có bậc lẻ.
8. Trong lý thuyết tập hợp, phép toán nào sau đây cho kết quả là tập hợp chứa các phần tử thuộc cả hai tập hợp A và B?
A. Hợp (Union)
B. Giao (Intersection)
C. Hiệu (Difference)
D. Tích Descartes (Cartesian Product)
9. Thuật toán Dijkstra thường được sử dụng để giải bài toán nào 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.
C. Tìm chu trình Hamilton.
D. Kiểm tra tính liên thông của đồ thị.
10. Cho hàm Boole f(x, y, z) = x′y + xz. Biểu thức nào sau đây là dạng chuẩn tuyển (DNF) của f?
A. x′yz′ + x′yz + xy′z + xyz
B. x′y′z′ + x′y′z + xy′z + xyz
C. x′yz′ + x′yz + xy′z′ + xyz
D. x′yz′ + x′y′z + xy′z + xyz
11. Hàm số f: A → B được gọi là đơn ánh (injective) khi:
A. Với mọi a1, a2 thuộc A, nếu f(a1) = f(a2) thì a1 = a2.
B. Với mọi b thuộc B, tồn tại ít nhất một a thuộc A sao cho f(a) = b.
C. Với mọi a thuộc A, tồn tại duy nhất một b thuộc B sao cho f(a) = b.
D. Với mọi b thuộc B, tồn tại nhiều nhất một a thuộc A sao cho f(a) = b.
12. Trong đại số quan hệ, phép toán `chọn′ (selection) có tác dụng gì?
A. Kết hợp dữ liệu từ hai quan hệ dựa trên điều kiện chung.
B. Chọn ra một tập hợp con các bộ (tuples) từ một quan hệ thỏa mãn một điều kiện cho trước.
C. Loại bỏ các thuộc tính (attributes) không mong muốn khỏi một quan hệ.
D. Sắp xếp các bộ trong một quan hệ theo một thứ tự nhất định.
13. Nguyên lý chuồng bồ câu (Pigeonhole Principle) phát biểu rằng:
A. Nếu có n con bồ câu và m chuồng bồ câu, với n > m, thì ít nhất một chuồng chứa ít nhất hai con bồ câu.
B. Nếu có n con bồ câu và m chuồng bồ câu, với n < m, thì mỗi chuồng chứa tối đa một con bồ câu.
C. Số bồ câu luôn bằng số chuồng bồ câu.
D. Số bồ câu luôn lớn hơn số chuồng bồ câu.
14. Một đồ thị phẳng là đồ thị có thể được vẽ trên mặt phẳng sao cho:
A. Các cạnh không cắt nhau tại đỉnh.
B. Các cạnh có thể cắt nhau tại đỉnh hoặc không phải đỉnh.
C. Các cạnh không cắt nhau, chỉ có thể giao nhau tại các đỉnh.
D. Các đỉnh không được nằm trên cùng một đường thẳng.
15. Trong logic mệnh đề, quy tắc Modus Ponens có dạng:
A. [(p → q) ∧ q] → p
B. [(p → q) ∧ ¬p] → ¬q
C. [(p → q) ∧ p] → q
D. [(p ∨ q) ∧ ¬p] → q
16. Trong một nhóm (G, *), phần tử nghịch đảo của phần tử a được ký hiệu là:
A. a′
B. -a
C. a⁻¹
D. 1∕a
17. 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. Số lượng phần tử được chọn
B. Thứ tự của các phần tử được chọn
C. Loại phần tử được chọn
D. Cách thức chọn phần tử
18. Trong giải tích thuật toán, độ phức tạp thời gian O(log n) thường được gọi là:
A. Tuyệt vời
B. Tuyến tính
C. Logarit
D. Bậc hai
19. Cho quan hệ thứ tự bộ phận (poset) (A, ≤). Một phần tử a ∈ A được gọi là phần tử tối đại nếu:
A. Không tồn tại b ∈ A sao cho b ≤ a và b ≠ a.
B. Không tồn tại b ∈ A sao cho a ≤ b và a ≠ b.
C. Với mọi b ∈ A, hoặc b ≤ a hoặc a ≤ b.
D. Với mọi b ∈ A, b ≤ a.
20. Số hoán vị của n phần tử là:
21. Trong lý thuyết mã hóa, mã Hamming được sử dụng để:
A. Nén dữ liệu
B. Mã hóa dữ liệu để bảo mật
C. Phát hiện và sửa lỗi trong quá trình truyền dữ liệu
D. Tăng tốc độ truyền dữ liệu
22. Trong logic mệnh đề, phép toán nào sau đây tương đương với biểu thức ¬(p ∧ q)?
A. ¬p ∧ ¬q
B. ¬p ∨ ¬q
C. p ∨ q
D. p ∧ q
23. Số cạnh tối thiểu trong một đồ thị liên thông có n đỉnh là:
A. n
B. n-1
C. n+1
D. n(n-1)∕2
24. Cho dãy số Fibonacci Fₙ được định nghĩa bởi F₀ = 0, F₁ = 1, và Fₙ = Fₙ₋₁ + Fₙ₋₂ với n ≥ 2. Giá trị của F₅ là:
25. Trong lý thuyết đồ thị, phát biểu nào sau đây về cây là SAI?
A. Cây là đồ thị liên thông không có chu trình.
B. Mọi cây đều là đồ thị hai phía.
C. Trong một cây có n đỉnh, có đúng n-1 cạnh.
D. Có thể tồn tại cây có chu trình.
26. Ký hiệu O lớn (Big O notation) thường được sử dụng để mô tả:
A. Độ phức tạp không gian của thuật toán.
B. Độ phức tạp thời gian tiệm cận của thuật toán.
C. Độ chính xác của thuật toán.
D. Độ dễ hiểu của thuật toán.
27. Trong lý thuyết số, ước chung lớn nhất (UCLN) của hai số nguyên a và b có ký hiệu là:
A. lcm(a, b)
B. gcd(a, b)
C. mod(a, b)
D. div(a, b)
28. Trong đại số Boole, định luật hấp thụ phát biểu rằng:
A. x + (x × y) = x
B. x + x′ = 1
C. x × x′ = 0
D. x + y = y + x
29. Cho tập hợp A = {a, b, c}. Số quan hệ hai ngôi khác nhau có thể xác định trên A là:
30. Cho quan hệ R trên tập hợp số nguyên Z xác định bởi aRb nếu a ≡ b (mod 3). Quan hệ R là quan hệ:
A. Tương đương
B. Thứ tự bộ phận
C. Thứ tự toàn phần
D. Phản xạ và đối xứng nhưng không bắc cầu
