Trắc nghiệm Tin học 11 Kết nối tri thức KHMT bài 24 Đánh giá độ phức tạp thời gian thuật toán
1. Độ 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 thực thi của thuật toán không phụ thuộc vào kích thước của dữ liệu đầu vào.
B. Thời gian thực thi của thuật toán tăng tuyến tính với kích thước của dữ liệu đầu vào.
C. Thời gian thực thi của thuật toán tăng theo bình phương của kích thước dữ liệu đầu vào.
D. Thời gian thực thi của thuật toán tăng theo logarit của kích thước dữ liệu đầu vào.
2. Độ phức tạp thời gian O(n log 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 sắp xếp hiệu quả như Merge Sort hoặc Quick Sort (trường hợp trung bình).
B. Các thuật toán tìm kiếm nhị phân.
C. Các thuật toán chỉ thực hiện một vài phép toán cơ bản.
D. Các thuật toán sắp xếp bằng lựa chọn (Selection Sort).
3. Thuật toán tìm kiếm nhị phân (binary search) trên một mảng đã sắp xếp có độ phức tạp thời gian là bao nhiêu?
A. O(log n)
B. O(n)
C. O(n^2)
D. O(1)
4. Độ phức tạp thời gian O(2^n) thường được gọi là gì và thường xuất hiện ở đâu?
A. Độ phức tạp hàm mũ, thường gặp trong các bài toán vét cạn hoặc đệ quy có nhiều nhánh con.
B. Độ phức tạp tuyến tính, thường gặp trong các thuật toán lặp.
C. Độ phức tạp đa thức, thường gặp trong các thuật toán sắp xếp.
D. Độ phức tạp hằng số, thường gặp trong các phép toán truy cập trực tiếp.
5. Độ phức tạp thời gian O(n^2) được gọi là gì?
A. Độ phức tạp bậc hai (hoặc đa thức bậc hai).
B. Độ phức tạp tuyến tính.
C. Độ phức tạp logarit.
D. Độ phức tạp hằng số.
6. Khi một thuật toán có độ phức tạp thời gian là O(n log n), điều này có ý nghĩa gì về hiệu năng của nó?
A. Hiệu năng tốt hơn O(n^2) nhưng kém hơn O(n) khi kích thước đầu vào lớn.
B. Hiệu năng tốt hơn O(n) nhưng kém hơn O(log n) khi kích thước đầu vào lớn.
C. Hiệu năng tương đương với O(n) khi kích thước đầu vào lớn.
D. Hiệu năng kém nhất trong các lựa chọn khi kích thước đầu vào lớn.
7. Trong các trường hợp sau, trường hợp nào có độ phức tạp thời gian cao nhất?
A. O(n!)
B. O(n^2)
C. O(n log n)
D. O(n)
8. Trong thuật toán sắp xếp Insertion Sort, ở mỗi bước, thuật toán thực hiện công việc gì?
A. Chọn một phần tử chưa được sắp xếp và chèn nó vào vị trí đúng trong phần đã sắp xếp.
B. Chia danh sách thành hai nửa và sắp xếp đệ quy từng nửa.
C. Hoán đổi các cặp phần tử liền kề nếu chúng sai thứ tự.
D. Tìm phần tử nhỏ nhất và đặt nó vào đầu danh sách.
9. Độ phức tạp thời gian của việc tìm kiếm một phần tử trong danh sách liên kết đơn (singly linked list) là bao nhiêu?
A. O(n)
B. O(1)
C. O(log n)
D. O(n^2)
10. Độ phức tạp thời gian O(log n) được gọi là gì?
A. Độ phức tạp logarit.
B. Độ phức tạp tuyến tính.
C. Độ phức tạp hằng số.
D. Độ phức tạp bậc hai.
11. Độ phức tạp thời gian O(n) được gọi là gì?
A. Độ phức tạp tuyến tính.
B. Độ phức tạp hằng số.
C. Độ phức tạp bậc hai.
D. Độ phức tạp logarit.
12. Độ phức tạp thời gian O(n^3) thường xuất hiện trong các thuật toán nào?
A. Các thuật toán nhân ma trận (matrix multiplication) theo phương pháp cơ bản.
B. Các thuật toán tìm kiếm nhị phân.
C. Các thuật toán sắp xếp nổi bọt (bubble sort).
D. Các thuật toán truy cập phần tử mảng.
13. Trong lý thuyết độ phức tạp thuật toán, ký hiệu "O" (Big O) dùng để biểu diễn điều gì của một thuật toán?
A. Giới hạn trên của tốc độ tăng trưởng của thời gian thực thi hoặc không gian bộ nhớ khi kích thước đầu vào tiến tới vô cùng.
B. Giới hạn dưới của tốc độ tăng trưởng của thời gian thực thi hoặc không gian bộ nhớ khi kích thước đầu vào tiến tới vô cùng.
C. Độ phức tạp chính xác của thời gian thực thi hoặc không gian bộ nhớ với mọi kích thước đầu vào.
D. Tốc độ trung bình của thời gian thực thi hoặc không gian bộ nhớ trên một tập hợp các đầu vào.
14. Việc đánh giá độ phức tạp thời gian thuật toán giúp chúng ta điều gì?
A. So sánh hiệu quả của các thuật toán khác nhau và dự đoán hiệu năng khi dữ liệu đầu vào lớn.
B. Tìm ra lỗi cú pháp trong mã nguồn của thuật toán.
C. Đảm bảo thuật toán luôn chạy trong một khoảng thời gian cố định.
D. Xác định ngôn ngữ lập trình tối ưu cho thuật toán.
15. Khi nói về độ phức tạp không gian (space complexity), chúng ta đang đánh giá điều gì?
A. Lượng bộ nhớ tối đa mà một thuật toán yêu cầu trong quá trình thực thi, phụ thuộc vào kích thước đầu vào.
B. Thời gian thực thi tối đa của một thuật toán, phụ thuộc vào kích thước đầu vào.
C. Số lượng phép toán mà thuật toán thực hiện.
D. Tốc độ truy cập dữ liệu của thuật toán.
16. Cấu trúc dữ liệu "ngăn xếp" (stack) hoạt động theo nguyên tắc nào?
A. Vào sau, ra trước (LIFO - Last In, First Out).
B. Vào trước, ra trước (FIFO - First In, First Out).
C. Truy cập ngẫu nhiên theo chỉ số.
D. Chỉ cho phép thêm phần tử vào cuối và xóa phần tử ở đầu.
17. Độ phức tạp thời gian O(n^2) thường là đặc trưng của loại thuật toán nào?
A. Các thuật toán sắp xếp đơn giản như Bubble Sort, Insertion Sort, Selection Sort.
B. Các thuật toán tìm kiếm nhị phân trên mảng đã sắp xếp.
C. Các thuật toán truy cập một phần tử cụ thể trong cấu trúc dữ liệu cây.
D. Các thuật toán xử lý dữ liệu với độ phức tạp hằng số.
18. Độ phức tạp thời gian O(log n) có nghĩa là thời gian thực thi tăng như thế nào khi kích thước đầu vào (n) tăng gấp đôi?
A. Thời gian thực thi tăng thêm một lượng không đổi (ví dụ: cộng thêm một hằng số).
B. Thời gian thực thi tăng gấp đôi.
C. Thời gian thực thi tăng gấp bốn lần.
D. Thời gian thực thi không đổi.
19. Độ phức tạp thời gian của việc chèn một phần tử vào đầu danh sách liên kết đơn (singly linked list) là bao nhiêu?
A. O(1)
B. O(n)
C. O(log n)
D. O(n^2)
20. Cấu trúc dữ liệu nào sau đây thường cho phép truy cập phần tử theo chỉ số với độ phức tạp thời gian O(1)?
A. Mảng (Array).
B. Danh sách liên kết (Linked List).
C. Cây tìm kiếm nhị phân (Binary Search Tree).
D. Ngăn xếp (Stack) chỉ cho phép truy cập phần tử đỉnh.
21. Độ phức tạp thời gian của việc xóa một phần tử từ cuối danh sách liên kết đơn (singly linked list) là bao nhiêu?
A. O(n)
B. O(1)
C. O(log n)
D. O(n^2)
22. Một thuật toán tìm kiếm tuần tự trong một danh sách chưa sắp xếp có độ phức tạp thời gian điển hình là bao nhiêu?
A. O(n)
B. O(1)
C. O(n^2)
D. O(log n)
23. Độ phức tạp thời gian O(n^2) có nghĩa là thời gian thực thi tăng như thế nào khi kích thước đầu vào (n) tăng gấp đôi?
A. Thời gian thực thi tăng gấp bốn lần.
B. Thời gian thực thi tăng gấp đôi.
C. Thời gian thực thi tăng thêm một lượng không đổi.
D. Thời gian thực thi không đổi.
24. Độ phức tạp thời gian O(n) có nghĩa là thời gian thực thi tăng như thế nào khi kích thước đầu vào (n) tăng gấp đôi?
A. Thời gian thực thi tăng gấp đôi.
B. Thời gian thực thi tăng gấp bốn lần.
C. Thời gian thực thi tăng thêm một lượng không đổi.
D. Thời gian thực thi không đổi.
25. Cấu trúc dữ liệu "hàng đợi" (queue) hoạt động theo nguyên tắc nào?
A. Vào trước, ra trước (FIFO - First In, First Out).
B. Vào sau, ra trước (LIFO - Last In, First Out).
C. Truy cập ngẫu nhiên theo chỉ số.
D. Chỉ cho phép thêm phần tử vào đầu và xóa phần tử ở cuối.
