1. Đồ thị vô hướng G = (V, E) được gọi là đồ thị đầy đủ nếu:
A. Mỗi đỉnh trong V đều có bậc bằng nhau.
B. Có một đường đi giữa mọi cặp đỉnh trong V.
C. Mỗi cặp đỉnh phân biệt trong V đều kề nhau.
D. Số cạnh |E| bằng số đỉnh |V| trừ 1.
2. Trong lý thuyết đồ thị, bậc của một đỉnh là gì?
A. Số đỉnh kề với nó.
B. Số cạnh liên thuộc với nó.
C. Tổng trọng số của các cạnh liên thuộc với nó.
D. Độ dài đường đi ngắn nhất từ đỉnh đó đến đỉnh khác.
3. Một cây có n đỉnh thì có bao nhiêu cạnh?
A. n
B. n + 1
C. n - 1
D. 2n
4. Trong logic mệnh đề, phép toán nào sau đây biểu diễn ý nghĩa 'P kéo theo Q'?
A. P ∧ Q
B. P ∨ Q
C. P → Q
D. P ↔ Q
5. Hàm số f: Z → Z được định nghĩa bởi f(x) = 2x + 1. Hàm số này là:
A. Song ánh (bijective).
B. Toàn ánh (surjective) nhưng không đơn ánh (injective).
C. Đơn ánh (injective) nhưng không toàn ánh (surjective).
D. Không đơn ánh và không toàn ánh.
6. Số cạnh tối đa trong một đồ thị đơn vô hướng có n đỉnh là bao nhiêu?
A. n
B. n-1
C. n(n-1)/2
D. n^2
7. Hệ đếm cơ số 16 còn được gọi là hệ đếm:
A. Bát phân.
B. Thập phân.
C. Nhị phân.
D. Thập lục phân (Hexadecimal).
8. Phép toán XOR (exclusive OR) giữa hai bit A và B cho kết quả là 1 khi nào?
A. Cả A và B đều là 1.
B. Cả A và B đều là 0.
C. A khác B.
D. A bằng B.
9. 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 quan tâm đến thứ tự, tổ hợp thì không.
B. Tổ hợp quan tâm đến thứ tự, chỉnh hợp thì không.
C. Chỉnh hợp chọn k phần tử từ n, tổ hợp chọn n phần tử từ k.
D. Tổ hợp sử dụng phép nhân, chỉnh hợp sử dụng phép cộng.
10. Trong lý thuyết đồ thị, chu trình Euler là gì?
A. Chu trình đi qua mỗi đỉnh của đồ thị đúng một lần.
B. Chu trình đi qua mỗi cạnh của đồ thị đúng một lần.
C. Đường đi ngắn nhất giữa hai đỉnh.
D. Cây bao trùm của đồ thị.
11. Trong đại số Boolean, luật De Morgan thứ nhất phát biểu rằng:
A. ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
B. ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
C. P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
D. P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
12. Cho hàm băm h(x) = x mod 10. Giá trị băm của 123 là:
13. Cho biểu thức logic (P ∧ Q) → R. Biểu thức logic tương đương nào sau đây?
A. (P → R) ∧ (Q → R)
B. (P → R) ∨ (Q → R)
C. ¬(P ∧ Q) ∨ R
D. (P ∨ Q) ∧ R
14. Trong toán học rời rạc, khái niệm 'đếm được' (countable) thường liên quan đến loại tập hợp nào?
A. Tập hợp hữu hạn.
B. Tập hợp vô hạn.
C. Tập hợp có thể ánh xạ một-một với tập số tự nhiên.
D. Tập hợp có lực lượng lớn hơn tập số thực.
15. Trong một nhóm 10 người, có bao nhiêu cách chọn ra một nhóm 3 người để tham gia một dự án?
A. 10!
B. 10P3
C. 10C3
D. 3^10
16. Trong lý thuyết automata, một DFA (Deterministic Finite Automaton) là gì?
A. Một loại máy Turing không xác định.
B. Một loại ô-tô-mát hữu hạn xác định.
C. Một loại ô-tô-mát đẩy xuống xác định.
D. Một loại ngữ pháp phi ngữ cảnh.
17. Số cách sắp xếp n đối tượng khác nhau vào n vị trí khác nhau là:
18. Phát biểu nào sau đây mô tả đúng nhất về quan hệ bao hàm (⊆) giữa các tập hợp?
A. A ⊆ B khi và chỉ khi A và B có cùng số phần tử.
B. A ⊆ B khi và chỉ khi mọi phần tử của A đều là phần tử của B.
C. A ⊆ B khi và chỉ khi có ít nhất một phần tử của A là phần tử của B.
D. A ⊆ B khi và chỉ khi A và B không có phần tử chung.
19. Thuật toán Dijkstra thường được sử dụng để giải quyết bài toán nào trên đồ thị?
A. Tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh còn lại.
B. Tìm chu trình Euler.
C. Tìm chu trình Hamilton.
D. Kiểm tra tính liên thông của đồ thị.
20. Trong lý thuyết số, ước số chung lớn nhất (ƯCLN) của hai số nguyên a và b, ký hiệu gcd(a, b), là gì?
A. Số nguyên nhỏ nhất chia hết cho cả a và b.
B. Số nguyên 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.
21. Phát biểu nào sau đây là đúng về quan hệ tương đương?
A. Quan hệ tương đương phải có tính phản xạ và đối xứng.
B. Quan hệ tương đương phải có tính đối xứng và bắc cầu.
C. Quan hệ tương đương phải có tính phản xạ và bắc cầu.
D. Quan hệ tương đương phải có tính phản xạ, đối xứng và bắc cầu.
22. Trong một đồ thị có trọng số, cây khung nhỏ nhất (Minimum Spanning Tree - MST) là gì?
A. Cây bao trùm chứa tất cả các đỉnh với tổng trọng số cạnh lớn nhất.
B. Cây bao trùm chứa tất cả các đỉnh với tổng trọng số cạnh nhỏ nhất.
C. Đường đi ngắn nhất giữa hai đỉnh bất kỳ.
D. Chu trình ngắn nhất đi qua tất cả các đỉnh.
23. Cho quan hệ R trên tập hợp A = {1, 2, 3} như sau: R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}. Quan hệ R có tính chất nào sau đây?
A. Chỉ phản xạ.
B. Phản xạ và đối xứng.
C. Đối xứng và bắc cầu.
D. Phản xạ, đối xứng và bắc cầu.
24. Cho hàm đệ quy tính số Fibonacci: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) với n ≥ 2. Giá trị F(4) là:
25. 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}
26. Phương pháp chứng minh quy nạp toán học 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.
B. Một mệnh đề đúng cho tất cả các số tự nhiên (hoặc một tập con 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.
27. Trong mật mã học, hàm băm mật mã (cryptographic hash function) có tính chất quan trọng nào sau đây?
A. Dễ dàng đảo ngược để khôi phục dữ liệu gốc.
B. Kháng tiền ảnh (preimage resistance) - khó tìm đầu vào từ giá trị băm.
C. Luôn tạo ra giá trị băm có độ dài ngắn hơn đầu vào.
D. Không bao giờ xảy ra đụng độ (collision).
28. Trong giải thuật tìm kiếm theo chiều rộng (Breadth-First Search - BFS) trên đồ thị, cấu trúc dữ liệu nào thường được sử dụng để quản lý các đỉnh cần duyệt?
A. Stack (Ngăn xếp).
B. Queue (Hàng đợi).
C. Priority Queue (Hàng đợi ưu tiên).
D. Linked List (Danh sách liên kết).
29. 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 (ngoại trừ tại các đỉnh).
C. Mọi đỉnh đều có bậc chẵn.
D. Có một chu trình Hamilton.
30. Một ngôn ngữ hình thức được gọi là ngôn ngữ chính quy nếu nó được chấp nhận bởi:
A. Máy Turing.
B. Ô-tô-mát hữu hạn (Finite Automaton).
C. Ô-tô-mát đẩy xuống (Pushdown Automaton).
D. Ngữ pháp phi ngữ cảnh (Context-Free Grammar).
