1. Định nghĩa nào sau đây mô tả đúng nhất về 'quan hệ tương đương'?
A. Quan hệ có tính phản xạ và đối xứng.
B. Quan hệ có tính phản xạ và bắc cầu.
C. Quan hệ có tính đối xứng và bắc cầu.
D. Quan hệ có tính phản xạ, đối xứng và bắc cầu.
2. Hàm số f: A → B là một đơn ánh (injective) khi nào?
A. Với mọi x, y ∈ A, nếu f(x) = f(y) thì x = y.
B. Với mọi y ∈ B, tồn tại ít nhất một x ∈ A sao cho f(x) = y.
C. Với mọi x ∈ A, tồn tại duy nhất một y ∈ B sao cho f(x) = y.
D. Với mọi x, y ∈ A, nếu x ≠ y thì f(x) ≠ f(y).
3. Một ngôn ngữ hình thức được định nghĩa là gì?
A. Một tập hợp các từ được xây dựng từ một bảng chữ cái hữu hạn theo một tập hợp các quy tắc.
B. Một ngôn ngữ tự nhiên như tiếng Anh hoặc tiếng Việt.
C. Một ngôn ngữ lập trình bậc cao như Python hoặc Java.
D. Một sơ đồ khối biểu diễn thuật toán.
4. Trong thuật toán Dijkstra, mục đích chính là tìm kiếm điều gì?
A. Chu trình Hamilton trong đồ thị.
B. Đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm.
C. Cây khung nhỏ nhất của đồ thị.
D. Thành phần liên thông mạnh của đồ thị.
5. Cho tập hợp A = {1, 2, 3} và B = {3, 4, 5}. Tập hợp giao của A và B (A ∩ B) là tập hợp nào?
A. {1, 2, 3, 4, 5}
B. {1, 2}
C. {4, 5}
D. {3}
6. Biểu thức (p ∨ q) ∧ (¬p ∨ q) tương đương với biểu thức nào?
7. Cho tập hợp A = {a, b, c}. Số tập con của tập A là bao nhiêu?
8. Trong một nhóm 10 người, có bao nhiêu cách chọn ra một tổ công tác gồm 3 người?
A. 10!
B. 10^3
C. A(10, 3)
D. C(10, 3)
9. Trong đại số Boolean, định luật De Morgan thứ nhất phát biểu rằng (A + B)' tương đương với biểu thức nào?
A. A' + B'
B. A' * B'
C. A * B
D. A + B
10. Đồ thị Euler là đồ thị liên thông có tính chất gì?
A. Mọi đỉnh đều có bậc chẵn.
B. Có đúng hai đỉnh bậc lẻ.
C. Có ít nhất một đỉnh bậc lẻ.
D. Mọi đỉnh đều có bậc lẻ.
11. Số dư của phép chia 17 cho 5 là bao nhiêu?
12. Trong hệ thập phân, số 1011 biểu diễn giá trị nào trong hệ thập phân?
A. Mười một
B. Mười
C. Ba
D. Bốn
13. Trong số học đồng dư, a ≡ b (mod m) có nghĩa là gì?
A. a bằng b.
B. a và b có cùng số dư khi chia cho m.
C. a chia hết cho b.
D. m chia hết cho (a - b).
14. 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ố hình học
B. Dãy số Fibonacci
C. Dãy số cấp số cộng
D. Dãy số lũy thừa
15. 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 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 của số tự nhiên).
C. Tính chất của một đồ thị cụ thể.
D. Sự tồn tại của một giải pháp cho một bài toán NP-khó.
16. Máy trạng thái hữu hạn (Finite Automaton) được sử dụng để làm gì?
A. Giải các bài toán tối ưu hóa.
B. Nhận dạng các mẫu trong chuỗi đầu vào.
C. Lưu trữ dữ liệu lớn.
D. Thực hiện các phép tính phức tạp.
17. Trong lý thuyết đồ thị, đồ thị phẳng là đồ thị có thể được vẽ như thế nào?
A. Trên một mặt phẳng sao cho không có hai cạnh nào cắt nhau (ngoài các đỉnh chung của chúng).
B. Trên một mặt cầu.
C. Trong không gian ba chiều.
D. Chỉ khi tất cả các đỉnh có bậc chẵn.
18. Biểu thức logic (p → q) ∧ (¬q) tương đương với biểu thức nào?
19. Số cạnh tối đa trong một đồ thị đơn vô hướng đầy đủ với n đỉnh là bao nhiêu?
A. n
B. n-1
C. n * (n-1) / 2
D. n^2
20. 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 (với mọi)
C. Phép kéo theo
D. Phép hội
21. Cây khung (spanning tree) của một đồ thị liên thông là gì?
A. Một chu trình Hamilton bao gồm tất cả các đỉnh của đồ thị.
B. Một đồ thị con liên thông, không chu trình và bao gồm tất cả các đỉnh của đồ thị ban đầu.
C. Một đường đi Euler đi qua tất cả các cạnh của đồ thị.
D. Một đồ thị con đầy đủ của đồ thị ban đầu.
22. Thuật toán Kruskal được sử dụng để tìm kiếm điều gì trong đồ thị?
A. Đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác.
B. Cây khung nhỏ nhất.
C. Chu trình Euler.
D. Chu trình Hamilton.
23. Nguyên lý Dirichlet (hay nguyên lý hộp nhốt chim bồ câu - Pigeonhole Principle) phát biểu điều gì?
A. Nếu có n con chim bồ câu và m > n lỗ, thì có ít nhất một lỗ chứa nhiều hơn một con chim.
B. Nếu có n con chim bồ câu và m < n lỗ, thì có ít nhất một lỗ chứa nhiều hơn một con chim.
C. Nếu có n con chim bồ câu và m = n lỗ, thì mỗi lỗ chứa đúng một con chim.
D. Số chim bồ câu luôn bằng số lỗ.
24. Trong ngôn ngữ hình thức, một từ (word) là gì?
A. Một ký tự đơn lẻ từ bảng chữ cái.
B. Một chuỗi hữu hạn các ký tự từ bảng chữ cái.
C. Một tập hợp các ký tự.
D. Một quy tắc ngữ pháp.
25. Cho quan hệ R = {(1, 1), (2, 2), (3, 3), (1, 2)} trên tập A = {1, 2, 3}. Quan hệ R có tính chất nào sau đây?
A. Đối xứng
B. Phản xạ và bắc cầu
C. Phản xạ và đối xứng
D. Bắc cầu và đối xứng
26. Trong logic mệnh đề, phép toán nào sau đây trả về giá trị 'đúng' khi và chỉ khi cả hai mệnh đề đầu vào đều 'đúng'?
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)
27. Trong logic mệnh đề, phép kéo theo (implication) p → q sai khi nào?
A. p đúng và q đúng.
B. p đúng và q sai.
C. p sai và q đúng.
D. p sai và q sai.
28. Trong lý thuyết đồ thị, bậc của một đỉnh là gì?
A. Số cạnh trong đồ thị.
B. Số đỉnh trong đồ thị.
C. Số cạnh liên thuộc với đỉnh đó.
D. Số đường đi ngắn nhất từ đỉnh đó đến tất cả các đỉnh khác.
29. Số hoán vị của n phần tử phân biệt được tính bằng công thức nào?
A. n!
B. 2^n
C. n^2
D. n * (n-1)
30. 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
B. Phản xạ
C. Phản đối xứng và đối xứng
D. Không phản xạ
