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

Ghi nhớ (memoisation) là gì?

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

Độ 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(E log V)
3. CO(V + E)
4. DO(V × E)

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. AQuicksort
2. BSắp xếp trộn
3. CSắp xếp nổi bọt
4. DSắp xếp vun đống

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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: (j = 1; while j < n: j = j × 2) là gì?

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

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

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

Vì sao thuật toán Dijkstra có thể cho kết quả sai khi một số trọng số cạnh âm?

1. ANó rơi vào vòng lặp vô hạn ở mọi cạnh âm
2. BMột đỉnh được chốt khi được lấy ra, nhưng một cạnh âm sau đó vẫn có thể cho nó một đường đi ngắn hơn
3. CSố âm không thể lưu trong hàng đợi ưu tiên
4. DNó chỉ hoạt động trên đồ thị vô hướng