Phiếu bài tập Thuật toán và độ phức tạp có đáp án

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

1. AO(log n)
2. BO(n²)
3. CO(2n)
4. DO(n)

Đệ quy là gì?

1. AMột loại cấu trúc dữ liệu
2. BMột vòng lặp không bao giờ kết thúc
3. CMột hàm gọi chính nó trên các đầu vào nhỏ hơn
4. DMột phương pháp sắp xếp

log₂ 1024 bằng bao nhiêu?

1. A32
2. B512
3. C10
4. D12

Công thức truy hồi T(n) = T(n − 1) + O(1) có nghiệm là gì?

1. AO(n²)
2. BO(n)
3. CO(log n)
4. DO(2ⁿ)

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ACác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
2. BLogarit luôn được làm tròn thành số nguyên
3. CCơ số chỉ quan trọng với n nhỏ
4. DMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

1. AO(2ⁿ)
2. BO(n)
3. CO(n²)
4. DO(log n)

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức
2. BChứng minh X không có thuật toán đa thức cho đầu vào nhỏ
3. CChứng minh X kiểm chứng được trong thời gian đa thức
4. DQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức

Lấy cả hai đầu mút của mọi cạnh trong một cặp ghép cực đại cho ta một phủ đỉnh. Phủ này tốt đến mức nào?

1. AKhông rõ chất lượng so với tối ưu
2. BLuôn là một phủ đỉnh nhỏ nhất
3. CCó kích thước tối đa gấp đôi phủ đỉnh nhỏ nhất
4. DTối đa log n lần giá trị nhỏ nhất