Bài tập trắc nghiệm Tin học 11 Khoa học máy tính Kết nối tri thức – Bài 24 giúp học sinh hiểu cách đánh giá hiệu quả thuật toán thông qua thời gian thực hiện và quy mô dữ liệu đầu vào. Bài 24: Đánh giá độ phức tạp thời gian thuật toán thuộc sách Kết nối tri thức trình bày số phép toán cơ bản như một thước đo độc lập tương đối với máy tính và ngôn ngữ lập trình. Học sinh sẽ tìm hiểu kích thước đầu vào, trường hợp xấu nhất và các mức độ tăng trưởng thường gặp như hằng số, tuyến tính, bậc hai hoặc lôgarit. Nội dung Tin học 11 Kết nối tri thức còn hướng dẫn nhận biết độ phức tạp qua câu lệnh tuần tự, vòng lặp đơn, vòng lặp lồng nhau và quá trình liên tục chia đôi phạm vi. Người học sẽ so sánh thuật toán bằng kí hiệu O lớn, ước lượng ảnh hưởng khi dữ liệu tăng và hiểu vì sao hiệu quả trở nên quan trọng với bài toán quy mô lớn. Kiến thức này hỗ trợ lựa chọn giải pháp lập trình hợp lí.
Dethitracnghiem cập nhật Bài tập trắc nghiệm Tin học 11 Khoa học máy tính Kết nối tri thức – Bài 24 cho năm học 2026–2027, bao gồm nhiều cấu trúc đề mới nhất về độ phức tạp. Hệ thống bài tập trắc nghiệm lớp 11 kiểm tra cách xác định kích thước đầu vào, đếm phép toán, phân tích vòng lặp và so sánh tốc độ tăng trưởng của các thuật toán. Các đề thi, bài tập trực tuyến giúp học sinh ôn thi dễ dàng, luyện đọc mã lệnh, ước lượng thời gian và lựa chọn giải pháp hiệu quả hơn trong từng trường hợp. Ngân hàng câu hỏi được cập nhật thường xuyên, bám sát định hướng đánh giá năng lực phân tích, tư duy định lượng và tối ưu hóa chương trình. Quy trình chấm điểm nhanh gọn, hoàn toàn miễn phí, hiển thị kết quả ngay sau khi hoàn tất. Mỗi câu hỏi đều có đáp án và lời giải chi tiết, chỉ rõ cách đếm số lần lặp, lược bỏ thành phần không chi phối và xác định đúng bậc độ phức tạp.
ĐỀ THI
Câu 1: Độ phức tạp thời gian phản ánh điều gì?
A. Mức tăng thời gian theo kích thước dữ liệu.
B. Kích thước tệp chứa mã nguồn.
C. Số biến được khai báo trong chương trình.
D. Dung lượng ổ đĩa của máy tính.
Câu 2: Kích thước dữ liệu vào thường được kí hiệu bằng gì?
A. m.
B. n.
C. x.
D. t.
Câu 3: Khi đánh giá thời gian thuật toán, thao tác cơ sở được hiểu là gì?
A. Một chương trình hoàn chỉnh.
B. Một thiết bị thực hiện tính toán.
C. Một tệp chứa dữ liệu đầu vào.
D. Một phép toán có thời gian xem như không đổi.
Câu 4: Số lần thực hiện thao tác cơ sở thường phụ thuộc vào yếu tố nào?
A. Màu nền của trình soạn thảo.
B. Tên biến trong chương trình.
C. Kích thước dữ liệu đầu vào.
D. Vị trí lưu tệp mã nguồn.
Câu 5: Đoạn lệnh gán đơn thực hiện một lần có độ phức tạp nào?
A. O(1).
B. O(n).
C. O(n²).
D. O(log n).
Câu 6: Một vòng lặp chạy từ 0 đến n – 1 thường có độ phức tạp nào?
A. O(1).
B. O(log n).
C. O(n).
D. O(n²).
Câu 7: Hai vòng lặp độc lập, mỗi vòng chạy n lần, có tổng độ phức tạp nào?
A. O(1).
B. O(n).
C. O(n²).
D. O(2ⁿ).
Câu 8: Hai vòng lặp lồng nhau, mỗi vòng chạy n lần, có độ phức tạp nào?
A. O(1).
B. O(log n).
C. O(n).
D. O(n²).
Câu 9: Với T(n)=3n+5, độ phức tạp tiệm cận là gì?
A. O(1).
B. O(n).
C. O(n²).
D. O(3ⁿ).
Câu 10: Với T(n)=2n²+4n+7, độ phức tạp là gì?
A. O(n²).
B. O(n).
C. O(log n).
D. O(n³).
Câu 11: Vì sao có thể bỏ hệ số hằng khi đánh giá độ phức tạp?
A. Hệ số hằng luôn bằng 0.
B. Hệ số hằng không xuất hiện trong chương trình.
C. Máy tính tự động loại bỏ mọi phép tính.
D. Nó không làm thay đổi tốc độ tăng tiệm cận.
Câu 12: Khi n rất lớn, thành phần nào chi phối n²+100n+500?
A. 500.
B. 100n.
C. n².
D. Tổng các hệ số.
Câu 13: Thuật toán O(log n) thường xuất hiện khi nào?
A. Phạm vi bài toán giảm theo tỉ lệ cố định.
B. Mỗi phần tử được xét đúng n lần.
C. Hai vòng lặp n lần được lồng nhau.
D. Tất cả tập con đều được duyệt.
Câu 14: Tìm kiếm tuần tự trong trường hợp xấu nhất có độ phức tạp nào?
A. O(1).
B. O(n).
C. O(log n).
D. O(n²).
Câu 15: Tìm kiếm nhị phân có độ phức tạp thời gian nào?
A. O(1).
B. O(n).
C. O(log n).
D. O(n²).
Câu 16: Sắp xếp lựa chọn với hai vòng lặp thường có độ phức tạp nào?
A. O(1).
B. O(log n).
C. O(n).
D. O(n²).
Câu 17: Thuật toán O(n) và O(n²), thuật toán nào tăng chậm hơn khi n lớn?
A. Thuật toán O(n).
B. Thuật toán O(n²).
C. Hai thuật toán tăng như nhau.
D. Không thuật toán nào phụ thuộc n.
Câu 18: Khi n tăng gấp đôi, thời gian của thuật toán O(n) xấp xỉ thế nào?
A. Không thay đổi.
B. Tăng gấp đôi.
C. Tăng gấp bốn.
D. Tăng gấp tám.
Câu 19: Khi n tăng gấp đôi, thời gian của thuật toán O(n²) xấp xỉ thế nào?
A. Tăng gấp đôi.
B. Tăng gấp ba.
C. Tăng gấp tám.
D. Tăng gấp bốn.
Câu 20: Một vòng lặp có số lần thực hiện lần lượt là n, n/2, n/4,… có độ phức tạp nào?
A. O(1).
B. O(n).
C. O(log n).
D. O(n²).
Câu 21: Đoạn lệnh gồm một vòng O(n), tiếp theo một vòng O(n²), có tổng độ phức tạp nào?
A. O(n).
B. O(n²).
C. O(n³).
D. O(2ⁿ).
Câu 22: Hai đoạn chương trình O(n) được thực hiện liên tiếp có độ phức tạp nào?
A. O(n).
B. O(n²).
C. O(2ⁿ).
D. O(log n).
Câu 23: Một vòng lặp ngoài chạy n lần, vòng trong chạy i lần. Tổng độ phức tạp là gì?
A. O(1).
B. O(log n).
C. O(n).
D. O(n²).
Câu 24: Trường hợp xấu nhất của thuật toán được hiểu như thế nào?
A. Thuật toán cho kết quả không chính xác.
B. Máy tính có cấu hình thấp nhất.
C. Đầu vào làm thuật toán thực hiện nhiều nhất.
D. Chương trình có số dòng mã lớn nhất.
Câu 25: Độ phức tạp thời gian cho phép so sánh thuật toán mà ít phụ thuộc vào yếu tố nào?
A. Cấu hình máy và ngôn ngữ cài đặt.
B. Kích thước dữ liệu đầu vào.
C. Cấu trúc của thuật toán.
D. Số lần thực hiện thao tác.
Câu 26: Thuật toán A có O(n), thuật toán B có O(log n). Khi n rất lớn, nhận định nào phù hợp?
A. A luôn nhanh hơn B.
B. Hai thuật toán luôn bằng nhau.
C. Không thể so sánh tốc độ tăng.
D. B thường có tốc độ tăng chậm hơn.
Câu 27: Một thuật toán thực hiện đúng 5n² phép so sánh có độ phức tạp nào?
A. O(5n).
B. O(n²).
C. O(n³).
D. O(5ⁿ).
Câu 28: Cho T(n)=n³+n²+10. Thành phần bậc cao nhất là gì?
A. 10.
B. n².
C. n³.
D. n³+n².
Câu 29: Vì sao thuật toán độ phức tạp thấp thường được ưu tiên?
A. Có khả năng mở rộng tốt với dữ liệu lớn.
B. Luôn có mã nguồn ngắn nhất.
C. Không cần kiểm thử kết quả.
D. Không sử dụng bộ nhớ máy tính.
Câu 30: Nhận định nào đúng về độ phức tạp thời gian?
A. Cho biết chính xác số giây trên mọi máy.
B. Mô tả xu hướng tăng của lượng tính toán.
C. Chỉ áp dụng cho thuật toán sắp xếp.
D. Không liên quan kích thước dữ liệu vào.
