Bài Tập, Đề Thi Trắc Nghiệm Online - Môn Toán Rời Rạc - Đề 01 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: Biểu thức logic nào sau đây tương đương với (p → q) ∧ (¬q)?
- A. ¬p ∧ ¬q
- B. p ∧ ¬q
- C. ¬p ∨ ¬q
- D. p ∨ q
Câu 2: Cho tập hợp A = {1, 2, 3, 4} và B = {a, b, c}. Hỏi có bao nhiêu hàm số khác nhau từ A đến B?
Câu 3: Quan hệ R trên tập hợp số nguyên Z được định nghĩa là aRb nếu a ≤ b. Quan hệ R có tính chất nào sau đây?
- A. Đối xứng và bắc cầu
- B. Phản xạ, phản đối xứng và bắc cầu
- C. Đối xứng, phản xạ và bắc cầu
- D. Phản xạ và đối xứng
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à bao nhiêu?
Câu 5: Có bao nhiêu xâu nhị phân độ dài 8 chứa đúng 3 số 1?
Câu 6: Thuật toán Euclid được sử dụng để tìm gì?
- A. Bội số chung nhỏ nhất
- B. Ước số chung lớn nhất
- C. Số nguyên tố
- D. Phân tích thừa số nguyên tố
Câu 7: Cho hàm số f(n) = 3n^2 + 2n + 1. Độ phức tạp thời gian của hàm f(n) thuộc lớp ký hiệu Big-O nào?
- A. O(n)
- B. O(log n)
- C. O(n^2)
- D. O(n^3)
Câu 8: Phát biểu nào sau đây là đúng về cây (tree) trong lý thuyết đồ thị?
- A. Là đồ thị liên thông và không có chu trình
- B. Là đồ thị có chu trình Euler
- C. Là đồ thị có chu trình Hamilton
- D. Là đồ thị đầy đủ
Câu 9: Sử dụng quy tắc nhân, có bao nhiêu cách chọn một mật khẩu gồm 6 ký tự, trong đó ký tự đầu tiên phải là chữ cái (26 lựa chọn), và 5 ký tự còn lại có thể là chữ cái hoặc chữ số (36 lựa chọn)?
- A. 26 * 36
- B. 36^6
- C. 26 + 36^5
- D. 26 * 36^5
Câu 10: Cho quan hệ R = {(1, 1), (1, 2), (2, 3), (3, 3)} trên tập A = {1, 2, 3}. Để R trở thành quan hệ bắc cầu, cần thêm vào cặp phần tử nào?
- A. (2, 1)
- B. (1, 3)
- C. (2, 2)
- D. (3, 1)
Câu 11: Trong logic vị từ, biểu thức ∀x∃yP(x, y) có nghĩa là gì?
- A. Tồn tại một x và một y sao cho P(x, y) đúng.
- B. Với mọi x và y, P(x, y) đúng.
- C. Với mọi x, tồn tại ít nhất một y sao cho P(x, y) đúng.
- D. Tồn tại ít nhất một x sao cho với mọi y, P(x, y) đúng.
Câu 12: Cho tập hợp A = {1, 2, 3}. Xét quan hệ "chia hết" trên A. Biểu diễn quan hệ này dưới dạng tập hợp các cặp có thứ tự.
- A. {(1, 1), (2, 2), (3, 3)}
- B. {(1, 1), (1, 2), (1, 3), (2, 2), (3, 3)}
- C. {(2, 1), (3, 1), (2, 2), (3, 3)}
- D. {(1, 1), (2, 1), (3, 1)}
Câu 13: Định lý Euler phát biểu rằng nếu gcd(a, n) = 1 thì a^φ(n) ≡ 1 (mod n), trong đó φ(n) là hàm Euler phi. Tính φ(10).
Câu 14: Cho mạch logic với cổng AND và OR. Biểu thức logic tương ứng với mạch (A AND B) OR (¬A AND C) là:
- A. (A ∨ B) ∧ (¬A ∨ C)
- B. (A ∧ B) ∧ (¬A ∧ C)
- C. (A ∧ B) ∨ (¬A ∧ C)
- D. (A ∨ C) ∧ (¬B ∨ A)
Câu 15: Trong một mạng xã hội, mỗi người là một đỉnh và một cạnh nối giữa hai đỉnh nếu hai người là bạn bè. Nếu mạng xã hội này được mô hình hóa bằng một đồ thị vô hướng đơn giản, phát biểu nào sau đây là đúng nếu đồ thị đó liên thông?
- A. Có một đường đi giữa bất kỳ hai người nào trong mạng xã hội.
- B. Mọi người trong mạng xã hội đều là bạn trực tiếp của nhau.
- C. Số bạn bè trung bình của mỗi người là như nhau.
- D. Không có người nào trong mạng xã hội không có bạn.
Câu 16: Cho phép đếm như sau: 1, 10, 100, 1000,... Đây là phép đếm cơ số mấy?
- A. Cơ số 2
- B. Cơ số 8
- C. Cơ số 10
- D. Cơ số 16
Câu 17: Cho tập hợp A = {a, b, c, d}. Hỏi có bao nhiêu tập con khác rỗng của A?
Câu 18: Định nghĩa nào sau đây mô tả đúng nhất về quan hệ tương đương?
- A. Quan hệ phản xạ và đối xứng
- B. Quan hệ phản xạ và bắc cầu
- C. Quan hệ đối xứng và bắc cầu
- D. Quan hệ phản xạ, đối xứng và bắc cầu
Câu 19: Cho đồ thị phẳng G. Nếu G có 10 đỉnh và 15 cạnh, hỏi G có bao nhiêu miền (faces)? (Sử dụng công thức Euler cho đồ thị phẳng liên thông: v - e + f = 2, với v là số đỉnh, e là số cạnh, f là số miền).
Câu 20: Phương pháp chứng minh quy nạp 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
- B. Một mệnh đề đúng cho mọi số tự nhiên
- C. Tính vô hạn của một tập hợp
- D. Sự tồn tại của một đối tượng toán học
Câu 21: 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 22: Cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông có trọng số là gì?
- A. Cây khung có tổng trọng số các cạnh nhỏ nhất.
- B. Cây khung chứa tất cả các đỉnh của đồ thị và có chu trình.
- C. Đường đi ngắn nhất giữa hai đỉnh bất kỳ trong đồ thị.
- D. Đồ thị con liên thông chứa tất cả các đỉnh và cạnh của đồ thị ban đầu.
Câu 23: Trong đại số Boole, luật De Morgan thứ nhất phát biểu rằng ¬(x ∧ y) tương đương với biểu thức nào?
- A. (¬x ∧ ¬y)
- B. (¬x ∨ ¬y)
- C. (x ∨ y)
- D. (x ∧ y)
Câu 24: Cho tập hợp các đỉnh V = {A, B, C, D} và tập cạnh E = {(A, B), (B, C), (C, D), (D, A), (A, C)}. Đồ thị G = (V, E) có phải là đồ thị phẳng không?
- A. Có
- B. Không
- C. Không xác định
- D. Chỉ phẳng khi vẽ trên mặt cầu
Câu 25: Trong bài toán tô màu đồ thị, số màu sắc tối thiểu cần thiết để tô màu các đỉnh của đồ thị sao cho không có hai đỉnh kề nhau nào cùng màu được gọi là gì?
- A. Bậc của đồ thị
- B. Kích thước đồ thị
- C. Số sắc ký
- D. Đường kính đồ thị
Câu 26: Cho số nguyên dương n. Độ phức tạp thời gian tốt nhất để tìm kiếm một phần tử trong một mảng đã sắp xếp có độ dài n là bao nhiêu?
- A. O(n)
- B. O(log n)
- C. O(n log n)
- D. O(n^2)
Câu 27: Hàm số f(x) = x^2 từ tập số thực R đến tập số thực R có phải là hàm đơn ánh (injective) không?
- A. Có
- B. Không
- C. Chỉ đơn ánh trên tập số thực dương
- D. Chỉ đơn ánh trên tập số tự nhiên
Câu 28: Cho quan hệ R trên tập số nguyên Z được định nghĩa là aRb nếu a ≡ b (mod 3). Đây là quan hệ gì?
- A. Quan hệ thứ tự
- B. Quan hệ phản xạ
- C. Quan hệ đối xứng
- D. Quan hệ tương đương
Câu 29: Trong lý thuyết đồ thị, đường đi Euler là gì?
- A. Đường đi ngắn nhất giữa hai đỉnh
- B. Đường đi thăm tất cả các đỉnh đúng một lần
- C. Đường đi thăm tất cả các cạnh đúng một lần
- D. Đường đi tạo thành một chu trình kín
Câu 30: Cho tập hợp A = {1, 2, 3, 4, 5}. Có bao nhiêu chỉnh hợp chập 2 của A?
