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?
AĐáp án A: O(n)O(n)O(n)
BĐáp án B: O(nlogn)O(n \log n)O(nlogn)
CĐáp án C: O(n2)O(n^2)O(n2)
DĐáp án D: O(n1.585)O(n^{1.585})O(n1.585)
Xem đáp án và lời giải
Lời giải do TopStudy biên soạn
Đáp án:D
Đá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.
Câu 2
1 điểm
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?
AĐáp án A: 2+n+1=n+32 + n + 1 = n + 32+n+1=n+3
BĐáp án B: n2+2n^2 + 2n2+2
CĐáp án C: 2n+32n + 32n+3
DĐáp án D: n2+3n^2 + 3n2+3
Xem đáp án và lời giải
Lời giải do TopStudy biên soạn
Đáp án:A
Đá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.
Câu 3
1 điểm
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ì?
AĐáp án A: O(n)O(n)O(n)
BĐáp án B: O(logn)O(\log n)O(logn)
CĐáp án C: O(n2)O(n^2)O(n2)
DĐáp án D: O(1)O(1)O(1)
Xem đáp án và lời giải
Lời giải do TopStudy biên soạn
Đáp án:C
Đá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).
Câu 4
1 điểm
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ì?
AĐáp án A: Chương trình có độ phức tạp tuyến tính
BĐáp án B: Chương trình có độ phức tạp bình phương
CĐáp án C: Chương trình có độ phức tạp mũ
DĐáp án D: Chương trình có độ phức tạp hàng số
Xem đáp án và lời giải
Lời giải do TopStudy biên soạn
Đáp án:A
Đá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.
Câu 5
1 điểm
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?
AĐáp án A: Khi có vòng lặp lồng nhau
BĐáp án B: Khi thực hiện hai chương trình nối tiếp nhau
CĐáp án C: Khi thực hiện phép toán nhân
DĐáp án D: Khi thực hiện phép toán chia
Xem đáp án và lời giải
Lời giải do TopStudy biên soạn
Đáp án:B
Đá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
Câu 6
1 điểm
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ì?