Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Toán Rời Rạc - Đề 03 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: Trong một lớp học có 35 học sinh, có 20 học sinh thích chơi bóng đá, 15 học sinh thích chơi bóng rổ và 5 học sinh không thích chơi cả hai môn thể thao này. Hỏi có bao nhiêu học sinh thích chơi cả bóng đá và bóng rổ?
Câu 2: Cho mệnh đề P: “Nếu trời mưa thì đường ướt”. Mệnh đề nào sau đây là mệnh đề đảo của P?
- A. Nếu trời không mưa thì đường không ướt.
- B. Nếu đường không ướt thì trời không mưa.
- C. Nếu đường ướt thì trời mưa.
- D. Trời mưa và đường ướt.
Câu 3: Một người cần chọn mật khẩu gồm 8 ký tự, bắt đầu bằng một chữ cái (26 lựa chọn) và kết thúc bằng một chữ số (10 lựa chọn). Các ký tự còn lại có thể là chữ cái hoặc chữ số. Hỏi có bao nhiêu mật khẩu khác nhau có thể được tạo ra?
- A. 26 * 10 * 36^6
- B. 26 * 10 * 6^36
- C. 36^8
- D. 26 * 36^6 * 10
Câu 4: Cho đồ thị vô hướng G = (V, E) với V = {1, 2, 3, 4, 5, 6} và E = {(1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6)}. Bậc của đỉnh 2 trong đồ thị G là:
Câu 5: Hàm số f: Z → Z được định nghĩa bởi f(x) = 3x - 5. Hàm số này có phải là song ánh không? Giải thích.
- 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.
Câu 6: Quan hệ R trên tập hợp A = {1, 2, 3} được cho bởi R = {(1, 1), (1, 2), (2, 2), (3, 3)}. Quan hệ R có tính chất nào sau đây?
- A. Phản xạ và bắc cầu.
- B. Đối xứng và bắc cầu.
- C. Phản xạ và đối xứng.
- D. Phản đối xứng và bắc cầu.
Câu 7: Cho dãy số được định nghĩa đệ quy: a_0 = 2, a_n = 2a_{n-1} + 1 với n ≥ 1. Tìm giá trị của a_3.
Câu 8: Trong hệ thập lục phân, số (2A)_16 tương đương với số nào trong hệ thập phân?
Câu 9: Phát biểu nào sau đây là đúng về cây (tree) trong lý thuyết đồ thị?
- A. Cây là đồ thị liên thông có chu trình đơn.
- B. Cây là đồ thị liên thông không có chu trình đơn.
- C. Cây là đồ thị không liên thông không có chu trình đơn.
- D. Cây là đồ thị không liên thông có chu trình đơn.
Câu 10: Cho tập hợp A = {a, b, c, d}. Số quan hệ tương đương có thể xác định trên tập A là bao nhiêu?
Câu 11: Xét phép toán * trên tập số nguyên Z định nghĩa bởi a * b = a + b - 2ab. Hỏi phép toán * có tính kết hợp không?
- A. Có, vì (a * b) * c = a * (b * c) luôn đúng.
- B. Không, vì (a * b) * c ≠ a * (b * c) trong một số trường hợp.
- C. Chỉ kết hợp khi a = b = c.
- D. Không thể xác định.
Câu 12: Biểu thức logic (p ∧ q) → (p ∨ r) tương đương với biểu thức nào sau đây?
- A. p ∨ q ∨ r
- B. ¬p ∧ ¬q ∧ r
- C. ¬(p ∧ q) ∨ (p ∨ r)
- D. (p ∧ q) ∧ (p ∨ r)
Câu 13: Có bao nhiêu xâu nhị phân độ dài 5 không chứa hai chữ số 0 liên tiếp?
Câu 14: Cho quan hệ R = {(a, b) | a chia hết cho b} trên tập số nguyên dương Z+. Quan hệ R có phải là quan hệ thứ tự bộ phận không?
- A. Có, vì nó phản xạ, phản đối xứng và bắc cầu.
- B. Không, vì nó không phản xạ.
- C. Không, vì nó không phản đối xứng.
- D. Không, vì nó không bắc cầu.
Câu 15: Thuật toán Dijkstra được sử dụng để giải quyết bài toán nào trong lý thuyết đồ thị?
- A. Tìm chu trình Euler.
- B. Tìm cây bao trùm nhỏ nhất.
- C. Tìm luồng cực đại trong mạng.
- D. Tìm đường đi ngắn nhất giữa hai đỉnh.
Câu 16: Số nghiệm nguyên không âm của phương trình x_1 + x_2 + x_3 + x_4 = 10 là bao nhiêu?
- A. 286
- B. 286
- C. 120
- D. 715
Câu 17: Trong đại số Boole, biểu thức (x + y) * (x" * y")" được rút gọn thành biểu thức nào?
- A. x * y
- B. x" + y"
- C. x + y
- D. x" * y"
Câu 18: Cho đồ thị phẳng liên thông có 10 đỉnh và 15 cạnh. Hỏi đồ thị này có bao nhiêu miền?
Câu 19: Cho tập hợp A = {1, 2, 3, 4, 5, 6}. Hỏi có bao nhiêu tập con của A chứa cả 1 và 6?
Câu 20: Trong logic vị từ, mệnh đề ∀x(P(x) → Q(x)) ∧ ∃xP(x) kéo theo mệnh đề nào sau đây?
- A. ∀xQ(x)
- B. ¬∃xQ(x)
- C. ∃xQ(x)
- D. ∀x¬Q(x)
Câu 21: Cho quan hệ R trên tập số tự nhiên N định nghĩa bởi (a, b) ∈ R nếu a ≡ b (mod 3). Quan hệ R là quan hệ gì?
- A. Quan hệ tương đương.
- B. Quan hệ thứ tự bộ phận.
- C. Quan hệ phản xạ nhưng không đối xứng.
- D. Quan hệ đối xứng nhưng không bắc cầu.
Câu 22: Một hội đồng gồm 7 người được chọn từ 5 phụ nữ và 6 đàn ông. Hỏi có bao nhiêu cách chọn nếu hội đồng phải có ít nhất 3 phụ nữ?
- A. 450
- B. 500
- C. 520
- D. 550
Câu 23: Tìm hạng tử tổng quát của dãy Fibonacci được định nghĩa bởi F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} với n ≥ 2.
- A. F_n = (φ^n - ψ^n) / √3
- B. F_n = (φ^n - ψ^n) / √5
- C. F_n = (φ^n + ψ^n) / √5
- D. F_n = (φ^n + ψ^n) / √3
Câu 24: Cho đồ thị có trọng số như hình bên (mô tả hình ảnh đồ thị). Sử dụng thuật toán Kruskal để tìm cây bao trùm nhỏ nhất. Tổng trọng số của cây bao trùm nhỏ nhất là bao nhiêu?
Câu 25: Hệ thức đệ quy T(n) = 2T(n/2) + n với T(1) = 1 có độ phức tạp thời gian là bao nhiêu theo ký hiệu Big O?
- A. O(n)
- B. O(n log n)
- C. O(n^2)
- D. O(2^n)
Câu 26: Cho ngôn ngữ chính quy L được biểu diễn bởi biểu thức chính quy (a|b)*ab. Máy trạng thái hữu hạn không đơn định (NFA) nào sau đây chấp nhận ngôn ngữ L?
- A. (Hình ảnh NFA 1)
- B. (Hình ảnh NFA 2)
- C. (Hình ảnh NFA 3)
- D. (Hình ảnh NFA 4)
Câu 27: Cho nhóm (G, *) với phép toán * có tính kết hợp và phần tử đơn vị e. Phát biểu nào sau đây là đúng về phần tử nghịch đảo?
- A. Mỗi phần tử có thể có nhiều phần tử nghịch đảo.
- B. Chỉ có phần tử đơn vị mới có phần tử nghịch đảo.
- C. Mỗi phần tử có duy nhất một phần tử nghịch đảo.
- D. Không phải phần tử nào cũng có phần tử nghịch đảo.
Câu 28: Xét hàm băm h(k) = k mod 7. Xung đột băm sẽ xảy ra khi nào?
- A. Khi k là số nguyên tố.
- B. Khi hai khóa khác nhau cho cùng một giá trị băm.
- C. Khi k chia hết cho 7.
- D. Khi k là số chẵn.
Câu 29: Cho mạch logic biểu diễn bởi biểu thức (x ∧ y) ∨ (¬x ∧ z). Hãy vẽ bảng chân trị cho mạch logic này.
- A. (Bảng chân trị 1)
- B. (Bảng chân trị 2)
- C. (Bảng chân trị 3)
- D. (Bảng chân trị 4)
Câu 30: Trong mô hình quan hệ cơ sở dữ liệu, phép toán nào sau đây được sử dụng để chọn các bộ thỏa mãn một điều kiện nhất định?
- A. Phép chiếu (projection)
- B. Phép kết (join)
- C. Phép chọn (selection)
- D. Phép hợp (union)
