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

Thuật toán vét cạn là gì?

1. AThuật toán thử mọi lời giải ứng viên có thể
2. BThuật toán đoán một đáp án ngẫu nhiên
3. CThuật toán chạy trên nhiều bộ xử lý
4. DThuật toán luôn dùng đệ quy

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

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(mn log n)
2. BO(2^m+n)
3. CO(mn)
4. DO(m + n)

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

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

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. AQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
2. BSắp xếp trộn đã là O(n)
3. CCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
4. DSắp xếp trộn không có cấu trúc đệ quy

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²)
3. CΘ(n log n)
4. DΘ(n log² n)

Dùng định lý chủ, T(n) = 8T(n/2) + O(n²) có nghiệm là:

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