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

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af tăng nhanh hơn g một cách nghiêm ngặt
2. Bf luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới
3. Cf tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g
4. Df tăng chậm hơn g một cách nghiêm ngặt

Thuật toán là gì?

1. ABất kỳ chương trình máy tính nào có giao diện đồ họa
2. BMột dãy hữu hạn các bước được xác định rõ để giải một bài toán
3. CMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học
4. DMột cấu trúc dữ liệu lưu trữ các số

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

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. BCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
3. CSắp xếp chèn là O(n log n) trong trường hợp xấu nhấ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

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

1. AO(n³)
2. BO(n)
3. CO(n²)
4. DO(n 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. ABắt buộc phải dùng Bellman–Ford trong mọi trường hợp
2. BTìm kiếm theo chiều sâu
3. CThuật toán Kruskal
4. DThuật toán Dijkstra

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)
3. CΘ(n log² n)
4. DΘ(n²)

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n^{log₂ 7}), khoảng n^2,81
2. BΘ(n² log n)
3. CΘ(n³)
4. DΘ(n²)