1. Phát biểu nào sau đây là đúng về cây nhị phân đầy đủ?
A. Mỗi nút có đúng 2 con
B. Mỗi nút có 0 hoặc 2 con
C. Tất cả các lá có cùng độ sâu
D. Cả B và C
2. Phát biểu nào sau đây là đúng về một đồ thị phẳng?
A. Đồ thị có thể vẽ trên mặt phẳng sao cho không có cạnh nào cắt nhau
B. Đồ thị có thể vẽ trên mặt phẳng sao cho tất cả các cạnh cắt nhau
C. Đồ thị có một chu trình Euler
D. Đồ thị có một đường đi Hamilton
3. Tìm số cách sắp xếp 5 người vào một bàn tròn.
4. Một cây có $n$ đỉnh thì có bao nhiêu cạnh?
A. $n$
B. $n-1$
C. $n+1$
D. $2n$
5. Đồ thị đầy đủ $K_n$ có bao nhiêu cạnh?
A. $n$
B. $n^2$
C. $\frac{n(n-1)}{2}$
D. $n!$
6. Điều kiện cần và đủ để một đồ thị có chu trình Hamilton là gì?
A. Đồ thị phải liên thông
B. Đồ thị phải có bậc của mỗi đỉnh lớn hơn hoặc bằng $n/2$, với $n$ là số đỉnh
C. Đồ thị phải có chu trình Euler
D. Không có điều kiện cần và đủ đã biết
7. Tìm số nghiệm nguyên không âm của phương trình $x_1 + x_2 + x_3 = 7$.
8. Cho $A$ và $B$ là hai tập hợp. Phát biểu nào sau đây là đúng về $(A \cup B)^c$?
A. $A^c \cup B^c$
B. $A^c \cap B^c$
C. $A \cap B$
D. $A \cup B$
9. Trong một đại số Boole, phát biểu nào sau đây là đúng?
A. $a + a` = 0$
B. $a \cdot a` = 1$
C. $a + a` = 1$
D. $a \cdot a = a`$
10. Trong một nhóm 10 người, mỗi người bắt tay với mọi người khác đúng một lần. Có bao nhiêu cái bắt tay?
11. 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 kề với đỉnh đó
C. Số đường đi từ đỉnh đó đến tất cả các đỉnh khác
D. Số chu trình đi qua đỉnh đó
12. Cho $A = \{1, 2, 3, 4, 5\}$. Có bao nhiêu tập con của $A$ có kích thước là 3?
13. Cho $A = \{1, 2, 3, 4, 5\}$. Có bao nhiêu song ánh (bijection) từ $A$ đến $A$?
A. 5
B. 25
C. 120
D. 3125
14. Cho quan hệ thứ tự toàn phần $R$ trên tập $A$. Điều gì sau đây là đúng?
A. Mọi cặp phần tử trong $A$ đều so sánh được
B. Không có cặp phần tử nào trong $A$ so sánh được
C. Chỉ một số cặp phần tử trong $A$ so sánh được
D. Quan hệ $R$ không có tính phản xạ
15. Số Stirling loại 2 $S(n, k)$ đếm cái gì?
A. Số cách chia một tập hợp có $n$ phần tử thành $k$ tập con không rỗng
B. Số cách chọn $k$ phần tử từ một tập hợp có $n$ phần tử
C. Số cách sắp xếp $n$ phần tử vào $k$ vị trí
D. Số cách chọn $n$ phần tử từ một tập hợp có $k$ phần tử
16. Cho $A = \{1, 2, 3\}$ và $B = \{a, b\}$. Tìm số hàm từ $A$ đến $B$.
17. Phát biểu nào sau đây là đúng về đồ thị Euler?
A. Đồ thị có một chu trình đi qua tất cả các cạnh, mỗi cạnh đúng một lần
B. Đồ thị có một đường đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần
C. Đồ thị có một chu trình đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần
D. Đồ thị có một đường đi qua tất cả các cạnh, mỗi cạnh đúng một lần
18. Cho tập hợp $A = \{1, 2, 3, 4\}$. Có bao nhiêu quan hệ hai ngôi trên $A$?
19. Trong logic mệnh đề, quy tắc suy diễn Modus Ponens có dạng:
A. $[(p \rightarrow q) \land p] \rightarrow q$
B. $[(p \rightarrow q) \land q] \rightarrow p$
C. $[(p \rightarrow q) \land \neg p] \rightarrow \neg q$
D. $[(p \rightarrow q) \land \neg q] \rightarrow \neg p$
20. Cho $p$ và $q$ là hai mệnh đề. Mệnh đề nào sau đây là hằng đúng?
A. $(p \rightarrow q) \rightarrow (q \rightarrow p)$
B. $(p \land q) \rightarrow (p \lor q)$
C. $(p \lor q) \rightarrow (p \land q)$
D. $(p \leftrightarrow q) \rightarrow (p \land q)$
21. Cho tập hợp $A = \{1, 2, 3\}$. Quan hệ nào sau đây trên $A$ là một quan hệ tương đương?
A. $\R = \{(1, 1), (2, 2), (3, 3)\}$
B. $\R = \{(1, 1), (2, 2), (3, 3), (1, 2)\}$
C. $\R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$
D. $\R = \{(1, 1), (2, 2), (1, 2), (2, 1)\}$
22. Một ngôn ngữ hình thức được định nghĩa là gì?
A. Một tập hợp hữu hạn các từ
B. Một tập hợp vô hạn các từ
C. Một tập hợp các chuỗi được xây dựng từ một bảng chữ cái
D. Một tập hợp các ký hiệu
23. Cho hàm $f(x) = x^2 + 1$ và $g(x) = 2x$. Tìm $(f \circ g)(x)$.
A. $2x^2 + 2$
B. $4x^2 + 1$
C. $2x^2 + 1$
D. $4x^2 + 2$
24. Số các hoán vị của $n$ phần tử là:
A. $n$
B. $2^n$
C. $n!$
D. $n^n$
25. Cho đồ thị vô hướng $G = (V, E)$ với $V = \{a, b, c, d\}$ và $E = \{\{a, b\}, \{b, c\}, \{c, d\}, \{d, a\}\}$. Đồ thị này có phải là đồ thị lưỡng phân không?
A. Không
B. Có
C. Không thể xác định
D. Có thể có hoặc không
26. Mệnh đề $p \rightarrow q$ tương đương với mệnh đề nào sau đây?
A. $q \rightarrow p$
B. $\neg p \lor q$
C. $p \land q$
D. $\neg q \rightarrow \neg p$
27. Cho $f(n) = 3f(n-1) + 2$, với $f(0) = 1$. Tìm $f(2)$.
28. Cho hàm sinh $G(x) = \frac{1}{1-x}$. Hệ số của $x^n$ trong $G(x)$ là:
29. Cho hàm $f: A \rightarrow B$. Hàm $f$ được gọi là đơn ánh (injective) nếu:
A. $\forall x_1, x_2 \in A, f(x_1) = f(x_2) \Rightarrow x_1 = x_2$
B. $\forall y \in B, \exists x \in A : f(x) = y$
C. $\forall x_1, x_2 \in A, x_1 = x_2 \Rightarrow f(x_1) = f(x_2)$
D. $\forall y \in B, \exists ! x \in A : f(x) = y$
30. Cho $A = \{a, b, c\}$. Tìm số quan hệ thứ tự bộ phận trên $A$ chứa quan hệ $R = \{(a, b), (b, c)\}$.
