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

Ghi nhớ (memoisation) là gì?

1. ALư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ớ
2. BGiải phóng bộ nhớ sau khi một hàm trả về
3. CTự độ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
4. DViết chú thích bên cạnh từng dòng mã

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

1. AQuy hoạch động
2. BLựa chọn tham lam
3. CChia để trị
4. DVét cạn

Một thuật toán O(n) mất 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A3 giây
2. B12 giây
3. C6 giây
4. D9 giây

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 100
2. BKhoảng 1,000
3. CKhoảng 20
4. DKhoảng 500,000

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

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

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

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AThuật toán Dijkstra
2. BFloyd–Warshall
3. CThuật toán Kruskal
4. DThuật toán Prim bắt đầu từ một nút

Vì sao tra cứu trung bình trong bảng băm là O(1) nhưng trường hợp xấu nhất là O(n)?

1. ANhiều khóa có thể va chạm vào cùng một ngăn
2. BMảng có truy cập O(n)
3. CHàm băm chậm
4. DCác khóa phải được sắp xếp trước