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

log₂ 1024 bằng bao nhiêu?

1. A32
2. B12
3. C512
4. D10

Đệ quy là gì?

1. AMột loại cấu trúc dữ liệu
2. BMột vòng lặp không bao giờ kết thúc
3. CMột hàm gọi chính nó trên các đầu vào nhỏ hơn
4. DMột phương pháp sắp xếp

Hàm nào sau đây tăng chậm nhất khi n lớn dần?

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

Vì sao nhiều hàm sắp xếp trong thư viện chuyển sang sắp xếp chèn cho các mảng con rất nhỏ?

1. ACác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
2. BSắp xếp chèn là O(n log n) trong trường hợp xấu nhất
3. CSắp xếp chèn ít chi phí phụ và nhanh trên đầu vào nhỏ hoặc gần như đã sắp xếp
4. DSắp xếp chèn dùng ít bộ nhớ hơn mọi thuật toán sắp xếp khác trên đầu vào lớ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(d(n + k))
2. BO(n²)
3. CO(n log n)
4. DO(dn log k)

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng mà các phần tử đều khác nhau
2. BMột mảng đã được sắp xếp
3. CMột mảng có độ dài 2
4. DMột mảng có thứ tự ngẫu nhiê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²)
2. BO(n √n)
3. CO(n log 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. ANhiều khóa có thể va chạm vào cùng một ngăn
2. BMảng có truy cập O(n)
3. CHàm băm chậm
4. DCác khóa phải được sắp xếp trước