Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Toán Rời Rạc - Đề 05 bao gồm nhiều câu hỏi hay, bám sát chương trình. Cùng làm bài tập trắc nghiệm ngay.
Câu 1: Cho hai mệnh đề P: “Hôm nay trời mưa” và Q: “Tôi ở nhà”. Mệnh đề “Nếu hôm nay trời không mưa thì tôi không ở nhà” được biểu diễn bằng ký hiệu logic nào?
- A. P → Q
- B. ¬P → Q
- C. ¬P → ¬Q
- D. P → ¬Q
Câu 2: Xét mệnh đề kéo theo P → Q. Mệnh đề nào sau đây tương đương logic với P → Q?
- A. Q → P
- B. ¬Q → ¬P
- C. P ∧ ¬Q
- D. ¬P ∧ Q
Câu 3: Cho tập hợp A = {1, 2, 3, 4}. Quan hệ R trên A được định nghĩa là R = {(a, b) ∈ A x A | a ≤ b}. Quan hệ R có tính chất nào sau đây?
- A. Đối xứng
- B. Phản đối xứng và đối xứng
- C. Bắc cầu và phản đối xứng nhưng không phản xạ
- D. Phản xạ và bắc cầu
Câu 4: Hàm số f: Z → Z được cho bởi f(x) = 2x + 1. Hàm số này có phải là đơn ánh không?
- A. Đúng, vì với mọi x1 ≠ x2 thì f(x1) ≠ f(x2)
- B. Sai, vì tồn tại x1 ≠ x2 nhưng f(x1) = f(x2)
- C. Không xác định được
- D. Chỉ đơn ánh khi x ≥ 0
Câu 5: Cho đồ thị vô hướng G = (V, E) với V = {a, b, c, d} và E = {{a, b}, {b, c}, {c, d}, {d, a}, {a, c}}. Bậc của đỉnh b trong đồ thị G là bao nhiêu?
Câu 6: Có bao nhiêu xâu nhị phân độ dài 4 bắt đầu bằng "1" hoặc kết thúc bằng "00"?
Câu 7: Phát biểu nào sau đây là đúng về tập hợp các số nguyên tố?
- A. Là tập hợp hữu hạn và có số lượng phần tử là một số nguyên tố
- B. Là tập hợp hữu hạn và có số lượng phần tử là một số chẵn
- C. Là tập hợp vô hạn
- D. Là tập hợp hữu hạn và có số lượng phần tử là một số lẻ
Câu 8: Cho quan hệ R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)} trên tập A = {1, 2, 3}. Quan hệ R có tính chất nào?
- A. Chỉ có tính phản xạ
- B. Chỉ có tính đối xứng
- C. Chỉ có tính bắc cầu
- D. Phản xạ, đối xứng và bắc cầu
Câu 9: Số cạnh tối thiểu cần thêm vào đồ thị vô hướng 5 đỉnh để nó trở thành đồ thị liên thông là bao nhiêu, nếu ban đầu đồ thị không có cạnh nào?
Câu 10: Trong một lớp học có 30 sinh viên, có 15 sinh viên thích Toán, 12 sinh viên thích Lý, và 7 sinh viên thích cả Toán và Lý. Hỏi có bao nhiêu sinh viên không thích môn nào trong hai môn Toán và Lý?
Câu 11: Cho hàm băm h(k) = k mod 7. Giá trị băm của khóa k = 25 là bao nhiêu?
Câu 12: Định nghĩa nào sau đây mô tả đúng nhất về thuật toán?
- A. Một dãy hữu hạn các bước rõ ràng để giải quyết một vấn đề
- B. Một chương trình máy tính phức tạp
- C. Một công thức toán học
- D. Một phương pháp thử và sai
Câu 13: Biểu thức (p ∧ q) → r tương đương logic với biểu thức nào sau đây?
- A. p ∨ q ∨ r
- B. p ∧ q ∧ r
- C. ¬p ∨ ¬q ∨ r
- D. p ∧ ¬q → r
Câu 14: Cho tập A = {a, b, c}. Có bao nhiêu tập con của tập A?
Câu 15: Trong các cấu trúc dữ liệu sau, cấu trúc nào hoạt động theo nguyên tắc LIFO (Last In, First Out)?
- A. Queue (hàng đợi)
- B. Stack (ngăn xếp)
- C. Linked list (danh sách liên kết)
- D. Tree (cây)
Câu 16: Cho vị từ P(x): “x là số chẵn”. Xét miền xác định là tập hợp các số nguyên Z. Giá trị chân lý của ∀x P(x) là gì?
- A. Đúng
- B. Sai
- C. Không xác định
- D. Chỉ đúng khi x > 0
Câu 17: Phương pháp chứng minh nào thường được sử dụng để chứng minh một mệnh đề đúng cho tất cả các số tự nhiên?
- A. Chứng minh phản chứng
- B. Chứng minh trực tiếp
- C. Chứng minh quy nạp toán học
- D. Chứng minh bằng phản ví dụ
Câu 18: Cho tập hợp A = {1, 2, 3, 4, 5, 6} và B = {2, 4, 6, 8}. Tập hợp A Δ B (hiệu đối xứng) là tập nào?
- A. {2, 4, 6}
- B. {1, 3, 5}
- C. {1, 3, 5, 8}
- D. {1, 2, 3, 4, 5, 6, 8}
Câu 19: Một người có 3 áo, 2 quần và 2 đôi giày. Hỏi người đó có bao nhiêu cách chọn một bộ trang phục gồm một áo, một quần và một đôi giày?
Câu 20: Trong đại số Boolean, luật De Morgan thứ nhất phát biểu rằng (x + y)" = x" * y". Phát biểu nào sau đây là luật De Morgan thứ hai?
- A. x + x" = 1
- B. x * x" = 0
- C. x + 1 = 1
- D. (x * y)" = x" + y"
Câu 21: Tính chất nào sau đây không phải là tính chất của cây (tree)?
- A. Liên thông
- B. Không có chu trình
- C. Có chu trình Euler
- D. Số cạnh bằng số đỉnh trừ 1
Câu 22: Cho số nguyên n = 24. Phân tích n thành thừa số nguyên tố.
- A. 2 * 3 * 4
- B. 2^3 * 3
- C. 2 * 2 * 6
- D. 3 * 8
Câu 23: Tìm số nghiệm nguyên không âm của phương trình x + y + z = 5.
Câu 24: Cho quan hệ tương đương R trên tập A. Các lớp tương đương của R tạo thành một cấu trúc nào trên A?
- A. Tập con
- B. Tập hợp
- C. Quan hệ thứ tự
- D. Phân hoạch
Câu 25: 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. Tổng cộng có bao nhiêu trận đấu trong giải?
Câu 26: Cho hàm số f(n) = 3n^2 + 2n + 1. Độ phức tạp thời gian của hàm f(n) được biểu diễn bằng ký hiệu Big O nào?
- A. O(n)
- B. O(log n)
- C. O(n^2)
- D. O(2^n)
Câu 27: Phát biểu nào sau đây là đúng về đồ thị phẳng?
- A. Luôn luôn là đồ thị đầy đủ
- B. Có thể vẽ trên mặt phẳng mà không có cạnh nào cắt nhau
- C. Luôn luôn có chu trình Hamilton
- D. Không thể tô màu bằng 4 màu
Câu 28: Tìm số dư khi chia 3^100 cho 7.
Câu 29: Cho mạch logic với cổng AND, OR, NOT. Cổng logic nào sau đây có thể thay thế cho tất cả các cổng AND, OR, NOT?
- A. XOR
- B. AND
- C. OR
- D. NAND
Câu 30: Trong thuật toán sắp xếp trộn (Merge Sort), độ phức tạp thời gian trung bình và trường hợp xấu nhất là bao nhiêu?
- A. O(n^2)
- B. O(n log n)
- C. O(n)
- D. O(log n)
