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

Thời gian chạy nào sau đây là đa thức?

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

Ba bước của một thuật toán chia để trị là gì?

1. AChia, trị, kết hợp
2. BĐoán, kiểm tra, lặp lại
3. CĐọc, tính toán, ghi
4. DSắp xếp, tìm kiếm, trả về

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng n²
2. BKhoảng log₂ n
3. CKhoảng n / 2
4. DKhoảng n

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

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

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

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

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

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. BThuật toán Kruskal
3. CThuật toán Prim bắt đầu từ một nút
4. DFloyd–Warshall

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. AMảng có truy cập O(n)
2. BNhiều khóa có thể va chạm vào cùng một ngăn
3. CCác khóa phải được sắp xếp trước
4. DHàm băm chậm