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

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

1. AΘ (Big Theta)
2. Bo (little o)
3. CO (Big O)
4. DΩ (Big Omega)

Một bài toán thường được gọi là khả thi (tractable) nếu:

1. ANó chỉ có thể được giải bằng cách thử mọi khả năng
2. BNó có thể được giải trong thời gian hằng số
3. CNó không có lời giải
4. DNó có thể được giải trong thời gian đa thức

Ghi nhớ (memoisation) là gì?

1. AViết chú thích bên cạnh từng dòng mã
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. DTự độ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

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AMột cây khung nhỏ nhất trong O(E log V)
2. BĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)
3. CMột thứ tự tô-pô trong O(V²)
4. DĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Đị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. BP không bằng NP
3. CBài toán dừng là bất khả quyết định
4. DBài toán thỏa mãn Boole (SAT) là NP-đầy đủ

Đường đi đơn ngắn nhất có thể tìm trong thời gian đa thức. Điều gì được biết về việc tìm đường đi đơn dài nhất giữa hai đỉnh trong đồ thị tổng quát?

1. ANó là NP-khó
2. BNó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu
3. CNó luôn giải được trong O(V + E)
4. DNó bất khả quyết định