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

Đệ quy là gì?

1. AMột vòng lặp không bao giờ kết thúc
2. BMột loại cấu trúc dữ liệu
3. CMột hàm gọi chính nó trên các đầu vào nhỏ hơn
4. DMột phương pháp sắp xếp

Độ phức tạp thời gian của tìm kiếm tuần tự trong một mảng chưa sắp xếp gồm n phần tử (trường hợp xấu nhất) là gì?

1. AO(n²)
2. BO(1)
3. CO(n)
4. DO(log 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(n log n)
3. CO(n)
4. DO(log n)

Quy hoạch động hữu ích khi một bài toán có:

1. ACác bài toán con chồng lặp và cấu trúc con tối ưu
2. BMột vòng lặp duy nhất
3. CHoàn toàn không có bài toán con, nên có thể giải trong một bước
4. DChỉ các đầu vào ngẫu nhiê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 bắt đầu sớm nhất
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 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
4. DChọn hoạt động ngắn nhất trước

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì n³ nhỏ hơn n² khi n lớn
2. BĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
3. CKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
4. DĐúng, nhưng chỉ khi n nhỏ hơn 100

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

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

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