1. Trong lý thuyết đồ thị, một chu trình Euler là gì?
A. Một chu trình đi qua tất cả các cạnh của đồ thị đúng một lần
B. Một chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần
C. Một đường đi ngắn nhất giữa hai đỉnh
D. Một chu trình đi qua tất cả các đỉnh và cạnh của đồ thị nhiều lần
2. Cho quan hệ $R = \{(a, b) | a \le b\}$ trên tập số nguyên. Quan hệ này có tính chất nào?
A. Phản xạ, phản đối xứng, bắc cầu
B. Đối xứng, bắc cầu
C. Phản xạ, đối xứng
D. Phản đối xứng, bắc cầu
3. Cho tập hợp $A = \{1, 2, 3\}$. Hỏi có bao nhiêu quan hệ hai ngôi khác nhau trên $A$?
A. 512
B. 64
C. 256
D. 128
4. Trong một đại số Boolean, đẳng thức nào sau đây là đúng?
A. $x + x` = 1$
B. $x + x = 0$
C. $x \cdot x` = 1$
D. $x \cdot 1 = 0$
5. Cho $A = \{a, b\}$ và $B = \{1, 2, 3\}$. Có bao nhiêu hàm từ $A$ đến $B$?
6. Định nghĩa nào sau đây là đúng về bậc của một đỉnh trong đồ thị vô hướng?
A. Số cạnh liên thuộc với đỉnh đó
B. Số đỉnh kề với đỉnh đó
C. Tổng số đỉnh và cạnh
D. Số đỉnh trừ số cạnh
7. Phát biểu nào sau đây là đúng về tính chất bắc cầu?
A. Nếu (a, b) thuộc R và (b, c) thuộc R thì (a, c) thuộc R
B. Nếu (a, b) thuộc R thì (b, a) thuộc R
C. Nếu (a, a) thuộc R với mọi a
D. Nếu (a, b) thuộc R và (b, a) thuộc R thì a = b
8. Cho $A$ và $B$ là hai tập hợp. Mệnh đề nào sau đây là đúng?
A. $A \cup B = B \cup A$
B. $A - B = B - A$
C. $A \cap B = A \cup B$
D. $A \subseteq B \Leftrightarrow B \subseteq A$
9. Cho $A$ và $B$ là hai tập hợp. Phát biểu nào sau đây là đúng về lực lượng của $A \times B$?
A. $|A \times B| = |A| \cdot |B|$
B. $|A \times B| = |A| + |B|$
C. $|A \times B| = max(|A|, |B|)$
D. $|A \times B| = min(|A|, |B|)$
10. Cho đồ thị $G$ có các đỉnh là {a, b, c, d} và các cạnh là {(a, b), (b, c), (c, d)}. Có bao nhiêu đường đi từ a đến d?
11. Số các số nguyên dương nhỏ hơn 100 và nguyên tố cùng nhau với 100 là bao nhiêu?
12. Cho $A = \{1, 2\}$. Tính lực lượng của tập lũy thừa của $A$.
13. Định nghĩa nào sau đây là đúng về cây khung nhỏ nhất (Minimum Spanning Tree)?
A. Một cây khung có tổng trọng số các cạnh là nhỏ nhất
B. Một cây khung chứa tất cả các đỉnh của đồ thị
C. Một cây khung không có chu trình
D. Tất cả các đáp án trên
14. Cho hàm $f: A \rightarrow B$. Điều kiện nào sau đây là điều kiện cần và đủ để $f$ là một song ánh?
A. $f$ là đơn ánh và toàn ánh
B. $f$ là đơn ánh
C. $f$ là toàn ánh
D. $|A| = |B|$
15. Cho $f(n) = n^2 + 1$ và $g(n) = n$. Hỏi $f(n)$ là $O(g(n))$ có đúng không?
A. Sai
B. Đúng
C. Không xác định
D. Chỉ đúng với n < 10
16. Mệnh đề nào sau đây là hằng đúng?
A. $(p \rightarrow q) \leftrightarrow (\neg q \rightarrow \neg p)$
B. $(p \rightarrow q) \leftrightarrow (q \rightarrow p)$
C. $(p \rightarrow q) \leftrightarrow (\neg p \rightarrow \neg q)$
D. $(p \rightarrow q) \leftrightarrow (\neg p \lor q)$
17. Trong một nhóm, phần tử đơn vị được định nghĩa như thế nào?
A. Là phần tử e sao cho a * e = e * a = a với mọi a trong nhóm
B. Là phần tử e sao cho a * e = e * a = e với mọi a trong nhóm
C. Là phần tử e sao cho a * e = e * a = 1 với mọi a trong nhóm
D. Là phần tử e sao cho a * e = e * a = 0 với mọi a trong nhóm
18. Cho một đồ thị phẳng liên thông có 10 đỉnh và 15 cạnh. Hỏi đồ thị này chia mặt phẳng thành bao nhiêu miền?
19. Số hoán vị của n phần tử là bao nhiêu?
20. Tìm số nghiệm nguyên không âm của phương trình $x_1 + x_2 + x_3 = 5$.
21. Cho đồ thị $G$ có ma trận kề là ma trận đơn vị. Phát biểu nào sau đây là đúng?
A. G không có cạnh
B. G là một đồ thị đầy đủ
C. G chỉ có các khuyên
D. G là một cây
22. 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ạ, đối xứng
C. Đối xứng, bắc cầu
D. Phản xạ, bắc cầu
23. Phát biểu nào sau đây là đúng về biểu thức chính tắc tuyển (Disjunctive Normal Form - DNF)?
A. Là tuyển của các hội
B. Là hội của các tuyển
C. Là tuyển của các biến
D. Là hội của các biến
24. Cho đồ thị vô hướng $G = (V, E)$ với $|V| = n$ và $|E| = m$. Điều kiện nào sau đây là điều kiện cần và đủ để $G$ là một cây?
A. $G$ liên thông và $m = n - 1$
B. $G$ liên thông và $m = n$
C. $G$ không có chu trình và $m = n$
D. $G$ có chu trình và $m = n - 1$
25. Số các số nguyên dương nhỏ hơn hoặc bằng 100 chia hết cho 2 hoặc 3 là bao nhiêu?
26. Cho $R$ là một quan hệ tương đương trên tập $A$. Điều gì xảy ra với các lớp tương đương của $A$?
A. Chúng tạo thành một phân hoạch của $A$
B. Chúng là các tập con rời nhau của $A$
C. Chúng là các tập con bằng nhau của $A$
D. Chúng tạo thành một tập hợp rỗng
27. Cho tập hợp $A = \{1, 2, 3, 4, 5\}$. Có bao nhiêu tập con của $A$ chứa phần tử 1?
28. Cho $A = \{1, 2, 3\}$ và $B = \{a, b\}$. Hỏi lực lượng của tập các hàm từ $A$ vào $B$ là bao nhiêu?
29. Số cạnh của một đồ thị đầy đủ $K_n$ là bao nhiêu?
A. $\frac{n(n-1)}{2}$
B. $n(n-1)$
C. $n$
D. $\frac{n(n+1)}{2}$
30. Cho đồ thị có hướng $G = (V, E)$. Khi nào thì thuật toán Dijkstra có thể được sử dụng để tìm đường đi ngắn nhất từ một đỉnh nguồn đến các đỉnh khác?
A. Khi tất cả các trọng số cạnh đều không âm
B. Khi đồ thị không có chu trình
C. Khi đồ thị là đồ thị đầy đủ
D. Luôn luôn
