1. Một đồ thị vô hướng được gọi là liên thông nếu…
A. Mỗi đỉnh có bậc ít nhất là 1
B. Có một đường đi giữa mọi cặp đỉnh phân biệt
C. Không có chu trình
D. Số đỉnh bằng số cạnh trừ 1
2. Một đồ thị Euler là đồ thị có tính chất nào?
A. Có một chu trình Hamilton
B. Có một đường đi Hamilton
C. Có một chu trình Euler
D. Có một đường đi Euler nhưng không có chu trình Euler
3. Trong đại số Boolean, định luật hấp thụ phát biểu điều gì?
A. x + (x × y) = x
B. x × (x + y) = y
C. x + (¬x × y) = x + y
D. x × (¬x + y) = x × y
4. Hàm số f(n) = O(g(n)) (Big O notation) có nghĩa là gì?
A. f(n) luôn nhỏ hơn g(n) với mọi n
B. f(n) lớn hơn hoặc bằng g(n) với mọi n đủ lớn
C. f(n) nhỏ hơn hoặc bằng c*g(n) với một hằng số c dương nào đó và mọi n đủ lớn
D. f(n) bằng g(n) với mọi n
5. Hàm số f: A → B được gọi là đơn ánh (injective) khi nào?
A. Mỗi phần tử của B có ít nhất một phần tử của A ánh xạ đến
B. Mỗi phần tử của B có nhiều nhất một phần tử của A ánh xạ đến
C. Mỗi phần tử của A ánh xạ đến một phần tử duy nhất của B
D. Mỗi phần tử của B có đúng một phần tử của A ánh xạ đến
6. Đâu là ứng dụng chính của lý thuyết đồ thị trong khoa học máy tính?
A. Phân tích dữ liệu tài chính
B. Mô hình hóa mạng lưới, đường đi và quan hệ giữa các đối tượng
C. Dự báo thời tiết
D. Thiết kế mạch điện tử analog
7. Trong đồ thị vô hướng, bậc của một đỉnh được định nghĩa là gì?
A. Số cạnh liên thuộc với đỉnh đó
B. Số đỉ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. Độ dài đường đi ngắn nhất từ đỉnh đó đến đỉnh khác
8. Trong tổ hợp, `chỉnh hợp chập k của n′ (permutation of n taken k) dùng để tính số cách chọn và sắp xếp thứ tự như thế nào?
A. Chọn k phần tử từ n phần tử, không quan tâm thứ tự
B. Chọn k phần tử từ n phần tử, có quan tâm thứ tự
C. Chọn n phần tử từ k phần tử, có quan tâm thứ tự
D. Chia n phần tử thành k nhóm
9. Trong logic mệnh đề, luật De Morgan phát biểu điều gì?
A. Phủ định của phép hội là phép tuyển của các phủ định
B. Phủ định của phép tuyển là phép hội của các phủ định
C. Cả hai đáp án 1 và 2 đều đúng
D. Cả hai đáp án 1 và 2 đều sai
10. 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 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 nghiệm cho một phương trình
D. Tính duy nhất của một nghiệm cho một phương trình
11. Thuật toán Kruskal được sử dụng để tìm…
A. Đường đi ngắn nhất giữa hai đỉnh
B. Cây khung tối thiểu (MST)
C. Chu trình Hamilton
D. Chu trình Euler
12. Phương pháp đếm cơ bản nào được sử dụng để tính số cách thực hiện một chuỗi các công việc độc lập?
A. Nguyên lý cộng
B. Nguyên lý nhân
C. Nguyên lý bù trừ
D. Nguyên lý Dirichlet
13. Nguyên lý chuồng bồ câu (Pigeonhole Principle) phát biểu điều gì?
A. Nếu có n vật và m hộp đựng, với n > m, thì có ít nhất một hộp chứa ít nhất hai vật
B. Nếu có n vật và m hộp đựng, với n < m, thì có ít nhất một hộp rỗng
C. Nếu có n vật và n hộp đựng, thì mỗi hộp chứa đúng một vật
D. Số vật luôn bằng số hộp
14. Tính chất bắc cầu (transitive) của một quan hệ R trên tập A được định nghĩa như thế nào?
A. Nếu aRb thì bRa
B. Nếu aRa với mọi a thuộc A
C. Nếu aRb và bRc thì aRc
D. Nếu aRb và aRc thì bRc
15. Trong lý thuyết tập hợp, tập lũy thừa (power set) của một tập A là gì?
A. Tập hợp chứa tất cả các phần tử của A
B. Tập hợp chứa tất cả các tập con của A
C. Tập hợp các số nguyên tố nhỏ hơn các phần tử của A
D. Tập hợp các hoán vị của các phần tử trong A
16. Ứng dụng nào sau đây KHÔNG phải là ứng dụng trực tiếp của toán rời rạc?
A. Thiết kế thuật toán và phân tích độ phức tạp
B. Mật mã học và an toàn thông tin
C. Xử lý tín hiệu analog
D. Lý thuyết cơ sở dữ liệu
17. Quan hệ R trên tập hợp A được gọi là quan hệ tương đương khi nó đồng thời có các tính chất nào sau đây?
A. Phản xạ, đối xứng, bắc cầu
B. Phản xạ, phản đối xứng, bắc cầu
C. Đối xứng, phản đối xứng, bắc cầu
D. Phản xạ, đối xứng, phản bắc cầu
18. Trong mật mã học, hàm băm (hash function) lý tưởng có tính chất nào quan trọng nhất?
A. Dễ dàng đảo ngược (reverse)
B. Khó đảo ngược (preimage resistance)
C. Luôn tạo ra giá trị băm có độ dài ngắn
D. Giá trị băm phải dễ đoán
19. Trong lý thuyết đồ thị, đồ thị lưỡng phân (bipartite graph) là đồ thị mà tập đỉnh có thể chia thành hai tập rời nhau sao cho…
A. Các đỉnh trong cùng một tập luôn kề nhau
B. Các đỉnh trong cùng một tập không kề nhau
C. Có một chu trình Euler
D. Có một chu trình Hamilton
20. Đường đi Hamilton trong đồ thị là gì?
A. Đường đi thăm mỗi cạnh đúng một lần
B. Đường đi thăm mỗi đỉnh đúng một lần
C. Chu trình thăm mỗi cạnh đúng một lần
D. Chu trình thăm mỗi đỉnh đúng một lần
21. Cây khung tối thiểu (Minimum Spanning Tree - MST) của một đồ thị liên thông có trọng số là gì?
A. Một cây con 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. Một cây con chứa tất cả các đỉnh của đồ thị và có tổng trọng số cạnh nhỏ nhất
C. Một chu trình đi qua tất cả các đỉnh của đồ thị với tổng trọng số cạnh nhỏ nhất
D. Một đường đi dài nhất giữa hai đỉnh bất kỳ trong đồ thị
22. 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ó cạnh nào cắt nhau (ngoại trừ tại các đỉnh)
C. Tất cả các đỉnh đều nằm trên một đường thẳng
D. Số đỉnh bằng số cạnh
23. Trong logic vị từ, lượng từ `∀` (với mọi) có nghĩa là gì?
A. Tồn tại ít nhất một
B. Với mọi
C. Không tồn tại
D. Có duy nhất một
24. Trong lý thuyết số, thuật toán Euclid được sử dụng để tìm gì?
A. Bội chung nhỏ nhất (BCNN) của hai số
B. Ước chung lớn nhất (ƯCLN) của hai số
C. Số nguyên tố lớn nhất nhỏ hơn một số cho trước
D. Phân tích thừa số nguyên tố của một số
25. Trong lý thuyết tập hợp, phép toán nào sau đây trả về một tập hợp chứa tất cả các phần tử thuộc ít nhất một trong hai tập hợp đầu vào?
A. Giao
B. Hợp
C. Hiệu
D. Tích Descartes
26. Mệnh đề `Nếu trời mưa thì đường ướt′ tương đương logic với mệnh đề nào sau đây?
A. Nếu đường ướt thì trời mưa
B. Nếu trời không mưa thì đường không ướt
C. Nếu đường không ướt thì trời không mưa
D. Trời mưa và đường ướt
27. Số Fibonacci thứ n, Fn<∕sub>, thường được định nghĩa đệ quy như thế nào (với F0<∕sub> = 0, F1<∕sub> = 1)?
A. Fn<∕sub> = Fn-1<∕sub> - Fn-2<∕sub>
B. Fn<∕sub> = Fn-1<∕sub> + Fn-2<∕sub>
C. Fn<∕sub> = 2 × Fn-1<∕sub>
D. Fn<∕sub> = Fn-1<∕sub>2<∕sup>
28. Biểu thức chính tắc tuyển (Disjunctive Normal Form - DNF) của một hàm Boolean là gì?
A. Tổng của các minterm
B. Tích của các maxterm
C. Biểu thức đơn giản nhất của hàm Boolean
D. Biểu thức chỉ chứa phép AND và NOT
29. Trong lý thuyết automata, DFA (Deterministic Finite Automaton) là gì?
A. Một loại máy tính có khả năng học hỏi
B. Một mô hình máy trạng thái hữu hạn xác định
C. Một loại ngôn ngữ lập trình bậc cao
D. Một cơ sở dữ liệu quan hệ
30. 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
