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

1. Cho $A = \{1, 2, 3\}$ và $B = \{a, b\}$. Có bao nhiêu hàm từ $A$ đến $B$?

A. 6

B. 8

C. 9

D. 12

2. Cho $A$ và $B$ là hai tập hợp. Mệnh đề nào sau đây là đúng?

A. $A - B = B - A \Leftrightarrow A = B$

B. $A - B = B - A \Leftrightarrow A = \emptyset$

C. $A - B = B - A \Leftrightarrow B = \emptyset$

D. $A - B = B - A \Leftrightarrow A \cap B = \emptyset$

3. Trong đại số Boole, biểu thức nào sau đây tương đương với $x + xy$?

A. $x$

B. $y$

C. $x+y$

D. $xy$

4. Trong một giải đấu có 8 đội bóng, mỗi đội phải đấu với mỗi đội khác đúng một trận. Hỏi có bao nhiêu trận đấu diễn ra?

A. 8

B. 28

C. 56

D. 64

5. Định nghĩa nào sau đây là đúng về đồ thị phẳng?

A. Một đồ thị phẳng là đồ thị có thể vẽ trên mặt phẳng sao cho các cạnh không cắt nhau.

B. Một đồ thị phẳng là đồ thị có thể vẽ trên mặt phẳng sao cho các đỉnh không cắt nhau.

C. Một đồ thị phẳng là đồ thị có thể vẽ trên mặt phẳng mà không có đỉnh nào bị trùng nhau.

D. Một đồ thị phẳng là đồ thị có thể vẽ trên mặt phẳng mà không có cạnh nào bị trùng nhau.

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

A. $q \rightarrow p$

B. $\neg p \rightarrow \neg q$

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

D. $p \land \neg q$

7. Cho quan hệ $R = \{(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (1, 3)\}$ trên tập $A = \{1, 2, 3, 4\}$. Bao đóng bắc cầu của $R$ là gì?

A. $\R = \{(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (1, 3)\}$

B. $\R = \{(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (1, 3), (1,4), (2,4), (3,4)\}$

C. $\R = \{(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (1, 3), (1, 4)\}$

D. $\R = \{(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (1, 3), (1, 4), (2, 4) \}$

8. Hàm $f(n)$ được định nghĩa như sau: $f(0) = 0$, $f(1) = 1$, $f(n) = f(n-1) + f(n-2)$ với $n > 1$. Hàm này là hàm gì?

A. Hàm mũ

B. Hàm logarit

C. Dãy Fibonacci

D. Hàm giai thừa

9. Cho một đường đi Euler trong đồ thị $G$. Phát biểu nào sau đây là đúng?

A. Đường đi Euler là đường đi đi qua tất cả các đỉnh của đồ thị đúng một lần.

B. Đường đi Euler là đường đi đi qua tất cả các cạnh của đồ thị đúng một lần.

C. Đường đi Euler là đường đi đi qua tất cả các đỉnh của đồ thị ít nhất một lần.

D. Đường đi Euler là đường đi đi qua tất cả các cạnh của đồ thị ít nhất một lần.

10. Cho $A$ và $B$ là hai tập hợp. Biểu thức nào sau đây biểu diễn số phần tử của $A \cup B$?

A. $|A| + |B|$

B. $|A| + |B| - |A \cap B|$

C. $|A| - |B|$

D. $|A| \times |B|$

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

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

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

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

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

12. Số nghiệm nguyên không âm của phương trình $x_1 + x_2 + x_3 = 10$ là bao nhiêu?

A. 10

B. 36

C. 66

D. 132

13. Cho một đồ thị vô hướng liên thông có 6 đỉnh và 8 cạnh. Hỏi có bao nhiêu cạnh cần loại bỏ để đồ thị trở thành cây?

A. 0

B. 1

C. 2

D. 3

14. Cho một hàm băm $h(x) = x \mod 10$. Nếu ta băm các số 12, 22, 32, 42 vào một bảng băm, thì có bao nhiêu va chạm (collision)?

A. 0

B. 1

C. 3

D. 6

15. Cho tập hợp $A = \{a, b, c\}$. Hỏi có bao nhiêu quan hệ tương đương trên $A$?

A. 3

B. 5

C. 6

D. 8

16. Cho $A$ và $B$ là hai tập hợp. Mệnh đề nào sau đây tương đương với $A \subseteq B$?

A. $A \cap B = B$

B. $A \cup B = A$

C. $A \cap B = A$

D. $A \cup B = A \cap B$

17. Cho một lưới ô vuông kích thước $m \times n$. Có bao nhiêu hình chữ nhật có thể tạo thành từ lưới này?

A. $mn$

B. $(m+1)(n+1)$

C. $\frac{m(m+1)n(n+1)}{4}$

D. $\frac{mn(m+1)(n+1)}{4}$

18. Cho đồ thị vô hướng $G = (V, E)$. Điều kiện nào sau đây là cần và đủ để $G$ có một chu trình Euler?

A. Mọi đỉnh của $G$ có bậc chẵn.

B. $G$ liên thông và mọi đỉnh của $G$ có bậc chẵn.

C. Mọi đỉnh của $G$ có bậc lẻ.

D. $G$ có ít nhất một đỉnh bậc chẵn.

19. Cho một ngôn ngữ chính quy. Phát biểu nào sau đây là đúng về ngôn ngữ này?

A. Ngôn ngữ chính quy có thể được biểu diễn bằng một biểu thức chính quy.

B. Ngôn ngữ chính quy không thể được biểu diễn bằng một biểu thức chính quy.

C. Ngôn ngữ chính quy chỉ có thể được biểu diễn bằng máy trạng thái hữu hạn không đơn định.

D. Ngôn ngữ chính quy không thể được chấp nhận bởi máy trạng thái hữu hạn.

20. Số các số nguyên dương nhỏ hơn hoặc bằng 1000 và chia hết cho 3 hoặc 5 là bao nhiêu?

A. 200

B. 266

C. 333

D. 666

21. Cho một hoán vị của tập \{1, 2, ..., n\}. Số phép so sánh tối thiểu để sắp xếp hoán vị này bằng thuật toán sắp xếp so sánh là bao nhiêu?

A. $n-1$

B. $n \log n$

C. $n^2$

D. $n!$

22. Đồ thị đầy đủ $K_n$ có bao nhiêu cạnh?

A. $n$

B. $n-1$

C. $\frac{n(n-1)}{2}$

D. $n!$

23. Cho một đồ thị có ma trận kề là ma trận đơn vị. Đồ thị này có bao nhiêu cạnh?

A. 0

B. 1

C. $n$

D. $\frac{n(n-1)}{2}$

24. 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 tất cả?

A. 15

B. 20

C. 30

D. 45

25. Cho hàm $f: A \rightarrow B$ và $g: B \rightarrow C$. Phát biểu nào sau đây là đúng?

A. Nếu $f$ và $g$ đều đơn ánh thì $g \circ f$ là toàn ánh.

B. Nếu $f$ và $g$ đều toàn ánh thì $g \circ f$ là đơn ánh.

C. Nếu $f$ và $g$ đều đơn ánh thì $g \circ f$ là đơn ánh.

D. Nếu $g \circ f$ là đơn ánh thì $f$ là toàn ánh.

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

A. $n-1$

B. $n$

C. $n+1$

D. $\frac{n(n-1)}{2}$

27. Cho $f(n) = 2f(n-1) + 1$ với $f(0) = 1$. Giá trị của $f(3)$ là bao nhiêu?

A. 5

B. 7

C. 11

D. 15

28. Cho $A = \{1, 2, 3, 4, 5\}$. Có bao nhiêu tập con của $A$ chứa số 1?

A. 16

B. 20

C. 24

D. 32

29. Cho đồ thị có bậc của các đỉnh lần lượt là 1, 2, 3, 4, 5. Đồ thị này có bao nhiêu cạnh?

A. 5

B. 7.5

C. 10

D. 15

30. Cho tập hợp $A = \{1, 2, 3, 4, 5\}$. Có bao nhiêu quan hệ thứ tự bộ phận (partial order) trên $A$ chứa quan hệ '$=$'?

A. 1

B. 5

C. 25

D. 120