1. Một cây có gốc (rooted tree) được gọi là cây nhị phân (binary tree) nếu:
A. Mỗi đỉnh có tối đa hai con.
B. Mỗi đỉnh có đúng hai con.
C. Mỗi đỉnh có ít nhất hai con.
D. Tất cả các lá đều ở cùng một mức.
2. Phương pháp chứng minh quy nạp thường được sử dụng để chứng minh:
A. Tính đúng đắn của một thuật toán cụ thể.
B. 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. Sự tồn tại của một đối tượng toán học.
D. Tính duy nhất của một nghiệm.
3. Phép toán nào sau đây KHÔNG phải là phép toán cơ bản trong đại số Boole?
A. Phép AND (∧)
B. Phép OR (∨)
C. Phép NOT (¬)
D. Phép XOR (⊕)
4. Trong logic mệnh đề, phép toán nào sau đây được gọi là phép kéo theo (implication)?
A. Phép hội (conjunction)
B. Phép tuyển (disjunction)
C. Phép kéo theo (implication)
D. Phép phủ định (negation)
5. Trong một nhóm 10 người, cần chọn ra 3 người để tham gia một đội. Số cách chọn là:
A. 10 × 9 × 8
B. 10! ∕ (3! × 7!)
C. 10! ∕ 3!
D. 10³
6. Trong lý thuyết đồ thị, bậc của một đỉnh là:
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 từ đỉnh đó đến đỉnh khác.
7. Cho hàm f: Z → Z, f(x) = 2x + 1. Hàm f có phải là song ánh (bijection) 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.
8. Trong logic vị từ, lượng từ ∀ được gọi là:
A. Lượng từ tồn tại (existential quantifier)
B. Lượng từ phổ quát (universal quantifier)
C. Lượng từ duy nhất (uniqueness quantifier)
D. Lượng từ số đếm (counting quantifier)
9. Đồ thị vô hướng được gọi là đồ thị đầy đủ nếu:
A. Mỗi đỉnh đều có bậc bằng nhau.
B. Có một đường đi giữa mọi cặp đỉnh.
C. Mọi cặp đỉnh phân biệt đều kề nhau.
D. Không có chu trình nào trong đồ thị.
10. Số cạnh tối thiểu trong một đồ thị liên thông có n đỉnh là:
A. n
B. n - 1
C. n + 1
D. n × (n - 1) ∕ 2
11. Cho tập hợp X = {a, b, c}. Số tập con của X là:
12. Trong các cấu trúc dữ liệu sau, cấu trúc nào KHÔNG phải là cấu trúc dữ liệu tuyến tính?
A. Mảng (Array)
B. Danh sách liên kết (Linked List)
C. Cây (Tree)
D. Hàng đợi (Queue)
13. Trong lý thuyết đồ thị, cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông có trọng số là:
A. Cây con chứa tất cả các đỉnh và có tổng trọng số cạnh nhỏ nhất.
B. Đường đi ngắn nhất giữa hai đỉnh bất kỳ.
C. Chu trình đi qua tất cả các đỉnh đúng một lần.
D. Đồ thị con đầy đủ của đồ thị ban đầu.
14. Trong lý thuyết đồ thị, đồ thị phẳng là đồ thị có thể vẽ được trên mặt phẳng sao cho:
A. Các cạnh không cắt nhau.
B. Mỗi đỉnh có bậc chẵn.
C. Có chu trình Hamilton.
D. Có chu trình Euler.
15. Định lý Euler về đồ thị phẳng liên quan đến số lượng đỉnh (V), cạnh (E) và miền (F) của đồ thị phẳng liên thông được phát biểu là:
A. V + E - F = 2
B. V - E + F = 2
C. V - E - F = 2
D. V + E + F = 2
16. Trong phép đếm, quy tắc cộng được áp dụng khi:
A. Các trường hợp xảy ra đồng thời.
B. Các trường hợp loại trừ lẫn nhau.
C. Các trường hợp phụ thuộc lẫn nhau.
D. Các trường hợp lặp lại.
17. Trong đại số Boole, luật hấp thụ (absorption law) được biểu diễn bởi:
A. x + (x ∧ y) = x
B. x ∧ (x + y) = y
C. x + (x ∨ y) = y
D. x ∧ (x ∨ y) = x ∨ y
18. 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à:
A. {1, 2, 3, 4, 5}
B. {1, 2}
C. {4, 5}
D. {3}
19. Một chu trình Euler trong đồ thị là chu trình đi qua:
A. Tất cả các đỉnh của đồ thị đúng một lần.
B. Tất cả các cạnh của đồ thị đúng một lần.
C. Một số đỉnh và cạnh của đồ thị.
D. Các đỉnh và cạnh theo thứ tự bất kỳ.
20. Cho quan hệ R trên tập hợp A = {1, 2, 3} được định nghĩa bởi R = {(1, 1), (2, 2), (3, 3), (1, 2)}. Quan hệ R có tính chất nào sau đây?
A. Phản xạ (Reflexive)
B. Đối xứng (Symmetric)
C. Phản đối xứng (Antisymmetric)
D. Bắc cầu (Transitive)
21. Trong thuật toán tô màu đồ thị, số màu sắc tối thiểu cần thiết để tô màu các đỉnh của đồ thị sao cho không có hai đỉnh kề nhau nào có cùng màu được gọi là:
A. Bậc của đồ thị
B. Số cạnh của đồ thị
C. Số sắc của đồ thị (chromatic number)
D. Kích thước đồ thị
22. Biểu thức logic (p ∧ q) → p là:
A. Hằng đúng (tautology)
B. Mâu thuẫn (contradiction)
C. Khả năng đúng (contingency)
D. Không xác định
23. Hệ đếm cơ số 16 còn được gọi là hệ đếm:
A. Nhị phân (Binary)
B. Bát phân (Octal)
C. Thập phân (Decimal)
D. Thập lục phân (Hexadecimal)
24. Số hoán vị của n phần tử phân biệt là:
25. Trong phép toán logic, phép tuyển loại trừ (exclusive OR - XOR) của hai mệnh đề p và q đúng khi:
A. Cả p và q đều đúng.
B. Cả p và q đều sai.
C. p đúng hoặc q đúng, nhưng không phải cả hai cùng đúng.
D. p đúng và q đúng.
26. Tính chất nào sau đây KHÔNG phải là tính chất của quan hệ tương đương?
A. Phản xạ (Reflexive)
B. Đối xứng (Symmetric)
C. Bắc cầu (Transitive)
D. Phản đối xứng (Antisymmetric)
27. Thuật toán Dijkstra được sử dụng để giải quyết bài toán nào sau đây?
A. Tìm cây khung nhỏ nhất của đồ thị.
B. Tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị có trọng số không âm.
C. Tìm chu trình Euler trong đồ thị.
D. Sắp xếp các đỉnh của đồ thị theo thứ tự tô pô.
28. Phát biểu nào sau đây là đúng về hàm băm (hash function) trong khoa học máy tính?
A. Hàm băm luôn tạo ra các giá trị băm duy nhất cho các đầu vào khác nhau.
B. Hàm băm được sử dụng để mã hóa dữ liệu.
C. Hàm băm ánh xạ dữ liệu có kích thước tùy ý sang dữ liệu có kích thước cố định.
D. Hàm băm chỉ áp dụng cho dữ liệu số.
29. Bài toán người giao hàng (Traveling Salesperson Problem - TSP) thuộc lớp bài toán nào?
A. P
B. NP
C. NP-complete
D. Dễ giải (tractable)
30. Trong lý thuyết tập hợp, luật De Morgan phát biểu rằng:
A. (A ∪ B)′ = A′ ∪ B′
B. (A ∩ B)′ = A′ ∩ B′
C. (A ∪ B)′ = A′ ∩ B′
D. (A ∩ B)′ = A ∪ B
