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 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 + E)
2. BO(V × E)
3. CO(E log V)
4. DO(V²)

Thời gian chạy nào sau đây là đa thức?

1. AO(n³)
2. BO(nⁿ)
3. CO(n!)
4. DO(2ⁿ)

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

Công thức truy hồi T(n) = T(n − 1) + O(1) có nghiệm là gì?

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

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ASắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớn
2. BSắp xếp chèn là O(n log n) trong trường hợp xấu nhất
3. CCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
4. DSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp trộn
2. BQuicksort (phiên bản tại chỗ điển hình)
3. CSắp xếp vun đống
4. DSắp xếp chọn (phiên bản điển hình)

Phát biểu nào về ký hiệu little-o là đúng?

1. An = o(n²), nhưng n không phải o(n)
2. Bn² = o(n)
3. C2n = o(n), vì 2n tăng chậm
4. Dn = o(n), vì mọi hàm đều là little-o của chính nó

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

1. ACác bài toán không thể giải trong thời gian đa thức
2. BCác bài toán quyết định có câu trả lời "có" kiểm chứng được trong thời gian đa thức khi cho một chứng chỉ
3. CCác bài toán không phải đa thức
4. DCác bài toán mà không thuật toán nào giải được