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

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 luôn dùng đệ quy
3. CThuật toán thử mọi lời giải ứng viên có thể
4. DThuật toán đoán một đáp án ngẫu nhiên

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

Lớp độ phức tạp nào tăng nhanh nhất khi n lớn?

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

Độ phức tạp thời gian của thuật toán Bellman–Ford trên đồ thị có V đỉnh và E cạnh là gì?

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

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. AQuy 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
2. BSắp xếp trộn không có cấu trúc đệ quy
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. DSắp xếp trộn đã là O(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 bắt đầu sớm nhất
4. DChọn hoạt động ngắn nhất trước

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

1. ACác bài toán không phải đa thức
2. BCác bài toán không thể giải trong thời gian đa thức
3. CCác bài toán mà không thuật toán nào giải được
4. DCá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ỉ

Đường đi đơn ngắn nhất có thể tìm trong thời gian đa thức. Điều gì được biết về việc tìm đường đi đơn dài nhất giữa hai đỉnh trong đồ thị tổng quát?

1. ANó có thể giải bằng thuật toán Dijkstra với trọng số đổi dấu
2. BNó luôn giải được trong O(V + E)
3. CNó là NP-khó
4. DNó bất khả quyết định