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

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

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

Trường hợp cơ sở của một hàm đệ quy là gì?

1. ADòng đầu tiên của hàm
2. BTrường hợp có đầu vào lớn nhất, được xử lý trước mọi lời gọi đệ quy
3. CTrường hợp được trả lời trực tiếp mà không thực hiện thêm lời gọi đệ quy nào
4. DLời gọi dùng nhiều bộ nhớ nhất

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

1. AO(n²)
2. BO(log n)
3. CO(n)
4. DO(n log 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(log n)
4. DO(n log n)

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

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^{log₂ 7}), khoảng n^2,81
3. CΘ(n²)
4. DΘ(n² log n)