1. Cho hàm Boole f(x, y) = x′y + xy′. Biểu thức nào sau đây tương đương với f(x, y)?
A. x ∧ y
B. x ∨ y
C. x XOR y
D. x XNOR y
2. Số Bell B(n) đếm cái gì?
A. Số hoán vị của n phần tử.
B. Số phân hoạch của tập hợp n phần tử.
C. Số tổ hợp chập k của n.
D. Số cây khung của đồ thị đầy đủ Kn.
3. Mệnh đề `∀x ∈ Z, x² ≥ 0′ có giá trị chân lý là:
A. Đúng
B. Sai
C. Vừa đúng vừa sai
D. Không xác định
4. Nếu một đồ thị vô hướng liên thông có n đỉnh và m cạnh là một cây, thì mối quan hệ giữa n và m là:
A. m = n
B. m = n - 1
C. m = n + 1
D. m = 2n
5. Cho hai tập hợp A = {1, 2, 3} và B = {3, 4, 5}. Phép hợp của hai tập hợp A ∪ B là:
A. {1, 2}
B. {4, 5}
C. {3}
D. {1, 2, 3, 4, 5}
6. Trong lý thuyết tập hợp, luật hấp thụ phát biểu rằng:
A. A ∪ (A ∩ B) = A và A ∩ (A ∪ B) = A
B. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
C. A ∪ (B ∪ C) = (A ∪ B) ∪ C
D. A ∪ B = B ∪ A
7. Trong hệ mã hóa RSA, khóa công khai được sử dụng để:
A. Giải mã thông điệp.
B. Mã hóa thông điệp.
C. Tạo chữ ký số.
D. Xác thực người dùng.
8. Một chu trình Hamilton trong đồ thị là gì?
A. Chu trình đi qua mọi cạnh của đồ thị đúng một lần.
B. Chu trình đi qua mọi đỉnh của đồ thị đúng một lần.
C. Chu trình ngắn nhất giữa hai đỉnh cho trước.
D. Chu trình dài nhất trong đồ thị.
9. Trong logic mệnh đề, phép toán nào sau đây tương ứng với liên từ `hoặc′ trong ngôn ngữ tự nhiên?
A. Phép hội (∧)
B. Phép tuyển (∨)
C. Phép kéo theo (→)
D. Phép tương đương (↔)
10. Số hoán vị của n phần tử khác nhau là:
11. Phương pháp chứng minh quy nạp thường được sử dụng để chứng minh mệnh đề nào sau đây?
A. Mệnh đề đúng cho một trường hợp cụ thể.
B. Mệnh đề đúng cho tất cả các số nguyên dương.
C. Mệnh đề sai cho tất cả các số nguyên dương.
D. Mệnh đề đúng cho một số hữu hạn các số nguyên dương.
12. Trong lý thuyết đồ thị, bậc của một đỉnh là:
A. Số cạnh kề với đỉnh đó.
B. Số đỉnh kề với đỉnh đó.
C. Tổng số đỉnh trong đồ thị.
D. Tổng số cạnh trong đồ thị.
13. Phủ định của mệnh đề `Mọi sinh viên đều thích Toán rời rạc′ là:
A. Mọi sinh viên đều không thích Toán rời rạc.
B. Có ít nhất một sinh viên không thích Toán rời rạc.
C. Không có sinh viên nào thích Toán rời rạc.
D. Một số sinh viên thích Toán rời rạc.
14. Cây là một loại đồ thị đặc biệt nào?
A. Đồ thị đầy đủ
B. Đồ thị có chu trình Euler
C. Đồ thị liên thông và không có chu trình
D. Đồ thị có chu trình Hamilton
15. Trong thuật toán Kruskal tìm cây khung nhỏ nhất (MST), các cạnh được xét theo thứ tự nào?
A. Theo thứ tự ngẫu nhiên.
B. Theo thứ tự trọng số tăng dần.
C. Theo thứ tự trọng số giảm dần.
D. Theo thứ tự đỉnh xuất hiện trong đồ thị.
16. 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 xạ
C. Phản đối xứng
D. Bắc cầu
17. Hàm số f: Z → Z được định nghĩa là f(x) = 2x + 1. Hàm số này có tính chất nào?
A. Toàn ánh
B. Đơn ánh
C. Song ánh
D. Không phải đơn ánh, toàn ánh, hay song ánh
18. Trong thuật toán Dijkstra tìm đường đi ngắn nhất, cấu trúc dữ liệu nào thường được sử dụng để quản lý tập hợp các đỉnh chưa được xét?
A. Hàng đợi (Queue)
B. Ngăn xếp (Stack)
C. Hàng đợi ưu tiên (Priority Queue)
D. Danh sách liên kết (Linked List)
19. Trong bài toán đếm, nguyên lý bù trừ (Principle of Inclusion-Exclusion) được sử dụng để:
A. Đếm số phần tử trong hợp của các tập hợp.
B. Đếm số phần tử trong giao của các tập hợp.
C. Đếm số phần tử trong hiệu của các tập hợp.
D. Đếm số phần tử trong tích Descartes của các tập hợp.
20. Trong lý thuyết đồ thị, một matching trong đồ thị là:
A. Tập hợp các đỉnh không kề nhau.
B. Tập hợp các cạnh không có đỉnh chung.
C. Tập hợp tất cả các cạnh của đồ thị.
D. Tập hợp tất cả các đỉnh của đồ thị.
21. Cho đồ thị có ma trận kề A. Phần tử A[i][j] của ma trận kề biểu thị điều gì?
A. Khoảng cách giữa đỉnh i và đỉnh j.
B. Số đường đi từ đỉnh i đến đỉnh j.
C. Có cạnh nối giữa đỉnh i và đỉnh j hay không.
D. Bậc của đỉnh i.
22. Biểu thức chính tắc tuyển (DNF - Disjunctive Normal Form) của một hàm Boole là:
A. Tổng của các tích các biến hoặc phủ định của chúng.
B. Tích của các tổng các biến hoặc phủ định của chúng.
C. Biểu thức chỉ chứa phép tuyển.
D. Biểu thức chỉ chứa phép hội.
23. Một đồ thị phẳng là đồ thị có thể được vẽ 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 điểm không phải là đỉnh.
C. Mỗi đỉnh có bậc không quá 3.
D. Số đỉnh bằng số cạnh.
24. Số Stirling loại hai S(n, k) đếm cái gì?
A. Số cách chia tập hợp n phần tử thành k tập hợp con không rỗng.
B. Số cách chọn k phần tử từ n phần tử có thứ tự.
C. Số cách sắp xếp n phần tử vào k hộp phân biệt.
D. Số cách phân hoạch số n thành k số hạng.
25. Số cách chọn k phần tử từ n phần tử khác nhau (không quan trọng thứ tự) là:
A. P(n, k) = n! ∕ (n-k)!
B. nᵏ
C. C(n, k) = n! ∕ (k! × (n-k)!)
D. k!
26. Hệ thức truy hồi nào sau đây mô tả dãy số Fibonacci?
A. F(n) = F(n-1) + F(n-2) với F(0) = 0, F(1) = 1
B. F(n) = 2F(n-1) + 1
C. F(n) = n × F(n-1)
D. F(n) = F(n-1) - F(n-2)
27. Trong số học đồng dư, a ≡ b (mod m) có nghĩa là:
A. a bằng b.
B. a chia hết cho b.
C. a và b có cùng số dư khi chia cho m.
D. a lớn hơn b.
28. Đồ thị vô hướng G = (V, E) được gọi là đồ thị Euler nếu:
A. Mọi đỉnh của đồ thị đều 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. Có nhiều hơn hai đỉnh có bậc lẻ.
29. Cho quan hệ R trên tập số nguyên Z được định nghĩa bởi aRb nếu a - b là số chẵn. Quan hệ R là quan hệ gì?
A. Quan hệ tương đương
B. Quan hệ thứ tự bộ phận
C. Quan hệ thứ tự toàn phần
D. Không phải quan hệ tương đương cũng không phải quan hệ thứ tự
30. Trong đại số Boole, luật De Morgan phát biểu rằng:
A. ¬(p ∧ q) ≡ (¬p ∨ ¬q) và ¬(p ∨ q) ≡ (¬p ∧ ¬q)
B. (p ∧ q) ≡ (q ∧ p) và (p ∨ q) ≡ (q ∨ p)
C. (p ∧ (q ∨ r)) ≡ ((p ∧ q) ∨ (p ∧ r))
D. (p ∨ (q ∧ r)) ≡ ((p ∨ q) ∧ (p ∨ r))
