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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó xử lý đúng một phần tử mỗi giây thời gian chạy
2. BThời gian chạy của nó không tăng theo kích thước đầu vào
3. CNó chỉ có thể chạy một lần
4. DNó luôn mất đúng một giây

Tốc độ tăng O(2ⁿ) được gọi là gì?

1. AHàm mũ
2. BĐa thức
3. CLogarit
4. DTuyến tính

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp vun đống
2. BSắp xếp chọn (phiên bản điển hình)
3. CQuicksort (phiên bản tại chỗ điển hình)
4. DSắp xếp trộn

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

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

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

Chi phí khấu hao của việc tăng một bộ đếm nhị phân là bao nhiêu, biết rằng một lần tăng có thể lật nhiều bit?

1. AO(n) mỗi lần tăng
2. BO(n log n) mỗi lần tăng
3. CO(1) mỗi lần tăng
4. DO(log n) mỗi lần tăng

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