1. Mệnh đề `∀x ∈ R, x² ≥ 0′ có nghĩa là:
A. Có một số thực x mà x² ≥ 0.
B. Với mọi số thực x, x² ≥ 0.
C. Tồn tại một số thực x mà x² < 0.
D. Với mọi số thực x, x² < 0.
2. Phương pháp chứng minh quy nạp thường được sử dụng để chứng minh:
A. Tính đúng đắn của một thuật toán cụ thể.
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 liên tục của một hàm số.
3. 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. 2n
4. Trong lý thuyết đồ thị, bậc của một đỉnh được định nghĩa là:
A. Số đỉnh kề với đỉnh đó.
B. Số cạnh liên thuộc với đỉnh đó.
C. Tổng số đỉnh và cạnh trong đồ thị.
D. Số đường đi ngắn nhất từ đỉnh đó đến tất cả các đỉnh khác.
5. Nếu một đồ thị phẳng có v đỉnh, e cạnh và f mặt, thì theo công thức Euler, mối quan hệ giữa v, e, f là:
A. v - e + f = 1
B. v + e - f = 2
C. v - e + f = 2
D. v + e + f = 2
6. Trong các cấu trúc dữ liệu sau, cấu trúc nào thường được sử dụng để biểu diễn đồ thị?
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 tìm kiếm.
7. 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ị, mỗi cạnh đúng một lần.
B. Chu trình đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần (trừ đỉnh đầu∕cuối).
C. Đường đi ngắn nhất giữa hai đỉnh.
D. Cây bao trùm nhỏ nhất của đồ thị.
8. 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
9. Trong các hệ thống số, số 1011 (hệ nhị phân) tương đương với số nào trong hệ thập phân?
10. Trong logic mệnh đề, phép toán nào sau đây được gọi là phép tuyển?
A. Phép hội (∧)
B. Phép tuyển (∨)
C. Phép kéo theo (→)
D. Phép tương đương (↔)
11. Cho tập hợp A = {1, 2, 3}. Hỏi có bao nhiêu tập con của tập A?
12. Cho hai tập hợp A = {a, b, c} và B = {c, d, e}. Tập hợp A ∩ B bằng:
A. {a, b, c, d, e}
B. {c}
C. {a, b, d, e}
D. {}
13. Thuật toán Dijkstra thường được sử dụng để giải quyết bài toán nào sau đây trên đồ thị?
A. Tìm chu trình Euler.
B. Tìm đường đi ngắn nhất giữa hai đỉnh.
C. Tìm cây bao trùm nhỏ nhất.
D. Kiểm tra tính liên thông của đồ thị.
14. Tính chất nào sau đây KHÔNG phải là tính chất của phép toán hội (∧) trong logic mệnh đề?
A. Tính giao hoán: p ∧ q ≡ q ∧ p
B. Tính kết hợp: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
C. Tính lũy đẳng: p ∧ p ≡ p
D. Tính hấp thụ: p ∧ (p ∨ q) ≡ q
15. Cho tập hợp A = {1, 2, 3, 4, 5}. Hỏi có bao nhiêu tập con của A có đúng 3 phần tử?
16. 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ó hay không có phần tử lặp lại.
17. Hệ đếm cơ số 16 còn được gọi là hệ đếm:
A. Nhị phân.
B. Bát phân.
C. Thập phân.
D. Hexadecimal.
18. 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ó (khác nhóm trưởng)?
A. 10
B. 90
C. 100
D. 10!
19. Phát biểu nào sau đây là đúng về đồ thị Euler?
A. Đồ thị Euler luôn là đồ thị Hamilton.
B. Đồ thị liên thông có chu trình Euler khi và chỉ khi mọi đỉnh có bậc chẵn.
C. Đồ thị có đường đi Euler khi và chỉ khi mọi đỉnh có bậc chẵn.
D. Đồ thị Euler là đồ thị không liên thông.
20. Cho hàm băm h(x) = x mod 10. Giá trị băm của số 123 là:
21. Trong các mệnh đề sau, mệnh đề nào là hằng đúng?
A. p ∧ ¬p
B. p ∨ ¬p
C. p → q
D. p ↔ q
22. Cho hàm số f: Z → Z xác định bởi f(x) = 2x + 1. Hàm số này là:
A. Song ánh.
B. Đơn ánh nhưng không toàn ánh.
C. Toàn ánh nhưng không đơn ánh.
D. Không đơn ánh và không toàn ánh.
23. Số hoán vị của n phần tử khác nhau là:
24. Cây là một loại đồ thị đặc biệt. Phát biểu nào sau đây KHÔNG đúng về cây?
A. Cây là đồ thị liên thông.
B. Cây là đồ thị vô hướng.
C. Cây chứa chu trình.
D. Cây có đúng một đường đi giữa hai đỉnh bất kỳ.
25. Trong logic vị từ, lượng từ tồn tại (∃) được đọc là:
A. Với mọi.
B. Tồn tại ít nhất một.
C. Không tồn tại.
D. Tất cả.
26. Quan hệ R trên tập A là quan hệ tương đương khi và chỉ khi R đồng thời có 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, phản bắc cầu.
27. 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) ∧ q] → p
D. [(p ∨ q) ∧ ¬p] → q
28. Cho quan hệ R = {(1, 1), (1, 2), (2, 2), (3, 3)} trên tập A = {1, 2, 3}. Quan hệ R 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. Phản xạ.
29. Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu:
A. Mọi đỉnh trong V đều có bậc khác 0.
B. Có một đường đi giữa mọi cặp đỉnh phân biệt trong V.
C. Số cạnh trong E bằng |V| - 1.
D. Đồ thị G không chứa chu trình.
30. Trong thuật toán Kruskal, mục tiêu là tìm:
A. Đường đi ngắn nhất.
B. Chu trình Hamilton.
C. Cây bao trùm nhỏ nhất.
D. Luồng cực đại trong mạng.
