1. Cây nhị phân đầy đủ (full binary tree) là cây nhị phân mà mỗi nút, ngoại trừ lá, có bao nhiêu nút con?
A. 0 hoặc 1
B. 0 hoặc 2
C. 1 hoặc 2
D. Chỉ có 2
2. Quan hệ 'chia hết' (divisibility) trên tập hợp số nguyên dương có tính chất nào sau đây?
A. Đối xứng (symmetric)
B. Phản xạ (reflexive) và đối xứng.
C. Phản xạ (reflexive) và bắc cầu (transitive).
D. Bắc cầu (transitive) và đối xứng.
3. Hàm số f: Z → Z (từ tập số nguyên Z sang chính nó) được định nghĩa là f(x) = 2x + 1. Hàm số này có phải là song ánh (bijective) 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.
4. Điều kiện cần và đủ để một đồ thị vô hướng liên thông có chu trình Euler là gì?
A. Tất cả các đỉnh có bậc chẵn.
B. Có đúng hai đỉnh có bậc lẻ.
C. Có ít nhất một đỉnh có bậc lẻ.
D. Tất cả các đỉnh có bậc lẻ.
5. Đồ thị nào sau đây KHÔNG thể là cây?
A. Đồ thị liên thông và không có chu trình.
B. Đồ thị có số đỉnh bằng số cạnh cộng 1 và liên thông.
C. Đồ thị có chu trình.
D. Đồ thị có đúng một đường đi giữa mọi cặp đỉnh.
6. Trong tổ hợp, hệ số nhị thức C(n, k) (tổ hợp chập k của n) được tính bằng công thức nào?
A. n! / (k! * (n-k)!)
B. n! / (n-k)!
C. n! / k!
D. k! / (n! * (n-k)!)
7. Số lượng cạnh tối thiểu trong một đồ thị liên thông có n đỉnh là bao nhiêu?
A. n - 2
B. n - 1
C. n
D. n + 1
8. Giá trị của P(5, 2) (chỉnh hợp chập 2 của 5) là bao nhiêu?
9. Trong toán học rời rạc, phát biểu nào sau đây mô tả đúng nhất về một 'tập hợp'?
A. Một danh sách các phần tử được sắp xếp theo thứ tự cụ thể.
B. Một nhóm các phần tử có thể trùng lặp.
C. Một bộ sưu tập các phần tử riêng biệt, không quan tâm đến thứ tự.
D. Một cấu trúc dữ liệu tuyến tính, tương tự như mảng.
10. Thuật toán Euclid được sử dụng để tìm gì?
A. Bội chung nhỏ nhất (LCM) của hai số.
B. Ước chung lớn nhất (GCD) của hai số.
C. Căn bậc hai của một số.
D. Số nguyên tố lớn nhất nhỏ hơn một số cho trước.
11. Trong quan hệ hai ngôi, một quan hệ R trên tập hợp A được gọi là quan hệ phản xạ (reflexive) khi nào?
A. Với mọi a, b ∈ A, nếu (a, b) ∈ R thì (b, a) ∈ R.
B. Với mọi a ∈ A, (a, a) ∈ R.
C. Với mọi a, b, c ∈ A, nếu (a, b) ∈ R và (b, c) ∈ R thì (a, c) ∈ R.
D. Với mọi a, b ∈ A, nếu (a, b) ∈ R thì (a, b) ∉ R.
12. Trong lý thuyết đồ thị, đồ thị phẳng (planar graph) là gì?
A. Đồ thị có thể vẽ được trên mặt phẳng sao cho không có hai cạnh nào cắt nhau (ngoại trừ tại đỉnh).
B. Đồ thị mà tất cả các đỉnh đều nằm trên cùng một mặt phẳng.
C. Đồ thị mà tất cả các cạnh đều là đường thẳng.
D. Đồ thị không có chu trình.
13. Ngôn ngữ nào sau đây KHÔNG phải là ngôn ngữ chính quy (regular language)?
A. Ngôn ngữ chứa tất cả các chuỗi nhị phân có số lượng bit 1 là số chẵn.
B. Ngôn ngữ chứa tất cả các chuỗi nhị phân bắt đầu bằng 0.
C. Ngôn ngữ chứa tất cả các chuỗi có dạng a^n b^n với n ≥ 0.
D. Ngôn ngữ chứa tất cả các chuỗi có độ dài không vượt quá 100.
14. Phép toán nào sau đây KHÔNG phải là một phép toán cơ bản trên tập hợp?
A. Phép hợp (Union)
B. Phép giao (Intersection)
C. Phép nhân (Multiplication)
D. Phép bù (Complement)
15. Chiều cao của một cây có gốc được định nghĩa là gì?
A. Số lượng nút trên đường đi dài nhất từ gốc đến một nút lá.
B. Số lượng cạnh trên đường đi dài nhất từ gốc đến một nút lá.
C. Số lượng nút trong cây.
D. Số lượng lá trong cây.
16. Giá trị của C(4, 2) (tổ hợp chập 2 của 4) là bao nhiêu?
17. Biểu thức Boolean nào sau đây tương đương với ¬(A ∧ B) ∨ C?
A. (¬A ∨ ¬B) ∧ C
B. (¬A ∨ ¬B) ∨ C
C. (A ∧ B) ∧ ¬C
D. (A ∨ B) ∨ C
18. Trong lý thuyết đồ thị, bậc của một đỉnh trong đồ thị vô hướng 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. Số lượng đường đi ngắn nhất từ đỉnh đó đến tất cả các đỉnh khác.
19. Phép toán nào sau đây KHÔNG thuộc về phép toán trên quan hệ hai ngôi?
A. Phép hợp (Union)
B. Phép giao (Intersection)
C. Phép chiếu (Projection)
D. Phép cộng (Addition)
20. Trong lý thuyết automata, DFA (Deterministic Finite Automaton) khác với NFA (Non-deterministic Finite Automaton) ở điểm nào?
A. DFA có thể có nhiều trạng thái kết thúc, NFA chỉ có một.
B. DFA có thể chuyển trạng thái dựa trên tập hợp trạng thái, NFA chỉ chuyển dựa trên một trạng thái.
C. Với mỗi trạng thái và mỗi ký tự đầu vào, DFA có duy nhất một chuyển trạng thái tiếp theo, NFA có thể có nhiều hoặc không có.
D. NFA luôn mạnh hơn DFA về khả năng nhận dạng ngôn ngữ.
21. Biểu thức logic nào sau đây là một hằng đúng (tautology)?
A. P ∨ ¬P
B. P ∧ ¬P
C. P → Q
D. P ↔ Q
22. Trong đại số Boolean, luật hấp thụ (absorption law) phát biểu rằng A ∨ (A ∧ B) tương đương với biểu thức nào?
A. A ∧ B
B. A ∨ B
C. A
D. B
23. Bước cơ sở (base case) trong chứng minh quy nạp là gì?
A. Giả định rằng mệnh đề đúng cho một số k bất kỳ.
B. Chứng minh rằng mệnh đề đúng cho trường hợp đầu tiên (thường là n=0 hoặc n=1).
C. Chứng minh rằng nếu mệnh đề đúng cho n=k thì nó cũng đúng cho n=k+1.
D. Kết luận rằng mệnh đề đúng cho tất cả các số tự nhiên.
24. Cho hai tập hợp A = {1, 2, 3} và B = {3, 4, 5}. Tập hợp A ∩ B (giao của A và B) là tập hợp nào?
A. {1, 2, 3, 4, 5}
B. {1, 2}
C. {3}
D. {}
25. Phương pháp chứng minh quy nạp (mathematical induction) 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ể cho một trường hợp cụ thể.
B. Tính đúng đắn của một mệnh đề cho tất cả các số tự nhiên (hoặc một tập con của số tự nhiên).
C. Tính đúng đắn của một mệnh đề cho một số hữu hạn các trường hợp.
D. Tính đúng đắn của một mệnh đề cho tất cả các số thực.
26. Trong số học mô đun, 7 mod 3 bằng bao nhiêu?
27. Trong lý thuyết đồ thị, đường đi Euler là gì?
A. Đường đi đi qua tất cả các đỉnh của đồ thị đúng một lần.
B. Đường đi đi qua tất cả các cạnh của đồ thị đúng một lần.
C. Chu trình đi qua tất cả các đỉnh của đồ thị đúng một lần (trừ đỉnh đầu và cuối trùng nhau).
D. Chu trình đi qua tất cả các cạnh của đồ thị đúng một lần.
28. Trong logic mệnh đề, mệnh đề phủ định của 'P và Q' (P ∧ Q) tương đương với mệnh đề nào theo luật De Morgan?
A. ¬P ∧ ¬Q
B. ¬P ∨ ¬Q
C. P ∨ Q
D. P → Q
29. Công thức Euler cho đồ thị phẳng liên thông là gì (với V là số đỉnh, E là số cạnh, và F là số miền)?
A. V - E + F = 1
B. V - E + F = 2
C. V + E - F = 2
D. V + E + F = 2
30. Trong tổ hợp, 'chỉnh hợp chập k của n' (permutations) khác với 'tổ hợp chập k của n' (combinations) ở điểm nào?
A. Chỉnh hợp có thứ tự, tổ hợp không có thứ tự.
B. Tổ hợp có thứ tự, chỉnh hợp không có thứ tự.
C. Chỉnh hợp chọn tất cả n phần tử, tổ hợp chọn k phần tử.
D. Tổ hợp sử dụng phép nhân, chỉnh hợp sử dụng phép cộng.
