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 trong trường hợp xấu nhất của sắp xếp chèn là gì?

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

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng n / 2
2. BKhoảng log₂ n
3. CKhoảng n²
4. DKhoảng n

Truy cập một phần tử theo chỉ số trong một mảng mất:

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

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(log n)
2. BO(n)
3. CO(n log 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. ASắ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
2. BCác thuật toán đệ quy không xử lý được mảng dưới 10 phần tử
3. CSắp xếp chèn là O(n log n) trong trường hợp xấu nhất
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

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. BLogarit luôn được làm tròn thành số nguyên
3. CMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu
4. DCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AChứng minh X kiểm chứng được trong thời gian đa thức
2. BQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức
3. CChứng minh X không có thuật toán đa thức cho đầu vào nhỏ
4. DQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức

n! và 2ⁿ so sánh với nhau thế nào khi n lớn?

1. An! tăng nhanh hơn 2ⁿ
2. BChúng tăng với cùng tốc độ
3. Cn! là O(n²)
4. D2ⁿ tăng nhanh hơn n!