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

1. Quan hệ R trên tập hợp A được gọi là quan hệ phản xạ khi nào?

A. Với mọi a thuộc A, (a, a) thuộc R.

B. Với mọi a, b thuộc A, nếu (a, b) thuộc R thì (b, a) thuộc R.

C. Với mọi a, b, c thuộc A, nếu (a, b) thuộc R và (b, c) thuộc R thì (a, c) thuộc R.

D. Không tồn tại a thuộc A sao cho (a, a) thuộc R.

2. Trong tổ hợp, chỉnh hợp chập k của n phần tử (k ≤ n) là gì?

A. Số cách chọn k phần tử từ n phần tử mà không quan tâm đến thứ tự.

B. Số cách chọn k phần tử từ n phần tử có quan tâm đến thứ tự và có thể lặp lại.

C. Số cách chọn k phần tử từ n phần tử có quan tâm đến thứ tự và không lặp lại.

D. Số cách chia n phần tử thành k nhóm.

3. Cho tập hợp A = {1, 2, 3}. Tập lũy thừa (power set) của A, P(A), có bao nhiêu phần tử?

A. 3

B. 6

C. 8

D. 9

4. Mệnh đề `Nếu trời mưa thì đường ướt` tương đương logic với mệnh đề nào sau đây?

A. Nếu đường ướt thì trời mưa.

B. Nếu trời không mưa thì đường không ướt.

C. Nếu đường không ướt thì trời không mưa.

D. Trời mưa và đường ướt.

5. Trong lý thuyết đồ thị, đường đi Hamilton là gì?

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

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

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

D. Đường đi dài nhất trong đồ thị.

6. Phát biểu nào sau đây là SAI về phép toán XOR (phép tuyển loại trừ) trong logic?

A. p XOR q đúng khi p đúng hoặc q đúng, nhưng không phải cả hai cùng đúng.

B. p XOR q đúng khi p và q có giá trị chân lý khác nhau.

C. p XOR p luôn luôn đúng.

D. p XOR q tương đương với (p ∨ q) ∧ ¬(p ∧ q).

7. Trong lý thuyết tập hợp, phép toán nào trả về tập hợp chứa tất cả các phần tử thuộc cả hai tập hợp đầu vào?

A. Hợp (Union)

B. Giao (Intersection)

C. Hiệu (Difference)

D. Bù (Complement)

8. Trong số học đồng dư, phần tử nghịch đảo modulo a của số b tồn tại khi nào?

A. gcd(a, b) = 0

B. gcd(a, b) = 1

C. gcd(a, b) > 1

D. a < b

9. Trong lý thuyết automata, ngôn ngữ chính quy (regular language) là gì?

A. Ngôn ngữ được nhận dạng bởi máy Turing.

B. Ngôn ngữ được nhận dạng bởi automata hữu hạn (finite automaton).

C. Ngôn ngữ được nhận dạng bởi automata đẩy xuống (pushdown automaton).

D. Ngôn ngữ được tạo ra bởi ngữ pháp phi ngữ cảnh (context-free grammar).

10. Trong lý thuyết đồ thị, đồ thị hai phía (bipartite graph) là đồ thị mà tập đỉnh của nó có thể chia thành hai tập rời nhau sao cho...

A. Mỗi cạnh nối hai đỉnh trong cùng một tập.

B. Mỗi cạnh nối hai đỉnh thuộc hai tập khác nhau.

C. Tất cả các đỉnh trong một tập có bậc bằng nhau.

D. Số đỉnh trong hai tập bằng nhau.

11. Số hoán vị của n phần tử là bao nhiêu?

A. n

B. 2^n

C. n!

D. n^n

12. Điều kiện cần và đủ để đồ thị vô hướng liên thông có chu trình Euler là gì?

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

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

C. Có ít nhất một đỉnh có bậc lẻ.

D. Không có đỉnh nào có bậc lẻ.

13. Trong số học modulo, 7 đồng dư với số nào modulo 3?

A. 1

B. 2

C. 0

D. 3

14. Thuật toán Euclid được sử dụng để tìm gì?

A. Ước chung nhỏ nhất (UCLN) của hai số nguyên.

B. Bội chung lớn nhất (BCNN) của hai số nguyên.

C. Phân tích thừa số nguyên tố của một số nguyên.

D. Nghiệm của phương trình đồng dư tuyến tính.

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

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)

16. Biểu thức logic nào sau đây tương đương với ¬(p ∧ q) ?

A. ¬p ∧ ¬q

B. ¬p ∨ ¬q

C. p ∨ q

D. p ∧ ¬q

17. Trong một đồ thị đầy đủ Kn (n đỉnh), số cạnh là bao nhiêu?

A. n

B. n-1

C. n(n-1)/2

D. n^2

18. Chọn phát biểu SAI về cây (tree) trong lý thuyết đồ thị.

A. Cây là đồ thị vô hướng, liên thông và không có chu trình.

B. Giữa hai đỉnh bất kỳ của cây luôn có duy nhất một đường đi.

C. Số cạnh của cây luôn bằng số đỉnh trừ 1.

D. Cây có thể chứa chu trình.

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

A. Tất cả các cạnh đều có độ dài bằng nhau.

B. Không có hai cạnh nào cắt nhau tại một điểm không phải là đỉnh.

C. Tất cả các đỉnh đều nằm trên cùng một đường thẳng.

D. Số đỉnh bằng số cạnh.

20. Chọn khẳng định đúng về quan hệ tương đương.

A. Quan hệ tương đương là quan hệ vừa phản xạ, vừa đối xứng, vừa phản đối xứng.

B. Quan hệ tương đương là quan hệ vừa phản xạ, vừa đối xứng, vừa bắc cầu.

C. Quan hệ tương đương là quan hệ vừa phản xạ, vừa phản đối xứng, vừa bắc cầu.

D. Quan hệ tương đương là quan hệ vừa đối xứng, vừa phản đối xứng, vừa bắc cầu.

21. Số tổ hợp chập k của n phần tử, C(n, k), được tính bằng công thức nào?

A. n! / (k! * (n-k)!)

B. n! / k!

C. n! / (n-k)!

D. k! / (n! * (n-k)!)

22. Đại số Boolean là một cấu trúc đại số được sử dụng chủ yếu trong lĩnh vực nào?

A. Thống kê và xác suất.

B. Hình học giải tích.

C. Điện tử số và thiết kế mạch logic.

D. Giải tích số.

23. Trong lý thuyết đồ thị, bậc của một đỉnh là gì?

A. Số cạnh kề với đỉnh đó.

B. Số đỉnh kề với đỉnh đó.

C. Tổng số đỉnh và cạnh trong đồ thị.

D. Số đỉnh trong đồ thị.

24. Trong lý thuyết automata, DFA là viết tắt của cụm từ nào?

A. Deterministic Finite Automaton

B. Dynamic Finite Automaton

C. Digital Function Automaton

D. Data Flow Automaton

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

A. Đối xứng

B. Phản đối xứng

C. Bắc cầu

D. Phản xạ

26. Cho hàm số f: Z -> Z xác định bởi f(x) = 2x + 1. Hàm số này là loại hàm số nào?

A. Song ánh (Bijective)

B. Toàn ánh (Surjective) nhưng không đơn ánh (Injective)

C. Đơn ánh (Injective) nhưng không toàn ánh (Surjective)

D. Không đơn ánh và không toàn ánh

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

A. Tính đúng đắn của một thuật toán cụ thể.

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 đúng đắn của một mệnh đề chỉ đúng cho một số hữu hạn trường hợp.

D. Tính đúng đắn của một mệnh đề cho tất cả các số thực.

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

A. Tồn tại (Existential)

B. Phổ quát (Universal)

C. Định danh (Identity)

D. Hàm ý (Implication)

29. Cho hàm đệ quy sau: F(n) = F(n-1) + F(n-2) với F(0) = 0, F(1) = 1. Đây là dãy số nào?

A. Dãy số Fibonacci

B. Dãy số Lucas

C. Dãy số hình vuông

D. Dãy số tam giác

30. Mệnh đề nào sau đây là hằng đúng (tautology)?

A. p ∨ ¬p

B. p ∧ ¬p

C. p → q

D. p ↔ q