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

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

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

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

1. AChia để trị
2. BVét cạn
3. CLựa chọn tham lam
4. DQuy hoạch động

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

1. AO(dn log k)
2. BO(n²)
3. CO(d(n + k))
4. DO(n log n)

Độ phức tạp thời gian của: for i = 1 to n: for (j = i; j ≤ n; j = j + i) thực hiện công việc O(1) là gì?

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

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