Câu 1
Độ phức tạp thời gian của phép nhân hai số nguyên có nnn chữ số, như trong ví dụ của Karatsuba, là bao nhiêu?
Đáp án và lời giải
Đáp án: D
Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24 (có đáp án): Đánh giá độ phức tạp thời gian thuật toán
Xem trước: đọc nhanh mọi câu dạng chữ, chưa tính giờ, chưa hiện đáp án.
Luyện tập: chọn đáp án là biết đúng sai ngay, kèm lời giải.
Thi thử: nộp bài mới chấm điểm và hiện lời giải.
Luyện tập: chọn đáp án là biết đúng sai ngay, kèm lời giải.
Thi thử: nộp bài mới chấm điểm và hiện lời giải.
Câu 2
Trong chương trình 1 ở Hình 24.2, tổng số đơn vị thời gian để thực hiện toàn bộ chương trình là bao nhiêu?
Đáp án và lời giải
Đáp án: A
Câu 3
Đáp án do AI giảiTrong chương trình 2 ở Hình 24.2, độ phức tạp thời gian của vòng lặp lồng nhau là gì?
Đáp án và lời giải
Đáp án: C
Câu 4
Ký hiệu O(n)O(n)O(n) trong phân tích độ phức tạp thời gian biểu thị điều gì?
Đáp án và lời giải
Đáp án: A
Câu 5
Quy tắc cộng trong tính độ phức tạp thời gian của thuật toán được áp dụng trong trường hợp nào?
Đáp án và lời giải
Đáp án: B
Câu 6
Nếu chương trình có độ phức tạp thời gian T(n)=n2+3n+1T(n) = n^2 + 3n + 1T(n)=n2+3n+1, độ phức tạp thời gian của nó là gì?
Đáp án và lời giải
Đáp án: A
Câu 7
Độ phức tạp thời gian của thuật toán sắp xếp chọn là bao nhiêu?
Đáp án và lời giải
Đáp án: C
Câu 8
Trong trường hợp nào độ phức tạp thời gian của chương trình là O(1)O(1)O(1)?
Đáp án và lời giải
Đáp án: B
Câu 9
Ký hiệu O(logn)O(\log n)O(logn) được dùng khi độ phức tạp thời gian của thuật toán là gì?
Đáp án và lời giải
Đáp án: B
Câu 10
Để tính độ phức tạp thời gian của chương trình với các phép toán lồng nhau, ta áp dụng quy tắc nào?
Đáp án và lời giải
Đáp án: B
Câu 11
Độ phức tạp thời gian của chương trình 1 trong Hình 24.2, với tổng thời gian tính toán là T1(n)=n+3T_1(n) = n + 3T1(n)=n+3, được đánh giá là:
- a)O(1)
- b)O(log n)
- c)O(n)
- d)O(n²)
Đáp án và lời giải
Đáp án: a) Sai; b) Sai; c) Đúng; d) Sai
Câu 12
Độ phức tạp thời gian của chương trình 2 trong Hình 24.2, với tổng thời gian tính toán là T2(n)=n2+3T_2(n) = n^2 + 3T2(n)=n2+3, được đánh giá là:
- a)O(n)
- b)O(n²)
- c)O(log n)
- d)O(1)
Đáp án và lời giải
Đáp án: a) Sai; b) Đúng; c) Sai; d) Sai
Câu 13
Độ phức tạp thời gian của chương trình 1 trong hình 24.2 là gì?
Đáp án và lời giải
Đáp án: Độ phức tạp thời gian của chương trình 1 là O(n) Giải thích: Chương trình 1 thực hiện một lệnh gán và một vòng lặp với n bước, trong đó mỗi bước của vòng lặp thực hiện một phép toán. Tổng thời gian chạy được tính là T₁(n) = 2 + n + 1 = n + 3, do đó khi n lớn, thời gian chạy có thể ước lượng là O(n), tức là tuyến tính.
Câu 14
Độ phức tạp thời gian của chương trình 2 trong hình 24.2 là gì?
Đáp án và lời giải
Đáp án: Độ phức tạp thời gian của chương trình 2 là O(n²). Giải thích: Chương trình 2 có hai vòng lặp lồng nhau, mỗi vòng lặp đều chạy n lần. Vì vậy, tổng số phép toán sẽ là n * n = n². Thời gian chạy được tính là T₂(n) = 2 + 2 + 1 + n² + n² + 3 = n² + 5, do đó khi n lớn, thời gian chạy có thể ước lượng là O(n²), tức là bình phương.
Câu 15
Tại sao việc ước lượng thời gian chạy của chương trình lại quan trọng trong lập trình?
Đáp án và lời giải
Đáp án: Việc ước lượng thời gian chạy giúp lập trình viên hiểu rõ hơn về hiệu suất của thuật toán và tối ưu hóa mã nguồn. Giải thích: Khi phát triển phần mềm, thời gian thực hiện của các thuật toán có thể ảnh hưởng lớn đến hiệu suất tổng thể của ứng dụng. Hiểu độ phức tạp thời gian giúp lập trình viên lựa chọn thuật toán phù hợp nhất cho dữ liệu đầu vào lớn, từ đó cải thiện khả năng xử lý và tiết kiệm tài nguyên máy tính.