Đề 3 – Đề thi, câu hỏi trắc nghiệm online Toán rời rạc

1. Cho đồ thị có ma trận kề là ma trận đơn vị. Đồ thị này có đặc điểm gì?

A. Đồ thị đầy đủ.

B. Đồ thị có khuyên tại mọi đỉnh.

C. Đồ thị không có cạnh.

D. Đồ thị liên thông.

2. Mệnh đề nào sau đây là hằng đúng?

A. $p \vee \neg p$

B. $p \wedge \neg p$

C. $p \rightarrow q$

D. $p \leftrightarrow q$

3. 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ị này có phải là đồ thị Euler không?

A. Không, vì có đỉnh bậc lẻ.

B. Có, vì mọi đỉnh đều có bậc chẵn.

C. Không thể xác định.

D. Có, vì đồ thị liên thông.

4. Trong một nhóm 10 người, mỗi người bắt tay với đúng 3 người khác. Hỏi có bao nhiêu cái bắt tay?

A. 15

B. 30

C. 10

D. 5

5. Số đỉnh của đồ thị đầy đủ $K_n$ là $n$. Hỏi số cạnh của $K_n$ là bao nhiêu?

A. $n$

B. $n-1$

C. $n(n-1)/2$

D. $n^2$

6. Phát biểu nào sau đây là đúng về đồ thị lưỡng phân (bipartite graph)?

A. Đồ thị có thể chia thành hai tập đỉnh không giao nhau sao cho mọi cạnh đều nối một đỉnh từ tập này với một đỉnh từ tập kia.

B. Đồ thị có thể chia thành hai tập đỉnh giao nhau sao cho mọi cạnh đều nối một đỉnh từ tập này với một đỉnh từ tập kia.

C. Đồ thị có chu trình độ dài lẻ.

D. Đồ thị có chu trình độ dài chẵn.

7. Phát biểu nào sau đây là đúng về quan hệ tương đương?

A. Quan hệ phản xạ, đối xứng, và bắc cầu.

B. Quan hệ phản xạ và đối xứng.

C. Quan hệ đối xứng và bắc cầu.

D. Quan hệ phản xạ và bắc cầu.

8. Công thức nào sau đây biểu diễn đúng quy tắc De Morgan cho hai tập hợp $A$ và $B$?

A. $(A \cap B)' = A' \cap B'$

B. $(A \cup B)' = A' \cup B'$

C. $(A \cap B)' = A' \cup B'$

D. $(A \cup B)' = A \cap B$

9. Cho hàm $f: A \rightarrow B$ và $g: B \rightarrow C$. Khi nào thì hàm hợp $g \circ f$ tồn tại?

A. Luôn luôn tồn tại.

B. Khi $A = C$.

C. Khi $f$ là đơn ánh.

D. Hàm hợp $g \circ f$ luôn tồn tại khi $f: A \rightarrow B$ và $g: B \rightarrow C$ được xác định.

10. Cho tập $A = \{1, 2, 3\}$. Tìm số lượng hoán vị của $A$.

A. 3

B. 6

C. 9

D. 27

11. Cho đồ thị G có 5 đỉnh. Biết bậc của các đỉnh lần lượt là 1, 2, 2, 3, 4. Hỏi đồ thị này có bao nhiêu cạnh?

A. 6

B. 12

C. 10

D. 5

12. Định nghĩa nào sau đây là đúng về đồ 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 mọi cạnh đều có độ dài bằng nhau.

C. Đồ thị có thể vẽ trên mặt phẳng sao cho mọi đỉnh đều có bậc bằng nhau.

D. Đồ thị có thể vẽ trên mặt phẳng sao cho tổng số đỉnh và cạnh bằng nhau.

13. Cho $A = \{1, 2, 3\}$. Tìm số lượng quan hệ thứ tự bộ phận trên $A$ chứa quan hệ $R = \{(1, 2), (2, 3)\}$.

A. 1

B. 2

C. 3

D. 5

14. Một đồ thị có 6 đỉnh và 8 cạnh. Hỏi tổng bậc của tất cả các đỉnh là bao nhiêu?

A. 6

B. 8

C. 14

D. 16

15. Trong đại số Boolean, biểu thức $A + A'$ bằng gì?

A. 0

B. A

C. 1

D. A'

16. Điều kiện cần và đủ để một đồ thị có chu trình Euler là gì?

A. Đồ thị liên thông và mọi đỉnh có bậc lẻ.

B. Đồ thị liên thông và mọi đỉnh có bậc chẵn.

C. Đồ thị có ít nhất một đỉnh bậc chẵn.

D. Đồ thị có ít nhất một đỉnh bậc lẻ.

17. Cho quan hệ $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ trên tập $A = \{1, 2, 3\}$. Quan hệ này có tính chất nào sau đây?

A. Phản xạ, đối xứng, bắc cầu.

B. Phản xạ và đối xứng.

C. Đối xứng và bắc cầu.

D. Phản xạ và bắc cầu.

18. Cho tập hợp $A = \{1, 2, 3, 4\}$. Hỏi có bao nhiêu tập con của $A$?

A. 4

B. 8

C. 16

D. 24

19. Phát biểu nào sau đây là đúng về cây (tree) trong lý thuyết đồ thị?

A. Cây là một đồ thị có chu trình.

B. Cây là một đồ thị liên thông không có chu trình.

C. Cây là một đồ thị không liên thông không có chu trình.

D. Cây là một đồ thị đầy đủ.

20. Cho hai mệnh đề $p$ và $q$. Biểu thức nào sau đây biểu diễn phép kéo theo (implication) $p \rightarrow q$?

A. $\neg p \vee q$

B. $p \wedge q$

C. $p \vee q$

D. $\neg p \wedge q$

21. Cho $A = \{a, b, c, d\}$. Tìm số lượng xâu có độ dài 3 trên $A$.

A. 4

B. 12

C. 64

D. 81

22. Cho $A = \{1, 2, 3, 4, 5\}$ và $B = \{a, b, c\}$. Hỏi có bao nhiêu hàm từ $A$ vào $B$?

A. 3

B. 5

C. 243

D. 125

23. Số cạnh tối thiểu trong một đồ thị liên thông có $n$ đỉnh là bao nhiêu?

A. $n$

B. $n-1$

C. $n(n-1)/2$

D. $n^2$

24. Cho hàm $f: \mathbb{Z} \rightarrow \mathbb{Z}$ xác định bởi $f(x) = 2x$. Hàm này có là đơn ánh không?

A. Có, vì với mọi $x_1 \neq x_2$ thì $f(x_1) \neq f(x_2)$.

B. Không, vì với mọi $x_1 \neq x_2$ thì $f(x_1) = f(x_2)$.

C. Có, vì $f$ là toàn ánh.

D. Không, vì $f$ không là toàn ánh.

25. Cho $f(x) = x^2$ và $g(x) = x + 1$. Tính $(f \circ g)(x)$.

A. $x^2 + 1$

B. $x^2 + 2x + 1$

C. $x^2 + x + 1$

D. $x^3 + x^2$

26. Cho tập hợp $A = \{1, 2, 3\}$. Hỏi có bao nhiêu quan hệ hai ngôi trên tập hợp $A$?

A. 9

B. 512

C. 8

D. 64

27. Cho tập hợp $A = \{1, 2, 3\}$ và $B = \{a, b\}$. Hỏi có bao nhiêu hàm toàn ánh từ $A$ vào $B$?

A. 0

B. 2

C. 6

D. 8

28. Đồ thị $K_5$ (đồ thị đầy đủ 5 đỉnh) có phải là đồ thị phẳng không?

A. Có.

B. Không.

C. Chỉ khi vẽ trên hình xuyến.

D. Không thể xác định.

29. Cho hàm băm $h(x) = x \mod 10$. Tìm $h(123)$.

A. 12

B. 3

C. 123

D. 0

30. Mệnh đề $p \rightarrow q$ tương đương với mệnh đề nào sau đây?

A. $q \rightarrow p$

B. $\neg p \vee q$

C. $\neg q \rightarrow \neg p$

D. $p \wedge q$