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

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới
2. Bf tăng chậm hơn g một cách nghiêm ngặt
3. Cf tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g
4. Df tăng nhanh hơn g một cách nghiêm ngặt

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

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

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(V²)
2. BO(V × E)
3. CO(V + E)
4. DO(E log V)

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

Quy hoạch động hữu ích khi một bài toán có:

1. AMột vòng lặp duy nhất
2. BChỉ các đầu vào ngẫu nhiên
3. CCác bài toán con chồng lặp và cấu trúc con tối ưu
4. DHoàn toàn không có bài toán con, nên có thể giải trong một bước

Phải chứng minh hai điều nào để chứng tỏ một bài toán quyết định X là NP-đầy đủ?

1. AX thuộc P, và X quy dẫn về SAT
2. BX quy dẫn về một bài toán trong P, và X thuộc NP
3. CX thuộc NP, và một bài toán NP-đầy đủ đã biết quy dẫn về X trong thời gian đa thức
4. DX không có thuật toán đa thức, và X quyết định được

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