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

Thuật toán là gì?

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

Ghi nhớ (memoisation) là gì?

1. AGiải phóng bộ nhớ sau khi một hàm trả về
2. BTự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi
3. CLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ
4. DViết chú thích bên cạnh từng dòng mã

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

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

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AĐúng, nhưng chỉ khi n nhỏ hơn 100
2. BKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
3. CKhông, vì n³ nhỏ hơn n² khi n lớn
4. DĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³

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

1. AO(n²)
2. BO(n)
3. CO(2ⁿ)
4. DO(log 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³)
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n^{log₂ 7}), khoảng n^2,81

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. ALuôn chọn phần tử đầu tiên
2. BChỉ dùng đệ quy ở phía bên trái
3. CChọn pivot đồng đều ngẫu nhiên
4. DSắp xếp đầu vào trước khi chạy quicksort