Trắc nghiệm Kết nối Tin học 11 KHMT bài 25 Xác định độ phức tạp thời gian thuộc toán
1. Đâu là ý nghĩa của độ phức tạp thời gian O(n^k), với k > 1 là một hằng số?
A. Thời gian thực thi tăng theo lũy thừa của kích thước đầu vào.
B. Thời gian thực thi tăng theo logarit của kích thước đầu vào.
C. Thời gian thực thi tăng tuyến tính với kích thước đầu vào.
D. Thời gian thực thi không đổi.
2. Khi phân tích độ phức tạp thời gian của một thuật toán đệ quy, phương pháp nào thường được sử dụng?
A. Phương pháp chia để trị (Master Theorem).
B. Phân tích từng bước chạy thủ công.
C. Sử dụng bộ gỡ lỗi (debugger).
D. Đo thời gian thực thi trực tiếp.
3. Tại sao độ phức tạp thời gian O(n^2) thường được coi là không hiệu quả cho các tập dữ liệu lớn?
A. Thời gian thực thi tăng lên rất nhanh khi n tăng, có thể dẫn đến thời gian chờ đợi rất lâu.
B. Nó yêu cầu nhiều bộ nhớ hơn các thuật toán khác.
C. Nó chỉ hoạt động tốt với các mảng nhỏ.
D. Nó không thể xử lý các loại dữ liệu khác nhau.
4. Đâu là độ phức tạp thời gian trường hợp xấu nhất của thuật toán sắp xếp nổi bọt (bubble sort) trên một mảng có n phần tử?
A. O(n^2)
B. O(n)
C. O(log n)
D. O(n log n)
5. Độ phức tạp thời gian trung bình (average-case time complexity) của thuật toán sắp xếp nhanh (quick sort) là bao nhiêu?
A. O(n log n)
B. O(n^2)
C. O(n)
D. O(log n)
6. Một thuật toán có độ phức tạp thời gian O(n) có nghĩa là gì?
A. Thời gian thực thi của thuật toán tăng tuyến tính với kích thước đầu vào (n).
B. Thời gian thực thi của thuật toán không thay đổi theo kích thước đầu vào.
C. Thời gian thực thi của thuật toán tăng theo bình phương kích thước đầu vào.
D. Thời gian thực thi của thuật toán tăng theo logarit kích thước đầu vào.
7. Độ phức tạp thời gian của thuật toán duyệt qua cây nhị phân tìm kiếm (binary search tree) theo thứ tự inorder traversal trong trường hợp xấu nhất (cây suy biến thành danh sách liên kết)?
A. O(n)
B. O(n^2)
C. O(log n)
D. O(n log n)
8. Đâu là độ phức tạp thời gian của thuật toán tìm kiếm trên một hash table (bảng băm) trong trường hợp xấu nhất (do xung đột nhiều)?
A. O(n)
B. O(1)
C. O(log n)
D. O(n^2)
9. Thuật toán tìm kiếm tuyến tính (linear search) trên một mảng chưa sắp xếp có độ phức tạp thời gian trường hợp xấu nhất là bao nhiêu?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(1)
10. Thuật toán nào sau đây có độ phức tạp thời gian O(n log n) trong trường hợp trung bình?
A. Merge Sort (Sắp xếp trộn).
B. Bubble Sort (Sắp xếp nổi bọt).
C. Linear Search (Tìm kiếm tuyến tính).
D. Selection Sort (Sắp xếp chọn).
11. 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) có độ phức tạp thời gian là bao nhiêu (với điều kiện có con trỏ đến cuối)?
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
12. Độ phức tạp thời gian O(1) biểu thị điều gì?
A. Thời gian thực thi không đổi, không phụ thuộc vào kích thước đầu vào.
B. Thời gian thực thi tăng tuyến tính với kích thước đầu vào.
C. Thời gian thực thi tăng theo bình phương kích thước đầu vào.
D. Thời gian thực thi thay đổi tùy thuộc vào dữ liệu cụ thể.
13. Đâu là độ phức tạp thời gian của thuật toán tính tổng các phần tử trong một mảng có n phần tử?
A. O(n)
B. O(1)
C. O(log n)
D. O(n^2)
14. Đâu là độ phức tạp thời gian của thuật toán duyệt qua cây nhị phân tìm kiếm (binary search tree) theo thứ tự inorder traversal trong trường hợp tốt nhất (cây cân bằng)?
A. O(n)
B. O(log n)
C. O(n log n)
D. O(n^2)
15. Đâu là độ phức tạp thời gian của thuật toán tìm kiếm trên một hash table (bảng băm) trong trường hợp trung bình?
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
16. Phân tích độ phức tạp thời gian giúp chúng ta điều gì?
A. Ước lượng hiệu năng của thuật toán khi kích thước đầu vào thay đổi.
B. Xác định ngôn ngữ lập trình tốt nhất cho thuật toán.
C. Đảm bảo thuật toán luôn chạy đúng.
D. Giảm thiểu dung lượng bộ nhớ cần thiết.
17. Việc thêm một phần tử vào đầu một danh sách liên kết đơn (singly linked list) có độ phức tạp thời gian là bao nhiêu?
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
18. Thuật toán nào sau đây thường có độ phức tạp thời gian O(log n)?
A. Tìm kiếm nhị phân (binary search) trên mảng đã sắp xếp.
B. Tìm kiếm tuyến tính (linear search) trên mảng chưa sắp xếp.
C. Sắp xếp nổi bọt (bubble sort).
D. Duyệt qua tất cả các phần tử của mảng.
19. Khi so sánh hai thuật toán có độ phức tạp thời gian O(n log n) và O(n^2), thuật toán nào hiệu quả hơn khi kích thước đầu vào (n) rất lớn?
A. Thuật toán có độ phức tạp O(n log n).
B. Thuật toán có độ phức tạp O(n^2).
C. Cả hai thuật toán có hiệu quả như nhau.
D. Hiệu quả phụ thuộc vào ngôn ngữ lập trình.
20. Độ phức tạp thời gian của thuật toán được đo lường dựa trên yếu tố nào?
A. Số lượng thao tác cơ bản mà thuật toán thực hiện theo kích thước dữ liệu đầu vào.
B. Số dòng mã nguồn của thuật toán.
C. Tốc độ xử lý của máy tính chạy thuật toán.
D. Dung lượng bộ nhớ mà thuật toán yêu cầu.
21. Khi nào thì việc phân tích độ phức tạp thời gian trường hợp tốt nhất (best-case) trở nên quan trọng?
A. Khi thuật toán có thể hoàn thành rất nhanh trong một số trường hợp đặc biệt.
B. Khi muốn đánh giá hiệu năng tối đa của thuật toán.
C. Khi thuật toán luôn có hiệu năng như nhau.
D. Khi chỉ quan tâm đến trường hợp xấu nhất.
22. Thuật toán sắp xếp nhanh (quick sort) có độ phức tạp thời gian trường hợp xấu nhất là bao nhiêu?
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(log n)
23. Việc sử dụng cấu trúc dữ liệu mảng để truy cập phần tử thứ k có độ phức tạp thời gian là bao nhiêu?
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
24. Ký hiệu Big O (O()) được sử dụng để biểu diễn loại độ phức tạp thời gian nào?
A. Độ phức tạp thời gian trường hợp xấu nhất (worst-case time complexity).
B. Độ phức tạp thời gian trường hợp trung bình (average-case time complexity).
C. Độ phức tạp thời gian trường hợp tốt nhất (best-case time complexity).
D. Độ phức tạp không gian (space complexity).
25. Đâu là độ phức tạp thời gian của thuật toán duyệt qua tất cả các cặp phần tử trong một mảng có n phần tử?
A. O(n^2)
B. O(n)
C. O(log n)
D. O(n log n)
