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

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Ghi nhớ (memoisation) là gì?

1. AViết chú thích bên cạnh từng dòng mã
2. BTự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi
3. CLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ
4. DGiải phóng bộ nhớ sau khi một hàm trả về

Ba bước của một thuật toán chia để trị là gì?

1. AĐoán, kiểm tra, lặp lại
2. BChia, trị, kết hợp
3. CSắp xếp, tìm kiếm, trả về
4. DĐọc, tính toán, ghi

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

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

Phân tích khấu hao đo lường điều gì?

1. AChi phí của một thuật toán trên đầu vào tốt nhất
2. BChi phí kỳ vọng trên các đầu vào ngẫu nhiên
3. CChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
4. DChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì n³ nhỏ hơn n² khi n lớn
2. BĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
3. CKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
4. DĐúng, nhưng chỉ khi n nhỏ hơn 100

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n^{log₂ 7}), khoảng n^2,81
4. DΘ(n³)

Phải chứng minh hai điều nào để chứng tỏ một bài toán quyết định X là NP-đầy đủ?

1. AX quy dẫn về một bài toán trong P, và X thuộc NP
2. BX thuộc NP, và một bài toán NP-đầy đủ đã biết quy dẫn về X trong thời gian đa thức
3. CX thuộc P, và X quy dẫn về SAT
4. DX không có thuật toán đa thức, và X quyết định được