Phiếu bài tập Thuật toán và độ phức tạp có đáp á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(k log n)
2. BO(n²)
3. CO(n + k)
4. DO(n log n)

Ghi nhớ (memoisation) là gì?

1. ATự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi
2. BLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ
3. CGiải phóng bộ nhớ sau khi một hàm trả về
4. DViết chú thích bên cạnh từng dòng mã

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. AΩ (Big Omega)
2. BΘ (Big Theta)
3. Co (little o)
4. DO (Big O)

Độ 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(2^m+n)
2. BO(m + n)
3. CO(mn)
4. DO(mn log 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. BLogarit luôn được làm tròn thành số nguyên
3. CCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
4. DMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AThứ tự tô-pô trong mọi đồ thị
2. BCây khung nhỏ nhất
3. CĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
4. DĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát

Sắp xếp tô-pô chỉ khả thi đối với:

1. AĐồ thị có hướng không chu trình
2. BĐồ thị đầy đủ
3. CĐồ thị có trọng số âm
4. DĐồ thị vô hướng

Định lý Cook–Levin đã thiết lập điều gì?

1. AMọi bài toán NP đều giải được trong thời gian hàm mũ
2. BBài toán dừng là bất khả quyết định
3. CBài toán thỏa mãn Boole (SAT) là NP-đầy đủ
4. DP không bằng NP