1. Trong số học, ước chung lớn nhất (ƯCLN) của hai số nguyên a và b có thể được tìm bằng thuật toán nào sau đây?
A. Thuật toán sắp xếp nổi bọt
B. Thuật toán Euclid
C. Thuật toán tìm kiếm nhị phân
D. Thuật toán Dijkstra
2. Trong số học modular, phép toán nào sau đây không được định nghĩa trực tiếp như phép toán ngược (inverse)?
A. Phép cộng
B. Phép trừ
C. Phép nhân
D. Phép chia
3. 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 đỉnh nằm trên cùng một đường thẳng.
B. Không có cạnh nào cắt nhau, ngoại trừ tại các đỉnh.
C. Mọi đỉnh đều có bậc bằng nhau.
D. Nó chứa một chu trình Hamilton.
4. Trong lý thuyết automata, DFA là viết tắt của cụm từ nào?
A. Deterministic Finite Automaton
B. Non-deterministic Finite Automaton
C. Digital Function Algorithm
D. Data Flow Analysis
5. Số lượng quan hệ hai ngôi khác nhau có thể xác định trên tập hợp A có n phần tử là bao nhiêu?
A. n!
B. 2^n
C. 2^(n*n)
D. n^2
6. Biểu thức logic nào sau đây tương đương với biểu thức ¬(p ∧ q) (phủ định của 'p và q')?
A. ¬p ∧ ¬q
B. ¬p ∨ ¬q
C. p ∨ q
D. p ∧ ¬q
7. Một đồ thị vô hướng được gọi là đồ thị đầy đủ (complete graph) khi nào?
A. Khi nó chứa một chu trình Hamilton.
B. Khi nó chứa một chu trình Euler.
C. Khi mọi cặp đỉnh phân biệt đều có một cạnh nối giữa chúng.
D. Khi nó là đồ thị phẳng.
8. Trong lý thuyết đồ thị, một đường đi Euler là gì?
A. Đường đi thăm mỗi đỉnh đúng một lần.
B. Đường đi thăm mỗi cạnh đúng một lần.
C. Chu trình thăm mỗi đỉnh đúng một lần và quay lại đỉnh xuất phát.
D. Chu trình thăm mỗi cạnh đúng một lần và quay lại đỉnh xuất phát.
9. Cho tập hợp A = {1, 2, 3}. Hỏi có bao nhiêu hoán vị của tập hợp A?
10. Trong thuật toán tô màu đồ thị, mục tiêu chính là gì?
A. Tìm đường đi ngắn nhất trong đồ thị.
B. Tìm cây khung nhỏ nhất của đồ thị.
C. Gán màu cho các đỉnh sao cho không có hai đỉnh kề nhau nào có cùng màu, sử dụng số màu ít nhất có thể.
D. Sắp xếp các đỉnh theo bậc giảm dần.
11. Hệ đếm cơ số 16 còn được gọi là hệ đếm nào?
A. Nhị phân
B. Thập phân
C. Bát phân
D. Hexadecimal
12. Trong lý thuyết đồ thị, bậc của một đỉnh được định nghĩa là gì?
A. Số lượng cạnh liên thuộc với đỉnh đó.
B. Số lượng đỉ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. Độ dài đường đi ngắn nhất từ đỉnh đó đến một đỉnh khác.
13. Phép toán nào sau đây không phải là phép toán cơ bản trên tập hợp?
A. Hợp
B. Giao
C. Hiệu
D. Tích phân
14. Mệnh đề 'Nếu trời mưa thì đường ướt' có dạng logic nào?
A. p ∧ q
B. p ∨ q
C. p → q
D. p ↔ q
15. Nguyên lý chuồng bồ câu (Pigeonhole Principle) phát biểu rằng nếu có n+1 con bồ câu nhốt vào n chuồng thì...
A. Mỗi chuồng có đúng một con bồ câu.
B. Có ít nhất một chuồng có ít nhất hai con bồ câu.
C. Tất cả các chuồng đều có bồ câu.
D. Một số chuồng không có bồ câu.
16. Trong lý thuyết đồ thị, ma trận kề (adjacency matrix) của một đồ thị được sử dụng để làm gì?
A. Biểu diễn đồ thị bằng danh sách các cạnh.
B. Biểu diễn đồ thị bằng ma trận các đỉnh.
C. Biểu diễn đồ thị bằng ma trận mà phần tử (i, j) cho biết có cạnh nối giữa đỉnh i và đỉnh j hay không.
D. Biểu diễn đồ thị bằng cách vẽ các đỉnh và cạnh.
17. Hàm số f: A → B được gọi là đơn ánh (injective) khi nào?
A. Với mọi b thuộc B, tồn tại ít nhất một a thuộc A sao cho f(a) = b.
B. Với mọi b thuộc B, tồn tại duy nhất một a thuộc A sao cho f(a) = b.
C. Với mọi a1, a2 thuộc A, nếu a1 ≠ a2 thì f(a1) ≠ f(a2).
D. Với mọi a1, a2 thuộc A, nếu f(a1) = f(a2) thì a1 = a2.
18. Trong đại số Boole, cổng logic nào sau đây thực hiện phép toán AND?
A. Cổng OR
B. Cổng NOT
C. Cổng AND
D. Cổng XOR
19. Trong tổ hợp, hệ số nhị thức (n chập k) ký hiệu là C(n, k) hoặc (n
k) tính giá trị gì?
A. Số cách sắp xếp k phần tử từ n phần tử.
B. Số cách chọn k phần tử từ n phần tử mà không quan tâm đến thứ tự.
C. Số cách chọn và sắp xếp k phần tử từ n phần tử.
D. Tổng của k phần tử đầu tiên trong dãy số tự nhiên.
20. 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 đến thứ tự.
B. Cả hai đề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 đến thứ tự.
D. Cả hai đều không quan tâm đến thứ tự.
21. Một quan hệ hai ngôi R trên tập hợp A được gọi là quan hệ phản xạ khi nào?
A. Với mọi a thuộc A, (a, a) thuộc R.
B. Với mọi (a, b) thuộc R, (b, a) thuộc R.
C. Với mọi (a, b) thuộc R và (b, c) thuộc R, (a, c) thuộc R.
D. Không có cặp (a, a) nào thuộc R.
22. Biểu thức (p → q) ↔ (¬q → ¬p) thể hiện quy tắc suy luận nào trong logic mệnh đề?
A. Modus Ponens
B. Modus Tollens
C. Luật phản đảo (Contrapositive)
D. Luật tam đoạn luận (Syllogism)
23. 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
24. Thuật toán Dijkstra thường được sử dụng để giải quyết bài toán nào trong lý thuyết đồ thị?
A. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm.
B. Tìm cây khung nhỏ nhất của đồ thị.
C. Kiểm tra tính liên thông của đồ thị.
D. Tìm chu trình Euler trong đồ thị.
25. Phương pháp chứng minh quy nạp thường được sử dụng để chứng minh điều gì trong toán học rời rạc?
A. Tính đúng đắn của một thuật toán.
B. Tính chất đú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 chất của một tập hợp hữu hạn.
D. Tính liên tục của một hàm số.
26. Trong đại số Boole, định luật nào sau đây phát biểu rằng x + (y * z) = (x + y) * (x + z)?
A. Luật giao hoán
B. Luật kết hợp
C. Luật phân phối
D. Luật De Morgan
27. Trong lý thuyết đồ thị, cây (tree) là một loại đồ thị đặc biệt. Tính chất nào sau đây không đúng với cây?
A. Liên thông
B. Không có chu trình
C. Có chu trình
D. Số cạnh bằng số đỉnh trừ 1
28. Giá trị của biểu thức logic (p ∨ ¬p) ∧ q luôn luôn là gì, bất kể giá trị chân lý của p và q?
A. Luôn đúng (True)
B. Luôn sai (False)
C. Phụ thuộc vào p
D. Phụ thuộc vào q
29. Trong logic vị từ, lượng từ ∀ được gọi là lượng từ nào?
A. Tồn tại
B. Phổ quát (với mọi)
C. Đặc biệt
D. Duy nhất
30. Một tập hợp A được gọi là đếm được (countable) nếu nó có thể tương ứng một-một với tập hợp nào sau đây?
A. Tập hợp số thực
B. Tập hợp số vô tỷ
C. Tập hợp số tự nhiên
D. Tập hợp số phức
