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

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp trộn
2. BSắp xếp nổi bọt
3. CQuicksort
4. DSắp xếp chèn

log₂ 1024 bằng bao nhiêu?

1. A12
2. B512
3. C32
4. D10

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp trộn
2. BQuicksort (phiên bản tại chỗ điển hình)
3. CSắp xếp vun đống
4. DSắp xếp chọn (phiên bản điển hình)

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ACơ số chỉ quan trọng với n nhỏ
2. BMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu
3. CCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
4. DLogarit luôn được làm tròn thành số nguyên

Cận nào là đúng cho log(n!)?

1. AΘ(n²)
2. BΘ(n)
3. CΘ(log n)
4. DΘ(n log 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. BNhiều khóa có thể va chạm vào cùng một ngăn
3. CHàm băm chậm
4. DCác khóa phải được sắp xếp trước