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

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng log₂ n
2. BKhoảng n²
3. CKhoảng n / 2
4. DKhoảng n

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. AVét cạn
2. BQuy hoạch động
3. CChia để trị
4. DLựa chọn tham lam

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

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

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

1. AO(k n log n)
2. BO(n + k)
3. CO(nk)
4. DO(n log n + k log n)

Thuật toán Prim xây dựng cây khung nhỏ nhất như thế nào?

1. ANó phát triển một cây từ đỉnh xuất phát, thêm cạnh rẻ nhất đi ra khỏi cây
2. BNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
3. CNó sắp xếp mọi cạnh theo trọng số và thêm từng cạnh trừ khi nó tạo chu trình trong rừng
4. DNó xóa cạnh đắt nhất cho đến khi không còn chu trình

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. ABài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó
2. BMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con
3. CBài toán có thể giải trong thời gian hằng số
4. DMọi bài toán con đều có cùng kích thước

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(2ⁿ) và không gian O(1)
2. BThời gian O(n) và không gian O(1)
3. CThời gian O(n) và không gian O(n)
4. DThời gian O(log n) và không gian O(n)

n! và 2ⁿ so sánh với nhau thế nào khi n lớn?

1. A2ⁿ tăng nhanh hơn n!
2. BChúng tăng với cùng tốc độ
3. Cn! là O(n²)
4. Dn! tăng nhanh hơn 2ⁿ