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

Độ phức tạp thời gian của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

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

Đệ quy là gì?

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

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

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

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

1. AO(n²)
2. BO(1)
3. CO(n)
4. DO(log 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í trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
3. CChi phí kỳ vọng trên các đầu vào ngẫu nhiên
4. DChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi

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

Thuật toán Bellman–Ford phát hiện chu trình trọng số âm có thể đến được từ nguồn bằng cách nào?

1. ANó chạy thuật toán Dijkstra hai lần và so sánh hai kết quả khoảng cách
2. BSau V − 1 vòng, nó kiểm tra xem có cạnh nào vẫn có thể được nới lỏng không
3. CNó kiểm tra xem có cạnh nào có trọng số âm không
4. DNó đếm các chu trình bằng tìm kiếm theo chiều sâu

Vì sao mọi tìm kiếm dựa trên so sánh trong một mảng đã sắp xếp cần Ω(log n) phép so sánh trong trường hợp xấu nhất?

1. AMỗi phép so sánh mất thời gian logarit
2. BMọi phần tử phải được so sánh ít nhất một lần
3. CMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n
4. DTìm kiếm nhị phân là thuật toán khả dĩ duy nhất, và nó cần log₂ n phép so sánh