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

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. AQuicksort
2. BSắp xếp trộn
3. CSắp xếp nổi bọt
4. DSắp xếp vun đống

Sắp xếp trộn dùng chiến lược thiết kế nào?

1. ALựa chọn tham lam
2. BVét cạn
3. CQuy hoạch động
4. DChia để trị

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Thuật toán nào tìm đường đi ngắn nhất từ một nguồn trong đồ thị có trọng số cạnh không âm?

1. ATìm kiếm theo chiều sâu
2. BThuật toán Dijkstra
3. CThuật toán Kruskal
4. DBắt buộc phải dùng Bellman–Ford trong mọi trường hợp

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
2. BMột thứ tự tô-pô trong O(V²)
3. CĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)
4. DMột cây khung nhỏ nhất trong O(E log V)

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

1. AO(n log n)
2. BO(n²)
3. CO(d(n + k))
4. DO(dn log k)

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

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

1. AΘ(n log n)
2. BΘ(n log² n)
3. CΘ(n²)
4. DΘ(n)