1. Độ phức tạp thuật toán của việc tìm phần tử lớn nhất trong một mảng chưa sắp xếp là bao nhiêu?
A. O(1)
B. O(log n)
C. O(n)
D. O(n^2)
2. Độ phức tạp thuật toán của việc kiểm tra xem một số có phải là số nguyên tố hay không bằng cách thử chia cho tất cả các số từ 2 đến căn bậc hai của số đó là bao nhiêu?
A. O(1)
B. O(log n)
C. O(sqrt(n))
D. O(n)
3. Khi đánh giá thuật toán, "trường hợp xấu nhất" (worst-case) đề cập đến tình huống nào?
A. Tình huống mà thuật toán chạy nhanh nhất.
B. Tình huống mà thuật toán yêu cầu lượng bộ nhớ tối thiểu.
C. Tình huống mà thuật toán yêu cầu thời gian hoặc không gian sử dụng tối đa.
D. Tình huống mà thuật toán sử dụng ít lệnh nhất.
4. Độ phức tạp của việc duyệt qua tất cả các phần tử trong một ma trận vuông kích thước n x n là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(2^n)
5. Độ phức tạp thuật toán của việc tìm kiếm một phần tử trong một bảng băm (hash table) có hàm băm tốt và không xung đột (collision) là bao nhiêu?
A. O(n)
B. O(n^2)
C. O(log n)
D. O(1)
6. Độ phức tạp thuật toán của việc sắp xếp một mảng bằng thuật toán Heap Sort là bao nhiêu trong trường hợp xấu nhất?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
7. Tại sao thuật toán đệ quy Fibonacci (tính F(n) = F(n-1) + F(n-2)) lại có độ phức tạp cao?
A. Vì nó chỉ thực hiện một vài phép cộng.
B. Vì nó tính toán lại các giá trị Fibonacci đã biết nhiều lần.
C. Vì nó sử dụng quá ít bộ nhớ.
D. Vì nó yêu cầu truy cập dữ liệu từ ngoài.
8. Độ phức tạp của thuật toán sắp xếp nổi bọt (Bubble Sort) trong trường hợp xấu nhất là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
9. Việc sử dụng cấu trúc dữ liệu nào có thể ảnh hưởng đến độ phức tạp của thuật toán?
A. Chỉ các cấu trúc dữ liệu lớn.
B. Chỉ các cấu trúc dữ liệu phức tạp.
C. Tất cả các cấu trúc dữ liệu, vì cách tổ chức và truy cập dữ liệu ảnh hưởng đến hiệu quả thao tác.
D. Không có cấu trúc dữ liệu nào ảnh hưởng đến độ phức tạp.
10. Tại sao việc đánh giá thuật toán lại quan trọng trong khoa học máy tính?
A. Để đảm bảo thuật toán luôn chạy đúng trong mọi trường hợp.
B. Để lựa chọn thuật toán hiệu quả nhất về thời gian và không gian cho một bài toán cụ thể.
C. Để làm cho mã nguồn dễ đọc và dễ bảo trì hơn.
D. Để giảm thiểu số lượng dòng code.
11. Độ phức tạp của thuật toán sắp xếp trộn (Merge Sort) trong mọi trường hợp (tốt nhất, trung bình, xấu nhất) là bao nhiêu?
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)
12. Cân nhắc thuật toán tìm kiếm nhị phân. Nếu mảng có 16 phần tử, số lần so sánh tối đa cần thiết là bao nhiêu?
A. 4
B. 8
C. 16
D. Log2(16)
13. Độ phức tạp tính toán của một thuật toán được đánh giá dựa trên yếu tố nào là chính?
A. Chất lượng mã nguồn và độ dễ đọc.
B. Số lượng lệnh cần thực hiện theo thời gian chạy trên một máy tính cụ thể.
C. Số lượng lệnh cần thực hiện phụ thuộc vào kích thước của dữ liệu đầu vào.
D. Tốc độ xử lý của phần cứng máy tính.
14. Ký hiệu "O(n)" trong đánh giá độ phức tạp thuật toán cho biết điều gì?
A. Thuật toán có độ phức tạp không đổi, không phụ thuộc đầu vào.
B. Thời gian chạy của thuật toán tăng tuyến tính với kích thước dữ liệu đầu vào.
C. Thời gian chạy của thuật toán tăng theo bình phương kích thước dữ liệu đầu vào.
D. Thời gian chạy của thuật toán tăng theo logarit kích thước dữ liệu đầu vào.
15. Thuật toán nào có độ phức tạp thời gian tốt nhất cho việc sắp xếp một mảng lớn các phần tử?
A. Sắp xếp chọn (Selection Sort)
B. Sắp xếp chèn (Insertion Sort)
C. Sắp xếp nhanh (Quick Sort) hoặc Sắp xếp trộn (Merge Sort)
D. Sắp xếp bong bóng (Bubble Sort)
16. Tại sao thuật toán đệ quy đôi khi có thể gặp vấn đề về hiệu suất?
A. Vì nó sử dụng quá nhiều biến cục bộ.
B. Vì nó có thể tạo ra nhiều lời gọi hàm lặp lại, tốn bộ nhớ ngăn xếp và thời gian xử lý.
C. Vì nó luôn có độ phức tạp cao hơn thuật toán lặp.
D. Vì nó không thể xử lý dữ liệu lớn.
17. Khi đánh giá thuật toán, "trường hợp trung bình" (average-case) đề cập đến điều gì?
A. Tình huống mà thuật toán chạy nhanh nhất.
B. Tình huống mà thuật toán yêu cầu thời gian hoặc không gian sử dụng trung bình trên tất cả các đầu vào có thể.
C. Tình huống mà thuật toán yêu cầu lượng bộ nhớ tối thiểu.
D. Tình huống mà thuật toán gặp ít lỗi nhất.
18. Yếu tố nào sau đây KHÔNG được xem là tiêu chí chính để đánh giá một thuật toán?
A. Độ phức tạp thời gian.
B. Độ phức tạp không gian.
C. Tính đúng đắn (correctness).
D. Số lượng dòng code.
19. Độ phức tạp thuật toán của việc thêm một phần tử vào cuối một danh sách liên kết đơn (singly linked list) là bao nhiêu, nếu ta có con trỏ đến cuối danh sách?
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
20. Độ phức tạp không gian (space complexity) của một thuật toán đề cập đến điều gì?
A. Thời gian tối đa mà thuật toán cần để hoàn thành.
B. Lượng bộ nhớ (RAM hoặc không gian lưu trữ) mà thuật toán sử dụng.
C. Số lượng các phép toán số học mà thuật toán thực hiện.
D. Số lượng các biến được khai báo trong mã nguồn.
21. Độ phức tạp O(1) có nghĩa là gì?
A. Thời gian chạy tăng theo bình phương kích thước dữ liệu.
B. Thời gian chạy tăng theo logarit kích thước dữ liệu.
C. Thời gian chạy không phụ thuộc vào kích thước dữ liệu.
D. Thời gian chạy tăng tuyến tính với kích thước dữ liệu.
22. Khi so sánh hai thuật toán cùng giải quyết một bài toán, nếu thuật toán A có độ phức tạp O(n) và thuật toán B có độ phức tạp O(n^2), thì thuật toán nào thường được ưu tiên hơn cho tập dữ liệu lớn?
A. Thuật toán A, vì nó hiệu quả hơn khi n lớn.
B. Thuật toán B, vì nó đơn giản hơn.
C. Cả hai đều như nhau.
D. Phụ thuộc vào ngôn ngữ lập trình.
23. Một thuật toán có độ phức tạp O(n^2) sẽ như thế nào khi kích thước dữ liệu đầu vào tăng gấp đôi?
A. Thời gian chạy sẽ tăng gấp đôi.
B. Thời gian chạy sẽ tăng gấp bốn lần.
C. Thời gian chạy sẽ giảm một nửa.
D. Thời gian chạy sẽ giữ nguyên.
24. Thuật toán nào sau đây thường có độ phức tạp thấp nhất đối với việc tìm kiếm một phần tử trong một mảng đã được sắp xếp?
A. Tìm kiếm tuần tự (Linear Search).
B. Tìm kiếm nhị phân (Binary Search).
C. Tìm kiếm nội suy (Interpolation Search).
D. Tìm kiếm nhảy (Jump Search).
25. Trong trường hợp nào, một thuật toán O(n log n) được coi là hiệu quả hơn một thuật toán O(n^2) cho cùng một bài toán?
A. Khi kích thước dữ liệu đầu vào rất nhỏ.
B. Khi kích thước dữ liệu đầu vào lớn.
C. Khi thuật toán O(n^2) sử dụng ít bộ nhớ hơn.
D. Khi thuật toán O(n log n) khó cài đặt hơn.
