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

Ghi nhớ (memoisation) là gì?

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

Sắp xếp chọn hoạt động như thế nào?

1. ANó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
2. BNó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển
3. CNó chia mảng làm đôi rồi trộn lại
4. DNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AMảng chỉ được chứa số dương
2. BMảng phải được sắp xếp
3. CMảng không được có quá 1000 phần tử
4. DĐộ dài mảng phải là lũy thừa của hai

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
2. BĐúng, nhưng chỉ khi n nhỏ hơn 100
3. CKhông, vì n³ nhỏ hơn n² khi n lớn
4. DĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(mn log n)
2. BO(mn)
3. CO(2^m+n)
4. DO(m + n)

Phân tích khấu hao đo lường điều gì?

1. AChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất
2. BChi phí của một thuật toán trên đầu vào tốt nhất
3. CChi phí kỳ vọng trên các đầu vào ngẫu nhiên
4. DChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi

Cận nào là đúng cho log(n!)?

1. AΘ(n)
2. BΘ(n²)
3. CΘ(log n)
4. DΘ(n log n)

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

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