1. Khi phân tích độ phức tạp của thuật toán, ký hiệu Ω (Omega) thường được dùng để chỉ:
A. Độ phức tạp trường hợp xấu nhất.
B. Độ phức tạp trường hợp tốt nhất.
C. Độ phức tạp trường hợp trung bình.
D. Độ phức tạp không gian.
2. Đâu là một ví dụ về trường hợp tốt nhất (best-case) khi đánh giá một thuật toán tìm kiếm tuyến tính?
A. Phần tử cần tìm nằm ở cuối danh sách.
B. Phần tử cần tìm nằm ở đầu danh sách.
C. Phần tử cần tìm không có trong danh sách.
D. Danh sách có kích thước rất lớn.
3. Trong phân tích thuật toán, ký hiệu Θ (Theta) được dùng để chỉ:
A. Độ phức tạp trường hợp xấu nhất.
B. Độ phức tạp trường hợp tốt nhất.
C. Độ phức tạp trường hợp trung bình.
D. Độ phức tạp mà cả trường hợp xấu nhất và tốt nhất đều có cùng giới hạn trên và dưới là hàm đó.
4. Thuật toán tìm kiếm nhị phân (Binary Search) hoạt động hiệu quả nhất trên loại dữ liệu nào?
A. Danh sách chưa sắp xếp.
B. Danh sách được sắp xếp.
C. Cây nhị phân cân bằng.
D. Mảng liên kết đơn.
5. Phân tích thuật toán giúp chúng ta hiểu rõ điều gì về thuật toán đó?
A. Nó sẽ chạy nhanh như thế nào trên mọi máy tính.
B. Nó tiêu tốn bao nhiêu tài nguyên (thời gian, bộ nhớ) khi kích thước đầu vào thay đổi.
C. Nó có thể xử lý các loại dữ liệu khác nhau hay không.
D. Nó có dễ dàng sửa lỗi hay không.
6. Đâu là một ví dụ về thuật toán có độ phức tạp thời gian O(N log N)?
A. Tìm kiếm tuyến tính.
B. Sắp xếp nhanh (Quick Sort).
C. Sắp xếp nổi bọt (Bubble Sort).
D. Tìm phần tử lớn nhất trong mảng.
7. Đâu là một ví dụ về thuật toán có độ phức tạp thời gian O(log N)?
A. Tìm kiếm tuyến tính.
B. Tìm kiếm nhị phân.
C. Sắp xếp nổi bọt.
D. Duyệt qua tất cả các cặp phần tử trong mảng.
8. Nếu một thuật toán có độ phức tạp thời gian O(N!), điều này có ý nghĩa gì đối với hiệu suất khi N tăng lên?
A. Thời gian chạy tăng rất chậm.
B. Thời gian chạy tăng nhanh một cách chóng mặt, trở nên không khả thi ngay cả với N nhỏ.
C. Thời gian chạy gần như không đổi.
D. Thời gian chạy tăng theo hàm logarit.
9. Khi đánh giá thuật toán, chúng ta thường quan tâm đến độ phức tạp theo trường hợp xấu nhất vì lý do gì?
A. Nó luôn cho kết quả nhanh nhất.
B. Nó đảm bảo thuật toán sẽ không bao giờ vượt quá giới hạn tài nguyên cho phép.
C. Nó dễ tính toán hơn các trường hợp khác.
D. Nó phản ánh hiệu suất tệ nhất có thể xảy ra.
10. Thuật toán đệ quy có thể dẫn đến vấn đề gì nếu không được thiết kế cẩn thận?
A. Tăng độ phức tạp thời gian lên O(N^2).
B. Giảm độ phức tạp không gian.
C. Tràn bộ nhớ (Stack Overflow) do gọi hàm lồng nhau quá sâu.
D. Tăng tốc độ thực thi của chương trình.
11. Độ phức tạp không gian O(1) có nghĩa là gì?
A. Thuật toán sử dụng bộ nhớ tăng theo hàm mũ.
B. Thuật toán sử dụng bộ nhớ không đổi, không phụ thuộc vào kích thước đầu vào.
C. Thuật toán sử dụng bộ nhớ tăng tuyến tính với kích thước đầu vào.
D. Thuật toán không sử dụng bất kỳ bộ nhớ nào.
12. Xét một thuật toán tìm kiếm tuyến tính trên một danh sách chưa được sắp xếp có N phần tử. Trong trường hợp xấu nhất, độ phức tạp thời gian của thuật toán này là bao nhiêu?
A. O(1)
B. O(log N)
C. O(N)
D. O(N^2)
13. Đâu là một ví dụ về trường hợp xấu nhất (worst-case) khi đánh giá một thuật toán sắp xếp mảng?
A. Mảng đã được sắp xếp theo thứ tự tăng dần.
B. Mảng được sắp xếp theo thứ tự giảm dần.
C. Mảng chứa các phần tử ngẫu nhiên.
D. Mảng chỉ chứa một phần tử.
14. Đâu là một ví dụ về thuật toán có độ phức tạp thời gian O(1)?
A. Sắp xếp mảng bằng Quick Sort.
B. Tìm kiếm nhị phân.
C. Truy cập một phần tử trong mảng bằng chỉ số.
D. Tính tổng các phần tử trong danh sách liên kết.
15. Một thuật toán được coi là hiệu quả nếu nó có độ phức tạp thời gian và không gian thuộc loại nào sau đây?
A. O(N^N)
B. O(2^N)
C. O(N log N) hoặc tốt hơn.
D. O(N!)
16. Đâu là một yếu tố quan trọng cần xem xét khi đánh giá thuật toán trong thực tế, ngoài độ phức tạp lý thuyết?
A. Sự phổ biến của ngôn ngữ lập trình được sử dụng.
B. Chi phí bản quyền của phần mềm IDE.
C. Các hệ số hằng và các yếu tố phụ thuộc vào phần cứng cụ thể.
D. Số lượng comment trong mã nguồn.
17. Độ phức tạp thời gian (Time Complexity) của một thuật toán được ký hiệu là gì?
A. O(n^2)
B. O(log n)
C. Ω(n)
D. T(n)
18. Khi so sánh hai thuật toán, nếu thuật toán A có độ phức tạp thời gian là O(N log N) và thuật toán B có độ phức tạp thời gian là O(N^2), trong trường hợp N lớn, thuật toán nào thường hiệu quả hơn?
A. Thuật toán A vì N log N tăng chậm hơn N^2.
B. Thuật toán B vì N^2 tăng chậm hơn N log N.
C. Cả hai thuật toán có hiệu quả tương đương khi N lớn.
D. Không thể xác định nếu không biết chi tiết về các hệ số hằng.
19. Đâu là tiêu chí chính để đánh giá tính hiệu quả của một thuật toán?
A. Số dòng code và độ phức tạp của cú pháp.
B. Thời gian chạy và bộ nhớ sử dụng.
C. Khả năng đọc hiểu và tính thẩm mỹ của mã nguồn.
D. Số lượng biến và cấu trúc dữ liệu được sử dụng.
20. Khi nào thì việc sử dụng thuật toán có độ phức tạp O(N^2) là chấp nhận được?
A. Chỉ khi N rất nhỏ, ví dụ N < 10.
B. Luôn luôn, vì nó dễ cài đặt.
C. Khi N có giá trị rất lớn, ví dụ N > 10^6.
D. Không bao giờ, chỉ nên dùng thuật toán O(N log N) hoặc tốt hơn.
21. Độ phức tạp không gian (Space Complexity) của một thuật toán đánh giá điều gì?
A. Số lượng phép toán mà thuật toán thực hiện.
B. Lượng bộ nhớ mà thuật toán yêu cầu để chạy.
C. Số bước thực thi của thuật toán.
D. Độ dài của mã nguồn thuật toán.
22. Đâu là một ví dụ về thuật toán có độ phức tạp thời gian O(N)?
A. Tìm kiếm nhị phân.
B. Sắp xếp trộn (Merge Sort).
C. Tìm phần tử lớn nhất trong mảng chưa sắp xếp.
D. Sắp xếp nhanh (Quick Sort) trong trường hợp xấu nhất.
23. Yếu tố nào KHÔNG phải là một tiêu chí quan trọng khi đánh giá một thuật toán?
A. Tính đúng đắn (Correctness).
B. Tính hiệu quả (Efficiency) về thời gian và không gian.
C. Tính dễ đọc và dễ bảo trì của mã nguồn.
D. Ngôn ngữ lập trình được sử dụng để triển khai.
24. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân trên một mảng N phần tử là bao nhiêu?
A. O(N)
B. O(N log N)
C. O(log N)
D. O(N^2)
25. Thuật toán sắp xếp nổi bọt (Bubble Sort) có độ phức tạp thời gian trung bình là bao nhiêu?
A. O(N)
B. O(N log N)
C. O(N^2)
D. O(log N)
