[KNTT] Trắc nghiệm Tin học 11 KHMT bài 25 Xác định độ phức tạp thời gian thuộc toán

1. Độ phức tạp không gian (space complexity) của một thuật toán đo lường điều gì?

A. Thời gian chạy của thuật toán.

B. Lượng bộ nhớ mà thuật toán yêu cầu để chạy.

C. Số lượng phép toán mà thuật toán thực hiện.

D. Độ phức tạp của logic thuật toán.

2. Khi phân tích độ phức tạp thời gian, ký hiệu Big O (O(...)) biểu thị điều gì?

A. Thời gian chạy chính xác của thuật toán.

B. Giới hạn trên của thời gian chạy của thuật toán khi kích thước đầu vào tăng lên.

C. Thời gian chạy trung bình của thuật toán.

D. Thời gian chạy ít nhất của thuật toán.

3. Độ phức tạp thời gian O(N) có nghĩa là gì?

A. Thời gian chạy tăng gấp đôi khi N tăng gấp đôi.

B. Thời gian chạy không đổi bất kể N.

C. Thời gian chạy tăng theo bình phương khi N tăng gấp đôi.

D. Thời gian chạy giảm khi N tăng.

4. Độ phức tạp thời gian O(N log N) thường thấy ở các thuật toán nào sau đây?

A. Tìm kiếm tuần tự, sắp xếp nổi bọt.

B. Tìm kiếm nhị phân.

C. Sắp xếp trộn (Merge Sort), sắp xếp nhanh (Quick Sort) trong trường hợp trung bình.

D. Truy cập một phần tử mảng bằng chỉ số.

5. Độ phức tạp thời gian của thuật toán tìm kiếm nhị phân trên một danh sách đã sắp xếp có N phần tử là bao nhiêu trong trường hợp xấu nhất?

A. O(N)

B. O(N^2)

C. O(log N)

D. O(1)

6. Thuật toán sắp xếp nhanh (Quick Sort) có độ phức tạp thời gian trung bình là bao nhiêu?

A. O(N^2)

B. O(N)

C. O(log N)

D. O(N log N)

7. Đâu là một ví dụ về thuật toán có độ phức tạp thời gian O(log N)?

A. Sắp xếp nổi bọt.

B. Tìm kiếm một phần tử trong danh sách đã sắp xếp bằng tìm kiếm nhị phân.

C. Duyệt qua tất cả các phần tử của danh sách.

D. Thực hiện phép nhân hai ma trận.

8. Khi phân tích thuật toán, trường hợp xấu nhất (worst-case) đề cập đến tình huống nào?

A. Thời gian chạy nhanh nhất có thể.

B. Thời gian chạy trung bình.

C. Tình huống mà thuật toán tiêu tốn nhiều thời gian hoặc tài nguyên nhất.

D. Tình huống mà thuật toán tiêu tốn ít thời gian hoặc tài nguyên nhất.

9. Đâu là một ví dụ về thuật toán có độ phức tạp thời gian O(log N)?

A. Duyệt qua tất cả các phần tử của mảng.

B. Tìm kiếm một phần tử trong cây tìm kiếm nhị phân cân bằng.

C. Sắp xếp mảng bằng thuật toán Quick Sort.

D. Thực hiện phép cộng hai số.

10. Độ phức tạp thời gian của thuật toán tìm kiếm tuyến tính (Linear Search) khi phần tử cần tìm nằm ở cuối danh sách có N phần tử là bao nhiêu?

A. O(log N)

B. O(N)

C. O(1)

D. O(N^2)

11. Thuật toán sắp xếp nổi bọt (Bubble Sort) thực hiện bao nhiêu lượt so sánh và đổi chỗ tối đa trong trường hợp xấu nhất để sắp xếp một mảng có N phần tử?

A. O(N)

B. O(log N)

C. O(N^2)

D. O(N log N)

12. Trong phân tích thuật toán, trường hợp trung bình (average-case) đề cập đến điều gì?

A. Thời gian chạy ít nhất có thể.

B. Thời gian chạy phụ thuộc vào một cấu hình đầu vào cụ thể.

C. Thời gian chạy trung bình trên tất cả các đầu vào có thể, với giả định về phân phối xác suất của các đầu vào đó.

D. Thời gian chạy nhiều nhất có thể.

13. Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trên một danh sách không sắp xếp có N phần tử là bao nhiêu trong trường hợp xấu nhất?

A. O(log N)

B. O(N^2)

C. O(N)

D. O(1)

14. Độ phức tạp thời gian của một thuật toán đệ quy thường được phân tích bằng phương pháp nào?

A. Phân tích trường hợp xấu nhất.

B. Phân tích trường hợp trung bình.

C. Sử dụng định lý Master (Master Theorem).

D. Sử dụng biểu đồ Gantt.

15. Một thuật toán có độ phức tạp thời gian O(N^2) sẽ có hiệu suất như thế nào khi N tăng gấp đôi?

A. Thời gian chạy tăng gấp đôi.

B. Thời gian chạy tăng gấp bốn lần.

C. Thời gian chạy tăng gấp đôi logarit.

D. Thời gian chạy không thay đổi đáng kể.

16. Khi N là rất nhỏ, thuật toán có độ phức tạp thời gian O(N^2) có thể chạy nhanh hơn thuật toán O(N log N) không?

A. Không, O(N) luôn nhanh hơn O(N^2).

B. Có, do các hằng số ẩn và chi phí ban đầu của thuật toán O(N log N) có thể cao hơn.

C. Chỉ khi N = 1.

D. Không, vì độ phức tạp thời gian chỉ quan tâm đến khi N tiến ra vô cùng.

17. Độ phức tạp thời gian của thuật toán sắp xếp chọn (Selection 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)

18. Xét một cấu trúc dữ liệu cho phép thêm phần tử vào cuối danh sách với độ phức tạp O(1) và xóa phần tử ở đầu danh sách với độ phức tạp O(1). Nếu ta thực hiện N phép thêm và N phép xóa, tổng độ phức tạp thời gian là bao nhiêu?

A. O(N^2)

B. O(log N)

C. O(N)

D. O(1)

19. Độ phức tạp thời gian của việc truy cập một phần tử trong mảng bằng chỉ số (ví dụ: `my_array[i]`) là bao nhiêu?

A. O(N)

B. O(log N)

C. O(N^2)

D. O(1)

20. Độ phức tạp thời gian O(1) có nghĩa là gì?

A. Thời gian chạy phụ thuộc tuyến tính vào kích thước đầu vào.

B. Thời gian chạy không phụ thuộc vào kích thước đầu vào.

C. Thời gian chạy phụ thuộc vào logarit của kích thước đầu vào.

D. Thời gian chạy phụ thuộc vào bình phương của kích thước đầu vào.

21. Khi phân tích độ phức tạp thời gian, trường hợp tốt nhất (best-case) đề cập đến tình huống nào?

A. Thời gian chạy nhiều nhất có thể.

B. Thời gian chạy trung bình.

C. Tình huống mà thuật toán tiêu tốn ít thời gian hoặc tài nguyên nhất.

D. Thời gian chạy phụ thuộc vào một cấu hình đầu vào cụ thể.

22. Đâu là một ví dụ về thuật toán có độ phức tạp thời gian O(N^2)?

A. Tìm kiếm nhị phân.

B. Thuật toán sắp xếp nổi bọt (Bubble Sort).

C. Truy cập phần tử mảng theo chỉ số.

D. Thuật toán sắp xếp trộn (Merge Sort).

23. Xét hai vòng lặp lồng nhau, mỗi vòng lặp chạy N lần, và bên trong vòng lặp có một câu lệnh O(1). Độ phức tạp thời gian của cấu trúc này là bao nhiêu?

A. O(N)

B. O(log N)

C. O(N^2)

D. O(2N)

24. Xét một vòng lặp chạy N lần, bên trong có một câu lệnh thực thi trong O(1) thời gian. Độ phức tạp thời gian của vòng lặp này là bao nhiêu?

A. O(N^2)

B. O(1)

C. O(N log N)

D. O(N)

25. Khi so sánh hai thuật toán A và B, nếu thuật toán A có độ phức tạp thời gian O(N) và thuật toán B có độ phức tạp thời gian O(N^2), thì thuật toán nào hiệu quả hơn khi N rất lớn?

A. Thuật toán B hiệu quả hơn.

B. Thuật toán A hiệu quả hơn.

C. Cả hai thuật toán có hiệu suất tương đương.

D. Không thể xác định nếu không biết kích thước đầu vào cụ thể.