Đề thi, bài tập trắc nghiệm online Toán rời rạc – Đề 5

1. Hàm băm (hash function) thường được sử dụng trong toán rời rạc và khoa học máy tính với mục đích chính là gì?

A. Mã hóa dữ liệu để bảo mật.

B. Nén dữ liệu để giảm kích thước lưu trữ.

C. Ánh xạ dữ liệu có kích thước lớn sang dữ liệu có kích thước nhỏ hơn (thường cố định) để truy xuất nhanh.

D. Sắp xếp dữ liệu theo thứ tự tăng dần.

2. Trong số học đồng dư, a ≡ b (mod m) có nghĩa là gì?

A. a bằng b.

B. a chia hết cho b.

C. a và b có cùng số dư khi chia cho m.

D. m chia hết cho a - b.

3. Phương pháp chứng minh quy nạp thường được sử dụng để chứng minh điều gì trong toán học rời rạc?

A. Tính đúng đắn của một thuật toán cụ thể cho một trường hợp.

B. Tính đúng đắn của một mệnh đề đúng cho tất cả các số tự nhiên (hoặc một tập con vô hạn của số tự nhiên).

C. Tính sai của một mệnh đề cho tất cả các số thực.

D. Tính tương đương giữa hai tập hợp hữu hạn.

4. Trong số học tổ hợp, số Catalan thứ n, ký hiệu Cn, được sử dụng để đếm số lượng của nhiều đối tượng tổ hợp khác nhau. Công thức đệ quy cho số Catalan là gì?

A. C₀ = 1 và Cn = Σ(i=0 to n-1) Ci × C(n-i-1) cho n ≥ 1.

B. C₀ = 1 và Cn = 2 × C(n-1) cho n ≥ 1.

C. C₀ = 0 và Cn = C(n-1) + n cho n ≥ 1.

D. C₀ = 1 và Cn = C(n-1) + C(n-2) cho n ≥ 2.

5. Thuật toán Euclid thường được sử dụng để tìm giá trị nào giữa hai số nguyên?

A. Bội chung nhỏ nhất (LCM).

B. Ước chung lớn nhất (GCD).

C. Trung bình cộng.

D. Trung bình nhân.

6. Trong tổ hợp, chỉnh hợp chập k của n phần tử khác với tổ hợp chập k của n phần tử ở điểm nào?

A. Chỉnh hợp không quan tâm đến thứ tự, tổ hợp có quan tâm đến thứ tự.

B. Chỉnh hợp và tổ hợp đều quan tâm đến thứ tự.

C. Chỉnh hợp quan tâm đến thứ tự, tổ hợp không quan tâm đến thứ tự.

D. Chỉnh hợp và tổ hợp đều không quan tâm đến thứ tự.

7. Số cách chọn ra 3 học sinh từ một nhóm 5 học sinh để tham gia đội văn nghệ là bao nhiêu?

A. 60

B. 10

C. 15

D. 125

8. Trong đại số Boole, luật hấp thụ phát biểu rằng:

A. x + (x × y) = y

B. x + (x × y) = x

C. x × (x + y) = y

D. x × (x + y) = x′

9. Đồ thị đầy đủ Kn là đồ thị đơn vô hướng trong đó:

A. Mỗi đỉnh kề với đúng một đỉnh khác.

B. Không có cạnh nào.

C. Mỗi đỉnh kề với tất cả các đỉnh còn lại.

D. Chỉ có một chu trình Hamilton.

10. Một cây có n đỉnh thì có bao nhiêu cạnh?

A. n

B. n - 1

C. n + 1

D. 2n

11. Trong đại số Boole, luật De Morgan thứ nhất phát biểu rằng (x + y)′ = x′ × y′. Luật De Morgan thứ hai phát biểu như thế nào?

A. (x × y)′ = x′ + y′

B. (x × y)′ = x′ × y′

C. (x + y)′ = x′ + y′

D. (x′ + y′)′ = x × y

12. Trong lý thuyết automata, DFA (Deterministic Finite Automaton) khác với NFA (Non-deterministic Finite Automaton) ở điểm nào?

A. DFA có thể có nhiều trạng thái kết thúc, NFA chỉ có một.

B. Trong DFA, với mỗi trạng thái và mỗi ký tự đầu vào, luôn có duy nhất một trạng thái chuyển tiếp tiếp theo. Trong NFA, có thể có không hoặc nhiều trạng thái chuyển tiếp tiếp theo.

C. NFA luôn chấp nhận nhiều ngôn ngữ hơn DFA.

D. DFA dễ xây dựng hơn NFA.

13. Biểu thức nào sau đây tương đương với mệnh đề p → q (p kéo theo q)?

A. ¬p → ¬q

B. q → p

C. ¬p ∨ q

D. p ∧ ¬q

14. Trong ngôn ngữ hình thức, một từ (word) được định nghĩa là gì?

A. Một tập hợp các ký tự.

B. Một chuỗi hữu hạn các ký tự từ một bảng chữ cái (alphabet).

C. Một ký tự duy nhất.

D. Một câu có nghĩa trong ngôn ngữ tự nhiên.

15. Trong logic mệnh đề, phép toán nào sau đây tương ứng với liên từ 'và' trong ngôn ngữ tự nhiên?

A. Phép tuyển (OR)

B. Phép hội (AND)

C. Phép kéo theo (IMPLICATION)

D. Phép phủ định (NOT)

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

A. Quan hệ tương đương có tính phản xạ.

B. Quan hệ tương đương có tính đối xứng.

C. Quan hệ tương đương có tính phản đối xứng.

D. Quan hệ tương đương có tính bắc cầu.

17. Trong logic mệnh đề, phép tuyển loại trừ (XOR) của hai mệnh đề p và q đúng khi nào?

A. Khi cả p và q đều đúng.

B. Khi cả p và q đều sai.

C. Khi p đúng và q sai, hoặc p sai và q đúng.

D. Khi p đúng hoặc q đúng (hoặc cả hai).

18. Hệ đếm cơ số 16 còn được gọi là hệ đếm gì?

A. Hệ nhị phân.

B. Hệ thập phân.

C. Hệ bát phân.

D. Hệ thập lục phân (Hexadecimal).

19. Cho hàm mệnh đề P(x): 'x là số nguyên tố'. Miền xác định là tập hợp các số nguyên dương. Giá trị chân lý của ∀x P(x) là gì?

A. Đúng

B. Sai

C. Không xác định

D. Tùy thuộc vào x

20. Hàm số f: Z → Z được định nghĩa bởi f(x) = 2x + 1. Hàm số này có phải là song ánh không?

A. Có, vì nó vừa đơn ánh vừa toàn ánh.

B. Không, vì nó không đơn ánh.

C. Không, vì nó không toàn ánh.

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

21. Trong lý thuyết đồ thị, một đường đi Euler tồn tại trong đồ thị liên thông khi và chỉ khi điều kiện nào sau đây được thỏa mãn?

A. Tất cả các đỉnh có bậc chẵn.

B. Có đúng hai đỉnh có bậc lẻ.

C. Có không quá hai đỉnh có bậc lẻ.

D. Tất cả các đỉnh có bậc lẻ.

22. Trong lý thuyết đồ thị, đồ thị phẳng là đồ thị có thể được vẽ trên mặt phẳng sao cho:

A. Các cạnh không giao nhau tại bất kỳ điểm nào.

B. Các cạnh có thể giao nhau tại các đỉnh.

C. Các cạnh chỉ giao nhau tại các đỉnh của đồ thị.

D. Các cạnh có thể giao nhau tại bất kỳ điểm nào, kể cả không phải đỉnh.

23. Cho tập hợp A = {a, b, c}. Số quan hệ hai ngôi khác nhau có thể định nghĩa trên tập hợp A là bao nhiêu?

A. 6

B. 8

C. 512

D. 2⁹ = 512

24. Cho đồ thị vô hướng G = (V, E). Phát biểu nào sau đây là đúng về bậc của đỉnh trong đồ thị?

A. Tổng bậc của tất cả các đỉnh luôn là một số lẻ.

B. Tổng bậc của tất cả các đỉnh bằng số cạnh của đồ thị.

C. Tổng bậc của tất cả các đỉnh bằng hai lần số cạnh của đồ thị.

D. Tồn tại một đồ thị mà tất cả các đỉnh đều có bậc lẻ.

25. Một chu trình Hamilton trong đồ thị là gì?

A. Một đường đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.

B. Một chu trình đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần (trừ đỉnh đầu và cuối trùng nhau).

C. Một đường đi ngắn nhất giữa hai đỉnh cho trước.

D. Một chu trình chứa tất cả các cạnh và đỉnh của đồ thị.

26. Trong logic vị từ, lượng từ ∀ được gọi là gì?

A. Lượng từ tồn tại.

B. Lượng từ phổ quát.

C. Lượng từ duy nhất.

D. Lượng từ phủ định.

27. Trong lý thuyết đồ thị, khái niệm 'đường kính′ của đồ thị liên thông được định nghĩa như thế nào?

A. Số đỉnh lớn nhất trong đồ thị.

B. Số cạnh nhỏ nhất cần loại bỏ để đồ thị trở nên không liên thông.

C. Khoảng cách lớn nhất giữa bất kỳ cặp đỉnh nào trong đồ thị.

D. Độ dài của chu trình ngắn nhất trong đồ thị.

28. Cho quan hệ R trên tập hợp A = {1, 2, 3} được biểu diễn bởi ma trận quan hệ [[1, 0, 1], [0, 1, 0], [1, 0, 1]]. Quan hệ R có tính chất nào sau đây?

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

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

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

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

29. Tập hợp nào sau đây là tập hợp rỗng?

A. {0}

B. {{}}

C. {x | x là số tự nhiên nhỏ hơn 0}

D. {x | x là số nguyên tố chẵn lớn hơn 2}

30. Trong logic mệnh đề, quy tắc Modus Ponens có dạng như thế nào?

A. ((p → q) ∧ q) → p

B. ((p → q) ∧ ¬p) → ¬q

C. ((p → q) ∧ p) → q

D. ((p ∨ q) ∧ ¬p) → q