1. Trong lý thuyết đồ thị, đồ thị vô hướng liên thông là đồ thị như thế nào?
A. Đồ thị không có chu trình
B. Đồ thị mà giữa bất kỳ hai đỉnh nào cũng có ít nhất một đường đi
C. Đồ thị mà tất cả các đỉnh đều có bậc bằng nhau
D. Đồ thị mà số đỉnh bằng số cạnh
2. Định lý Euler về đồ thị phẳng phát biểu điều gì?
A. Tổng bậc của tất cả các đỉnh trong một đồ thị bằng hai lần số cạnh
B. Trong một đồ thị phẳng liên thông, số đỉnh trừ số cạnh cộng số miền bằng 2
C. Một đồ thị có chu trình Euler khi và chỉ khi tất cả các đỉnh của nó có bậc chẵn
D. Một đồ thị có đường đi Hamilton khi và chỉ khi nó có đủ số cạnh nhất định
3. 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. Chỉnh hợp có quan tâm đến thứ tự, tổ hợp không quan tâm đến thứ tự
C. Chỉnh hợp có lặp lại phần tử, tổ hợp không lặp lại phần tử
D. Chỉnh hợp tính số cách chọn, tổ hợp tính số cách sắp xếp
4. Cây nhị phân tìm kiếm (Binary Search Tree - BST) có đặc điểm chính nào?
A. Các nút con trái luôn lớn hơn nút cha, các nút con phải luôn nhỏ hơn nút cha
B. Các nút con trái luôn nhỏ hơn hoặc bằng nút cha, các nút con phải luôn lớn hơn hoặc bằng nút cha
C. Tất cả các nút lá đều ở cùng một mức
D. Cây luôn cân bằng hoàn toàn
5. Cho quan hệ R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)}. Bao đóng phản xạ (reflexive closure) của R là quan hệ nào?
A. {(1, 2), (2, 3)}
B. {(1, 1), (2, 2), (3, 3)}
C. {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)}
D. {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (2, 1), (3, 2)}
6. Cho tập hợp S = {a, b, c}. Số tập con của S là bao nhiêu?
7. Đồ thị Euler là đồ thị có đặc điểm gì?
A. Có chu trình Hamilton
B. Có đường đi Hamilton
C. Có chu trình Euler
D. Có đường đi Euler nhưng không có chu trình Euler
8. Trong lý thuyết đồ thị, chu trình Hamilton là gì?
A. Chu trình đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần
B. Chu trình đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần
C. Đường đi ngắn nhất giữa hai đỉnh trong đồ thị
D. Chu trình có tổng trọng số các cạnh nhỏ nhất
9. Trong lý thuyết tập hợp, phép toán nào tương ứng với `phần bù` của một tập hợp?
A. Phép giao (∩)
B. Phép hợp (∪)
C. Phép hiệu ( hoặc -)
D. Tích Descartes (×)
10. 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 De Morgan
C. Luật bài trung (law of excluded middle)
D. Nguyên tắc mâu thuẫn (principle of contradiction)
11. Trong lý thuyết automata, DFA là viết tắt của cụm từ nào?
A. Deterministic Finite Automaton
B. Dynamic Flow Algorithm
C. Distributed File Architecture
D. Data Flow Analysis
12. 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 (Hexadecimal)
13. 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 phủ định (¬)
14. Trong thuật toán sắp xếp, độ phức tạp thời gian trung bình của thuật toán sắp xếp nhanh (Quick Sort) là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)
15. Phép toán XOR (Exclusive OR) giữa hai bit trả về giá trị 1 khi nào?
A. Khi cả hai bit đều là 0
B. Khi cả hai bit đều là 1
C. Khi hai bit khác nhau
D. Khi ít nhất một trong hai bit là 1
16. Cho mệnh đề P: `Hôm nay trời mưa′ và Q: `Tôi mang ô`. Mệnh đề `Nếu hôm nay trời mưa thì tôi mang ô` được biểu diễn bằng ký hiệu logic nào?
A. P ∧ Q
B. P ∨ Q
C. P → Q
D. P ↔ Q
17. Cho hàm số f: Z → Z xác định bởi f(x) = 2x + 1. Hàm số này có phải là song ánh không?
A. Có, vì nó vừa đơn ánh vừa toàn ánh
B. Không, vì nó không đơn ánh
C. Không, vì nó không toàn ánh
D. Không thể xác định
18. Trong số học, ước số chung lớn nhất (ƯCLN) của hai số nguyên a và b là gì?
A. Số nhỏ nhất chia hết cho cả a và b
B. Số lớn nhất chia hết cả a và b
C. Tích của tất cả các ước số chung của a và b
D. Thương của a và b
19. 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
D. Vừa phản xạ vừa phản đối xứng
20. Trong lý thuyết đồ thị, bậc của một đỉnh được định nghĩa là gì?
A. Số đỉnh kề với đỉnh đó
B. Số cạnh liên thuộc 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
21. Trong số học đồng dư, a ≡ b (mod m) có nghĩa là gì?
A. a chia hết cho b
B. a và b có cùng số dư khi chia cho m
C. a lớn hơn b
D. a nhân b chia hết cho m
22. Cho hai 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. {3}
D. {4, 5}
23. Trong lý thuyết đồ thị, cây (tree) là một loại đồ thị đặc biệt như thế 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ó đường đi Hamilton
24. Trong đại số Boolean, luật De Morgan phát biểu điều gì?
A. Phép tuyển và phép hội là phân phối lẫn nhau
B. Phủ định của phép tuyển bằng phép hội của các phủ định, và ngược lại
C. Mọi biểu thức Boolean có thể được đưa về dạng chuẩn tắc tuyển hoặc dạng chuẩn tắc hội
D. Luật kết hợp cho phép tuyển và phép hội
25. Trong giải thuật đệ quy, điều kiện dừng (base case) có vai trò gì?
A. Tăng tốc độ thực thi của thuật toán
B. Đảm bảo thuật toán luôn tìm ra lời giải
C. Ngăn chặn việc gọi đệ quy vô hạn
D. Giảm độ phức tạp bộ nhớ của thuật toán
26. Một ngôn ngữ hình thức được định nghĩa là gì?
A. Một tập hợp các câu văn có nghĩa
B. Một tập hợp hữu hạn các từ
C. Một tập hợp các chuỗi được xây dựng từ một bảng chữ cái theo một tập quy tắc
D. Một hệ thống ký hiệu dùng để giao tiếp giữa con người
27. 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 chu trình Euler
B. Tìm đường đi Hamilton
C. Tìm cây khung nhỏ nhất
D. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm
28. Trong logic mệnh đề, mệnh đề nào sau đây là hằng đúng (tautology)?
A. p ∧ ¬p
B. p ∨ ¬p
C. p → q
D. p ↔ q
29. Trong lý thuyết automata, NFA khác với DFA chủ yếu ở điểm nào?
A. NFA có ít trạng thái hơn DFA
B. NFA có thể có nhiều chuyển trạng thái cho cùng một đầu vào từ một trạng thái
C. NFA chấp nhận được nhiều ngôn ngữ hơn DFA
D. NFA dễ dàng hiện thực hóa bằng phần cứng hơn DFA
30. 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 đúng đắn của một định lý cho tất cả các số tự nhiên
C. Sự tồn tại của một cấu trúc rời rạc nào đó
D. Tính vô hạn của một tập hợp
