1. Cho tập hợp A = {a, b, c, d} và quan hệ R = {(a, a), (b, b), (c, c), (d, d), (a, b), (b, a)}. Bao đóng phản xạ của R là:
A. {(a, b), (b, a)}
B. {(a, a), (b, b), (c, c), (d, d)}
C. {(a, a), (b, b), (c, c), (d, d), (a, b), (b, a)}
D. {(a, a), (b, b), (c, c), (d, d), (a, b), (b, a), (c, a), (d, b)}
2. Đồ thị vô hướng G được gọi là đồ thị Euler nếu:
A. G là đồ thị liên thông và mọi đỉnh có bậc chẵn.
B. G là đồ thị liên thông và tồn tại một chu trình đi qua mọi cạnh, mỗi cạnh đúng một lần.
C. G là đồ thị liên thông và mọi đỉnh có bậc lẻ.
D. G là đồ thị có chu trình Hamilton.
3. Cho hàm Boole f(x, y, z) = x'y + xz + yz'. Biểu thức tối giản dạng tổng các tích (SOP) của hàm f là:
A. x'y + xz
B. xz + yz'
C. x'y + yz'
D. x'y + xz + yz'
4. Cho tập hợp A = {1, 2, 3, 4, 5}. Số tập con có đúng 3 phần tử của A là:
A. 5!
B. 3!
C. C(5, 3)
D. P(5, 3)
5. Trong logic mệnh đề, phép toán nào sau đây **không** phải là phép toán hai ngôi?
A. Phủ định
B. Hội
C. Tuyển
D. Kéo theo
6. Trong số học modulo, phép toán nào sau đây **không** luôn xác định trên tập số nguyên modulo n (Zn) với mọi n > 1?
A. Phép cộng
B. Phép trừ
C. Phép nhân
D. Phép chia
7. Trong logic vị từ, mệnh đề 'Mọi số tự nhiên đều lớn hơn 0' được biểu diễn bằng ký hiệu nào sau đây (với N(x) là 'x là số tự nhiên', L(x, y) là 'x lớn hơn y')?
A. ∀x (N(x) → L(x, 0))
B. ∃x (N(x) ∧ L(x, 0))
C. ∀x (N(x) ∧ L(x, 0))
D. ∃x (N(x) → L(x, 0))
8. 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 chu trình Euler.
B. Tìm chu trình Hamilton.
C. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm.
D. Tìm cây khung nhỏ nhất.
9. Trong phép đếm, quy tắc cộng được áp dụng khi:
A. Các trường hợp xảy ra đồng thời.
B. Các trường hợp là độc lập và không giao nhau.
C. Các trường hợp có giao nhau.
D. Cần tính số cách sắp xếp.
10. Trong tổ hợp, chỉnh hợp chập k của n phần tử (k ≤ n) là:
A. Số cách chọn k phần tử từ n phần tử, không quan tâm thứ tự.
B. Số cách chọn k phần tử từ n phần tử, có quan tâm thứ tự.
C. Số cách sắp xếp n phần tử.
D. Số cách chia n phần tử thành k nhóm.
11. Số cạnh tối đa trong một đồ thị đơn vô hướng có n đỉnh là:
A. n
B. n-1
C. n(n-1)/2
D. n^2
12. Phát biểu nào sau đây về quan hệ tương đương là **đúng**?
A. Quan hệ tương đương chỉ cần có tính phản xạ và đối xứng.
B. Quan hệ tương đương chỉ cần có tính đối xứng và bắc cầu.
C. Quan hệ tương đương chỉ cần có tính phản xạ và bắc cầu.
D. Quan hệ tương đương phải có cả tính phản xạ, đối xứng và bắc cầu.
13. Trong logic vị từ, lượng từ nào sau đây biểu thị ý nghĩa 'tồn tại ít nhất một'?
A. ∀ (lượng từ phổ quát)
B. ∃ (lượng từ tồn tại)
C. ¬ (phủ định)
D. ∧ (hội)
14. Trong tổ hợp, tổ hợp lặp chập k của n phần tử là:
A. Số cách chọn k phần tử từ n phần tử, có thể lặp lại và không quan tâm thứ tự.
B. Số cách chọn k phần tử từ n phần tử, không lặp lại và không quan tâm thứ tự.
C. Số cách chọn k phần tử từ n phần tử, có thể lặp lại và có quan tâm thứ tự.
D. Số cách chọn k phần tử từ n phần tử, không lặp lại và có quan tâm thứ tự.
15. Hệ thức truy hồi Fibonacci được định nghĩa bởi:
A. F(n) = F(n-1) + F(n-2), với F(0) = 0, F(1) = 1.
B. F(n) = 2F(n-1) + 1, với F(0) = 1.
C. F(n) = n * F(n-1), với F(0) = 1.
D. F(n) = F(n-1) - F(n-2), với F(0) = 0, F(1) = 1.
16. Cho tập hợp A = {1, 2, {1, 2}}. Phát biểu nào sau đây là **sai**?
A. 1 ∈ A
B. {1, 2} ∈ A
C. {1} ⊂ A
D. {1, 2} ⊂ A
17. Thuật toán Kruskal được sử dụng để tìm:
A. Đường đi ngắn nhất.
B. Chu trình Euler.
C. Cây khung nhỏ nhất.
D. Chu trình Hamilton.
18. Cho đồ thị G có ma trận kề A. Phần tử A[i, j] của ma trận kề biểu thị:
A. Trọng số của cạnh nối đỉnh i và đỉnh j.
B. Số lượng cạnh nối đỉnh i và đỉnh j.
C. Có tồn tại cạnh nối đỉnh i và đỉnh j hay không.
D. Bậc của đỉnh i.
19. Số hoán vị của n phần tử là:
A. n!
B. 2^n
C. n^2
D. n^n
20. Đồ thị phẳng là đồ thị:
A. Có thể vẽ trên mặt phẳng sao cho không có hai cạnh nào cắt nhau (ngoài đỉnh chung).
B. Luôn có thể tô màu bằng 2 màu.
C. Có chu trình Euler.
D. Có chu trình Hamilton.
21. Trong hệ đếm cơ số 2 (hệ nhị phân), số 101101 tương ứng với số nào trong hệ thập phân?
22. Cho tập hợp A = {1, 2, 3}. Hỏi có bao nhiêu quan hệ hai ngôi có thể xác định trên tập A?
23. 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?
A. Phản xạ
B. Phản đối xứng
C. Bắc cầu
D. Đối xứng
24. Trong đại số Boole, định luật De Morgan phát biểu rằng:
A. (x + y)' = x' + y'
B. (x + y)' = x'y'
C. (xy)' = x'y'
D. (xy)' = xy
25. Nguyên lý Dirichlet (nguyên lý chuồng chim bồ câu) phát biểu rằng:
A. Nếu có n+1 con chim bồ câu nhốt vào n chuồng, thì có ít nhất một chuồng chứa ít nhất 2 con chim.
B. Nếu có n con chim bồ câu nhốt vào n+1 chuồng, thì có ít nhất một chuồng rỗng.
C. Số chuồng phải lớn hơn số chim bồ câu.
D. Số chim bồ câu phải lớn hơn số chuồng.
26. Trong logic mệnh đề, mệnh đề nào sau đây tương đương logic với mệnh đề p → q?
A. q → p
B. ¬p → ¬q
C. ¬p ∨ q
D. p ∧ ¬q
27. Cho hàm f: Z -> Z xác định bởi f(x) = 2x + 1. Hàm f có phải là song ánh không?
A. Có, vì f là đơn ánh và toàn ánh.
B. Không, vì f không là đơn ánh.
C. Không, vì f không là toàn ánh.
D. Không xác định được.
28. Cho quan hệ R trên tập số nguyên Z xác định bởi xRy khi và chỉ khi x - y là số chẵn. Quan hệ R có tính chất nào sau đây?
A. Phản xạ và đối xứng, nhưng không bắc cầu.
B. Đối xứng và bắc cầu, nhưng không phản xạ.
C. Phản xạ và bắc cầu, nhưng không đối xứng.
D. Phản xạ, đối xứng và bắc cầu.
29. 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 và không có chu trình.
B. Trong một cây, giữa hai đỉnh bất kỳ luôn có duy nhất một đường đi.
C. Mọi cây đều là đồ thị phẳng.
D. Mọi cây đều có chu trình Euler.
30. Cây khung của một đồ thị liên thông G là:
A. Một đồ thị con liên thông chứa tất cả các đỉnh của G và không có chu trình.
B. Một đồ thị con chứa tất cả các cạnh của G và là một cây.
C. Một chu trình đi qua tất cả các đỉnh của G.
D. Một đường đi ngắn nhất giữa hai đỉnh của G.
