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 theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

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

Big O của 3n² + 5n + 2 là gì?

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

Ghi nhớ (memoisation) là gì?

1. AViết chú thích bên cạnh từng dòng mã
2. BTự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi
3. CLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ
4. DGiải phóng bộ nhớ sau khi một hàm trả về

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)

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

Công thức truy hồi T(n) = T(n − 1) + O(n) có nghiệm là gì?

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

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n³)
2. BΘ(n^{log₂ 7}), khoảng n^2,81
3. CΘ(n²)
4. DΘ(n² log n)

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 không có thuật toán đa thức, và X quyết định được
2. BX thuộc P, và X quy dẫn về SAT
3. CX quy dẫn về một bài toán trong P, và X thuộc NP
4. DX 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