1. Cho tập hợp A = {a, b, c}. Số quan hệ hai ngôi khác nhau có thể định nghĩa trên A là bao nhiêu?
2. Trong lý thuyết đồ thị, bậc của một đỉnh là gì?
A. Số lượng đỉnh kề với đỉnh đó.
B. Tổng trọng số của các cạnh liên thuộc với đỉnh đó.
C. Số lượng 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.
3. Mục tiêu chính của việc chuẩn hóa cơ sở dữ liệu trong toán rời rạc (và khoa học máy tính) là gì?
A. Tăng tốc độ truy vấn dữ liệu.
B. Giảm dung lượng lưu trữ dữ liệu.
C. Giảm dư thừa dữ liệu và cải thiện tính nhất quán dữ liệu.
D. Tăng cường bảo mật dữ liệu.
4. Định lý Cayley phát biểu rằng:
A. Mọi đồ thị phẳng đều có thể tô màu bằng 4 màu.
B. Mọi cây có n đỉnh đều đẳng cấu với một cây khung của đồ thị đầy đủ K_n.
C. Mọi nhóm đều đẳng cấu với một nhóm con của nhóm đối xứng.
D. Mọi đồ thị có chu trình Euler đều có chu trình Hamilton.
5. Cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông, có trọng số là gì?
A. Cây con liên thông chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh lớn nhất.
B. Cây con liên thông chứa một số đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất.
C. Cây con liên thông chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất.
D. Cây con không liên thông chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất.
6. Cho hàm f: Z → Z định nghĩa bởi f(x) = 2x + 1. Hàm f có phải là song ánh (bijective) không?
A. Có, vì f là đơn ánh và toàn ánh.
B. Không, vì f không phải là đơn ánh.
C. Không, vì f không phải là toàn ánh.
D. Có, vì f có hàm ngược.
7. Hàm băm (hash function) lý tưởng trong khoa học máy tính nên có tính chất nào?
A. Dễ dàng tính toán và luôn tạo ra giá trị băm trùng lặp cho các đầu vào khác nhau.
B. Khó tính toán và tạo ra giá trị băm khác nhau cho các đầu vào giống nhau.
C. Dễ dàng tính toán và tạo ra giá trị băm khác nhau cho các đầu vào khác nhau (tránh tối đa xung đột).
D. Khó tính toán và luôn tạo ra giá trị băm giống nhau cho các đầu vào giống nhau.
8. Trong lý thuyết đồ thị, thuật toán Kruskal và thuật toán Prim đều được sử dụng để tìm:
A. Đường đi ngắn nhất giữa hai đỉnh.
B. Chu trình Euler.
C. Cây khung nhỏ nhất (MST).
D. Chu trình Hamilton.
9. Trong các cấu trúc dữ liệu sau, cấu trúc nào thường được sử dụng để cài đặt hàng đợi (Queue)?
A. Ngăn xếp (Stack)
B. Cây nhị phân tìm kiếm (Binary Search Tree)
C. Danh sách liên kết (Linked List)
D. Đồ thị (Graph)
10. 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 cây khung nhỏ nhất (MST).
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. Tìm chu trình Hamilton trong đồ thị.
11. Cho đồ thị vô hướng liên thông G. Điều kiện cần và đủ để G có chu trình Hamilton là gì?
A. Mọi đỉnh trong G có bậc lớn hơn hoặc bằng n/2, với n là số đỉnh của G (Định lý Dirac).
B. G là đồ thị Euler.
C. G là cây.
D. G không chứa chu trình con.
12. 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. 120
B. 30
C. 720
D. 1000
13. Cho tập hợp A = {1, 2, 3, 4}. Quan hệ R trên A được định nghĩa là 'x chia hết cho y'. Hỏi quan hệ R có tính chất nào sau đây?
A. Phản xạ và đối xứng
B. Phản xạ và phản đối xứng
C. Đối xứng và bắc cầu
D. Bắc cầu và phản đối xứng
14. Trong logic vị từ, lượng từ ∀ (với mọi) được gọi là gì?
A. Lượng từ tồn tại.
B. Lượng từ tổng quát.
C. Lượng từ duy nhất.
D. Lượng từ phủ định.
15. Phương pháp chứng minh quy nạp 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ể.
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 thỏa mãn một số tính chất nhất định.
D. Tính sai của một mệnh đề toán học.
16. Biểu thức chính quy (Regular Expression) được sử dụng để làm gì trong khoa học máy tính?
A. Mô tả ngôn ngữ lập trình bậc cao.
B. Mô tả các ngôn ngữ hình thức, đặc biệt là ngôn ngữ chính quy.
C. Thiết kế cơ sở dữ liệu quan hệ.
D. Phát triển giao diện người dùng đồ họa.
17. Cho mệnh đề P: 'Nếu trời mưa thì đường ướt'. Mệnh đề phản đảo (contrapositive) của P là gì?
A. Nếu trời không mưa thì đường không ướt.
B. Nếu đường ướt thì trời mưa.
C. Nếu đường không ướt thì trời không mưa.
D. Nếu trời mưa thì đường không ướt.
18. Trong lý thuyết đồ thị, hai đồ thị được gọi là đẳng cấu (isomorphic) nếu:
A. Chúng có cùng số đỉnh và số cạnh.
B. Chúng có cùng bậc cho tất cả các đỉnh tương ứng.
C. Chúng có thể được vẽ giống nhau trên mặt phẳng.
D. Có một song ánh giữa tập đỉnh của chúng sao cho bảo toàn tính kề nhau (adjacency).
19. Trong logic mệnh đề, phép toán nào sau đây có tính giao hoán?
A. Hàm ý (→)
B. Phủ định (¬)
C. Hội (∧)
D. Kéo theo logic (⇒)
20. 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
B. n-1
C. n(n-1)/2
D. n^2
21. Phát biểu nào sau đây là đúng về quan hệ tương đương?
A. Quan hệ tương đương chỉ cần có tính phản xạ và đối xứng.
B. Quan hệ tương đương cần có tính phản xạ, đối xứng và bắc cầu.
C. Quan hệ tương đương chỉ cần có tính đối xứng và bắc cầu.
D. Quan hệ tương đương cần có tính phản xạ và bắc cầu, nhưng không cần đối xứng.
22. Trong tổ hợp, chỉnh hợp chập k của n phần tử (k ≤ n) 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ả chỉnh hợp và tổ hợp đều quan tâm đến thứ tự.
C. Chỉnh hợp quan tâm đến thứ tự, tổ hợp không quan tâm đến thứ tự.
D. Cả chỉnh hợp và tổ hợp đều không quan tâm đến thứ tự.
23. Trong đại số Boolean, luật De Morgan phát biểu điều gì?
A. Phủ định của phép hội tương đương với hội của các phủ định.
B. Phủ định của phép tuyển tương đương với tuyển của các phủ định.
C. Phủ định của phép hội tương đương với tuyển của các phủ định.
D. Phủ định của phép tuyển tương đương với hội của các tuyển.
24. Phát biểu nào sau đây SAI về phép kéo theo logic (logical implication - ⇒)?
A. Nếu p ⇒ q đúng và p đúng, thì q phải đúng (Modus Ponens).
B. Nếu p ⇒ q đúng và q sai, thì p phải sai (Modus Tollens).
C. Nếu p sai, thì p ⇒ q luôn đúng, bất kể giá trị chân lý của q.
D. Nếu q đúng, thì p ⇒ q luôn sai, bất kể giá trị chân lý của p.
25. Trong lý thuyết đồ thị, một đồ thị phẳng là đồ thị có thể được vẽ trên mặt phẳng sao cho:
A. Các cạnh không giao nhau tại bất kỳ điểm nào ngoài các đỉnh của chúng.
B. Mọi đỉnh đều có bậc chẵn.
C. Đồ thị là liên thông.
D. Đồ thị có chu trình Hamilton.
26. Ứng dụng nào sau đây KHÔNG phải là ứng dụng trực tiếp của lý thuyết đồ thị?
A. Mạng máy tính và Internet.
B. Thiết kế mạch điện tử.
C. Phân tích mạng xã hội.
D. Giải tích vi phân và tích phân.
27. Đồ thị vô hướng G = (V, E) được gọi là đồ thị Euler nếu:
A. Mọi đỉnh trong đồ thị đều có bậc chẵn.
B. Đồ thị là liên thông và mọi đỉnh có bậc chẵn.
C. Đồ thị có chứa chu trình Hamilton.
D. Đồ thị là cây.
28. Phép tuyển (OR) trong đại số Boolean tương ứng với phép toán nào trong lý thuyết tập hợp?
A. Giao (Intersection - ∩)
B. Hợp (Union - ∪)
C. Hiệu (Difference - )
D. Bù (Complement - ')
29. Trong lý thuyết automata, DFA (Deterministic Finite Automaton) và NFA (Non-deterministic Finite Automaton) khác nhau cơ bản ở đ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ể có chuyển trạng thái rỗng (ε-transitions), NFA thì không.
C. Từ một trạng thái và một ký tự đầu vào, DFA chỉ có duy nhất một trạng thái chuyển tiếp tiếp theo, trong khi NFA có thể có nhiều hoặc không có trạng thái chuyển tiếp.
D. NFA mạnh mẽ hơn DFA trong việc nhận dạng ngôn ngữ chính quy.
30. Trong các hệ đếm cơ số, hệ đếm nào sau đây sử dụng 16 ký hiệu (từ 0-9 và A-F)?
A. Hệ nhị phân (Binary - cơ số 2).
B. Hệ thập phân (Decimal - cơ số 10).
C. Hệ bát phân (Octal - cơ số 8).
D. Hệ thập lục phân (Hexadecimal - cơ số 16).
