[Cánh diều] Trắc nghiệm Tin học 11 KHMT bài 5 Đánh giá thuật toán

1. Độ phức tạp thời gian O(N^3) thường gặp ở loại thuật toán nào?

A. Tìm kiếm nhị phân.

B. Nhân hai ma trận bằng phương pháp cơ bản.

C. Sắp xếp trộn.

D. Tìm kiếm tuần tự.

2. Thuật toán sắp xếp nhanh (Quick Sort) có độ phức tạp thời gian trong trường hợp trung bình là bao nhiêu?

A. O(N)

B. O(N log N)

C. O(N^2)

D. O(log N)

3. Khi một thuật toán có độ phức tạp thời gian là O(1), điều này có nghĩa là gì?

A. Thời gian thực thi phụ thuộc tuyến tính vào kích thước đầu vào.

B. Thời gian thực thi không phụ thuộc vào 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 phụ thuộc theo logarit của kích thước đầu vào.

4. Độ phức tạp thời gian của thuật toán đệ quy Fibonacci F(n) = F(n-1) + F(n-2) nếu không sử dụng ghi nhớ (memoization) là bao nhiêu?

A. O(N)

B. O(log N)

C. O(N^2)

D. O(2^N)

5. Để giảm độ phức tạp thời gian của một thuật toán từ O(N^2) xuống O(N log N), người ta thường áp dụng phương pháp nào?

A. Sử dụng cấu trúc dữ liệu mảng thay vì danh sách liên kết.

B. Áp dụng kỹ thuật chia để trị hoặc sử dụng cấu trúc dữ liệu hiệu quả hơn.

C. Tăng gấp đôi kích thước đầu vào.

D. Giảm số lượng biến trong thuật toán.

6. Cho thuật toán sau: lặp từ i = 1 đến N, trong mỗi lần lặp thực hiện một thao tác duy nhất. Độ phức tạp thời gian của thuật toán này là gì?

A. O(1)

B. O(log N)

C. O(N)

D. O(N^2)

7. Thuật toán tìm kiếm nhị phân hoạt động dựa trên nguyên tắc nào?

A. Duyệt tuần tự từ đầu đến cuối danh sách.

B. Chia đôi phạm vi tìm kiếm ở mỗi bước dựa trên việc so sánh với phần tử giữa.

C. So sánh phần tử cần tìm với mọi phần tử khác.

D. Sử dụng cấu trúc dữ liệu cây nhị phân tìm kiếm.

8. Khi đánh giá thuật toán, ký hiệu Big O (ví dụ: O(N)) được sử dụng để biểu diễn điều gì?

A. Thời gian chạy chính xác của thuật toán.

B. Giới hạn trên của tốc độ tăng trưởng tài nguyên (thời gian hoặc không gian) của thuật toán.

C. Tỷ lệ thành công của thuật toán.

D. Số lượng dòng code của thuật toán.

9. Tại sao việc đánh giá thuật toán là quan trọng trong khoa học máy tính?

A. Để tăng số dòng code.

B. Để chọn thuật toán hiệu quả nhất về thời gian và không gian cho bài toán cụ thể.

C. Để làm cho thuật toán khó hiểu hơn.

D. Để đảm bảo thuật toán luôn trả về kết quả sai.

10. Trong đánh giá thuật toán, khái niệm độ phức tạp thời gian (time complexity) của thuật toán chủ yếu đo lường điều gì?

A. Lượng bộ nhớ mà thuật toán sử dụng.

B. Số bước thực hiện của thuật toán theo hàm số của kích thước đầu vào.

C. Độ chính xác của kết quả đầu ra.

D. Tính dễ đọc và dễ hiểu của mã nguồn thuật toán.

11. Độ 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. Tìm kiếm tuần tự.

B. Sắp xếp nổi bọt.

C. Tìm kiếm nhị phân trên mảng đã sắp xếp.

D. Duyệt qua tất cả các cặp phần tử.

12. Khi nói về Average-case complexity (độ phức tạp trường hợp trung bình), chúng ta đang đề cập đến điều gì?

A. Số bước ít nhất thuật toán có thể thực hiện.

B. Số bước nhiều nhất thuật toán có thể thực hiện.

C. Số bước thực hiện trung bình trên một tập hợp lớn các đầu vào ngẫu nhiên.

D. Lượng bộ nhớ tối đa thuật toán sử dụng.

13. Khi so sánh hai thuật toán A và B, nếu thuật toán A có độ phức tạp thời gian là O(N) và thuật toán B là O(N^2) với N là kích thước đầu vào, thì thuật toán nào được coi là hiệu quả hơn khi N lớn?

A. Thuật toán A, vì nó có độ phức tạp tuyến tính.

B. Thuật toán B, vì nó có độ phức tạp bậc hai.

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.

14. Độ phức tạp không gian (space complexity) của một thuật toán liên quan đến yếu tố nào?

A. Thời gian thực thi của thuật toán.

B. Lượng bộ nhớ mà thuật toán yêu cầu sử dụng.

C. Số phép so sánh mà thuật toán thực hiện.

D. Số lần lặp của vòng lặp trong thuật toán.

15. Yếu tố nào sau đây KHÔNG được xem là tiêu chí để đánh giá một thuật toán?

A. Độ phức tạp thời gian.

B. Độ phức tạp không gian.

C. Tính dễ đọc của mã nguồn.

D. Tính đúng đắn của thuật toán.

16. Độ phức tạp thời gian O(N log N) là đặc trưng cho các thuật toán sắp xếp hiệu quả nào?

A. Sắp xếp chọn (Selection Sort) và Sắp xếp chèn (Insertion Sort).

B. Sắp xếp nhanh (Quick Sort) và Sắp xếp trộn (Merge Sort).

C. Sắp xếp nổi bọt (Bubble Sort) và Sắp xếp vun đống (Heap Sort).

D. Sắp xếp đếm (Counting Sort) và Sắp xếp theo cơ số (Radix Sort).

17. Thuật toán nào sau đây thường có độ phức tạp thời gian trung bình là O(N log N) đối với việc sắp xếp?

A. Sắp xếp chọn (Selection Sort).

B. Sắp xếp chèn (Insertion Sort).

C. Sắp xếp trộn (Merge Sort).

D. Sắp xếp nổi bọt (Bubble Sort).

18. Khái niệm Best-case complexity (độ phức tạp trường hợp tốt nhất) của thuật toán đề cập đến điều gì?

A. Số bước thực hiện ít nhất khi đầu vào được sắp xếp theo một cách đặc biệt.

B. Số bước thực hiện trung bình trên tất cả các trường hợp đầu vào.

C. Số bước thực hiện nhiều nhất có thể.

D. Lượng bộ nhớ tối thiểu thuật toán cần.

19. Xét hai thuật toán: Thuật toán 1 thực hiện N phép tính. Thuật toán 2 thực hiện N * log N phép tính. Khi N rất lớn, thuật toán nào hiệu quả hơn?

A. Thuật toán 1.

B. Thuật toán 2.

C. Cả hai như nhau.

D. Phụ thuộc vào giá trị cụ thể của N.

20. Ký hiệu Omega (Ω) trong đánh giá thuật toán dùng để biểu thị điều gì?

A. Giới hạn trên của tốc độ tăng trưởng tài nguyên.

B. Giới hạn dưới của tốc độ tăng trưởng tài nguyên.

C. Tốc độ tăng trưởng tài nguyên chính xác.

D. Tốc độ tăng trưởng tài nguyên trung bình.

21. Cho thuật toán tìm kiếm tuần tự trên một danh sách chưa sắp xếp có N phần tử. Trong trường hợp xấu nhất, độ phức tạp thời gian của thuật toán này là bao nhiêu?

A. O(1)

B. O(log N)

C. O(N)

D. O(N^2)

22. Độ phức tạp thời gian O(N^2) mô tả một mối quan hệ như thế nào giữa thời gian thực thi và kích thước đầu vào N?

A. Thời gian thực thi tăng tuyến tính với N.

B. Thời gian thực thi tăng theo bình phương của N.

C. Thời gian thực thi tăng theo logarit của N.

D. Thời gian thực thi gần như không đổi.

23. Thuật toán nào sau đây KHÔNG phải là thuật toán sắp xếp?

A. Merge Sort.

B. Binary Search.

C. Quick Sort.

D. Heap Sort.

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)

B. O(N log N)

C. O(N^2)

D. O(log N)

25. Trong các ký hiệu độ phức tạp, ký hiệu nào biểu thị tốc độ tăng trưởng tài nguyên nhanh nhất?

A. O(N)

B. O(log N)

C. O(N^2)

D. O(N!)