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

Một bài toán thường được gọi là khả thi (tractable) nếu:

1. ANó chỉ có thể được giải bằng cách thử mọi khả năng
2. BNó có thể được giải trong thời gian hằng số
3. CNó có thể được giải trong thời gian đa thức
4. DNó không có lời giải

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

Ghi nhớ (memoisation) là gì?

1. ATự độ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
2. BGiải phóng bộ nhớ sau khi một hàm trả về
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. DViết chú thích bên cạnh từng dòng mã

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

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

1. AO(n + k)
2. BO(k n log n)
3. CO(nk)
4. DO(n log n + k log n)

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

1. AO(n log n)
2. BO(n)
3. CO(n²)
4. DO(log 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² log n)
2. BΘ(n^{log₂ 7}), khoảng n^2,81
3. CΘ(n³)
4. DΘ(n²)

Bài toán người bán hàng rong được phân loại thế nào?

1. APhiên bản quyết định thuộc P nhưng phiên bản tối ưu hóa là NP-đầy đủ
2. BNó bất khả quyết định
3. CPhiên bản quyết định là NP-đầy đủ và phiên bản tối ưu hóa là NP-khó
4. DNó thuộc P vì thuật toán Dijkstra giải được nó bằng cách thăm mỗi thành phố một lần