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

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp chèn
2. BSắp xếp nổi bọt
3. CQuicksort
4. DSắp xếp trộn

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. AHằng số
2. BTuyến tính
3. CBậc hai
4. DLogarit

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. AMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu
2. BCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
3. CLogarit luôn được làm tròn thành số nguyên
4. DCơ số chỉ quan trọng với n nhỏ

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

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

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

Bài toán cái túi 0/1 giải bằng quy hoạch động mất thời gian O(nW). Vì sao điều này được gọi là giả đa thức?

1. AVì n luôn nhỏ
2. BVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào
3. CW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W
4. DVì nó chỉ hoạt động khi W = 0

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

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