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

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AVét cạn
2. BLựa chọn tham lam
3. CChia để trị
4. DQuy hoạch động

Big O của 3n² + 5n + 2 là gì?

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

log₂ 1024 bằng bao nhiêu?

1. A12
2. B10
3. C32
4. D512

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng có độ dài 2
2. BMột mảng mà các phần tử đều khác nhau
3. CMột mảng đã được sắp xếp
4. DMột mảng có thứ tự ngẫu nhiên

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động ngắn nhất trước
2. BChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích
3. CChọn hoạt động bắt đầu sớm nhất
4. DChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

Sắp xếp chèn chạy trong O(n) trên đầu vào đã sắp xếp. Điều này có mâu thuẫn với cận dưới Ω(n log n) cho sắp xếp dựa trên so sánh không?

1. AKhông, cận dưới áp dụng cho trường hợp xấu nhất trên mọi đầu vào, không phải cho từng đầu vào
2. BCó, nhưng chỉ với mảng ngắn hơn 100
3. CKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh
4. DCó, nên cận dưới là sai

Chi phí khấu hao của việc tăng một bộ đếm nhị phân là bao nhiêu, biết rằng một lần tăng có thể lật nhiều bit?

1. AO(n) mỗi lần tăng
2. BO(n log n) mỗi lần tăng
3. CO(1) mỗi lần tăng
4. DO(log n) mỗi lần tăng