1. Định nghĩa nào sau đây mô tả đúng về cây (tree) trong lý thuyết đồ thị?
A. Một đồ thị vô hướng liên thông không có chu trình.
B. Một đồ thị có hướng liên thông mạnh.
C. Một đồ thị có chứa ít nhất một chu trình.
D. Một đồ thị có tất cả các đỉnh đều có bậc lẻ.
2. Cho tập hợp $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$. Có bao nhiêu số có 3 chữ số khác nhau được tạo thành từ các chữ số trong $A$?
A. 1000
B. 720
C. 504
D. 100
3. Cho $A$ và $B$ là hai tập hợp. Mệnh đề nào sau đây đúng?
A. $A \cap B = A \cup B$ khi và chỉ khi $A = B$.
B. $A - B = B - A$ khi và chỉ khi $A = \emptyset$.
C. Nếu $A \subset B$ thì $A \cap B = B$.
D. $A \cup B = \emptyset$ khi và chỉ khi $A = B$.
4. Cho đồ thị có hướng $G = (V, E)$ với ma trận kề $A = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}$. Tìm độ dài đường đi ngắn nhất từ đỉnh 1 đến đỉnh 3.
A. 1
B. 2
C. 3
D. Không tồn tại đường đi.
5. Tìm số dư khi chia $2^{100}$ cho 3.
6. Phát biểu nào sau đây là đúng về đồ thị phẳng?
A. Mọi đồ thị đều là đồ thị phẳng.
B. Một đồ thị phẳng có thể vẽ trên mặt phẳng mà không có cạnh nào cắt nhau.
C. Một đồ thị phẳng luôn có chu trình Euler.
D. Một đồ thị phẳng luôn có chu trình Hamilton.
7. Cho tập hợp $A = \{1, 2, 3\}$ và $B = \{a, b\}$. Hỏi số lượng các hàm từ $A$ vào $B$ là bao nhiêu?
8. Cho $A = \{1, 2, 3, 4, 5\}$. Số hàm toàn ánh (surjective) từ $A$ vào $B = \{a, b, c\}$ là:
A. 25
B. 150
C. 300
D. 243
9. Cho hàm $f: A \rightarrow B$ và $g: B \rightarrow C$. Điều kiện nào sau đây là cần và đủ để $g \circ f$ là một song ánh?
A. $f$ và $g$ đều là toàn ánh.
B. $f$ và $g$ đều là đơn ánh.
C. $f$ là đơn ánh và $g$ là toàn ánh.
D. $f$ và $g$ đều là song ánh.
10. Cho đồ thị $G$ có 6 đỉnh và 7 cạnh. Tổng bậc của tất cả các đỉnh của $G$ là bao nhiêu?
11. Cho quan hệ $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ trên tập $A = \{1, 2, 3\}$. Quan hệ $R$ 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, bắc cầu.
D. Phản xạ, đối xứng.
12. Cho $A = \{1, 2, 3\}$. Tìm số lượng các quan hệ tương đương trên $A$.
13. Trong đại số Boole, biểu thức $A + A`B$ tương đương với biểu thức nào?
A. $A$
B. $B$
C. $A + B$
D. $AB$
14. Cho $p$ và $q$ là hai mệnh đề. Mệnh đề nào sau đây tương đương với $\neg (p \lor q)$?
A. $\neg p \lor \neg q$
B. $\neg p \land \neg q$
C. $p \land q$
D. $p \rightarrow q$
15. Cho đồ thị vô hướng $G = (V, E)$ với $V = \{1, 2, 3, 4\}$ và $E = \{(1, 2), (2, 3), (3, 4), (4, 1)\}$. Đồ thị $G$ có phải là đồ thị Euler không?
A. Không, vì có đỉnh bậc lẻ.
B. Có, vì tất cả các đỉnh đều có bậc chẵn.
C. Không, vì đồ thị không liên thông.
D. Có, vì đồ thị liên thông.
16. Cho $A = \{a, b, c\}$. Hỏi có bao nhiêu quan hệ trên $A$?
17. Cho $f(x) = x + 1$. Hỏi $f$ có phải là một hàm một-một (injective) từ tập số nguyên $\mathbb{Z}$ vào $\mathbb{Z}$ không?
A. Có
B. Không
C. Chỉ khi $x > 0$
D. Chỉ khi $x < 0$
18. Cho tập $A=\{1,2,3,4,5\}$. Hỏi có bao nhiêu quan hệ thứ tự bộ phận trên $A$?
A. 1
B. 5
C. Vô số
D. Không thể xác định
19. Trong thuật toán tìm kiếm theo chiều rộng (BFS), cấu trúc dữ liệu nào được sử dụng?
A. Stack
B. Queue
C. Linked List
D. Tree
20. Mệnh đề `Nếu trời mưa thì đường ướt` tương đương với mệnh đề nào sau đây?
A. Nếu đường ướt thì trời mưa.
B. Nếu trời không mưa thì đường không ướt.
C. Nếu đường không ướt thì trời không mưa.
D. Trời mưa và đường ướt.
21. Số các hoán vị của n phần tử là:
A. $n!$
B. $2^n$
C. $n^2$
D. $n$
22. Cho $G$ là một đồ thị đầy đủ với $n$ đỉnh. Hỏi số cạnh của $G$ là bao nhiêu?
A. $n$
B. $n-1$
C. $\frac{n(n-1)}{2}$
D. $n^2$
23. Cho hàm $f(n)$ được định nghĩa như sau: $f(0) = 1$, $f(n) = f(n-1) + n$ với $n > 0$. Tìm $f(4)$.
24. Mệnh đề nào sau đây là hằng đúng?
A. $p \rightarrow (q \rightarrow p)$
B. $(p \rightarrow q) \rightarrow p$
C. $p \rightarrow (p \rightarrow q)$
D. $(p \rightarrow q) \rightarrow q$
25. Cho quan hệ tương đương $R$ trên tập $A$. Nếu $aRb$ và $bRc$ thì điều gì xảy ra?
A. $cRa$
B. $aRc$
C. $a = c$
D. $R = \emptyset$
26. Tìm số nghiệm nguyên dương của phương trình $x_1 + x_2 + x_3 = 7$.
27. Trong một nhóm 10 người, có bao nhiêu cách chọn ra một nhóm 3 người để tham gia một dự án?
A. 30
B. 120
C. 720
D. 10
28. Cho tập hợp $A = \{1, 2, 3, 4, 5\}$. Số tập con có 3 phần tử của $A$ là:
29. Cho $f(x) = x^2 + 1$ và $g(x) = 2x - 3$. Tìm $(f \circ g)(x)$.
A. $4x^2 - 12x + 10$
B. $2x^2 - 1$
C. $4x^2 - 12x + 8$
D. $2x^3 - 3x^2 + 2x - 3$
30. Cho một đồ thị $G$ có $n$ đỉnh. Điều kiện cần và đủ để $G$ có chu trình Hamilton là gì?
A. Mọi đỉnh đều có bậc lớn hơn hoặc bằng 2.
B. G là đồ thị liên thông.
C. G là đồ thị phẳng.
D. Không có điều kiện cần và đủ đơn giản.
