1. Cho quan hệ R = {(1, 2), (2, 3), (1, 3)} trên tập A = {1, 2, 3}. Quan hệ R có tính chất bắc cầu không?
A. Có
B. Không
C. Chỉ bắc cầu trên một số cặp
D. Không xác định
2. Cho tập hợp A = {a, b, c, d}. Hỏi có bao nhiêu chỉnh hợp chập 2 của A?
3. 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. Khoảng cách từ đỉnh đó đến đỉnh xa nhất.
D. Số đường đi ngắn nhất đến đỉnh đó.
4. Trong thuật toán Dijkstra tìm đường đi ngắn nhất, tập hợp nào sau đây được sử dụng để theo dõi các đỉnh đã được xét và khoảng cách ngắn nhất đến chúng?
A. Hàng đợi ưu tiên
B. Ngăn xếp
C. Danh sách liên kết
D. Mảng
5. Cho bảng chân trị của phép toán logic. Hỏi phép toán nào có bảng chân trị sau:
| p | q | ? |
|---|---|---|
| Đ | Đ | S |
| Đ | S | S |
| S | Đ | S |
| S | S | Đ |
A. p ∧ q
B. p ∨ q
C. p → q
D. p ↔ q
6. Phép toán XOR (phép tuyển loại trừ) của hai bit là gì?
A. 1 khi cả hai bit đều là 1.
B. 0 khi cả hai bit đều là 1.
C. 1 khi cả hai bit khác nhau.
D. 0 khi cả hai bit khác nhau.
7. Cho quan hệ R trên tập hợp A = {1, 2, 3} được định nghĩa bởi R = {(1, 1), (1, 2), (2, 3)}. Quan hệ R có tính chất phản xạ không?
A. Có
B. Không
C. Chỉ phản xạ trên một số phần tử
D. Không xác định
8. Cho hàm f: A → B. Hàm f được gọi là đơn ánh (injective) khi:
A. Với mọi y ∈ B, tồn tại x ∈ A sao cho f(x) = y.
B. Với mọi x1, x2 ∈ A, nếu f(x1) = f(x2) thì x1 = x2.
C. Với mọi x ∈ A, tồn tại duy nhất y ∈ B sao cho f(x) = y.
D. Tập A và B có cùng số phần tử.
9. 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. Đường đi ngắn nhất giữa hai đỉnh.
D. Chu trình chứa tất cả các đỉnh và cạnh.
10. Phương pháp chứng minh nào 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 phản chứng
B. Chứng minh trực tiếp
C. Quy nạp toán học
D. Chứng minh bằng phản ví dụ
11. Mệnh đề phủ định của `Mọi số tự nhiên đều là số chẵn` là:
A. Mọi số tự nhiên đều là số lẻ.
B. Có ít nhất một số tự nhiên là số chẵn.
C. Có ít nhất một số tự nhiên không phải là số chẵn.
D. Không có số tự nhiên nào là số chẵn.
12. Biểu thức logic (p ∧ q) → p là một:
A. Mâu thuẫn
B. Hằng đúng
C. Khả năng
D. Không xác định
13. Cây nhị phân đầy đủ là cây nhị phân mà:
A. Mỗi nút có đúng 2 con.
B. Mỗi nút không phải lá có đúng 2 con và tất cả các lá ở cùng một mức.
C. Tất cả các nút đều có con.
D. Chỉ có nút gốc có con.
14. Đồ thị vô hướng G được gọi là liên thông nếu:
A. Mọi đỉnh trong G đều có bậc lớn hơn 0.
B. Có một đường đi giữa bất kỳ cặp đỉnh nào trong G.
C. Số cạnh của G bằng số đỉnh trừ 1.
D. G không chứa chu trình.
15. Cây có gốc là một dạng đặc biệt của đồ thị nào?
A. Đồ thị đầy đủ
B. Đồ thị phẳng
C. Đồ thị có hướng
D. Đồ thị vô hướng
16. Trong đại số Boolean, luật De Morgan phát biểu rằng:
A. ¬(p ∧ q) ≡ ¬p ∧ ¬q
B. ¬(p ∨ q) ≡ ¬p ∨ ¬q
C. ¬(p ∧ q) ≡ ¬p ∨ ¬q
D. ¬(p → q) ≡ ¬p ∧ ¬q
17. Hàm f(n) = 3n² + 2n + 1 có độ phức tạp thời gian là bao nhiêu theo ký hiệu Big O?
A. O(n)
B. O(n log n)
C. O(n²)
D. O(2ⁿ)
18. Trong số học đồng dư, tìm x sao cho x ≡ 3 (mod 5). Giá trị nào sau đây của x thỏa mãn?
19. Trong hệ đếm cơ số 2 (hệ nhị phân), số 1011 tương đương với số nào trong hệ thập phân?
20. Phép toán nào sau đây là phép giao của hai tập hợp?
21. Tính chất bắc cầu áp dụng cho loại quan hệ nào sau đây?
A. Quan hệ đối xứng
B. Quan hệ phản xạ
C. Quan hệ tương đương
D. Quan hệ phản đối xứng
22. Công thức nào sau đây tính số tổ hợp chập k của n phần tử?
A. n!
B. n! ∕ (n-k)!
C. n! ∕ (k! × (n-k)!)
D. k! ∕ (n! × (n-k)!)
23. Trong thuật toán Kruskal tìm cây khung nhỏ nhất, tiêu chí nào sau đây được sử dụng để chọn cạnh thêm vào cây?
A. Chọn cạnh có trọng số lớn nhất.
B. Chọn cạnh có trọng số nhỏ nhất và không tạo chu trình.
C. Chọn cạnh ngẫu nhiên.
D. Chọn cạnh liên thuộc với đỉnh có bậc cao nhất.
24. Cho tập hợp A = {1, 2, 3}. Hỏi có bao nhiêu tập con của A?
25. Trong logic vị từ, lượng từ ∀ được gọi là:
A. Lượng từ tồn tại
B. Lượng từ phổ dụng
C. Lượng từ duy nhất
D. Lượng từ phủ định
26. Cho tập hợp A = {1, 2, 3, 4, 5} và B = {3, 5, 6, 7}. Tính A ∪ B.
A. {3, 5}
B. {1, 2, 4, 6, 7}
C. {1, 2, 3, 4, 5, 6, 7}
D. {1, 2, 3, 4, 5}
27. Trong số học đồng dư, phát biểu nào sau đây là đúng về quan hệ đồng dư modulo n?
A. Quan hệ không phản xạ
B. Quan hệ không đối xứng
C. Quan hệ tương đương
D. Quan hệ thứ tự bộ phận
28. Công thức nào sau đây là đúng cho số hoán vị của n phần tử?
29. Trong một đồ thị đầy đủ Kn, mỗi đỉnh có bậc là bao nhiêu?
30. Trong logic mệnh đề, phép toán nào sau đây biểu diễn cho mệnh đề `P kéo theo Q`?
A. P ∧ Q
B. P ∨ Q
C. P → Q
D. P ↔ Q
