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

Độ phức tạp không gian đo lường:

1. ALượng bộ nhớ một thuật toán cần khi đầu vào tăng
2. BKích thước vật lý của máy tính
3. CDung lượng đĩa của tệp chương trình sau khi được biên dịch
4. DSố dòng mã

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A8 giây
2. B2 giây
3. C4 giây
4. D1 giây

log₂ 1024 bằng bao nhiêu?

1. A512
2. B12
3. C10
4. D32

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Độ phức tạp thời gian khấu hao của việc thêm phần tử vào cuối một mảng động nhân đôi dung lượng khi đầy là bao nhiêu?

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

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

1. AO(V × E)
2. BO(V³)
3. CO(V + E)
4. DO((V + E) log V)

Thuật toán Bellman–Ford phát hiện chu trình trọng số âm có thể đến được từ nguồn bằng cách nào?

1. ANó chạy thuật toán Dijkstra hai lần và so sánh hai kết quả khoảng cách
2. BNó kiểm tra xem có cạnh nào có trọng số âm không
3. CNó đếm các chu trình bằng tìm kiếm theo chiều sâu
4. DSau V − 1 vòng, nó kiểm tra xem có cạnh nào vẫn có thể được nới lỏng không