Trắc nghiệm Kết nối Tin học 11 KHMT bài 24 Đánh giá độ phức tạp thời gian thuật toán
1. Trong ký hiệu Big O (O), phát biểu nào sau đây mô tả chính xác nhất ý nghĩa của O(n)?
A. Thời gian chạy của thuật toán tăng tuyến tính theo kích thước đầu vào n.
B. Thời gian chạy của thuật toán tăng theo bình phương của kích thước đầu vào n.
C. Thời gian chạy của thuật toán không phụ thuộc vào kích thước đầu vào n.
D. Thời gian chạy của thuật toán tăng theo logarit của kích thước đầu vào n.
2. Độ phức tạp thời gian O(n!) thường xuất hiện trong các bài toán liên quan đến việc:
A. Tìm tất cả các hoán vị của một tập hợp.
B. Tìm kiếm trên một mảng đã sắp xếp.
C. Thực hiện phép cộng hai số.
D. Tìm phần tử lớn nhất trong một mảng.
3. Phát biểu nào sau đây là sai về độ phức tạp thời gian?
A. Độ phức tạp thời gian luôn đo lường thời gian thực tế bằng giây.
B. Ký hiệu Big O (O) biểu thị giới hạn trên cho sự tăng trưởng của thời gian thực thi.
C. Thuật toán có độ phức tạp O(n) hiệu quả hơn thuật toán có độ phức tạp O(n^2) với n lớn.
D. Độ phức tạp thời gian giúp so sánh hiệu quả của các thuật toán khác nhau.
4. Khi đánh giá độ phức tạp thời gian, chúng ta thường quan tâm đến trường hợp nào?
A. Trường hợp xấu nhất (Worst-case)
B. Trường hợp tốt nhất (Best-case)
C. Trường hợp trung bình (Average-case)
D. Cả ba trường hợp trên đều quan trọng như nhau.
5. Thuật toán nào sau đây thường có độ phức tạp thời gian là O(n log n)?
A. Merge Sort (Sắp xếp trộn)
B. Bubble Sort (Sắp xếp nổi bọt)
C. Selection Sort (Sắp xếp chọn)
D. Insertion Sort (Sắp xếp chèn)
6. Độ 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 sau đây?
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 sắp xếp nổi bọt.
C. Thuật toán duyệt qua tất cả các cặp phần tử trong mảng.
D. Thuật toán sắp xếp trộn (Merge Sort) trên danh sách chưa sắp xếp.
7. Độ phức tạp thời gian O(n log n) thường được coi là hiệu quả cho các tác vụ sắp xếp vì:
A. Nó cân bằng giữa tốc độ xử lý và khả năng mở rộng với dữ liệu lớn.
B. Nó luôn là thuật toán nhanh nhất có thể.
C. Nó chỉ yêu cầu một lượng bộ nhớ nhỏ.
D. Nó có thể được thực hiện bằng một vòng lặp đơn giản.
8. Trong các độ phức tạp thời gian sau đây, độ phức tạp nào được coi là kém hiệu quả nhất khi kích thước đầu vào n rất lớn?
A. O(n^3)
B. O(n log n)
C. O(n)
D. O(log n)
9. Khi một thuật toán có độ phức tạp thời gian là O(log n), điều này cho thấy nó xử lý dữ liệu hiệu quả như thế nào khi kích thước tăng lên?
A. Rất hiệu quả, thời gian tăng rất chậm.
B. Khá hiệu quả, thời gian tăng theo đường thẳng.
C. Kém hiệu quả, thời gian tăng nhanh.
D. Không hiệu quả, thời gian tăng theo bình phương.
10. Khái niệm độ phức tạp thời gian của một thuật toán chủ yếu dùng để đo lường yếu tố nào của thuật toán đó?
A. Số lượng bước thực hiện của thuật toán trên một tập dữ liệu đầu vào cụ thể.
B. Tốc độ thực thi của thuật toán trên một cấu hình phần cứng cụ thể.
C. Lượng bộ nhớ mà thuật toán sử dụng trong quá trình chạy.
D. Số lượng lệnh máy mà bộ xử lý thực thi khi chạy thuật toán.
11. Khi phân tích độ phức tạp thời gian, chúng ta thường bỏ qua các hằng số và các số hạng bậc thấp hơn vì:
A. Chúng không ảnh hưởng đáng kể đến sự tăng trưởng của thuật toán với kích thước đầu vào lớn.
B. Chúng làm cho việc phân tích trở nên phức tạp hơn.
C. Chúng là những giá trị cố định và không thay đổi.
D. Chúng chỉ quan trọng đối với các thuật toán nhỏ.
12. Thuật toán nào sau đây có độ phức tạp thời gian tốt nhất (nhanh nhất) cho việc tìm kiếm trên một mảng đã sắp xếp?
A. Tìm kiếm nhị phân (Binary Search)
B. Tìm kiếm tuần tự (Linear Search)
C. Tìm kiếm theo bước nhảy (Jump Search)
D. Tìm kiếm nội suy (Interpolation Search)
13. Yếu tố nào sau đây không ảnh hưởng trực tiếp đến việc đánh giá độ phức tạp thời gian của một thuật toán?
A. Số lượng lệnh máy được tạo ra bởi trình biên dịch.
B. Kích thước của dữ liệu đầu vào.
C. Các phép toán cơ bản được thực hiện (so sánh, gán, cộng).
D. Số lần lặp hoặc đệ quy.
14. Phát biểu nào sau đây mô tả chính xác nhất ý nghĩa của độ phức tạp thời gian O(1)?
A. Thời gian thực hiện thuật toán không đổi, không phụ thuộc vào kích thước đầu vào.
B. Thời gian thực hiện thuật toán tăng theo bình phương kích thước đầu vào.
C. Thời gian thực hiện thuật toán tăng tuyến tính theo kích thước đầu vào.
D. Thời gian thực hiện thuật toán tăng theo logarit kích thước đầu vào.
15. Độ phức tạp thời gian O(log n) có nghĩa là khi kích thước đầu vào n tăng gấp đôi, thời gian thực hiện thuật toán sẽ tăng lên khoảng bao nhiêu lần?
A. Khoảng 1 lần (không đáng kể)
B. 2 lần
C. log 2 lần
D. n lần
16. Độ 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 sau đây?
A. Các thuật toán duyệt qua tất cả các tập con của một tập hợp có n phần tử.
B. Các thuật toán sắp xếp nhanh (Quick Sort).
C. Các thuật toán tìm kiếm nhị phân.
D. Các thuật toán thực hiện một vòng lặp duy nhất.
17. Thuật toán sắp xếp nào sau đây thường có độ phức tạp thời gian O(n log n) trong trường hợp trung bình?
A. Quick Sort (Sắp xếp nhanh)
B. Bubble Sort (Sắp xếp nổi bọt)
C. Selection Sort (Sắp xếp chọn)
D. Insertion Sort (Sắp xếp chèn)
18. Một thuật toán thực hiện một vòng lặp qua một mảng n phần tử, và bên trong vòng lặp đó lại có một vòng lặp khác cũng chạy n lần, thì độ phức tạp thời gian của thuật toán này là bao nhiêu?
A. O(n^2)
B. O(n)
C. O(2n)
D. O(n log n)
19. Độ phức tạp thời gian O(n^2) thường xuất hiện trong các thuật toán nào?
A. Các thuật toán lồng hai vòng lặp, mỗi vòng lặp duyệt qua n phần tử.
B. Các thuật toán tìm kiếm nhị phân.
C. Các thuật toán duyệt qua một lần duy nhất một mảng n phần tử.
D. Các thuật toán chỉ thực hiện một vài phép toán độc lập với kích thước đầu vào.
20. Trong phân tích độ phức tạp, ký hiệu Omega (Ω) được sử dụng để chỉ điều gì?
A. Giới hạn dưới cho sự tăng trưởng của thời gian thực thi.
B. Giới hạn trên cho sự tăng trưởng của thời gian thực thi.
C. Giới hạn chặt chẽ cho sự tăng trưởng của thời gian thực thi.
D. Thời gian thực thi trung bình của thuật toán.
21. Khi so sánh hai thuật toán có độ phức tạp thời gian là O(n) và O(n^2), thuật toán nào hiệu quả hơn đối với các tập dữ liệu đầu vào có kích thước lớn?
A. Thuật toán có độ phức tạp O(n) hiệu quả hơn.
B. Thuật toán có độ phức tạp O(n^2) hiệu quả hơn.
C. Cả hai thuật toán có hiệu quả tương đương.
D. Phụ thuộc vào ngôn ngữ lập trình được sử dụng.
22. Một thuật toán tìm kiếm tuần tự trong một danh sách không 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(n^2)
D. O(1)
23. Trong phân tích độ phức tạp thời gian, n đại diện cho yếu tố nào?
A. Kích thước của dữ liệu đầu vào.
B. Tốc độ của bộ xử lý.
C. Số lượng dòng code của thuật toán.
D. Ngôn ngữ lập trình được sử dụng.
24. 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 log n)
C. O(n)
D. O(log n)
25. Độ phức tạp thời gian O(n^2) có nghĩa là khi kích thước đầu vào n tăng gấp đôi, thời gian thực hiện thuật toán sẽ tăng lên khoảng bao nhiêu lần?
A. 4 lần
B. 2 lần
C. n lần
D. log n lần
