Phiếu bài tập Thuật toán và độ phức tạp có đáp á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 chỉ được chứa số dương
3. CMảng không được có quá 1000 phần tử
4. DĐộ dài mảng phải là lũy thừa của hai

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

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

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(V + E)
2. BO(E log V)
3. CO(V²)
4. DO(V × E)

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

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

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

Một thuật toán tham lam:

1. AThử mọi lời giải có thể
2. BLuôn cho lời giải tối ưu
3. CChỉ dùng đệ quy
4. DĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước

2²ⁿ có thuộc O(2ⁿ) không?

1. AKhông, vì 2²ⁿ = 4ⁿ và 4ⁿ / 2ⁿ = 2ⁿ tăng không giới hạn
2. BCó, vì cả hai đều là hàm mũ
3. CCó, vì các hệ số hằng trong số mũ luôn bị bỏ qua trong Big O
4. DKhông, vì 2²ⁿ tăng chậm hơn 2ⁿ

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. ACó, nhưng chỉ với mảng ngắn hơn 100
2. BKhô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
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