1. Cổng logic NAND thực hiện phép toán logic nào?
A. Phép hội (AND)
B. Phép tuyển (OR)
C. Phép kéo theo (implication)
D. Phép phủ định của hội (NOT AND)
2. Biểu thức hậu tố (Reverse Polish Notation - RPN) của biểu thức trung tố (infix) `A + B × C′ là:
A. A B C × +
B. A B + C *
C. + A × B C
D. * + A B C
3. Trong số học modulo, `đồng dư` có nghĩa là:
A. Hai số bằng nhau.
B. Hai số có cùng số dư khi chia cho một số nguyên dương m.
C. Hai số có tích bằng nhau.
D. Hai số có ước chung lớn nhất bằng 1.
4. Tính chất bắc cầu áp dụng cho quan hệ nào sau đây?
A. Quan hệ `là anh∕chị∕em ruột của′
B. Quan hệ `là bạn của′
C. Quan hệ `lớn hơn hoặc bằng′ trên tập số thực
D. Quan hệ `khác′ trên tập số nguyên
5. Số cạnh tối thiểu trong một đồ thị liên thông có n đỉnh là:
A. n
B. n - 1
C. n + 1
D. 2n
6. Cho mệnh đề P: `Trời mưa′ và Q: `Đường ướt′. Mệnh đề `Nếu trời không mưa thì đường không ướt′ được biểu diễn bằng ký hiệu logic nào?
A. P → Q
B. ¬P → ¬Q
C. Q → P
D. ¬Q → ¬P
7. Trong logic mệnh đề, phép toán nào sau đây được sử dụng để biểu thị ý nghĩa `nếu P thì Q′?
A. Phép hội (∧)
B. Phép tuyển (∨)
C. Phép kéo theo (→)
D. Phép phủ định (¬)
8. Cho hàm mệnh đề P(x): `x là số chẵn′. Miền xác định là tập hợp số nguyên Z. Giá trị chân lý của ∀x P(x) là:
A. Đúng
B. Sai
C. Vừa đúng vừa sai
D. Không xác định
9. Có bao nhiêu cách chọn 3 học sinh từ một nhóm 5 học sinh để tham gia đội văn nghệ?
10. Trong combinatorics, `chỉnh hợp′ khác với `tổ hợp′ ở điểm nào?
A. Chỉnh hợp không quan tâm đến thứ tự, tổ hợp có quan tâm.
B. Chỉnh hợp quan tâm đến thứ tự, tổ hợp không quan tâm.
C. Chỉnh hợp không lặp lại phần tử, tổ hợp có thể lặp lại.
D. Chỉnh hợp dùng cho tập vô hạn, tổ hợp dùng cho tập hữu hạn.
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. Trong một nhóm 10 người, bắt tay nhau mỗi người một lần. Hỏi có bao nhiêu cái bắt tay?
13. Phương pháp chứng minh nào thường được sử dụng để chứng minh một mệnh đề đúng cho tất cả các số tự nhiên?
A. Chứng minh trực tiếp
B. Chứng minh phản chứng
C. Chứng minh quy nạp
D. Chứng minh bằng phản ví dụ
14. Trong lý thuyết đồ thị, `bậc của một đỉnh′ là gì?
A. Số đỉnh kề với đỉnh đó.
B. Số cạnh liên thuộc với đỉnh đó.
C. Độ dài đường đi ngắn nhất từ đỉnh đó đến đỉnh khác.
D. Số chu trình đi qua đỉnh đó.
15. Trong một lớp học có 30 học sinh, mỗi học sinh hoặc giỏi Toán hoặc giỏi Văn hoặc giỏi cả hai môn. Biết rằng có 20 học sinh giỏi Toán và 18 học sinh giỏi Văn. Hỏi có bao nhiêu học sinh giỏi cả Toán và Văn?
16. Số nào sau đây là số nguyên tố?
17. 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ổ quát)
B. ∃ (lượng từ tồn tại)
C. ¬ (phủ định)
D. ∧ (hội)
18. Hệ đếm cơ số 16 còn được gọi là hệ đếm:
A. Nhị phân
B. Bát phân
C. Thập phân
D. Hexadecimal
19. Phát biểu nào sau đây là mệnh đề?
A. Hôm nay trời đẹp quá!
B. Bạn có khỏe không?
C. 2 + 2 = 4
D. Hãy đóng cửa sổ!
20. 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. 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 xạ
21. Đồ thị vô hướng được gọi là liên thông nếu:
A. Mỗi đỉnh có bậc lớn hơn 0.
B. Có một đường đi giữa mọi cặp đỉnh phân biệt.
C. Số cạnh bằng số đỉnh trừ 1.
D. Không có chu trình.
22. Phép toán nào sau đây KHÔNG phải là 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 tích Descartes (Cartesian product)
D. Phép tích phân (integration)
23. Trong thuật toán tìm kiếm theo chiều rộng (BFS), cấu trúc dữ liệu nào thường được sử dụng để quản lý các đỉnh cần xé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)
24. Cây là một loại đồ thị đặc biệt. Phát biểu nào sau đây KHÔNG đúng về cây?
A. Cây là đồ thị liên thông.
B. Cây không có chu trình.
C. Trong cây, giữa hai đỉnh bất kỳ luôn có duy nhất một đường đi.
D. Cây có thể có chu trình.
25. Cho tập hợp A = {a, b, c}. Số tập con của tập A là:
26. Thuật toán nào sau đây thường được sử dụng để tìm đường đi ngắn nhất giữa hai đỉnh trong một đồ thị có trọng số dương?
A. Thuật toán Prim
B. Thuật toán Kruskal
C. Thuật toán Dijkstra
D. Thuật toán Floyd-Warshall
27. Cho hàm băm h(x) = x mod 7. Giá trị băm của khóa 23 là:
28. Quan hệ nào sau đây là một hàm từ tập hợp A sang tập hợp B?
A. {(1, a), (1, b), (2, c)}
B. {(1, a), (2, b), (3, c)}
C. {(a, 1), (b, 2), (c, 3), (d, 4)} nếu A = {a, b, c, d}, B = {1, 2, 3, 4}
D. {(1, a), (2, a), (2, b)}
29. Cho đồ thị G có ma trận kề A. Phần tử A[i, j] của ma trận kề biểu thị điều gì?
A. Trọng số của cạnh nối đỉnh i và đỉnh j.
B. Số lượng đường đi từ đỉnh i đến đỉnh j.
C. Có tồn tại cạnh nối đỉnh i và đỉnh j hay không.
D. Bậc của đỉnh i.
30. Cho tập hợp A = {1, 2, 3, 4, 5} và B = {3, 5, 6, 7}. Tập hợp giao của A và B (A ∩ B) là:
A. {1, 2, 3, 4, 5, 6, 7}
B. {1, 2, 4, 6, 7}
C. {3, 5}
D. {}
