1. Đồ thị phẳng là đồ thị có tính chất gì?
A. Có thể vẽ trên mặt phẳng sao cho không có cạnh nào cắt nhau (ngoại trừ tại các đỉnh).
B. Tất cả các đỉnh đều có bậc bằng nhau.
C. Có thể biểu diễn bằng một ma trận vuông.
D. Có chu trình Euler.
2. Trong combinatorics, hệ số nhị thức (binomial coefficient) C(n, k) (hay nCk) đếm cái gì?
A. Số hoán vị của k phần tử chọn từ n phần tử.
B. Số tập con có k phần tử có thể chọn từ một tập hợp có n phần tử.
C. Số đường đi từ điểm (0, 0) đến điểm (n, k) trên lưới nguyên.
D. Số cách chia n phần tử thành k nhóm.
3. Hàm số f: A → B được gọi là đơ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 x, y ∈ A, nếu x = y thì f(x) = f(y).
C. Với mọi y ∈ B, tồn tại ít nhất một x ∈ A sao cho f(x) = y.
D. Với mọi y ∈ B, tồn tại duy nhất một x ∈ A sao cho f(x) = y.
4. Cho tập hợp A = {1, 2, 3}. Số quan hệ hai ngôi khác nhau có thể định nghĩa trên tập hợp A là bao nhiêu?
5. Cây khung (spanning tree) của một đồ thị liên thông G là gì?
A. Một đồ thị con của G chứa tất cả các đỉnh của G và là một chu trình.
B. Một đồ thị con của G chứa tất cả các đỉnh của G và là một cây.
C. Một đồ thị con của G là một cây, nhưng không nhất thiết chứa tất cả các đỉnh của G.
D. Một đồ thị con của G là một chu trình, nhưng không nhất thiết chứa tất cả các đỉnh của G.
6. Hệ đếm cơ số 16 còn được gọi là hệ đếm nào?
A. Hệ nhị phân
B. Hệ thập phân
C. Hệ bát phân
D. Hệ thập lục phân
7. Trong đồ thị vô hướng, bậc của một đỉnh được định nghĩa là gì?
A. Số cạnh liên thuộc với đỉnh đó.
B. Số đỉnh kề với đỉnh đó.
C. Tổng trọng số của các 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.
8. Phương pháp phản chứng (proof by contradiction) dựa trên nguyên tắc logic nào?
A. Luật tam đoạn luận.
B. Luật loại trừ giữa.
C. Luật De Morgan.
D. Luật hấp thụ.
9. Trong logic mệnh đề, quy tắc Modus Ponens cho phép suy ra kết luận nào từ hai tiền đề P và P → Q?
A. ¬P
B. ¬Q
C. Q
D. P ∧ Q
10. Trong lý thuyết số học, phép đồng dư modulo n (congruence modulo n) là một quan hệ như thế nào?
A. Quan hệ tương đương.
B. Quan hệ thứ tự bộ phận.
C. Quan hệ phản xạ.
D. Quan hệ phản đối xứng.
11. Số các hoán vị của n phần tử khác nhau là bao nhiêu?
12. Trong quan hệ, bao đóng bắc cầu (transitive closure) của một quan hệ R là gì?
A. Quan hệ nhỏ nhất chứa R và có tính phản xạ.
B. Quan hệ nhỏ nhất chứa R và có tính đối xứng.
C. Quan hệ nhỏ nhất chứa R và có tính bắc cầu.
D. Quan hệ lớn nhất chứa R và có tính bắc cầu.
13. Trong tổ hợp, chỉnh hợp chập k của n phần tử khác với tổ hợp chập k của n phần tử ở điểm nào?
A. Chỉnh hợp không quan tâm đến thứ tự, tổ hợp có quan tâm.
B. Cả chỉnh hợp và tổ hợp đều quan tâm đến thứ tự.
C. Chỉnh hợp có quan tâm đến thứ tự, tổ hợp không quan tâm.
D. Cả chỉnh hợp và tổ hợp đều không quan tâm đến thứ tự.
14. 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 vô hạn của số tự nhiên).
C. Tính đúng đắn của một mệnh đề chỉ đúng cho một số hữu hạn trường hợp.
D. Tính đúng đắn của một mệnh đề liên quan đến các đối tượng rời rạc bất kỳ.
15. Trong lý thuyết đồ thị, chu trình Hamilton là chu trình như thế nào?
A. Đi qua tất cả các cạnh của đồ thị đúng một lần.
B. Đi qua tất cả các đỉnh của đồ thị đúng một lần.
C. Là đường đi ngắn nhất giữa hai đỉnh bất kỳ.
D. Là chu trình có độ dài ngắn nhất trong đồ thị.
16. Trong lý thuyết đồ thị, thuật toán Prim và thuật toán Kruskal đều được sử dụng để giải bài toán nào?
A. Tìm đường đi ngắn nhất.
B. Tìm cây khung nhỏ nhất.
C. Tìm chu trình Hamilton.
D. Tìm đường đi Euler.
17. Trong logic vị từ, lượng từ `∀` được gọi là lượng từ gì?
A. Lượng từ tồn tại.
B. Lượng từ phổ quát.
C. Lượng từ duy nhất.
D. Lượng từ phủ định.
18. Trong số học modular, nghịch đảo modular của a modulo n (nếu tồn tại) là số x sao cho điều gì đúng?
A. (a + x) ≡ 0 (mod n)
B. (a - x) ≡ 0 (mod n)
C. (a × x) ≡ 1 (mod n)
D. (a ∕ x) ≡ 1 (mod n)
19. Trong lý thuyết tập hợp, phép toán nào sau đây cho phép tạo ra tập hợp chứa các cặp có thứ tự, trong đó phần tử đầu tiên thuộc tập hợp thứ nhất và phần tử thứ hai thuộc tập hợp thứ hai?
A. Hợp
B. Giao
C. Hiệu
D. Tích Descartes
20. Mệnh đề phủ định của mệnh đề `Mọi số tự nhiên đều lớn hơn 0′ là mệnh đề nào?
A. Có ít nhất một số tự nhiên nhỏ hơn 0.
B. Mọi số tự nhiên đều nhỏ hơn hoặc bằng 0.
C. Không có số tự nhiên nào lớn hơn 0.
D. Có ít nhất một số tự nhiên không lớn hơn 0.
21. 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 cây khung nhỏ nhất.
B. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có trọng số không âm.
C. Tìm chu trình Hamilton.
D. Tìm đường đi Euler.
22. Nguyên lý Dirichlet (hay nguyên lý ngăn kéo) phát biểu điều gì?
A. Nếu có n vật được đặt vào m ngăn kéo, với n > m, thì có ít nhất một ngăn kéo chứa ít nhất hai vật.
B. Nếu có m vật được đặt vào n ngăn kéo, với n > m, thì có ít nhất một ngăn kéo rỗng.
C. Số vật bằng số ngăn kéo thì mỗi ngăn kéo chứa đúng một vật.
D. Không có ngăn kéo nào chứa quá hai vật.
23. Loại đồ thị nào sau đây KHÔNG thể có chu trình Euler?
A. Đồ thị liên thông mà tất cả các đỉnh đều có bậc chẵn.
B. Đồ thị liên thông mà có đúng hai đỉnh bậc lẻ.
C. Đồ thị không liên thông.
D. Đồ thị liên thông mà có nhiều hơn hai đỉnh bậc lẻ.
24. Trong đồ thị có hướng, đường đi Hamilton có hướng là đường đi như thế nào?
A. Đi qua tất cả các cạnh của đồ thị theo đúng hướng của cạnh.
B. Đi qua tất cả các đỉnh của đồ thị đúng một lần theo hướng của cạnh.
C. Là đường đi ngắn nhất giữa hai đỉnh bất kỳ theo hướng cạnh.
D. Là chu trình có hướng đi qua tất cả các đỉnh đúng một lần.
25. Biểu thức chính tắc tuyển chuẩn tắc (Disjunctive Normal Form - DNF) của một hàm Boolean là gì?
A. Một tổng của các tích, trong đó mỗi tích là một minterm.
B. Một tích của các tổng, trong đó mỗi tổng là một maxterm.
C. Một biểu thức chứa chỉ các phép toán AND và NOT.
D. Một biểu thức chứa chỉ các phép toán OR và NOT.
26. Quan hệ R trên tập hợp A được gọi là quan hệ tương đương nếu nó thỏa mãn đồng thời các tính chất nào sau đây?
A. Phản xạ, đối xứng, bắc cầu.
B. Phản xạ, phản đối xứng, bắc cầu.
C. Đối xứng, phản đối xứng, bắc cầu.
D. Phản xạ, đối xứng, phản bắc cầu.
27. Trong lý thuyết tập hợp, phép toán nào sau đây cho phép tạo ra một tập hợp mới chứa tất cả các phần tử thuộc ít nhất một trong hai tập hợp ban đầu?
A. Giao
B. Hợp
C. Hiệu
D. Tích Descartes
28. Trong lý thuyết đồ thị, đường đi Euler là đường đi như thế nào?
A. Đi qua tất cả các đỉnh của đồ thị đúng một lần.
B. Đi qua tất cả các cạnh của đồ thị đúng một lần.
C. Là đường đi ngắn nhất giữa hai đỉnh bất kỳ.
D. Là chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần.
29. Hàm số f(n) = O(g(n)) (ký hiệu Big O) có nghĩa là gì?
A. f(n) tăng trưởng nhanh hơn g(n) khi n đủ lớn.
B. f(n) tăng trưởng chậm hơn g(n) khi n đủ lớn.
C. Tồn tại hằng số c > 0 và n0 sao cho |f(n)| ≤ c|g(n)| với mọi n ≥ n0.
D. Tồn tại hằng số c > 0 và n0 sao cho |g(n)| ≤ c|f(n)| với mọi n ≥ n0.
30. Trong đại số Boolean, định luật De Morgan phát biểu điều gì?
A. Phân phối của phép AND qua phép OR.
B. Phân phối của phép OR qua phép AND.
C. Phủ định của phép AND là phép OR của các phủ định, và phủ định của phép OR là phép AND của các phủ định.
D. Luật lũy đẳng của phép AND và phép OR.
