[KNTT] Trắc nghiệm Tin học 11 KHMT bài 24 Đánh giá độ phức tạp thời gian thuật toán
1. Một thuật toán có độ phức tạp thời gian O(n^2) và một thuật toán khác có độ phức tạp O(n log n). Khi kích thước đầu vào tăng từ 10 lên 1000, điều gì có khả năng xảy ra?
A. Cả hai thuật toán đều tăng thời gian chạy theo cùng một tỷ lệ.
B. Thời gian chạy của thuật toán O(n^2) sẽ tăng nhanh hơn đáng kể so với O(n log n).
C. Thời gian chạy của thuật toán O(n log n) sẽ tăng nhanh hơn đáng kể so với O(n^2).
D. Thời gian chạy của cả hai thuật toán sẽ giảm.
2. Độ 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. Duyệt qua tất cả các phần tử của mảng.
B. Tìm kiếm trong cây nhị phân tìm kiếm đã cân bằng hoặc thuật toán chia để trị như tìm kiếm nhị phân.
C. Thực hiện một phép gán biến.
D. Thực hiện hai phép cộng.
3. Trong phân tích độ phức tạp, chúng ta thường bỏ qua các hệ số hằng số và các số hạng bậc thấp hơn. Tại sao lại làm như vậy?
A. Để làm cho kết quả phức tạp hơn.
B. Vì chúng không ảnh hưởng đến tốc độ tăng trưởng khi kích thước đầu vào n trở nên rất lớn.
C. Để làm cho thuật toán chạy nhanh hơn.
D. Vì chúng không thể tính toán được.
4. Độ phức tạp thời gian O(1) có nghĩa là gì đối với một thuật toán?
A. Thời gian chạy tăng tuyến tính với 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 và là hằng số.
C. Thời gian chạy tăng theo bình phương kích thước đầu vào.
D. Thời gian chạy tăng theo logarit của kích thước đầu vào.
5. Độ 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ả nào?
A. Sắp xếp nổi bọt (Bubble Sort)
B. Sắp xếp chọn (Selection Sort)
C. Sắp xếp nhanh (Quick Sort) và Sắp xếp trộn (Merge Sort)
D. Sắp xếp chèn (Insertion Sort) trong trường hợp xấu nhất
6. Phân tích độ phức tạp thời gian của một thuật toán có ích lợi gì?
A. Giúp xác định chính xác thời gian chạy trên mọi máy tính.
B. Giúp so sánh hiệu quả của các thuật toán khác nhau một cách trừu tượng, độc lập với phần cứng.
C. Đảm bảo thuật toán luôn chạy nhanh nhất trong mọi trường hợp.
D. Cung cấp thông tin về mức tiêu thụ bộ nhớ của thuật toán.
7. Độ phức tạp thời gian O(n^2) thường có thể gặp phải ở các thuật toán nào?
A. Tìm kiếm tuần tự trong một mảng.
B. Sắp xếp nổi bọt (Bubble Sort) hoặc các thuật toán sắp xếp lồng nhau đơn giản.
C. Tìm kiếm nhị phân trong một mảng đã sắp xếp.
D. Truy cập một phần tử mảng bằng chỉ số.
8. Xét thuật toán tìm kiếm tuần tự trong một mảng chưa sắp xếp. Trong trường hợp xấu nhất, thời gian thực thi của thuật toán này tỉ lệ với độ lớn của mảng (n). Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trong trường hợp xấu nhất được biểu diễn như thế nào?
A. O(n^2)
B. O(log n)
C. O(n)
D. O(1)
9. Xét hai vòng lặp lồng nhau, vòng lặp bên ngoài chạy n lần và vòng lặp bên trong cũng chạy n lần cho mỗi lần lặp của vòng ngoài. Độ phức tạp thời gian của cấu trúc này là gì?
A. O(n)
B. O(n^2)
C. O(2n)
D. O(log n)
10. Trong thuật toán tìm kiếm nhị phân, mỗi bước chúng ta loại bỏ một nửa phạm vi tìm kiếm. Điều này dẫn đến độ phức tạp thời gian là bao nhiêu?
A. O(n)
B. O(n^2)
C. O(log n)
D. O(1)
11. Khi hai thuật toán có cùng độ phức tạp thời gian, ví dụ O(n log n), yếu tố nào có thể khiến một thuật toán nhanh hơn thuật toán kia trên thực tế?
A. Chỉ số RAM của máy tính.
B. Hệ điều hành đang chạy.
C. Các hệ số hằng số và các số hạng bậc thấp trong biểu thức độ phức tạp.
D. Tên của biến được sử dụng trong mã.
12. Khi phân tích độ phức tạp thời gian của một đoạn mã, chúng ta thường tập trung vào phần nào của đoạn mã?
A. Các câu lệnh gán biến đơn giản.
B. Các phép toán số học cơ bản.
C. Các vòng lặp và lời gọi hàm đệ quy, vì chúng có thể lặp lại nhiều lần.
D. Các câu lệnh khai báo biến.
13. 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)
B. O(log n)
C. O(n log n)
D. O(n^2)
14. Độ phức tạp thời gian của một thuật toán khi thực hiện một chuỗi các thao tác là gì?
A. Là tổng độ phức tạp của từng thao tác.
B. Là tích độ phức tạp của từng thao tác.
C. Là độ phức tạp của thao tác có độ phức tạp cao nhất.
D. Là trung bình độ phức tạp của các thao tác.
15. Độ phức tạp thời gian của một thuật toán có thể bị ảnh hưởng bởi yếu tố nào sau đây?
A. Tốc độ của bộ xử lý máy tính.
B. Ngôn ngữ lập trình được sử dụng.
C. Cấu trúc dữ liệu và thuật toán được lựa chọn.
D. Chỉ số RAM của máy tính.
16. Trong lý thuyết độ phức tạp thuật toán, ký hiệu Big O (O()) được sử dụng để biểu diễn giới hạn trên của tốc độ tăng trưởng của một hàm số hoặc tốc độ tăng trưởng của thời gian thực thi của một thuật toán. Điều này có nghĩa là gì?
A. Nó cho biết thời gian chạy chính xác của thuật toán với mọi kích thước đầu vào.
B. Nó mô tả hiệu suất tốt nhất có thể của thuật toán.
C. Nó cung cấp ước lượng về hiệu suất xấu nhất của thuật toán khi kích thước đầu vào tăng lên.
D. Nó chỉ ra thời gian chạy trung bình của thuật toán.
17. Trong các trường hợp sau, trường hợp nào thể hiện độ phức tạp thời gian tệ nhất (tăng nhanh nhất khi kích thước đầu vào n tăng)?
A. O(n)
B. O(log n)
C. O(n^2)
D. O(n log n)
18. Độ phức tạp thời gian O(n^3) có nghĩa là gì?
A. Thời gian chạy tăng theo hàm mũ.
B. Thời gian chạy tăng theo lập phương của kích thước đầu vào.
C. Thời gian chạy không đổi.
D. Thời gian chạy tăng theo logarit.
19. Một hàm đệ quy gọi chính nó hai lần với kích thước đầu vào giảm đi một nửa ở mỗi lần gọi, ví dụ f(n) = 2f(n/2) + O(1). Độ phức tạp thời gian của hàm này thường là gì?
A. O(n)
B. O(n^2)
C. O(log n)
D. O(n log n)
20. Khi một thuật toán thực hiện k phép toán độc lập, mỗi phép toán có độ phức tạp là O(f(n)), độ phức tạp tổng thể của thuật toán là gì?
A. O(k + f(n))
B. O(k * f(n))
C. O(f(n) / k)
D. O(f(n)^k)
21. Độ phức tạp thời gian O(n!) có ý nghĩa gì trong thực tế lập trình?
A. Thuật toán rất hiệu quả, phù hợp cho mọi kích thước đầu vào.
B. Thời gian chạy tăng cực kỳ nhanh, chỉ phù hợp với các giá trị n rất nhỏ.
C. Thời gian chạy không đổi, độc lập với n.
D. Thời gian chạy tỉ lệ thuận với n.
22. Trong phân tích độ phức tạp, trường hợp tốt nhất (best-case) của một thuật toán đề cập đến điều gì?
A. Kích thước đầu vào lớn nhất mà thuật toán có thể xử lý.
B. Kịch bản mà thuật toán thực thi nhanh nhất.
C. Kịch bản mà thuật toán thực thi chậm nhất.
D. Thời gian chạy trung bình của thuật toán.
23. Khi so sánh hai thuật toán có độ phức tạp thời gian lần lượt là O(n) và O(n^2), với kích thước đầu vào n rất lớn, thuật toán nào thường hiệu quả hơn?
A. Thuật toán O(n^2) vì nó xử lý nhiều trường hợp hơn.
B. Thuật toán O(n) vì thời gian chạy tăng chậm hơn.
C. Cả hai thuật toán có hiệu suất tương đương khi n lớn.
D. Không thể xác định hiệu quả chỉ dựa trên ký hiệu Big O.
24. Độ phức tạp thời gian O(n^2) có thể được cải thiện thành O(n log n) bằng cách nào?
A. Bỏ qua một nửa dữ liệu đầu vào.
B. Sử dụng cấu trúc dữ liệu và thuật toán hiệu quả hơn, ví dụ thay thế sắp xếp nổi bọt bằng sắp xếp trộn.
C. Giảm số lượng biến trong chương trình.
D. Tăng kích thước bộ nhớ RAM.
25. Độ phức tạp thời gian O(2^n) thường xuất hiện trong các thuật toán nào?
A. Sắp xếp nhanh (Quick Sort)
B. Tìm kiếm nhị phân (Binary Search)
C. Các bài toán đệ quy không tối ưu hóa, ví dụ như tính số Fibonacci bằng đệ quy thuần túy.
D. Duyệt một mảng theo thứ tự.
