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 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)

Thuật toán vét cạn là gì?

1. AThuật toán chạy trên nhiều bộ xử lý
2. BThuật toán đoán một đáp án ngẫu nhiên
3. CThuật toán thử mọi lời giải ứng viên có thể
4. DThuật toán luôn dùng đệ quy

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AMảng không được có quá 1000 phần tử
2. BĐộ dài mảng phải là lũy thừa của hai
3. CMảng chỉ được chứa số dương
4. DMảng phải được sắp xếp

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ASắp xếp trộn không có cấu trúc đệ quy
2. BSắp xếp trộn đã là O(n)
3. CCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
4. DQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng

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

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

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm
2. BĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát
3. CThứ tự tô-pô trong mọi đồ thị
4. DCây khung nhỏ nhất

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

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

Sự khác biệt giữa một bài toán bất khả quyết định và một bài toán không khả thi (intractable) là gì?

1. ACả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
2. BBài toán bất khả quyết định không có thuật toán nào cho mọi đầu vào; bài toán không khả thi có thuật toán, nhưng quá chậm
3. CBài toán không khả thi không thể giải bằng bất kỳ thuật toán nào, còn bài toán bất khả quyết định chỉ cần thời gian hàm mũ
4. DBài toán bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P