1. 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) ∧ q) → p
2. Ứng dụng nào sau đây KHÔNG phải là ứng dụng của đồ thị trong khoa học máy tính?
A. Mạng xã hội
B. Hệ thống định tuyến đường đi
C. Cơ sở dữ liệu quan hệ
D. Thiết kế mạch điện tử
3. Một đồ thị đầy đủ (complete graph) Kn có bao nhiêu cạnh?
A. n
B. n - 1
C. n * (n - 1)
D. n * (n - 1) / 2
4. Cho hàm băm h(x) = x mod 10. Giá trị băm của số 123 là:
5. Trong một đồ thị phẳng, công thức Euler liên hệ giữa số đỉnh (V), số cạnh (E) và số miền (F) là:
A. V - E + F = 1
B. V - E + F = 2
C. V + E - F = 2
D. V + E + F = 2
6. Hàm số f: Z → Z được định nghĩa bởi f(x) = 2x + 1. Hàm số này là:
A. Song ánh
B. Toàn ánh nhưng không đơn ánh
C. Đơn ánh nhưng không toàn ánh
D. Không đơn ánh và không toàn ánh
7. 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 chu trình Hamilton
B. Tìm đường đi ngắn nhất giữa hai đỉnh
C. Tìm cây khung nhỏ nhất
D. Tìm luồng cực đại trong mạng
8. 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
9. Trong lý thuyết đồ thị, cây là một loại đồ thị đặc biệt, nó phải thỏa mãn tính chất nào sau đây?
A. Có chu trình và liên thông
B. Không có chu trình và liên thông
C. Có chu trình và không liên thông
D. Không có chu trình và không liên thông
10. Trong logic mệnh đề, phép tương đương logic (≡) có tính chất nào sau đây?
A. Chỉ có tính phản xạ
B. Chỉ có tính đối xứng
C. Chỉ có tính bắc cầu
D. Có cả tính phản xạ, đối xứng và bắc cầu
11. Trong đại số Boolean, luật De Morgan phát biểu rằng:
A. Phủ định của hội bằng tuyển của phủ định
B. Phủ định của tuyển bằng hội của phủ định
C. Hội của phủ định bằng tuyển của phủ định
D. Tuyển của phủ định bằng hội của phủ định
12. Trong một đồ thị vô hướng liên thông, đường đi Euler tồn tại khi và chỉ khi:
A. Tất cả các đỉnh có bậc chẵn
B. Có đúng hai đỉnh có bậc lẻ
C. Có không quá hai đỉnh có bậc lẻ
D. Có ít nhất một đỉnh có bậc lẻ
13. Cho tập hợp A = {1, 2, 3} và B = {3, 4, 5}. Tập hợp giao của A và B (A ∩ B) là:
A. {1, 2, 3, 4, 5}
B. {1, 2}
C. {3}
D. {}
14. Trong lý thuyết đồ thị, bậc của một đỉnh được định nghĩa là gì?
A. Số đỉnh kề với nó
B. Số cạnh liên thuộc với nó
C. Tổng trọng số của các cạnh liên thuộc
D. Độ dài đường đi ngắn nhất từ đỉnh đó đến đỉnh khác
15. Cho tập hợp S = {a, b, c}. Số tập con của tập hợp S là:
16. Trong lý thuyết đồ thị, đồ thị lưỡng phân (bipartite graph) là đồ thị mà:
A. Các đỉnh có thể chia thành hai tập độc lập sao cho mọi cạnh đều nối đỉnh từ tập này sang tập kia
B. Mọi đỉnh đều có bậc chẵn
C. Có chu trình Euler
D. Không có chu trình lẻ
17. Số lượng hoán vị của n phần tử phân biệt là:
18. Trong logic mệnh đề, mệnh đề kéo theo p → q sai khi nào?
A. p đúng và q đúng
B. p đúng và q sai
C. p sai và q đúng
D. p sai và q sai
19. Trong một nhóm gồm 10 người, cần chọn ra 3 người để thành lập một ban đại diện. Số cách chọn khác nhau là:
A. 10
B. 30
C. 120
D. 720
20. Phương pháp chứng minh nào sau đây thường được sử dụng để chứng minh một mệnh đề đúng cho tất cả các số tự nhiên?
A. Chứng minh trực tiếp
B. Chứng minh bằng phản chứng
C. Chứng minh quy nạp
D. Chứng minh bằng xét tất cả các trường hợp
21. Phép toán nào sau đây KHÔNG phải là phép toán cơ bản trong logic mệnh đề?
A. Phép hội (AND)
B. Phép tuyển (OR)
C. Phép kéo theo (IMPLICATION)
D. Phép tích phân (INTEGRATION)
22. Trong toán học rời rạc, cấu trúc nào sau đây dùng để biểu diễn mối quan hệ giữa các đối tượng?
A. Ma trận
B. Đồ thị
C. Hàm số
D. Tập hợp
23. Trong quan hệ chia hết trên tập số nguyên dương, quan hệ này có tính chất nào sau đây?
A. Đối xứng
B. Phản đối xứng
C. Bắc cầu
D. Vừa đối xứng vừa phản đối xứng
24. 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ử mà 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 chia n phần tử thành k nhóm
D. Số cách sắp xếp n phần tử vào k vị trí
25. Phép toán nào sau đây KHÔNG phải là phép toán tập hợp cơ bản?
A. Phép hợp (UNION)
B. Phép giao (INTERSECTION)
C. Phép hiệu (DIFFERENCE)
D. Phép nhân (MULTIPLICATION)
26. 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
27. Cho tập hợp A = {1, 2, 3}. Số quan hệ hai ngôi có thể định nghĩa trên tập A là:
28. Thuật toán Kruskal được sử dụng để tìm:
A. Chu trình Hamilton
B. Đường đi Euler
C. Cây khung nhỏ nhất
D. Luồng cực đại
29. Quan hệ R trên tập hợp A là quan hệ tương đương khi và chỉ khi nó thỏa mãn đồng thời 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. Bất phản xạ, đối xứng, bắc cầu
D. Phản xạ, đối xứng, không bắc cầu
30. Trong đại số Boolean, biểu thức A + A'B tương đương với biểu thức nào?
