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. AChia để trị
2. BQuy hoạch động
3. CVét cạn
4. DLựa chọn tham lam

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(1)
2. BO(n)
3. CO(log n)
4. DO(n²)

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AMảng phải được sắp xếp
2. BMảng không được có quá 1000 phần tử
3. CĐộ dài mảng phải là lũy thừa của hai
4. DMảng chỉ được chứa số dương

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

1. AKhoảng n
2. BKhoảng log₂ n
3. CKhoảng √n
4. DKhoảng n / 2

Quy hoạch động hữu ích khi một bài toán có:

1. AHoàn toàn không có bài toán con, nên có thể giải trong một bước
2. BMột vòng lặp duy nhất
3. CChỉ các đầu vào ngẫu nhiên
4. DCác bài toán con chồng lặp và cấu trúc con tối ưu

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. AQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
2. BSắp xếp trộn đã là O(n)
3. CSắp xếp trộn không có cấu trúc đệ quy
4. DCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. AChọn pivot đồng đều ngẫu nhiên
2. BLuôn chọn phần tử đầu tiên
3. CSắp xếp đầu vào trước khi chạy quicksort
4. DChỉ dùng đệ quy ở phía bên trái

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(log n) và không gian O(n)
2. BThời gian O(n) và không gian O(1)
3. CThời gian O(2ⁿ) và không gian O(1)
4. DThời gian O(n) và không gian O(n)