15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 24 có đáp án
15 câu hỏi
PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ lựa chọn một phương án.
Độ 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?
O(n)O(n)O(n)
O(nlogn)O(n \log n)O(nlogn)
O(n2)O(n^2)O(n2)
O(n1.585)O(n^{1.585})O(n1.585)
Đáp án: D
Giải thích: Phép nhân hai số có nnn chữ số sử dụng thuật toán Karatsuba có độ phức tạp O(n1.585)O(n^{1.585})O(n1.585), cải thiện từ O(n2)O(n^2)O(n2) của thuật toán thông thường.
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?
2+n+1=n+32 + n + 1 = n + 32+n+1=n+3
n2+2n^2 + 2n2+2
2n+32n + 32n+3
n2+3n^2 + 3n2+3
Đáp án: A
Giải thích: Với chương trình 1, mỗi lệnh đơn tốn 1 đơn vị thời gian và có nnn bước trong vòng lặp, tổng thời gian là T1(n)=n+3T_1(n) = n + 3T1(n)=n+3.
Trong 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ì?
O(n)O(n)O(n)
O(logn)O(\log n)O(logn)
O(n2)O(n^2)O(n2)
O(1)O(1)O(1)
Đáp án: C
Giải thích: Do hai vòng lặp chạy lồng nhau với nnn lần, tổng độ phức tạp thời gian là O(n2)O(n^2)O(n2).
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ì?
Chương trình có độ phức tạp tuyến tính
Chương trình có độ phức tạp bình phương
Chương trình có độ phức tạp mũ
Chương trình có độ phức tạp hàng số
Đáp án: A
Giải thích: O(n)O(n)O(n) biểu thị độ phức tạp tuyến tính, tức là thời gian chạy tăng tuyến tính với kích thước đầu vào nnn.
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?
Khi có vòng lặp lồng nhau
Khi thực hiện hai chương trình nối tiếp nhau
Khi thực hiện phép toán nhân
Khi thực hiện phép toán chia
Đáp án: B
Giải thích: Quy tắc cộng được áp dụng khi tính độ phức tạp thời gian của hai chương trình nối tiếp nhau, lấy giá trị độ phức tạp lớn nhất
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ì?
O(n2)O(n^2)O(n2)
O(n)O(n)O(n)
O(logn)O(\log n)O(logn)
O(n3)O(n^3)O(n3)
Đáp án: A
Giải thích: Do n2n^2n2 là hàm bậc cao nhất, độ phức tạp thời gian của chương trình này là O(n2)O(n^2)O(n2).
Độ phức tạp thời gian của thuật toán sắp xếp chọn là bao nhiêu?
O(n)O(n)O(n)
O(logn)O(\log n)O(logn)
O(n2)O(n^2)O(n2)
O(nlogn)O(n \log n)O(nlogn)
Đáp án: C
Giải thích: Thuật toán sắp xếp chọn có độ phức tạp thời gian là O(n2)O(n^2)O(n2) do mỗi phần tử cần phải so sánh với các phần tử còn lại
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)?
Khi chương trình có vòng lặp lồng nhau
Khi chương trình chỉ có các phép toán đơn và không phụ thuộc vào nnn
Khi chương trình có độ phức tạp tuyến tính
Khi chương trình có độ phức tạp lũy thừa
Đáp án: B
Giải thích: Độ phức tạp O(1)O(1)O(1) có nghĩa là thời gian chạy không phụ thuộc vào kích thước đầu vào nnn.
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ì?
Tuyến tính
Logarit
Đa thức
Mũ
Đáp án: B
Giải thích: O(logn) biểu thị thuật toán có độ phức tạp logarit, thường thấy trong các thuật toán như tìm kiếm nhị phân.
Để 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?
Quy tắc cộng
Quy tắc nhân
Quy tắc chia
Quy tắc cộng và chia
Đáp án: B
Giải thích: Khi tính độ phức tạp thời gian của các phép toán lồng nhau, quy tắc nhân được áp dụng.
PHẦN II. Câu trắc nghiệm đúng sai. Thí sinh trả lời từ câu 1 đến câu 2. Trong mỗi ý a), b), c), d) ở mỗi câu, thí sinh chọn đúng hoặc sai
Độ 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²)
a) Sai, O(1) biểu thị độ phức tạp hằng số, không phụ thuộc vào kích thước đầu vào nnn, trong khi độ phức tạp của chương trình 1 phụ thuộc tuyến tính vào nnn.
b) Sai. O(log n) chỉ đúng cho các thuật toán mà thời gian tính toán tăng tỷ lệ logarit với nnn, điều này không đúng trong chương trình 1.
c) Đúng. O(n) nghĩa là thời gian tính toán tăng tuyến tính với kích thước đầu vào nnn, phù hợp với hàm T1(n)=n+3T_1(n) = n + 3T1(n)=n+3.
d) Sai. O(n²) mô tả độ phức tạp bậc hai, thường xuất hiện ở các thuật toán có vòng lặp lồng nhau, điều này không áp dụng cho chương trình 1.
Độ 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)
a) Sai. O(n) biểu thị độ phức tạp tuyến tính, không phù hợp với T2(n)=n2+3T_2(n) = n^2 + 3T2(n)=n2+3, vì thời gian tính toán của chương trình 2 tăng theo bậc hai của nnn.
b) Đúng. O(n²) biểu thị độ phức tạp bậc hai, phù hợp với cấu trúc vòng lặp lồng nhau của chương trình 2.
c) Sai. O(log n) biểu thị độ phức tạp logarit, thường gặp ở các thuật toán chia để trị, không áp dụng cho chương trình 2.
d) Sai. O(1) nghĩa là độ phức tạp hằng số, không thay đổi với kích thước đầu vào, không đúng với chương trình 2.
PHẦN III. Câu trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 3
Độ phức tạp thời gian của chương trình 1 trong hình 24.2 là gì?
Đá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.
Độ phức tạp thời gian của chương trình 2 trong hình 24.2 là gì?
Đá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.
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: 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.
