Trắc nghiệm Tin học 11 Kết nối tri thức KHMT bài 25 Xác định độ phức tạp thời gian thuộc toán
1. Độ phức tạp thời gian O(n!) có ý nghĩa gì?
A. Thời gian thực thi tăng rất nhanh theo cấp số nhân của giai thừa.
B. Thời gian thực thi tăng theo bình phương của n.
C. Thời gian thực thi là hằng số.
D. Thời gian thực thi tăng tuyến tính.
2. Thuật toán sắp xếp nổi bọt (Bubble Sort) có độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?
A. O(n^2)
B. O(n)
C. O(log n)
D. O(n log n)
3. Độ phức tạp thời gian O(n^3) cho thấy thời gian thực thi tăng trưởng như thế nào khi "n" tăng gấp đôi?
A. Tăng gấp 8 lần.
B. Tăng gấp 4 lần.
C. Tăng gấp 2 lần.
D. Tăng gấp 3 lần.
4. 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 tăng tuyến tính theo kích thước đầu vào n.
B. Thời gian thực thi tăng theo bình phương của kích thước đầu vào n.
C. Thời gian thực thi là hằng số, không phụ thuộc vào n.
D. Thời gian thực thi tăng theo logarit của n.
5. Độ phức tạp thời gian O(n^2) có nghĩa là khi kích thước đầu vào tăng gấp đôi, thời gian thực thi sẽ tăng lên khoảng bao nhiêu lần?
A. 4 lần.
B. 2 lần.
C. 8 lần.
D. Logarit cơ số 2 của 2 lần.
6. Khi phân tích độ phức tạp thời gian của một thuật toán có nhiều vòng lặp lồng nhau, ta cần xem xét điều gì?
A. Độ phức tạp của vòng lặp bên trong nhân với độ phức tạp của vòng lặp bên ngoài.
B. Độ phức tạp của vòng lặp bên ngoài cộng với độ phức tạp của vòng lặp bên trong.
C. Chỉ xem xét vòng lặp chạy nhiều nhất.
D. Bỏ qua các vòng lặp lồng nhau nếu chúng độc lập.
7. Ký hiệu "O" lớn (Big O notation) trong phân tích độ phức tạp thời gian dùng để biểu thị điều gì?
A. Giới hạn trên về tốc độ tăng của thời gian thực thi thuật toán.
B. Giới hạn dưới về tốc độ tăng của thời gian thực thi thuật toán.
C. Thời gian thực thi chính xác của thuật toán.
D. Mức sử dụng bộ nhớ của thuật toán.
8. Thuật toán nào sau đây có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất?
A. Insertion Sort.
B. Binary Search.
C. Merge Sort.
D. Hash Table Lookup.
9. Khi độ phức tạp thời gian là O(n), điều này có nghĩa là thuật toán sẽ thực hiện bao nhiêu phép toán?
A. Một số phép toán tỷ lệ thuận với "n".
B. Một số phép toán không đổi.
C. Một số phép toán tăng theo bình phương của "n".
D. Một số phép toán tăng theo logarit của "n".
10. Đâu là một ví dụ về thuật toán có độ phức tạp thời gian O(n log n)?
A. Heap Sort.
B. Linear Search.
C. Bubble Sort.
D. Sequential Scan.
11. Thuật toán tìm kiếm tuần tự trong một mảng chưa sắp xếp có độ phức tạp thời gian là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
12. Thuật toán nào có độ phức tạp thời gian O(log n) cho phép tìm kiếm một phần tử trong tập dữ liệu lớn?
A. Binary Search (Tìm kiếm nhị phân).
B. Linear Search (Tìm kiếm tuần tự).
C. Breadth-First Search (Tìm kiếm theo chiều rộng) trên cây.
D. Depth-First Search (Tìm kiếm theo chiều sâu) trên cây.
13. Khi phân tích độ phức tạp thời gian, chúng ta thường tập trung vào trường hợp nào?
A. Trường hợp xấu nhất (Worst-case scenario).
B. Trường hợp tốt nhất (Best-case scenario).
C. Trường hợp trung bình (Average-case scenario).
D. Tất cả các trường hợp trên.
14. Độ phức tạp thời gian của một thuật toán được đo lường dựa trên yếu tố nào sau đây khi số lượng đầu vào tăng lên?
A. Số bước thực hiện của thuật toán.
B. Bộ nhớ mà thuật toán sử dụng.
C. Tốc độ xử lý của máy tính chạy thuật toán.
D. Ngôn ngữ lập trình mà thuật toán được viết bằng.
15. Độ phức tạp thời gian O(log n) thường xuất hiện trong các thuật toán nào?
A. Thuật toán tìm kiếm nhị phân trên mảng đã sắp xếp.
B. Thuật toán duyệt qua tất cả các phần tử của mảng.
C. Thuật toán sắp xếp các phần tử ngẫu nhiên.
D. Thuật toán thực hiện lặp "n" lần.
16. Trong các thuật toán sắp xếp sau đây, thuật toán nào có độ phức tạp thời gian tốt nhất (nhanh nhất) trong trường hợp trung bình?
A. Quick Sort.
B. Bubble Sort.
C. Selection Sort.
D. Insertion Sort.
17. Thuật toán đệ quy để tính giai thừa của một số "n" có độ phức tạp thời gian là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
18. Độ phức tạp thời gian O(n log n) thường thấy ở các thuật toán sắp xếp hiệu quả như thế nào?
A. Merge Sort và Quick Sort.
B. Bubble Sort và Insertion Sort.
C. Linear Search và Binary Search.
D. Selection Sort và Counting Sort.
19. Trong trường hợp nào sau đây, một phép toán truy cập phần tử mảng theo chỉ số (ví dụ: `array[i]`) thường có độ phức tạp thời gian O(1)?
A. Khi mảng được lưu trữ liên tục trong bộ nhớ.
B. Khi mảng được lưu trữ dưới dạng danh sách liên kết.
C. Khi mảng có kích thước rất lớn.
D. Khi mảng chứa các giá trị phức tạp.
20. Phân tích độ phức tạp thời gian giúp chúng ta làm gì khi lựa chọn thuật toán?
A. Ước lượng hiệu suất và hiệu quả của thuật toán.
B. Xác định số dòng code của thuật toán.
C. Đảm bảo thuật toán luôn chạy đúng.
D. Chọn ngôn ngữ lập trình tối ưu.
21. Độ phức tạp thời gian O(n^2) so với O(n log n) thì như thế nào khi n lớn?
A. O(n^2) chậm hơn đáng kể.
B. O(n^2) nhanh hơn đáng kể.
C. Cả hai có tốc độ tương đương.
D. O(n^2) chậm hơn một chút.
22. Độ 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 nhanh theo kích thước đầu vào.
C. Thời gian thực thi phụ thuộc vào hằng số nhân.
D. Thời gian thực thi tăng theo hàm mũ.
23. Yếu tố nào sau đây KHÔNG ảnh hưởng trực tiếp đến việc xác định độ phức tạp thời gian của một thuật toán?
A. Tốc độ của CPU.
B. Kích thước của dữ liệu đầu vào.
C. Số lượng các phép toán cơ bản.
D. Cấu trúc của dữ liệu đầu vào.
24. Độ phức tạp thời gian O(2^n) thường liên quan đến loại bài toán nào?
A. Các bài toán thuộc lớp NP-hard, ví dụ như bài toán người du lịch.
B. Các bài toán có thể giải quyết bằng quy hoạch động.
C. Các bài toán tìm kiếm nhị phân.
D. Các bài toán xử lý mảng đơn giản.
25. Độ phức tạp thời gian của thuật toán duyệt qua một danh sách liên kết đơn để tìm một phần tử là bao nhiêu?
A. O(n)
B. O(log n)
C. O(1)
D. O(n^2)
