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

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. AΘ (Big Theta)
2. BΩ (Big Omega)
3. Co (little o)
4. DO (Big O)

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. ASắp xếp trộn
2. BSắp xếp vun đống
3. CSắp xếp nổi bọt
4. DQuicksort

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

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

Độ 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)

Một bài toán có cấu trúc con tối ưu nghĩa là gì?

1. AMột lời giải tối ưu có thể được xây dựng từ các lời giải tối ưu của các bài toán con
2. BBài toán có thể giải trong thời gian hằng số
3. CMọi bài toán con đều có cùng kích thước
4. DBài toán có đúng một lời giải tối ưu, và mọi bài toán con đều dùng chung lời giải đó

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

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

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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