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

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

Thời gian chạy nào sau đây là đa thức?

1. AO(2ⁿ)
2. BO(nⁿ)
3. CO(n³)
4. DO(n!)

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

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

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

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

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. ATì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
2. BMỗi phép so sánh mất thời gian logarit
3. CMọi phần tử phải được so sánh ít nhất một lần
4. DMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n

Định nghĩa nào của lớp P là đúng?

1. ACác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
2. BCác bài toán cần thời gian hàm mũ trên mọi máy tính
3. CCác bài toán có thể giải song song
4. DCác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức