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 trong trường hợp xấu nhất của sắp xếp trộn là gì?

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

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ALời gọi dùng nhiều bộ nhớ nhất
2. BTrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nào
3. CDòng đầu tiên của hàm
4. DTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

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 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
2. BChọ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
3. CChọn hoạt động ngắn nhất trước
4. DChọn hoạt động bắt đầu sớm nhất

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(nk)
2. BO(n + k)
3. CO(k n log n)
4. DO(n log n + k log n)

Đị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ó thể giải song song
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ó lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức

Bài toán thỏa mãn nào sau đây được biết là giải được trong thời gian đa thức?

1. A3-SAT, trong đó mỗi mệnh đề có đúng ba literal
2. BThỏa mãn mạch
3. C2-SAT, trong đó mỗi mệnh đề có tối đa hai literal
4. DSAT tổng quát trên các công thức dạng chuẩn tắc hội