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

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g
2. Bf luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới
3. Cf tăng nhanh hơn g một cách nghiêm ngặt
4. Df tăng chậm hơn g một cách nghiêm ngặt

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

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

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích
2. BChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích
3. CChọn hoạt động bắt đầu sớm nhất
4. DChọn hoạt động ngắn nhất trước

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

1. ANó xóa cạnh đắt nhất cho đến khi không còn chu trình
2. BNó chạy tìm kiếm theo chiều rộng và giữ lại cây BFS
3. CNó 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
4. DNó 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

Phân tích khấu hao đo lường điều gì?

1. AChi phí kỳ vọng trên các đầu vào ngẫu nhiên
2. BChi phí của một thuật toán trên đầu vào tốt nhất
3. CChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
4. DChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất

2²ⁿ có thuộc O(2ⁿ) không?

1. ACó, vì cả hai đều là hàm mũ
2. BKhông, vì 2²ⁿ tăng chậm hơn 2ⁿ
3. CKhông, vì 2²ⁿ = 4ⁿ và 4ⁿ / 2ⁿ = 2ⁿ tăng không giới hạn
4. DCó, vì các hệ số hằng trong số mũ luôn bị bỏ qua trong Big O

Định nghĩa nào của lớp P là đúng?

1. ACác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức
2. BCác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
3. CCác bài toán cần thời gian hàm mũ trên mọi máy tính
4. DCác bài toán có thể giải song song