1. Hệ đếm cơ số 16 còn được gọi là hệ đếm gì?
A. Nhị phân
B. Thập phân
C. Bát phân
D. Hexadecimal
2. Trong một đồ thị vô hướng liên thông, điều kiện cần và đủ để có đường đi Hamilton là gì?
A. Tất cả các đỉnh có bậc chẵn
B. Đồ thị phải là cây
C. Không có điều kiện cần và đủ đơn giản đã được biết đến; bài toán tìm đường đi Hamilton là NP-complete
D. Đồ thị phải phẳng
3. Hàm f(x) = 3x + 5 có phải là song ánh (bijective) từ tập số thực R vào R không?
A. Không, vì nó không đơn ánh
B. Không, vì nó không toàn ánh
C. Có, vì nó vừa đơn ánh vừa toàn ánh
D. Không xác định
4. 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ể cho một trường hợp
B. Tính đúng đắn của 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. Tính sai của một mệnh đề cho ít nhất một trường hợp
D. Tính đúng đắn của một mệnh đề chỉ cho một số hữu hạn trường hợp
5. Trong lý thuyết đồ thị, bậc của một đỉnh được định nghĩa là gì?
A. Số đỉnh kề với đỉnh đó
B. Số cạnh liên thuộc với đỉnh đó
C. Số đường đi ngắn nhất từ đỉnh đó đến đỉnh khác
D. Tổng trọng số của các cạnh liên thuộc với đỉnh đó
6. Trong một nhóm 10 người, cần chọn ra 3 người để thành lập một ban đại diện. Có bao nhiêu cách chọn?
A. 10!
B. 10^3
C. P(10, 3)
D. C(10, 3)
7. Cho hàm f(x) = x^2 và g(x) = 2x + 1. Hàm hợp (f ∘ g)(x) bằng biểu thức nào?
A. 2x^2 + 1
B. (2x + 1)^2
C. x^2(2x + 1)
D. 2x^3 + x^2
8. Số hoán vị của n phần tử khác nhau được tính bằng công thức nào?
A. n!
B. 2^n
C. n^2
D. n * (n-1) / 2
9. Số tổ hợp chập k của n phần tử, ký hiệu C(n, k) hoặc <0xE2><0x81><0xB5>₋n<0xE2><0x82><0x8D>k<0xE2><0x82><0x89>, được tính bằng công thức nào?
A. n! / k!
B. n! / (n-k)!
C. n! / (k! * (n-k)!)
D. k! / (n! * (n-k)!)
10. Thuật toán Euclid được sử dụng để tìm gì?
A. Ước chung nhỏ nhất của hai số nguyên
B. Bội chung lớn nhất của hai số nguyên
C. Ước chung lớn nhất của hai số nguyên
D. Bội chung nhỏ nhất của ba số nguyên
11. Trong logic vị từ, lượng từ nào sau đây biểu thị 'tồn tại ít nhất một'?
A. ∀ (lượng từ phổ dụng)
B. ∃ (lượng từ tồn tại)
C. ¬ (phủ định)
D. ∧ (và)
12. Đếm số cạnh trong một đồ thị đầy đủ Kn với n đỉnh.
A. n
B. n-1
C. n(n-1)/2
D. n^2
13. Trong lý thuyết tập hợp, phép toán nào sau đây cho phép tạo ra một tập hợp mới chứa các phần tử thuộc cả hai tập hợp ban đầu?
A. Phép hợp
B. Phép giao
C. Phép hiệu
D. Phép bù
14. Độ phức tạp thời gian tốt nhất của thuật toán tìm kiếm nhị phân (binary search) là gì?
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
15. Trong số học modular, 7 đồng dư với số nào sau đây modulo 3?
16. Trong đại số Boole, luật hấp thụ 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
17. Cho tập hợp A = {1, 2, 3}. Số quan hệ hai ngôi có thể định nghĩa trên tập A là bao nhiêu?
A. 3
B. 2^3
C. 2^9
D. 3^2
18. Phát biểu nào sau đây là đúng về đồ thị Euler?
A. Đồ thị Euler luôn chứa chu trình Hamilton
B. Đồ thị Euler có một chu trình đi qua tất cả các cạnh, mỗi cạnh đúng một lần
C. Đồ thị Euler không thể chứa chu trình
D. Đồ thị Euler là đồ thị phẳng
19. Quan hệ R trên tập A là quan hệ tương đương khi và chỉ khi nó đồng thời có các tính chất nào?
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
20. Phát biểu nào sau đây là đúng về quan hệ thứ tự bộ phận?
A. Quan hệ thứ tự bộ phận bắt buộc phải là quan hệ toàn phần
B. Quan hệ thứ tự bộ phận phải phản xạ, phản đối xứng và bắc cầu
C. Quan hệ thứ tự bộ phận chỉ cần phản xạ và bắc cầu
D. Quan hệ thứ tự bộ phận chỉ cần phản đối xứng và bắc cầu
21. Giá trị của biểu thức (5 + 7) mod 8 là bao nhiêu?
22. Phát biểu nào sau đây là sai về cây?
A. Cây là đồ thị liên thông
B. Cây không chứa chu trình
C. Giữa hai đỉnh bất kỳ trong cây có duy nhất một đường đi
D. Cây có thể chứa chu trình
23. 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 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. Trời mưa và đường ướt
24. Một hàm f: A → B được gọi là đơn ánh (injective) nếu thỏa mãn điều kiện nào?
A. Với mọi x, y thuộc A, nếu f(x) = f(y) thì x = y
B. Với mọi y thuộc B, tồn tại x thuộc A sao cho f(x) = y
C. Với mọi x thuộc A, tồn tại duy nhất y thuộc B sao cho f(x) = y
D. Với mọi x, y thuộc A, nếu x ≠ y thì f(x) = f(y)
25. Số cách chọn k phần tử từ n phần tử có thứ tự (hoán vị) được tính bằng công thức nào?
A. C(n, k)
B. n!
C. P(n, k)
D. k^n
26. Một đồ thị vô hướng được gọi là cây khi nó có tính chất nào sau đây?
A. Liên thông và chứa chu trình
B. Không liên thông và không chứa chu trình
C. Liên thông và không chứa chu trình
D. Không liên thông và chứa chu trình
27. Biểu thức logic nào sau đây tương đương với ¬(p ∧ q)?
A. ¬p ∧ ¬q
B. ¬p ∨ ¬q
C. p ∨ q
D. p ∧ ¬q
28. Trong đại số Boole, biểu thức (A + B) . (A + C) tương đương với biểu thức nào?
A. A + B . C
B. A . (B + C)
C. A + B + C
D. A . B . C
29. Cho tập hợp A = {a, b, c, d}. Xét quan hệ R = {(a, a), (b, b), (c, c), (d, d), (a, b), (b, a)}. 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. Phản xạ, đối xứng và bắc cầu
D. Chỉ đối xứng
30. Một đồ thị phẳng là đồ thị có thể được vẽ trên mặt phẳng sao cho...
A. Các cạnh cắt nhau tại các đỉnh
B. Các cạnh không cắt nhau (ngoại trừ tại các đỉnh)
C. Tất cả các đỉnh nằm trên cùng một đường thẳng
D. Đồ thị có chu trình Euler
