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

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

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

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

1. ALựa chọn tham lam
2. BChia để trị
3. CQuy hoạch động
4. DVét cạn

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

Phân tích khấu hao đo lường điều gì?

1. AChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
2. BChi phí của một thuật toán trên đầu vào tốt nhất
3. CChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
4. DChi phí kỳ vọng trên các đầu vào ngẫu nhiên

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 500,000
2. BKhoảng 20
3. CKhoảng 1,000
4. DKhoảng 100

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

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

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

1. AΘ(n)
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n log² n)

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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