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

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

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

1 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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?

C. 2

D. 3

A. 0

B. 1

14 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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 / 30

Category: Toán rời rạc

Tags: Bộ đề 9

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

Đề trắc nghiệm liên quan: